Planning Problem (HTN)

A Planning Problem (HTN) is a formal specification comprising three core components: a domain description, an initial state, and an initial task network. The domain description is a library of primitive actions (operators) and compound tasks with associated decomposition methods. The initial state is a snapshot of the world before planning begins. The initial task network is a set of high-level, often compound, tasks that define the planner's objective, which is to decompose this network into a sequence of executable primitive actions.

This formalism is the input to an HTN planner, which searches through the space of possible task decompositions rather than action sequences. The planner recursively applies methods to compound tasks, expanding the task network until it consists solely of primitive actions whose preconditions are satisfied in the expected world state. A valid solution is a hierarchical plan—a fully decomposed, executable sequence that achieves the initial tasks from the initial state, respecting all ordering and causal constraints imposed by the methods.

A Hierarchical Task Network (HTN) Planning Problem is a formal instance requiring a solution. It is defined by three mandatory components that together specify what needs to be accomplished, the rules for how to accomplish it, and the starting conditions.

The Domain Description is the rulebook and capability catalog for the planner. It formally defines:

Operators: The atomic, executable actions. Each operator has preconditions (logical conditions that must be true for it to run) and effects (how it changes the world state).
Task Schemas: Templates for both Primitive Tasks (which map directly to operators) and Compound Tasks (high-level, abstract goals).
Methods: The recipes for decomposition. Each method specifies how a single Compound Task can be broken down into a network of smaller subtasks (which can be compound or primitive), provided its preconditions are met. This description is reusable across many different planning problems within the same operational domain, such as logistics, manufacturing, or software deployment.

The planner begins with an initial task network, which contains the high-level goal tasks. It selects a compound task from this network and searches the domain description for an applicable method. A method is applicable if its preconditions are satisfied by the current world state. The planner applies the method, replacing the compound task with the method's specified network of subtasks. This task decomposition process repeats recursively on the new subtasks.

Decomposition continues until the network contains only primitive tasks, which correspond directly to executable operators. The planner ensures all ordering constraints and resource constraints are satisfied throughout this process. The final output is a solution plan: a totally ordered sequence of primitive actions guaranteed to be executable from the initial state and to achieve the original goals, as verified through plan verification. This hierarchical approach makes HTN planning highly efficient for complex, structured domains.

A Planning Problem in Hierarchical Task Network (HTN) planning is a formal problem instance defined by three core components: a Domain Description, an Initial State, and an Initial Task Network. The planner's objective is to decompose the initial task network, using methods from the domain, into a sequence of primitive, executable actions that, when applied starting from the initial state, achieve the desired goal.

Domain Description: The 'knowledge base' containing all task schemas, methods for decomposing compound tasks, and operators (primitive actions with preconditions and effects).
Initial State: A complete snapshot of the world before planning begins, specifying all facts that are true.
Initial Task Network: The high-level goal, represented as one or more (often compound) tasks that need to be accomplished.

The planner solves this problem through task decomposition, recursively replacing abstract tasks with subtasks until only primitive operators remain, resulting in a solution plan.

A Planning Problem (HTN) is defined by its core components. These related terms specify the formal elements that constitute the problem instance and the mechanisms for solving it.

The overarching planning formalism in which a Planning Problem is defined. An HTN represents tasks at multiple levels of abstraction, from high-level goals to primitive actions. The planner's job is to find a valid decomposition path through this hierarchy.

Core Idea: Break down 'what' needs to be done (tasks) before deciding 'how' to do it (actions).
Contrast with Classical Planning: Classical planners search through sequences of actions; HTN planners search through possible task decompositions.

The Initial World State is a complete snapshot of the environment at the start of the planning process. It is a set of grounded logical propositions that describe what is true. For example:

(robot-at dock-1)
(package-loaded pkg-a truck-1)
(battery-level robot-1 85) The planner uses this state to evaluate the preconditions of operators and methods. A method or operator is only applicable if all its preconditions are logically satisfied by the current world state. This component grounds the abstract planning problem in a specific, concrete scenario.

The Initial Task Network is the 'to-do' list given to the planner. It specifies the high-level goal(s) that need to be accomplished, expressed as one or more Compound Tasks. This is not a simple goal state (a desired set of conditions); it is a task to be performed.

For instance, instead of a goal (delivered pkg-a warehouse-5), the initial task network would contain the compound task (deliver pkg-a warehouse-5). The planner's job is to recursively decompose this task using methods from the domain description until it produces a sequence of executable primitive actions (operators) that, when applied to the initial state, result in the package being delivered.

