HTN Planning: Complexity and Expressivity

Kutluhan Erol, James A. Hendler, Dana S. NauAAAI 1994

Introduction

For years, Hierarchical Task Network (HTN) planning was often dismissed by AI theorists as a mere "efficiency hack" for practical systems—a way to hard-code domain knowledge to speed up search. This seminal research proves the opposite: HTN planning is fundamentally more expressive than standard STRIPS-style planning. It occupies a higher rung on the computational ladder, analogous to the jump from regular to context-free languages, and is actually undecidable in its most general form.

The Gap Between Theory and Practice

In the early 1990s, a significant rift existed in the AI planning community. Theoretical research focused almost exclusively on STRIPS-style planning, which utilizes simple preconditions and effects to reach a goal state. Meanwhile, practical, real-world systems like SIPE or O-Plan relied on HTNs. These systems work by decomposing high-level compound tasks into smaller, more detailed sub-tasks until they reach primitive actions that can be executed.

The core problem was that HTN planning lacked a rigorous theoretical foundation. Many researchers assumed HTNs were simply a heuristic layer over STRIPS. This paper sets out to answer whether HTN planning is inherently more powerful and to map its computational complexity under various constraints.

Formalizing Task Networks

The authors provide the first formal, mathematical definition of HTN planning suitable for rigorous analysis. They define a language $\mathcal{L}$ that centers on Task Networks: sets of tasks with associated constraints, including ordering, variable bindings, and "truth constraints" regarding the state of the world.

Example of a task network with ordering and truth constraints.

In this formalism, Methods act as rules for decomposing a "compound task" into a more detailed task network. By mapping HTN problems to known complexity classes, the authors demonstrate that HTNs can simulate the intersection of context-free grammars, a property that leads directly to their findings on undecidability.

Key Insights and Theoretical Power

The Grammar Analogy

The most striking insight is the relationship between STRIPS and HTN planning. The authors argue it is exactly like the relationship between Regular Languages and Context-Free Languages. STRIPS is essentially a restricted, "flat" special case of the hierarchical power inherent in HTNs.

The Path to Undecidability

One of the paper's most surprising findings is how easily undecidability is reached. A complex system isn't required to break the decidability barrier; allowing just two non-primitive tasks in a network without a fixed order makes the problem undecidable. This means no algorithm can be guaranteed to find a plan or prove that one does not exist for every possible input.

Expressivity of Intermediate States

Unlike STRIPS, which primarily focuses on the final state, HTNs allow users to express constraints on how a goal is achieved. For example, a user can mandate that a table must be cleared before it is moved. This makes HTNs inherently more expressive for complex, procedural real-world tasks where the sequence of events is as important as the outcome.

Complexity Results

The paper presents a definitive complexity table that categorizes HTN planning based on different restrictions, such as task ordering and the use of variables.

Summary of complexity results for HTN planning under various restrictions.

Key findings from this analysis include:

  • General HTN Planning: Undecidable.
  • Totally Ordered HTNs: Decidable, but computationally expensive, ranging from PSPACE-hard to EXPSPACE-complete.
  • Regular HTNs (at most one non-primitive task): PSPACE-complete to EXPSPACE-complete, matching the complexity of STRIPS.
  • Primitive HTNs (no decomposition): NP-complete, as the problem essentially reduces to a constraint satisfaction problem.

The authors prove that certain planning domains simply cannot be represented by any finite number of STRIPS operators, yet they are easily handled by HTNs.

Discussion and Limitations

While the paper focuses on worst-case complexity, the authors acknowledge a paradox: although HTN planning is "harder" in theory, its hierarchical structure is precisely what makes it faster in practice. The hierarchy allows human designers to prune the search space effectively.

Furthermore, the study focuses on finding any valid plan rather than the optimal (shortest) plan. In many HTN applications, following a specific procedure is more important than finding the absolute shortest path to a goal. This work laid the groundwork for decades of subsequent research into HTN heuristics and more efficient solvers.

Summary updated

BibTeX
@inproceedings{erol1994htn,
  author = {Kutluhan Erol and James A. Hendler and Dana S. Nau},
  title = {{HTN Planning: Complexity and Expressivity}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1994},
}
Figure