Hierarchical Task Network (HTN)

A compound task is a high-level, abstract goal that cannot be executed directly by an agent. It represents a problem to be solved, such as 'Navigate to Room' or 'Assemble Product'. In HTN planning, the planner's job is to decompose compound tasks into a network of simpler subtasks using available methods. The initial planning problem is typically defined as a single top-level compound task.

A primitive task (or action) is a low-level, directly executable operation. It represents the atomic building blocks of a plan, such as 'Turn 90 degrees', 'Grasp object A', or 'Move forward 1 meter'. Primitive tasks have preconditions that must be true in the world to execute them and effects that describe how they change the world state. The decomposition process stops when all tasks in the network are primitive.

A method is a recipe for decomposing a compound task into a partially ordered set of subtasks. It defines a way to accomplish the high-level goal. Each method has:

• Task Head: The compound task it can decompose.
• Preconditions: Logical conditions that must hold for this method to be applicable.
• Subtasks: A network (sequence or partial order) of smaller compound or primitive tasks.

A single compound task may have multiple methods, allowing the planner to choose different strategies based on the current world state.

An operator is the formal definition of a primitive task's executable logic. It is analogous to an action in STRIPS or PDDL and specifies:

• Name & Parameters: The action identifier and its variables.
• Precondition: A logical formula that must be satisfied in the current state for the operator to be legally applied.
• Effect: A description of how the operator changes the state, typically divided into an add list (facts that become true) and a delete list (facts that become false). Operators are the bridge between the symbolic plan and the robot's low-level control system.

The planning domain is the complete knowledge base or library that defines the capabilities available to the planner. It is a static collection of:

• All operators (primitive actions).
• All methods for decomposing compound tasks.
• The ontology (predicates and types) used to describe states.

The domain encodes the how—the possible ways the agent can interact with and change the world, independent of any specific problem instance.

A planning problem defines a specific instance to be solved. It consists of three key elements:

1. Initial State: A complete snapshot of the world at the start, described as a set of grounded logical predicates (e.g., (robot-at lobby), (door-open room1)).
2. Task Network: The initial high-level task to be accomplished, usually a single compound task (e.g., (deliver package room5)).
3. Domain: A reference to the planning domain containing the methods and operators.

The planner's job is to use the domain to decompose the initial task network, given the initial state, into a sequence of executable primitive operators.

HTNs are a proven alternative to Behavior Trees and Finite State Machines for creating robust, believable AI in video games and simulations. Designers encode domain knowledge as methods, allowing NPCs to perform complex activities like "Defend Fortress" by reasoning about subtasks:

• Evaluate Threat → Patrol Walls or Man Artillery.
• Resource Management → Fetch Ammunition or Repair Gate. The explicit task hierarchy makes AI behavior more transparent, debuggable, and modular than black-box reinforcement learning approaches, crucial for maintaining narrative and gameplay balance.

HTNs have been historically significant in military planning applications (e.g., the O-Plan and SHOP2 planners) for missions like "Conduct Reconnaissance." They rigorously model:

• Temporal constraints and concurrent actions.
• Resource constraints (fuel, ammunition).
• Hierarchical decomposition of commands: Mission → Phase → Unit Task → Action. This formalism allows planners to generate, evaluate, and validate complex courses of action from high-level directives, providing commanders with explainable, auditable plans.

The general process of breaking a complex, high-level goal into a structured hierarchy of simpler, actionable subtasks. HTN planning is a specific, formalized approach to this process, using a library of methods to recursively decompose tasks until primitive actions are reached. This is distinct from simply sequencing pre-defined actions, as it involves selecting appropriate decomposition methods based on the current world state.

Foundational languages and representations for classical planning, which HTN extends.

• STRIPS (Stanford Research Institute Problem Solver): A seminal planning model where actions are defined by preconditions (what must be true to execute), add lists (facts made true), and delete lists (facts made false).
• PDDL (Planning Domain Definition Language): The standardized, formal language descended from STRIPS used to model planning problems. HTN planning often uses HTN extensions to PDDL (like PDDL2.2 or PDDL3) to define tasks and methods alongside actions.

A modular, hierarchical control architecture used extensively in game AI and robotics for decision-making. While both HTNs and Behavior Trees are hierarchical, they differ fundamentally:

• HTN: A planning formalism. It generates a plan (sequence of actions) offline or online by searching through possible decompositions.
• Behavior Tree: An execution and reactive control structure. It executes a pre-defined tree of nodes (tasks, conditions, sequences, selectors) and can react dynamically to changes in the environment by traversing different branches.

The algorithmic process of computing a feasible, often optimal, path or trajectory for a robot from a start to a goal configuration while avoiding obstacles. HTN planning operates at a higher task level, producing a sequence of what to do (e.g., PickUp(block_A), PlaceOn(block_A, table)). Motion planning solves the lower-level how, computing the specific joint angles and velocities to execute a primitive action like PickUp. The integration of HTN task planning with motion planning is a key challenge in robotics.

A curated repository of reusable, parameterized motion primitives or behavioral modules. In an HTN framework, the primitive tasks at the leaves of the decomposition hierarchy often correspond to executable skills drawn from such a library. For example, an HTN method might decompose Assemble(Widget) into Fetch(part_A), Fetch(part_B), Align(part_A, part_B), where each of these is a parameterized skill (e.g., a trained policy or a optimized trajectory) stored in the library.

A major category of planning algorithms contrasted with state-space planning. HTN planning is a plan-space approach.

• State-Space Planning (e.g., STRIPS solvers): Searches through a graph of world states, applying actions to transform one state into another.
• Plan-Space Planning (HTN): Searches through a space of partially specified plans (task networks). It starts with an abstract high-level task and refines it by applying methods, working on the plan structure itself rather than simulating state transitions. This allows it to handle complex hierarchical constraints more naturally.