A Planning Problem P is formally defined as the triple: P = (D, s0, t0) where:

D is the Domain Description.
s0 is the Initial World State.
t0 is the Initial Task Network. The planner's algorithm searches for a Solution Plan—a fully decomposed network where all tasks are primitive and ordering constraints are satisfied. The plan is valid if, when the primitive actions are executed in sequence starting from s0, they successfully accomplish the decomposition of t0.

HTN planning fundamentally differs from Classical (STRIPS-style) Planning:

Classical: Given an initial state and a goal state, find any sequence of actions that transforms one into the other.
HTN: Given an initial state and an initial task network, find a sequence of actions by recursively decomposing tasks according to provided methods. HTN is not just about achieving a state; it's about performing tasks in a prescribed, often procedurally constrained, manner. This makes HTN more expressive for modeling complex, hierarchical procedures but requires more upfront knowledge engineering in the domain description.

Consider a robot warehouse problem:

Domain (D): Contains operators like drive, load, unload. Contains compound tasks like transport-package. Contains a method: (transport-package ?p ?loc) can be decomposed into [navigate-to ?p, pick-up ?p, navigate-to ?loc, drop ?p].
Initial State (s0): (robot-at charging-station), (package-at pkg-1 shelf-a).
Initial Task (t0): (transport-package pkg-1 loading-dock). The HTN planner decomposes t0 using the method, checks preconditions for each new subtask (e.g., navigate-to requires knowing the robot's location), and eventually outputs a primitive sequence: [drive charging-station shelf-a, load pkg-1, drive shelf-a loading-dock, unload pkg-1].

The knowledge base that defines the rules of the planning world. It is a mandatory component of a Planning Problem (HTN). This description includes:

Operators: Definitions of primitive, executable actions (preconditions & effects).
Methods: Recipes for decomposing compound tasks into subtask networks.
Task Schemas: Templates for all possible tasks (primitive and compound).
Axioms & Constraints: Additional logical rules and limitations (e.g., resource limits).

Without a domain description, a planner has no knowledge of how to act or decompose tasks.

The starting goal specification for the planning problem. It is not a single goal state but one or more high-level compound tasks that need to be accomplished. This network is the root of the decomposition tree.

Example: [achieve(goal_state)] or [build(house), paint(house)].
Role in Planning: The planner's objective is to transform this initial network into a network containing only primitive tasks (actions) that are executable from the initial world state.

A task that corresponds directly to an executable action (operator) in the world. It is the leaf node in an HTN decomposition. Primitive tasks have no further subtasks; they are carried out by the execution engine.

Characteristics: Defined by an operator with preconditions (must be true to start) and effects (changes to the world state).
Example: pick_up(block_A), turn_valve(left, 90_degrees).
End State of Planning: A solution plan is a sequence of ordered primitive tasks.

A high-level, abstract task that cannot be executed directly. It must be decomposed into a network of subtasks (which can be other compound tasks or primitive tasks) using an applicable method. Compound tasks define 'what' without specifying 'how'.

Role: They provide the hierarchical structure. The initial task network typically contains compound tasks.
Decomposition: A single compound task may have multiple methods, each representing a different way to achieve it under different conditions.
Example: build_wall() is a compound task; methods might decompose it into [lay_foundation(), stack_blocks(), apply_mortar()].

A decomposition rule that specifies one way to accomplish a compound task. A method is defined by:

Task Head: The compound task it decomposes.
Preconditions: Logical conditions that must hold in the current state for this method to be applicable.
Subtasks: The network of (compound or primitive) tasks that replace the parent task.
Ordering Constraints: Temporal relations between the subtasks.

Key Function: Methods encode procedural knowledge (different ways to do things). The planner searches through applicable methods to find a decomposition that leads to a feasible primitive action sequence.

What is a Planning Problem (HTN)?

The Three Core Components

Domain Description

How an HTN Planner Solves a Planning Problem

Frequently Asked Questions

Initial World State

Initial Task Network

Formal Problem Statement

Contrast with Classical Planning

Example: Logistics Domain

Initial Task Network

Primitive Task

Compound Task

Method (HTN)

Planning Problem (HTN)

What is a Planning Problem (HTN)?

The Three Core Components

Domain Description

How an HTN Planner Solves a Planning Problem

Frequently Asked Questions

Related Terms

Hierarchical Task Network (HTN)

Domain Description (HTN)

Initial World State

Initial Task Network

Formal Problem Statement

Contrast with Classical Planning

Example: Logistics Domain

Initial Task Network

Primitive Task

Compound Task

Method (HTN)