9 Conclusion

This article provides a formalization of Hierarchical Task Network planning that, unlike the UMCP formalism [Erol, Nau, Hendler, 1994b], includes actions with temporal extent. We introduce a sound and complete algorithm that can be used to generate a plan, coordinate a group of agents with hierarchical plans, and interleave planning and coordination.

The algorithms for summarizing propositional state and metric resource conditions and effects at abstract levels and the mechanisms that reason about this summary information can facilitate the construction of other planning and coordination systems that reason about plans at multiple levels of abstraction. These mechanisms for reasoning about summary information determine whether a task (at any level of abstraction) must or may achieve, clobber, or undo a condition of another task under partial order constraints on endpoints of tasks. Built on these mechanisms, other mechanisms determine whether a group of agents can decompose and execute a set of partially ordered abstract tasks in any way ($CanAnyWay$), might decompose and execute them in some way ($MightSomeWay$), or cannot execute them consistently in any way ($\neg MightSomeWay$).

These algorithms enable a planning system to find solutions at multiple levels of abstraction without needing to fully detail the task hierarchy. These abstract solutions support flexible execution by remaining uncommitted about which of the alternative methods will be selected at runtime, based on the circumstances, to achieve plan subgoals.

Our complexity analyses and experiments in different problem domains have quantified the benefits of using summary information for a refinement planning and local search scheduling algorithm. There is a potential doubly exponential speedup of $O(k^{b^d-b^i} b^{2(d-i)})$ for $k$ ways to resolve a conflict, a hierarchy branching factor $b$, a depth of the hierarchy $d$, and an abstract solution depth $i$. An exponential speedup is obtained if abstract solutions are found, if there are fewer summary conditions at abstract levels, or if alternative decomposition choices lead to varying numbers of threats. These conditions for exponential improvement are a significant relaxation compared to prior work, and the performance improvement is greater.

A domain modeler can run the summarization algorithms offline for a library of plan hierarchies so that summary information is available for the coordination and planning of any set of goal tasks supported by the library. Using algorithms for reasoning about summary information, agents can discover with whom they should coordinate and over which states and resources they must coordinate/negotiate. Communicating summary information at different levels of abstraction reduces communication costs exponentially under conditions similar to those reducing computation time.

The use of summary information in a local search planner (like ASPEN, Section 6.3) is another contribution of this work. The strength of local search algorithms is their ability to efficiently reason about large numbers of tasks with constraints on metric resources, state variables, and other complex resource classes. By integrating algorithms for reasoning about summarized propositional state and metric resource constraints into a heuristic local search planner/scheduler, we enable such scalable planning systems to scale to even larger problem domains. This use of summary information in a different style of planner demonstrates the applicability of abstract reasoning in improving the performance of different kinds of planning (and plan coordination) systems.

Future work is needed to evaluate the use of summary information in other planning and scheduling systems and for wider classes of problems requiring more expressive representations for resources and temporal constraints. Already, an approach for exploiting cooperative action among agents based on summary information has been developed [Cox, Durfee, 2003]. Other promising approaches include abstracting other plan information, such as probabilistic conditions and effects and classes of resources and states (e.g. location regions and sub-regions). More work is also needed to understand how and when to communicate summary information in a distributed planning system.

The authors wish to thank Pradeep Pappachan, Gregg Rabideau, and Russell Knight for help with implementation. We also thank our anonymous reviewers for their many valuable suggestions. This work was performed at the Jet Propulsion Laboratory, California Institute of Technology, under contract with the National Aeronautics and Space Administration, and at the University of Michigan supported in part by DARPA (F30602-98-2-0142).