On Succinct Groundings of HTN Planning Problems

Gregor Behnke, Daniel Höller, Alexander Schmid, Pascal Bercher, Susanne BiundoAAAI 2020 · DOI

Abstract

Grounding is the process of translating abstract, variable-heavy planning models into concrete, executable ones. In Hierarchical Task Network (HTN) planning, this process is a major bottleneck due to the combinatorial explosion of possible task and action instances. This paper introduces pandaPI, a new grounder that unifies state-based and hierarchical reachability analysis into a single "Generalised Planning Graph" (GPG). This approach, combined with parameter splitting and iterative pruning, produces significantly smaller models in a fraction of the time compared to previous state-of-the-art tools.

Introduction

Most automated planners work with grounded representations, where every action is explicitly defined with specific objects. However, humans author planning domains in a "lifted" fashion using variables to keep models concise. The challenge lies in the translation: a naive grounding of a drive(?truck, ?from, ?to) action with 10 trucks and 50 cities results in 25,000 instances, most of which are unreachable "distractor actions."

In HTN planning, grounding must account for both the physical state of the world and the hierarchical decomposition of tasks. Existing grounders were often slow, produced bloated models, or struggled with recursive task structures. pandaPI addresses these issues by optimizing the reachability analysis that identifies which groundings are actually necessary.

Methodology

The authors introduce three main innovations to improve grounding efficiency and succinctness:

Parameter Splitting

Parameter splitting is a preprocessing step that breaks down complex decomposition methods. If a method contains variables that are independent of the parent task, pandaPI splits the method into smaller pieces. This prevents the "multiplication" of groundings, potentially turning an $O(n^3)$ grounding problem into $O(n^2)$.

Illustration of parameter splitting: a complex navigation task is decomposed into intermediate steps to reduce the number of grounded instances.

Generalised Planning Graph (GPG)

The core contribution is the unification of two reachability analyses: delete-relaxed reachability (can we physically reach this state?) and TDG-based reachability (can this task be decomposed into primitives?). The authors realized these are algorithmically identical and developed the GPG to handle both using a single, optimized engine. This unification allows for a more robust handling of recursion, which is critical for complex domains like Minecraft.

Iterative Pruning

pandaPI performs reachability analysis and pruning iteratively until convergence. Because pruning a task might make a certain state unreachable, and vice versa, this "virtuous cycle" results in a much tighter grounded model. The system is implemented in C++ and uses an efficient caching strategy for antecedent matching to avoid redundant computations.

Evaluation and Results

The authors evaluated pandaPI using 330 problem instances across 17 domains, including benchmarks from GTOHP, Tree-Rex, and PANDA, as well as a recursive Minecraft domain.

Runtime comparison of pandaPI against GTOHP, Tree-REX, and PANDA. pandaPI consistently outperforms existing tools, especially on larger, more complex instances.

Key findings include:

  • Speed: pandaPI is orders of magnitude faster than PANDA, grounding all instances within 38 seconds, compared to PANDA's 20-minute peak.
  • Efficiency: It successfully grounded the Minecraft domain where GTOHP and Tree-Rex failed due to memory exhaustion.
  • Succinctness: In almost all cases, pandaPI produced smaller or equal-sized groundings compared to other tools, which directly reduces the search space for subsequent planning.

Conclusion

pandaPI demonstrates that unifying state-based and hierarchical reachability analysis leads to significant gains in grounding performance. By producing more succinct models faster, it enables planners to solve more complex HTN problems. Future work will focus on supporting derived predicates and exploring even more aggressive action schema splitting techniques.

Summary updated

BibTeX
@inproceedings{behnke2020succinct,
  author = {Gregor Behnke and Daniel Höller and Alexander Schmid and Pascal Bercher and Susanne Biundo},
  title = {{On Succinct Groundings of HTN Planning Problems}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.1609/aaai.v34i06.6529},
}
Figure