Abstract
Hierarchical Task Network (HTN) planning often suffers from "formula explosion" when translated into Boolean Satisfiability (SAT) problems, primarily due to the complexity of handling partial ordering. This paper presents a novel approach that pre-computes ordering constraints using a Solution Order Graph (SOG). By enforcing order-consistent child arrangements in the decomposition tree, the authors reduce the SAT formula size from $\Theta(n^4)$ to a practical $O(n^2)$, significantly improving performance over state-of-the-art planners.
Introduction
HTN planning is a powerful framework for modeling complex domains by recursively decomposing high-level tasks into primitive actions. While computationally demanding, leveraging modern SAT solvers for HTN planning is a promising research direction. However, previous SAT-based planners struggled with partially ordered tasks, where the lack of a strict sequence led to a quadratic growth in constraints, resulting in a $\Theta(n^4)$ formula size relative to plan length. This "chaos" of partial ordering often exceeded memory limits for complex problems.
Methodology
The proposed solution centers on three primary innovations designed to streamline the SAT encoding process:
1. Order-Consistent Child Arrangement
The foundation of the approach is the Path Decomposition Tree (PDT). To manage ordering, the authors ensure that the children of any node in the PDT are arranged to respect the ordering constraints of all applicable methods. This structural consistency allows for a more predictable mapping of tasks.
2. Solution Order Graphs (SOGs)
By fixing the arrangement of children, the ordering of leaf tasks (primitive actions) becomes deterministic. These constraints are captured in a Solution Order Graph (SOG) before the SAT formula is generated. The SOG serves as a static roadmap of valid task sequences, offloading the burden of "discovering" order from the SAT solver.
3. SAT-F Encoding and Parallelism
The authors introduce the SAT-F encoding, which utilizes the SOG to propagate ordering constraints via "forbiddenness" variables. This reduces theoretical complexity to $O(n^3)$, which empirically behaves like $O(n^2)$. Furthermore, they integrate "$\exists$-step" parallelism, allowing non-conflicting actions to occur simultaneously, which further reduces the required formula length.
Evaluation
The planner was evaluated across several standard HTN benchmark domains, including UM-TRANSLOG, SATELLITE, ROVER, and WOODWORKING. These domains encompass a variety of challenges, such as recursive structures and complex partial orderings.
Key Results
- Enhanced Coverage: The SAT-F $\exists$ planner solved 121 out of 144 instances, outperforming both the best previous search-based planner (PANDApro, 95 instances) and the leading SAT-based approach (116 instances).
- Formula Efficiency: In the "Rover" domain, the SAT-F encoding prevented the out-of-memory errors that plagued previous methods, producing formulas up to two orders of magnitude smaller.
- Runtime Performance: The integration with the
expMCsolver allowed the planner to find solutions significantly faster than competing technologies.
Conclusion
The core insight of this work is that pre-computing structural ordering constraints significantly simplifies the SAT solver's task. By transforming a dynamic reasoning problem into a static graph-based verification, the authors achieved a major leap in efficiency. Future work may involve refining the greedy algorithms used for tree construction and exploring the utility of SOGs in search-based planning contexts.
Summary updated