Automated planning is fundamentally about finding a sequence of actions that transforms an initial state into a desired goal state. In classical planning (like STRIPS), this process resembles finding a path through a massive graph of states. While computationally challenging—typically PSPACE-complete—the plan itself is a flat, linear sequence.
Hierarchical Task Network (HTN) planning changes the paradigm. Instead of building a plan from scratch using atomic actions, an HTN planner begins with a high-level abstract task (e.g., "Build a House") and systematically decomposes it into sub-tasks (e.g., "Lay Foundation", "Build Walls") using predefined recipes called methods. This process continues until the entire network is reduced to primitive, executable actions.
While this hierarchical structure mirrors human problem-solving and domain organization, it introduces a profound computational burden. Understanding the complexity of hierarchical planning requires looking at it not as simple pathfinding, but as formal language parsing.
The Grammar of Action and Undecidability
To understand why hierarchical planning is uniquely difficult, consider the mathematical difference between classical and hierarchical models. Classical planning transitions from state to state, making it analogous to a regular language recognized by a finite automaton. Hierarchical planning, by contrast, relies on recursive task decomposition. This structural recursion elevates the formalism to the level of context-free grammars.
As Kutluhan Erol et al. demonstrated in their foundational work, HTN Planning: Complexity and Expressivity, this shift makes HTN planning fundamentally more expressive than classical planning, but it triggers a severe theoretical penalty: general HTN planning is completely undecidable. The planner is not merely searching a state space; it is attempting to find the intersection of complex task networks. The authors proved that even minimal structural freedom—such as allowing just two unordered non-primitive tasks within a network—is enough to make it impossible for any universal algorithm to guarantee termination.
Why Even Verification is Hard
In classical planning, verifying whether a proposed plan is valid is trivial: you simply simulate the actions from the initial state and check if the final state satisfies the goal. In the hierarchical world, this intuition completely breaks down.
Even if you are handed a flat sequence of primitive actions, confirming that it constitutes a valid hierarchical plan is highly complex. As Songtuan Lin et al. showed in On the Computational Complexity of Plan Verification, (Bounded) Plan-Optimality Verification, and Bounded Plan Existence, plan verification remains NP-complete. The reason is structural: the verifier cannot just simulate the state transitions; it must reconstruct the hidden derivation tree to prove that this specific sequence of actions could have legally originated from the initial high-level tasks. As noted by Cornelius Brand et al. in A Structural Complexity Analysis of Hierarchical Task Network Planning, this structural overhead means that almost all fundamental reasoning tasks in HTNs inherit severe computational barriers.
The Ordering and Relaxation Dilemma
To make these problems manageable, researchers often enforce constraints on how tasks can be ordered. The most restrictive variant is total ordering, where the methods specify an exact, immutable sequence for all sub-tasks.
However, restricting the order does not make the problem simple. Gregor Behnke et al. established in totSAT - Totally-Ordered Hierarchical Planning Through SAT that totally-ordered HTN planning is EXPTIME-complete. When planners loosen this constraint to allow partial ordering (where some tasks can occur in parallel or flexible sequences), Michael Katz et al. note in On Partial Satisfaction Planning with Total-Order HTNs that the search space quickly expands back toward undecidability.
This complexity also resists standard heuristic shortcuts. In classical planning, algorithms use "delete-relaxation" (ignoring the negative side-effects of actions) to quickly estimate how close they are to a goal. But Vikas Shivashankar et al. proved in Incorporating Domain-Independent Planning Heuristics in Hierarchical Planning that hierarchical planning remains NP-hard even under delete-relaxation. The bottleneck isn't the physical effects of the actions; it is the rigid combinatorial requirement of satisfying the hierarchy itself. To build effective heuristics, a planner must relax the hierarchical constraints rather than the state transitions.
Task Insertion as a Computational Safety Valve
Counterintuitively, one of the most effective ways to bound the complexity of hierarchical planning is to allow the planner to "break the rules" of the hierarchy.
In pure HTN planning, every single action in the final plan must be explicitly derived from a top-level task recipe. If the environment requires an unexpected intermediate step—like picking up a key that wasn't mentioned in the "Open Door" recipe—the planner fails.
If we modify the framework to allow task insertion—giving the planner the freedom to inject arbitrary primitive actions outside the strict decomposition tree—the complexity landscape changes dramatically. Ron Alford et al. explored this interaction in Hierarchical Planning: Relating Task and Goal Decomposition with Task Sharing. They discovered that task insertion acts as a computational safety valve. By allowing the planner to fall back on classical action sequences to bridge gaps, the infinite recursive loops of pure HTNs are broken. This shifts the complexity from semi-decidable to NEXPTIME-complete, and down to PSPACE-complete for goal-oriented networks.
Even when augmented with complex state constraints, as shown by Zhanhao Xiao et al. in Hierarchical Task Network Planning with Task Insertion and State Constraints, task insertion keeps the problem decidable (at 2-NEXPTIME-complete), preventing it from slipping into the black hole of complete undecidability.
Nondeterminism and the Cost of Flexibility
When planning moves from predictable environments to nondeterministic worlds (where actions have uncertain outcomes), one might expect the uncertainty to be the primary driver of complexity. However, the structural hierarchy remains the dominant factor.
Dillon Z. Chen et al. demonstrated in Fully Observable Nondeterministic HTN Planning - Formalisation and Complexity Results that the fundamental undecidability of hierarchical planning persists in nondeterministic settings, driven entirely by the recursive structure of the task network rather than the predictability of individual actions.
The complexity escalates based on when the agent is allowed to make choices:
- Static/Offline Decisions: If the agent must commit to a rigid decomposition strategy before executing the plan, the complexity is bounded by the structural constraints of the network.
- Reactive/Online Decisions: If the agent can wait and choose how to decompose a high-level task reactively based on the outcomes of previous actions, the complexity spikes.
In Flexible FOND HTN Planning: A Complexity Analysis, the authors showed that adopting these flexible, reactive method-based policies increases the computational complexity by an entire complexity class (for instance, turning PSPACE-complete variants into EXPTIME-complete problems). This occurs because the planner can no longer evaluate a single static tree; it must construct and verify a policy that branches across both environmental outcomes and decomposition choices simultaneously.
Key Foundational Work
HTN Planning: Complexity and Expressivity (1994) — contributed 2 concept elements to this direction.
Dominance and Subsumption in Constraint-Posting Planning (1987) — contributed 2 concept elements to this direction.