Abstract
This paper presents totSAT, a state-of-the-art planner that applies modern SAT solvers to totally-ordered Hierarchical Task Network (HTN) planning. By encoding the hierarchical decomposition process into propositional logic using a novel "Path Decomposition Tree" (PDT) structure, totSAT significantly outperforms existing search-based and translation-to-classical-planning systems. Empirical results demonstrate that totSAT achieves near-perfect coverage on standard and complex benchmarks, solving 125 out of 127 instances.
Introduction
Hierarchical Task Network (HTN) planning is a powerful paradigm for modeling complex problems by decomposing abstract tasks into simpler sub-tasks until executable primitive actions are reached. While HTN planning is more expressive than classical STRIPS planning—capable of representing context-free languages—it is also computationally more demanding, with totally-ordered HTN planning being EXPTIME-complete.
Historically, HTN planners have relied on domain-specific heuristics or blind search, which often struggle with combinatorial complexity. Recent attempts to translate HTN problems into classical planning have shown promise but often fail to fully exploit the structural information inherent in the hierarchy. totSAT bridges this gap by creating a direct SAT-based encoding for HTNs, analogous to the impact of SATPlan on classical planning.
The totSAT Method
totSAT follows the standard SAT-based planning loop: it selects a bound $K$, translates the planning problem into a SAT formula that is satisfiable if and only if a plan exists within that bound, and increments $K$ if the formula is unsatisfiable.
Path Decomposition Trees (PDTs)
The primary challenge in SAT-based HTN planning is representing the tree-like decomposition structure in a flat propositional formula. The authors introduce the Path Decomposition Tree (PDT), a static structure that acts as a template for all possible decomposition trees up to a height $K$.
The resulting SAT formula consists of two main components:
- Decomposition ($F_D$): Ensures that the chosen tasks and methods form a valid hierarchy starting from the initial abstract task.
- Executability ($F_E$): Ensures that the sequence of primitive actions at the leaves of the decomposition tree is executable in the initial state, following standard STRIPS semantics.
Empirical Evaluation
The authors evaluated totSAT on seven HTN domains, including standard benchmarks (UM-Translog, Woodworking, Satellite, SmartPhone) and more challenging domains (ENTERTAINMENT, ROVER, TRANSPORT).
Key Results
- Superior Coverage: totSAT (using the
cryptominisat5solver) solved 125 out of 127 benchmark instances. In comparison, the popular SHOP-PANDA planner solved 92, and the translation-based HTN2STRIPS solved only 82. - Robustness: totSAT was the only planner capable of effectively solving both the combinatorially difficult
TRANSPORTdomain and the hierarchy-heavyROVERdomain. - Structural Exploitation: Analysis revealed that over 90% of the clauses in the generated SAT formulas are Horn clauses. Modern SAT solvers are exceptionally efficient at handling Horn-heavy formulas, contributing to totSAT's high performance.
Discussion and Limitations
A key insight of totSAT is bounding decomposition height rather than plan length. This is often a more natural and smaller bound for hierarchical problems. However, totSAT is currently limited to totally-ordered HTN planning. Extending the encoding to partially-ordered planning is significantly more complex because the leaf order is not fixed, complicating the executability formula.
Furthermore, totSAT is a satisficing planner. Because it maps tasks to a fixed PDT structure, it finds a valid plan but not necessarily the shortest one. In some cases, plans can be up to 90% longer than optimal. Future work will focus on handling partial ordering and optimizing plan length.
Summary updated