Hierarchical Plan

The core characteristic is the preservation of the task decomposition tree. A high-level goal (e.g., 'Build a Website') is not just a label but a node linked to its subtasks ('Design UI', 'Develop Backend', 'Deploy'). This structure allows the system to understand which actions belong to which abstract objective, enabling context-aware replanning and explainability. If 'Deploy' fails, the system knows it must replan within that specific branch of the hierarchy.

A hierarchical plan contains tasks at multiple levels of abstraction simultaneously. It is not merely a pre-execution blueprint that gets flattened. It maintains:

• Compound Tasks: Abstract, non-executable goals (e.g., 'Acquire Customer').
• Primitive Tasks: Grounded, executable actions (e.g., 'Send API call to CRM'). This allows for partial plan execution where high-level parts of the plan remain abstract while others are being concretely executed, adapting to runtime feedback without discarding the overall goal structure.

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 core planning formalism that generates hierarchical plans. An HTN is a structured representation where high-level, compound tasks are recursively decomposed into networks of subtasks using methods until only primitive tasks (executable actions) remain. This approach contrasts with classical planning by starting with an abstract goal and refining it, rather than searching a space of atomic actions.

The fundamental recursive process at the heart of HTN planning. It involves replacing a non-executable, compound task with a network of subtasks by applying a matching decomposition method. This process repeats until the entire plan consists solely of primitive actions. The result is a decomposition tree that visually maps the hierarchical relationships in the final plan.

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.