TL;DR
This paper introduces a new class of HTN planning problems called "delete- and ordering-free" (DOF) planning, which is NP-complete. They then develop novel heuristics for HTN planning by relaxing the original problem into this DOF class and solving it using an integer programming model. These heuristics are more informed than existing ones, capturing the interplay between hierarchical decomposition and action execution more accurately.
What Problem Does This Paper Address?
Hierarchical Task Network (HTN) planning is a powerful paradigm for representing complex tasks and their decomposition into simpler actions. However, designing effective heuristics for HTN planning has been challenging. Existing heuristics often relax the problem too much, for instance, by allowing "task insertion" (adding actions not originally part of the decomposition) or ignoring the crucial interplay between the hierarchical structure and the actual sequence of actions. This can lead to heuristics that are not very informative, resulting in inefficient search. The paper aims to bridge this gap by developing heuristics that more accurately reflect the HTN structure while remaining computationally feasible.
Methods
The core contribution of this paper is the introduction of Delete- and Ordering-Free (DOF) HTN planning. This is a restricted form of HTN planning where:
- Delete-effects are empty: Actions don't remove state features.
- Ordering relations are empty: Tasks within a network can be executed in any order.
The authors prove that the plan existence problem for DOF HTN planning is NP-complete. They then leverage this DOF class to create heuristics. The key idea is to take a given HTN planning problem (or a subproblem at a search node) and relax it into a DOF problem. This relaxation is achieved by:
- Ignoring delete-effects: All actions are treated as if they have no delete-effects.
- Ignoring ordering constraints: All ordering relations within task networks and methods are disregarded.
To compute the heuristic value (which represents the minimum number of actions and methods needed to solve the relaxed problem), they formulate an integer programming (IP) model. This model captures the decomposition structure and the task execution requirements. For computational efficiency, they also explore relaxing the IP model to a linear programming (LP) model.
Datasets
The paper evaluates their heuristics on a standard benchmark set of 144 HTN planning instances, which is also used in related work. They do not introduce a new benchmark dataset.
Key Insights and Ideas
- DOF HTN Planning as a Relaxed Problem: Defining a restricted HTN planning problem (DOF) provides a principled way to relax the original problem for heuristic calculation. This class is still computationally hard (NP-complete), indicating it's not trivially solvable but still more constrained than general HTN planning.
- IP Model for Heuristic Calculation: Formulating the DOF problem as an Integer Program allows for a precise calculation of the heuristic value. This approach directly models the decomposition process and task dependencies.
- Trade-off between NP-hard and LP Relaxation: The authors found that their full NP-hard IP model (which is more accurate) performed better in terms of coverage than the LP-relaxed version, suggesting that the exact integer solutions are valuable for heuristic quality.
- Avoiding Task Insertion: Unlike many prior heuristics, their approach avoids "task insertion" during heuristic calculation. This means the heuristic value is derived solely from the tasks and methods present in the original decomposition, leading to more informed estimates.
- Capturing Hierarchy-Action Interplay: The IP model explicitly encodes how abstract tasks are decomposed into methods, and how these methods contain further tasks. This allows the heuristic to better capture the interaction between the hierarchical structure and the actual actions.
Key Results
- Competitive Coverage: Their best heuristic configurations achieved competitive coverage compared to state-of-the-art HTN planning systems, particularly outperforming many search-based heuristics.
- More Informed Heuristics: Analysis of search nodes showed that their IP-based heuristics were significantly more informed than LP-relaxed versions and other heuristics like RCFF, leading to fewer search nodes explored.
- Performance of NP-hard IP: The full NP-hard IP model generally yielded better results than the LP-relaxed version, indicating that the exact integer solutions are beneficial for heuristic quality.
- Handling Cycles: The IP model includes constraints to handle cycles in the task decomposition graph, preventing the generation of disconnected subproblems.
Limitations and Future Work
- Computational Cost: Solving the IP model can be computationally expensive, especially for large problems. While they explore LP relaxation, it comes at the cost of heuristic accuracy.
- Future Work: The authors suggest several promising directions:
- Enhanced IP Models: Incorporating additional information like landmarks or net-change constraints into the IP model to further improve heuristic accuracy.
- LP Relaxation Improvements: Finding ways to improve the LP relaxation to achieve better heuristic values while maintaining polynomial time complexity.
- Optimal Action Costs: Adapting the framework to find HTN plans with optimal action costs, not just a valid plan.
- Handling Task Insertion: While they currently avoid task insertion, future work could explore principled ways to incorporate it.
Summary updated