Revealing Hidden Preconditions and Effects of Compound HTN Planning Tasks - A Complexity Analysis

Conny Olz, Susanne Biundo, Pascal BercherAAAI 2021 · DOI

Introduction

In Hierarchical Task Network (HTN) planning, high-level goals are represented as compound tasks. Unlike primitive actions in classical planning (e.g., STRIPS), which have explicitly defined preconditions and effects, compound tasks are abstract "recipes." They decompose into sequences of other tasks via "methods" until they eventually reach executable primitive actions.

The Problem of Hidden Task Properties

A significant challenge in HTN modeling is that languages like HDDL do not require authors to specify the preconditions or effects for these high-level tasks. These properties are "hidden" within the hierarchy. Without knowing what a high-level task requires or achieves, it is difficult to build efficient search heuristics, prune impossible branches, or coordinate multi-agent systems without fully expanding the entire task tree.

Figure 1: Decomposition of the compound task get-to(C) into various methods, illustrating hidden preconditions and effects.

As shown in the figure above, a task like get-to(C) can be achieved through multiple methods ($m_1$ through $m_4$). Some methods require the agent to be at location A, while others require being at B. Determining what is always true (guaranteed effects) or must be true (mandatory preconditions) across all possible refinements is a non-trivial task.

Complexity Analysis

The researchers performed a rigorous complexity analysis to determine how difficult it is to infer these hidden properties. They defined three key types of inferred properties:

  • Mandatory Preconditions: Facts that must hold for any refinement of a task to be executable.
  • Guaranteed Effects: Facts that will always be true after any successful refinement.
  • Possible Effects: Facts that might be true depending on the chosen method.

The study reveals a "Complexity Parity": determining these properties is exactly as hard as solving the planning problem itself (the "plan existence" problem). For totally ordered HTNs, this ranges from PSPACE-complete for acyclic models to EXPTIME-complete for general recursive models.

Practical Solutions: Executability-Relaxation

To overcome this computational barrier, the authors introduced executability-relaxation. By ignoring the preconditions of primitive actions and focusing solely on what an action would do if executed, the complexity drops significantly.

This relaxation allows for the development of polynomial-time algorithms. The authors proposed a bottom-up propagation procedure that identifies "empty-refinable" tasks to curtail task networks. Unlike previous methods, this approach successfully handles recursive (cyclic) domains by focusing on the boundary tasks that actually change the world state.

Key Results and Insights

  • Efficiency: Relaxed inference for both preconditions and effects can be decided in polynomial time (P).
  • Safety: The inferred relaxed effects are a subset of the true guaranteed effects, making them "safe" for use in pruning or heuristic calculations.
  • Link to Classical Planning: The authors noted that "guaranteed effects" are essentially fact landmarks, bridging HTN inference with established classical planning research.

Limitations and Future Work

While this work provides a strong theoretical foundation, it is currently limited to totally ordered HTN domains. Future research will need to address partially ordered domains and integrate these algorithms into active planners to measure empirical speedups on standard benchmarks. Additionally, the "relaxation gap"—the amount of information lost by ignoring primitive preconditions—remains to be quantified.

Summary updated

BibTeX
@inproceedings{olz2021revealing,
  author = {Conny Olz and Susanne Biundo and Pascal Bercher},
  title = {{Revealing Hidden Preconditions and Effects of Compound HTN Planning Tasks - A Complexity Analysis}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i13.17414},
}

Loading related content...

Figure