Title: Learn2Plan: Learning variable ordering heuristics for scalable task planning

Abstract:

Traditional approaches to planning attempt to transform a system into a goal state by applying specific actions in a specific order. In these methods, there is an exponential search space due to considering many possible actions at every decision point. Hierarchical Task Networks use incremental steps in breaking down an abstract goal task into more specific tasks by leveraging domain knowledge in a structured manner. In space systems, timeline-based planning imposes a set of temporal constraints that govern the timelines of multiple independent but interacting agents supported by a habitat. Such systems must be robust to unforeseen circumstances and failures, leading to recent research in accommodating temporal reasoning via flexible timeline structures for complex resource constraints in multi-agent scenarios. However, other aspects come into play in terms of unforeseen circumstances and critical failures in shared human environments. Firstly, HTN-based multi-agent planners inherently have a time-consuming graph search process because of backtracking, requiring all macro slots to be checked to find optimality. This search process prevents the planner from being used for urgent tasks in space, such as gas leaks and valve failures. Secondly, planning for multiple robots in an environment where resources might be shared with a human lack interpretability. Low interpretability limits confidence in the generated plan, restricts onboard autonomy, and makes understanding the plan difficult.

This thesis proposes solutions to aid planners in both aspects, namely efficiency and interpretability. First, a learning framework to aid HTN planners in making quick decisions for time-critical and essential onboard tasks. This learning framework consists of a multi-task deep neural network baseline with an LSTM memory network that speeds up the backtracking in the search process of planners and learns variable ordering heuristics through spatial and temporal reasoning. It predicts the best macro slot that optimizes for makespan and predicts the makespan to inform downstream tasks. Second, a simulation pipeline that simulates a plan to enhance the physical understanding of the reasoning used by the planner. This simulator also incorporates real-world physics to execute the plan better and can query the planner in case of a failed execution. Both of these solutions form a part of a planning system that can aid multi-agent task planning in space habitats. This planning system is robust, efficient, and interpretable and can also be used in tasks outside of space systems.

Committee:

Prof. Stephen Smith (co-chair)

Dr. Zachary Rubinstein (co-chair)

Prof. Jean Oh

Sha Yi