TL;DR
This paper introduces a novel method to leverage the sophisticated heuristics developed for classical AI planning within the domain of Hierarchical Task Network (HTN) planning. By transforming HTN problems into a classical planning framework, they enable existing classical heuristics to guide HTN search, significantly outperforming state-of-the-art HTN planning approaches.
What Problem Does This Paper Address?
AI planning aims to find sequences of actions to achieve goals. Two major paradigms exist: classical planning, which deals with a flat set of actions and states, and Hierarchical Task Network (HTN) planning, which introduces task hierarchies and decomposition methods to model complex behaviors. While classical planning has benefited greatly from advanced heuristic search techniques, HTN planning has lagged behind in this regard. This gap makes HTN planning systems less efficient, often requiring explicit domain advice to guide their search. The core challenge is adapting the powerful, state-based heuristics from classical planning to the hierarchical and task-decomposition-centric nature of HTN planning, which doesn't inherently have a state-based goal.
Methods
The authors propose a "Relaxed Composition" (RC) heuristic approach. The key idea is to translate an HTN planning problem into a classical planning problem. This translation involves:
- State Representation: New state features are introduced to represent the status of abstract and primitive tasks (e.g.,
Utask_namefor whether a task is part of the decomposition tree). - Action Transformation:
- Primitive HTN actions are augmented with a precondition indicating they are "reachable" within the current context.
- HTN decomposition methods are transformed into classical actions. The preconditions of these new actions correspond to the subtasks of the method, and their add effect signifies that the parent abstract task is now decomposed.
- Goal Definition: The goal in the classical problem is defined by the state features corresponding to the tasks in the current HTN task network.
This transformation allows any classical planning heuristic to be applied. The paper also discusses how to handle action reachability and ordering constraints, often by adding preconditions to actions.
Datasets
Not discussed in the paper. The paper focuses on a theoretical framework and experimental evaluation using standard HTN planning domains.
Key Insights and Ideas
- Bridging the Heuristic Gap: The most significant insight is that the rich heuristic landscape of classical planning can be effectively "ported" to HTN planning through a clever problem transformation. This bypasses the need to develop entirely new heuristics for HTN.
- Bottom-Up Heuristic Construction: The RC heuristic approach effectively works backward from the desired outcome (a decomposed task network) to estimate the cost of achieving it, mirroring how classical heuristics estimate the distance to a state goal.
- Theoretical Guarantees: The encoding allows for the creation of "safe, goal-aware, and admissible" HTN heuristics, meaning they are never infinite if a solution exists, return zero for goal states, and do not overestimate the distance to the goal. This is crucial for efficient and complete search.
- Handling Hierarchy: The transformation explicitly addresses the challenges posed by HTN hierarchies, such as ensuring actions are reachable and integrated into the plan, by encoding these constraints into the classical problem's state and actions.
Key Results
The paper demonstrates that their approach, when combined with classical heuristics like Add, FF, and LM-Cut, and a new progression search algorithm, outperforms existing state-of-the-art search-based HTN planning systems in terms of coverage. Figure 4 shows their system achieving the highest coverage across various benchmarks compared to other HTN planning systems.
Limitations and Future Work
- Ignoring Ordering Relations: A key relaxation in the RC model is the ignoring of explicit ordering relations between tasks within HTN task networks. While this simplifies the translation, it means the heuristic might suggest plans that violate these orderings.
- Potential for Redundant Actions: The approach might suggest actions that are not strictly necessary or might be inserted in ways that violate the hierarchy's intended structure.
- Future Work: The authors suggest further research into incorporating ordering constraints more effectively into the heuristic calculation and exploring the use of their framework for finding cost-optimal HTN plans. They also mention an improved progression search algorithm (not detailed in this paper) that further enhances coverage.
Summary updated