HTN Planning

A task schema is a template that defines a class of tasks within the planning domain. It specifies the task's name and parameters, acting as a blueprint. There are two fundamental types:

• Primitive Task Schema: Defines a directly executable action. It is associated with a planning operator that has preconditions and effects.
• Compound Task Schema: Defines a high-level, abstract goal that cannot be executed directly and must be decomposed using methods. For example, a Deliver(Package, Location) task schema would be compound, requiring decomposition into Navigate, PickUp, and DropOff subtasks.

A method is the core rule for hierarchical decomposition. It specifies one possible way to break down a compound task into a network of smaller subtasks, provided its preconditions are satisfied in the current world state.

Structure: Method(CompoundTask, Preconditions, SubtaskNetwork)

• The subtask network defines the new tasks (which can be primitive or compound) and any ordering constraints between them.
• Multiple methods can exist for the same compound task, representing different strategies or contextual approaches. The planner's job is to select an applicable method whose preconditions hold.

An operator is the formal, executable representation of a primitive action. It defines the atomic unit of change in the world.

Key Components:

• Preconditions: Logical statements that must be true in the current state for the operator to be legally applied.
• Effects: Statements that describe how the operator changes the world state (additions and deletions). Operators are grounded (all parameters are bound to concrete objects) during planning. For instance, a Drive(Vehicle, From, To) operator would have preconditions like Fuel(Vehicle) > 0 and At(Vehicle, From), with effects At(Vehicle, To) and not(At(Vehicle, From)).

The initial task network is the planner's starting goal. It is typically a small network containing one or more high-level compound tasks (e.g., [BuildHouse]). This is the root that undergoes recursive decomposition.

The initial world state is a complete, ground logical description of the starting environment. It is a set of propositions (facts) that are true at time zero, such as Has(Hammer), At(Robot, Workshop). All planning—checking method preconditions and operator applicability—is performed relative to this state and its simulated progression.

Task decomposition is the recursive core algorithm. The planner selects a non-primitive (compound) task in the current network, finds an applicable method whose preconditions match the state, and replaces that task with the method's subtask network.

Plan refinement is the iterative result. The plan evolves from an abstract skeletal plan (containing high-level tasks) into a fully specified solution plan (a sequence of grounded primitive operators). This process interleaves planning with state simulation to ensure logical consistency at every step.

HTNs encode crucial constraints that govern valid decomposition and execution.

• Ordering Constraints: Temporal relations (Before(TaskA, TaskB)) enforced within a method's subtask network. They ensure actions occur in a necessary sequence (e.g., ObtainBricks before BuildWall).
• Resource Constraints: Limitations on consumable or reusable assets (e.g., Energy, Workers, Money). Methods and operators must respect availability. The planner must decompose tasks in a way that does not exceed resource capacities, often requiring backtracking if constraints are violated.

The broader field of AI concerned with generating sequences of actions to achieve goals. HTN Planning is a specific approach within this field, distinguished by its hierarchical decomposition. Other major paradigms include:

• Classical Planning: Searches for a sequence of operators in a state space.
• Contingent Planning: Generates plans that include branches for different possible outcomes.
• Temporal Planning: Considers the duration of actions and concurrent execution. HTN is often preferred for complex, structured domains where expert knowledge about task breakdown is available.

A seminal, forward-chaining HTN planning algorithm. SHOP performs task decomposition in a depth-first, state-progressive manner, meaning it simulates the effects of actions as it plans. Its key characteristics are:

• Ordered Task Decomposition: Subtasks are processed in the order they appear in a method.
• Efficiency: By interleaving planning with state simulation, it can prune irrelevant branches early.
• Determinism: Given the same domain and problem, it produces the same plan, which is valuable for debugging. SHOP and its successor, SHOP2, are foundational references for implementing practical HTN planners.

The output of an HTN planner, which retains the decomposition structure of the solution. Unlike a flat sequence of actions, a hierarchical plan explicitly shows:

• Which compound tasks were decomposed.
• Which methods were selected for each decomposition.
• The parent-child relationships between tasks and subtasks. This structure is invaluable for plan explanation, execution monitoring, and replanning, as failures can be traced back to specific high-level tasks for repair.

A classical planning paradigm that searches through the space of partial plans, refining them by adding actions and constraints until a solution is found. It contrasts with state-space planning (which searches world states) and HTN planning. Key differences:

• HTN searches through possible task decompositions.
• Plan-Space searches through sequences of planning operations (like adding an action or enforcing an ordering). HTN can be more efficient in domains with strong hierarchical structure, while plan-space planners like UCPOP are more flexible for problems with complex temporal interactions.

A reinforcement learning paradigm where an agent learns an internal model of its environment's dynamics and uses it for planning. Connections to HTN include:

• Shared Planning Core: Both use a model (transition dynamics / task methods) to simulate future outcomes.
• Hierarchy: Advanced MBRL often uses hierarchical models where high-level actions are temporally extended, analogous to compound tasks.
• Synergy: An HTN can provide a structured skeleton or skill library for an MBRL agent, guiding its exploration and learning in complex tasks.

The automatic generation of executable code from a high-level specification. HTN Planning is a form of procedural program synthesis. The parallels are direct:

• A compound task is like a function call.
• A method is like a function definition or a code recipe.
• Task decomposition is the process of inlining and composing these recipes. This relationship makes HTN a powerful technique for automating workflow generation and agentic code execution, where the goal is to produce a reliable sequence of API calls or system commands.