TL;DR
This paper introduces a novel admissible heuristic for Hierarchical Task Network (HTN) planning, enabling optimal solutions to be found efficiently. The heuristic leverages a Task Decomposition Graph (TDG) to estimate the cost of decomposing abstract tasks into primitive actions, and its accuracy can be improved by recomputing the TDG during the search process.
What Problem Does This Paper Address?
Hierarchical Task Network (HTN) planning is a powerful approach for complex planning problems, offering greater expressivity than classical planning by allowing for abstract tasks and hierarchical task decomposition. However, finding optimal or high-quality solutions in HTN planning often requires specialized search control knowledge or the use of admissible heuristics. While domain-independent heuristics exist for classical planning, they are less common and less developed for HTN planning. This paper addresses the need for an admissible, domain-independent heuristic that can guide HTN planners towards optimal solutions without relying on hand-crafted search control. The challenge lies in effectively exploiting the hierarchical structure of HTN problems to provide accurate cost estimates for abstract tasks.
Methods
The core contribution is the Cost-Aware TDG Heuristic ($TDG_c$). This heuristic is built upon the Task Decomposition Graph (TDG), a data structure that represents the AND/OR structure of an HTN problem's task hierarchy.
Here's a breakdown of the key methods:
- Task Decomposition Graph (TDG): The TDG is constructed from the HTN problem's domain and initial plan. It's a bipartite graph with task vertices and method vertices, representing how abstract tasks can be decomposed into sub-tasks via methods.
- TDG Cost Estimates: The heuristic assigns cost estimates to each vertex in the TDG.
- For primitive tasks (actions), the cost is their given action cost.
- For abstract tasks, the cost is the minimum cost of refining it through any of its applicable methods.
- For method vertices, the cost is the sum of the estimated costs of the tasks within that method's decomposition.
- Admissibility: The heuristic is proven admissible, meaning it never overestimates the true cost to reach a solution. This is crucial for guaranteeing optimality when used with search algorithms like A*.
- TDG Recomputation: A significant innovation is the proposal to recompute the TDG during the planning search. Decomposing abstract tasks can change the reachability of other tasks, potentially making the TDG and thus the heuristic estimates more accurate. The paper analyzes when recomputation is beneficial and proposes a technique for incremental updates.
- Modification-Aware TDG Heuristic ($TDG_m$): An improved version of the heuristic, $TDG_m$, is also proposed, which accounts for modifications made during search, specifically by subtracting the number of causal links.
Datasets
The empirical evaluation was conducted on four standard HTN planning domains:
- UM-Translog: Originally designed for HTN planning.
- SmartPhone: Originally designed for hybrid planning.
- Satellite: Originally designed for International Planning Competitions (IPCs) and adapted to hybrid planning.
- Woodworking: Originally designed for IPCs and adapted to hybrid planning.
These domains were converted into standard HTN domains by removing preconditions and effects from abstract tasks and causal links from methods. The evaluation used a total of 59 problem instances across these domains.
Key Insights and Ideas
- Exploiting Hierarchy for Heuristics: The paper demonstrates that the hierarchical structure itself, beyond just defining tasks and methods, can be directly leveraged to create effective, domain-independent heuristics.
- TDG as a Powerful Representation: The TDG proves to be a valuable data structure for capturing the decomposition possibilities and estimating costs in HTN planning.
- Dynamic Heuristic Improvement: The idea of recomputing the TDG during search is a key insight. It highlights that static heuristics based on initial problem structure can be significantly improved by adapting to the evolving state of the search.
- Trade-off between Accuracy and Runtime: Recomputing the TDG can improve heuristic accuracy and reduce the search space, but it comes at the cost of increased computation time for the recomputation itself. The paper investigates this trade-off.
- Admissibility Doesn't Mean Poor Coverage: While admissible heuristics can sometimes lead to lower coverage than inadmissible ones, the proposed $TDG_c$ and $TDG_m$ heuristics show competitive coverage, especially when used with Greedy-A*.
Key Results
- Coverage: The proposed heuristics ($TDG_c$ and $TDG_m$) achieve high coverage, solving between 54 and 57 out of 59 problems when used with A and Greedy-A. $TDG_m$ with A* was the best performer in terms of coverage, solving 57 problems.
- Plan Quality: When used with A*, the admissible $TDG_c$ heuristic guarantees optimal solutions. While other heuristics sometimes found suboptimal solutions (up to 31% worse), the TDG-based heuristics generally produced optimal or near-optimal plans.
- TDG Recomputation Impact:
- Search Space: TDG recomputation consistently reduced the search space in most problem instances.
- Runtime: While search space was reduced, runtime was not always improved. In some cases, the overhead of recomputation led to increased runtimes, particularly in the Woodworking domain. However, in other instances, runtime was significantly reduced (e.g., 83% search space reduction leading to a 54% runtime reduction).
- Heuristic Accuracy: Recomputation frequently led to more accurate heuristic estimates, as indicated by the "h-im/rec" metric.
Limitations and Future Work
- TDG Recomputation Overhead: The primary limitation acknowledged is the computational cost associated with recomputing the TDG. While it improves heuristic accuracy and reduces search space, it can increase overall runtime.
- Predicting Beneficial Recomputation: The authors suggest future work should investigate how to predict when a TDG recomputation will be beneficial, rather than performing it speculatively after every decomposition. This could involve analyzing structural properties of the TDG.
- Grounding Assumption: The empirical evaluation assumed ground models for TDG recomputation. Extending this to lifted planning, where variables are not fully instantiated, would be a valuable direction.
- Domain-Specific Heuristics: While the proposed heuristic is domain-independent, the paper notes that domain-specific heuristics can still outperform it in terms of coverage. Future work could explore hybrid approaches.
Summary updated