totSAT - Totally-Ordered Hierarchical Planning Through SAT

Gregor Behnke, Daniel Höller, Susanne BiundoAAAI 2018 · DOI

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 Path Decomposition Tree (PDT) structure used to encode hierarchical task decomposition into propositional logic.

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).

Coverage results across various HTN domains, comparing totSAT variants against existing planners like SHOP-PANDA and HTN2STRIPS.

Key Results

  • Superior Coverage: totSAT (using the cryptominisat5 solver) 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 TRANSPORT domain and the hierarchy-heavy ROVER domain.
  • 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

BibTeX
@inproceedings{behnke2018totsat,
  author = {Gregor Behnke and Daniel Höller and Susanne Biundo},
  title = {{totSAT - Totally-Ordered Hierarchical Planning Through SAT}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.1609/aaai.v32i1.12083},
}
Figure