Semantic Attachments for HTN Planning

Maurício Cecílio Magnaguagno, Felipe MeneguzziAAAI 2020 · DOI

Abstract

This paper introduces a formal integration of external procedural code, termed Semantic Attachments (SAs), into Hierarchical Task Network (HTN) planning. By implementing SAs as semi-coroutines, the proposed framework, HyperTensioN U, enables efficient search through infinite numeric or geometric state spaces. Experimental results demonstrate significant performance improvements over state-of-the-art numeric planners in complex domains such as plant watering and linear car control.

Introduction

Planning in real-world environments, particularly in robotics, necessitates handling continuous variables like spatial coordinates, battery levels, and physical dimensions. Traditional symbolic planners often struggle with these due to the infinite nature of numeric domains and the complexity of modeling geometric shapes in pure logic. While "Semantic Attachments" have been used in classical planning to link predicates to external code, their application in HTN planning has historically been ad-hoc, often failing to integrate smoothly with the planner's backtracking mechanisms.

Methodology: The HyperTensioN U Framework

The authors propose a three-layered architecture—Symbolic, Intermediate, and External—implemented in a framework called HyperTensioN U.

The three-layered architecture of HyperTensioN U, showing the interaction between symbolic logic and external procedures via a symbol-object table.

Key innovations include:

  • SAs as Semi-Coroutines: Instead of returning an exhaustive list of values, an SA acts as a coroutine. It yields one value at a time and pauses; if the planner backtracks, the coroutine resumes to provide the next possibility. This allows for efficient exploration of potentially infinite search spaces.
  • Symbolic Anchors (SO-table): To maintain a clean symbolic representation, complex external objects (e.g., a high-fidelity polygon) are represented by simple symbols. A Symbol-Object Table maps these symbols to the actual data structures used by external libraries.
  • Precondition Reordering and Lazy Evaluation: The compiler prioritizes standard logical predicates to prune the search space before invoking more computationally expensive SAs. For instance, an ADJACENT SA calculates neighbors on-the-fly only when required by the planner.

Experimental Evaluation

The approach was evaluated on two primary domains: Plant Watering, which tests movement and resource management in a 2D grid, and Car Linear, a control problem involving temporal constraints and continuous acceleration. The HTN planner was compared against modern classical numeric planners, specifically ENHSP and Metric-FF.

Performance comparison showing the execution time of HTN with Semantic Attachments versus classical numeric planners like Metric-FF and ENHSP.

Key Results

The results demonstrated a substantial performance advantage for the HTN with SA approach:

  • Plant Watering: The proposed system achieved execution times near 0.01s, outperforming Metric-FF (0.11s) and scaling more predictably as problem complexity increased.
  • Car Linear: The performance gap was most evident in the most complex instances. For Problem 9, the HTN with SA solved the task in 1.402 seconds, while the state-of-the-art ENHSP (aibr configuration) required 63.585 seconds.
  • Domain Modeling: The authors found that domain descriptions using SAs were significantly shorter and more intuitive than standard PDDL descriptions for numeric problems.

Discussion and Future Work

The "aha moment" of this research is treating external code as an iterator aware of the planner's search process rather than a black-box function. This separation of concerns allows domain experts to write clean HTN methods while delegating complex physics or geometry to external code.

However, the use of external calls introduces challenges regarding formal correctness proofs, especially if functions have side effects. Additionally, because SAs can theoretically iterate indefinitely, domain designers must implement manual stop conditions. Future research will focus on extracting metrics from these black-box SAs to better guide the planner's heuristic search.

Summary updated

BibTeX
@inproceedings{magnaguagno2020semantic,
  author = {Maurício Cecílio Magnaguagno and Felipe Meneguzzi},
  title = {{Semantic Attachments for HTN Planning}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.1609/aaai.v34i06.6548},
}
Figure