Abstract
Finding cost-optimal solutions in Total-Order Hierarchical Task Network (HTN) planning is a significant challenge due to the complex interplay between hierarchical constraints and state-space search. This paper introduces autoSym, the first symbolic search approach for this problem. By integrating automata-based reachability analysis with Binary Decision Diagrams (BDDs), autoSym explores sets of states simultaneously, significantly outperforming existing SAT-based and heuristic search planners.
Introduction
Hierarchical Task Network (HTN) planning involves decomposing abstract tasks into primitive actions based on a predefined grammar. While finding any valid plan (satisficing) has seen progress, finding the optimal (cheapest) plan is notoriously difficult. Most existing planners rely on heuristic search, but creating "admissible" heuristics that account for hierarchical constraints is a major hurdle. The authors address this by moving away from searching individual states and instead using symbolic search to explore sets of states simultaneously.
The autoSym Algorithm
The core contribution of this work is the autoSym algorithm, which treats Total-Order HTN (TOHTN) planning as a reachability problem in pushdown systems. The approach rests on three technical pillars:
1. Automata for Task Stacks
In TOHTN, the remaining tasks can be viewed as a stack. The algorithm represents the set of all reachable task stacks as a finite automaton. This allows the planner to manage the hierarchical "grammar" of the problem efficiently. Before planning, the system performs Regularisation, converting complex task decompositions into a "2-TOHTN" form (where each task decomposes into at most two sub-tasks), which simplifies the automata construction.
2. Cost Layers (Buckets)
To ensure optimality, autoSym constructs a sequence of automata in increasing order of cost. This "bucket" approach ensures that the first time the "empty stack" (the goal) is reached, it is guaranteed to be via the cheapest possible path.
3. BDDs for State Variables
To handle the "world state" (propositional facts), the edges of the automata are annotated with Binary Decision Diagrams (BDDs). This allows the planner to compactly represent and transition between sets of possible world states associated with specific task sequences. This decoupling allows the automaton to handle the hierarchy while the BDDs handle the logic.
Evaluation and Key Results
The authors evaluated autoSym on a benchmark set of 465 instances across 21 domains, including benchmarks from the 2020 International Planning Competition (IPC).
- Superior Coverage:
autoSymsolved 242 out of 465 instances, whereas its closest competitor, a SAT-based planner, solved only 174. - Performance Scaling: While heuristic A* search is faster on very simple problems,
autoSymscales significantly better as problem difficulty increases, often performing an order of magnitude faster than previous state-of-the-art methods. - Efficiency: Once the symbolic structure is built, the time required to extract the specific sequence of actions is negligible.
Limitations and Future Work
Currently, autoSym is restricted to Total-Order HTNs and cannot handle Partial-Order HTNs. Additionally, in domains with an extremely high number of decomposition methods (e.g., Barman), the resulting automata can become too large for memory, a phenomenon known as the "method explosion" problem. Future work includes extending the symbolic approach to partial orders and implementing more sophisticated BDD variable-ordering heuristics to further improve performance.
Summary updated