Hierarchical Plan

The plan encodes how tasks are achieved, not just what actions to take. This is represented through HTN methods—rules that define valid ways to decompose a compound task. For example, the method for 'Ship Product' might specify that it decomposes into 'Pack Item' THEN 'Generate Label' THEN 'Hand to Courier'. This makes the plan a direct instantiation of domain-specific procedural knowledge, differentiating it from a plan generated by a classical planner that only reasons about action preconditions and effects.

The hierarchical relationships impose temporal and logical constraints on subtasks. These are not just sequential lists but networks with:

• Ordering Constraints: 'Mix Ingredients' must precede 'Bake'.
• Causal Links: The effect of 'Unlock Door' enables the precondition of 'Open Door'.
• Resource Constraints: Subtasks may share and consume limited resources. The plan structure makes these dependencies explicit, allowing for constraint propagation during both planning and execution monitoring, ensuring the plan remains feasible.

Classical planning starts with a goal state (e.g., 'Block A on Block B'). Hierarchical planning, as used in HTNs, starts with a set of tasks to accomplish. The plan's success is measured by the successful execution and decomposition of these tasks, which indirectly achieves desired world states. This task-centric view aligns more naturally with instruction following and business process automation, where the agent is given a job ('Onboard the client') rather than a precise final state specification.

When execution fails or the environment changes, the hierarchical structure enables localized repair. Instead of discarding the entire plan, the system can isolate the failure to a specific branch of the decomposition tree (e.g., the 'Payment Processing' subtask). It can then re-decompose only that compound task using alternative methods, preserving the rest of the valid plan structure. This leads to more efficient and robust recovery behavior compared to replanning from scratch.

The two fundamental types of tasks in an HTN domain.

• Primitive Task: Corresponds directly to an executable operator with defined preconditions and effects. It is a leaf node in the decomposition tree (e.g., 'PickUp(Object_A)').
• Compound Task: An abstract, high-level goal that cannot be executed directly. It must be decomposed into subtasks via a method (e.g., 'DeliverPackage'). The choice of method defines the strategy for achieving it.

A schema that defines one possible way to achieve a compound task. A method specifies:

• The compound task it can decompose.
• Preconditions that must hold in the current world state for it to be applicable.
• A task network (a set of subtasks with ordering constraints) that refines the compound task. Planners select among applicable methods, making HTNs highly expressive for encoding domain-specific strategies and procedures.

The Simple Hierarchical Ordered Planner, a seminal and influential HTN planning algorithm. SHOP performs forward decomposition, interleaving planning with state progression. It starts with the initial task list and state, decomposes the first task, updates the state with the effects of new primitive actions, and repeats. This makes it efficient and directly executable, forming the basis for many modern hierarchical planning systems.

Key concepts in the iterative generation of a hierarchical plan.

• Skeletal Plan: A partially specified, abstract plan containing high-level compound tasks. It is the starting point before full decomposition.
• Plan Refinement: The iterative process of replacing abstract tasks in the skeletal plan with more concrete subtasks or primitive actions via applicable methods. This continues until the plan is fully grounded and executable.