TL;DR
This paper investigates the decidability of Hierarchical Task Network (HTN) planning, a powerful AI planning paradigm. The authors show that while standard HTN planning is undecidable, allowing the insertion of tasks and ordering constraints (a form of "hybrid planning") makes the problem decidable, with an EXPSPACE upper complexity bound. This finding suggests that a degree of flexibility in planning can paradoxically lead to more computationally tractable problems.
What Problem Does This Paper Address?
AI planning aims to find a sequence of actions to achieve a goal. Two main approaches exist: classical state-based planning and Hierarchical Task Network (HTN) planning. Classical planning, while well-understood in terms of complexity (ranging from PSPACE-complete to undecidable), can be computationally expensive. HTN planning introduces a hierarchy of tasks, allowing complex tasks to be decomposed into simpler ones, which can guide the search and potentially improve efficiency. However, this hierarchical structure, as formalized by Erol et al., leads to undecidability for the plan existence problem – meaning there's no guaranteed algorithm to determine if a plan exists.
This paper tackles the question of whether a specific modification to HTN planning, termed "hybrid planning," can restore decidability. Hybrid planning, as defined here, allows for the decomposition of compound tasks (like in HTN) but also permits the arbitrary insertion of primitive tasks and ordering constraints into the task network. This flexibility aims to overcome a key criticism of HTN planning: its rigidity in responding to unforeseen situations. The authors want to understand if this added flexibility makes the planning problem decidable.
Methods
The authors present a simplified, propositional formalization of HTN planning with and without task insertion. They then prove the undecidability of HTN planning without task insertion by reducing the problem of checking for non-empty intersection of context-free grammars (CFGs) to HTN planning. This involves constructing a planning problem where a solution exists if and only if the two CFGs generate a common word.
For hybrid planning (with task insertion), the core of their contribution lies in proving decidability. They achieve this by:
- Decomposition Trees: Introducing a tree-like representation of task decomposition, analogous to parse trees in formal grammars.
- Bounding Solution Sizes: Developing lemmas that allow for the removal of cycles in decomposition sequences and establish an upper bound on the size of "short" solutions. This is crucial for making the search space finite.
- Task Insertion for Executability: Showing how task insertion can be used to ensure that decomposed plans become executable, effectively transforming the problem into a series of classical planning problems.
- Complexity Analysis: Deriving an EXPSPACE upper bound for the plan existence problem in hybrid planning.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- Flexibility Can Lead to Tractability: Counter-intuitively, adding the ability to arbitrarily insert tasks and ordering constraints (making the planning problem more flexible) transforms an undecidable problem (HTN planning) into a decidable one (hybrid planning).
- Decomposition Trees as a Powerful Tool: The concept of decomposition trees provides a structured way to reason about the decomposition process and is key to proving bounds on solution sizes.
- Cycles in Decomposition are Problematic: Cycles in the decomposition process are a source of complexity and undecidability. The paper shows how to eliminate them and still maintain a valid plan.
- Bridging HTN and Classical Planning: Hybrid planning effectively bridges the gap between HTN and classical planning, inheriting some benefits of both while managing complexity.
Key Results
- Undecidability of HTN Planning: The paper formally proves that standard HTN planning (without task insertion) is undecidable.
- Decidability of Hybrid Planning: The core result is that HTN planning with task insertion (hybrid planning) is decidable.
- EXPSPACE Upper Bound: The plan existence problem for propositional hybrid planning is shown to be in EXPSPACE.
- PSPACE-Hardness: The formalism captures ground classical planning, which is PSPACE-complete, implying that hybrid planning is at least PSPACE-hard.
Limitations and Future Work
- Propositional Planning: The current formalization is restricted to propositional planning (no function symbols). Extending this to first-order planning might reintroduce undecidability, depending on the specific features.
- Complexity Bounds: While an EXPSPACE upper bound is established, the authors note that they did not aim for tight complexity bounds and that the PSPACE-hardness is a trivial lower bound. Further work could refine these bounds.
- Comparison to Other Formalisms: The paper acknowledges that other formalizations of hybrid planning exist (e.g., those with causal links or lifted representations) and suggests that their decidability results might not directly apply to those. Future work could explore these connections.
- Practical Implications: The authors suggest that their results could inform the design of practical planning systems, such as the Duet planning system, by providing mechanisms for guaranteed termination and potentially pruning plans that exceed certain sizes.
Summary updated