How is HTN planning different from classical planning?

Classical planning searches for any action sequence that reaches a goal state, using only the actions' preconditions and effects. HTN planning instead starts from tasks to accomplish and decomposes them using methods that encode how, procedurally, those tasks are normally done, so it relies on richer domain knowledge.

Why can HTN planning be undecidable?

Because methods can decompose a compound task into networks that include further compound tasks, the decomposition process can recurse without bound, much like a grammar generating arbitrarily long derivations. In its general form, deciding whether a valid decomposition exists is therefore undecidable.

Hierarchical Task Network Planning

Hierarchical task network (HTN) planning solves problems by recursively decomposing high-level tasks into subtasks using a library of methods, rather than searching directly over primitive actions to reach a goal state.

Definition

HTN planning represents a problem as an initial network of tasks to be performed and a set of methods for decomposing compound tasks into subtasks; a solution is a decomposition into primitive, executable actions that respects the methods' constraints.

Scope

This topic covers the HTN planning paradigm: tasks (primitive and compound), methods that specify how to decompose a compound task into subtasks, and the planning process that refines an initial task network until only executable primitive actions remain. It addresses the expressivity and complexity of HTN planning relative to classical planning and notable HTN planners. The classical, goal-state-based planning model is treated in the related topics; HTN planning instead encodes procedural domain knowledge.

Core questions

How do methods encode domain knowledge about how to accomplish compound tasks?
How does task decomposition differ from searching toward a goal state in classical planning?
What is the expressivity and computational complexity of HTN planning compared with classical planning?
How are ordering and precondition constraints among subtasks handled during decomposition?

Key concepts

primitive and compound tasks
methods and decomposition
task networks
ordering constraints
procedural domain knowledge
HTN expressivity
ordered task decomposition
SHOP2

Key theories

Task decomposition with methods: HTN planning replaces goal-directed search with recursive decomposition: compound tasks are expanded into networks of subtasks via methods until all tasks are primitive, letting human expertise about how to perform tasks be encoded directly.
Expressivity and complexity of HTN planning: HTN planning is strictly more expressive than classical STRIPS planning; in its general form plan existence can be undecidable, and restricted forms occupy higher complexity classes, reflecting the power of method-based decomposition.
Ordered task decomposition planners: Practical HTN planners such as SHOP2 plan by decomposing tasks in the order they will be executed, which lets them evaluate preconditions against fully determined states and incorporate rich domain knowledge efficiently.

Clinical relevance

HTN planning is widely used where expert procedures are known and must be followed, such as manufacturing process planning, military and logistics operations, web-service composition, and game and story generation, because methods let domain experts encode standard ways of accomplishing tasks.

History

Hierarchical planning traces to Sacerdoti's NOAH and abstraction hierarchies in the 1970s. Erol, Hendler, and Nau formalized HTN planning and analyzed its complexity in the early 1990s, and the SHOP and SHOP2 planners (around 2000-2003) made ordered HTN planning a practical and widely used technology.

Key figures

Dana Nau
Kutluhan Erol
James Hendler
Earl D. Sacerdoti
Austin Tate

Seminal works

erol1994
nau2003

Frequently asked questions

How is HTN planning different from classical planning?: Classical planning searches for any action sequence that reaches a goal state, using only the actions' preconditions and effects. HTN planning instead starts from tasks to accomplish and decomposes them using methods that encode how, procedurally, those tasks are normally done, so it relies on richer domain knowledge.
Why can HTN planning be undecidable?: Because methods can decompose a compound task into networks that include further compound tasks, the decomposition process can recurse without bound, much like a grammar generating arbitrarily long derivations. In its general form, deciding whether a valid decomposition exists is therefore undecidable.