Hierarchical Task Network (HTN)

A Compound Task is a high-level, abstract objective that cannot be executed directly. It serves as a placeholder that must be decomposed into a network of simpler subtasks using applicable methods. Examples include DeliverPackage(city) or DiagnoseSystemFault(). It represents the 'what' without specifying the 'how'.

A Primitive Task (or Operator) is a directly executable action at the leaves of the decomposition tree. It is defined by:

• Preconditions: Logical conditions that must be true in the world state for the action to be applicable.
• Effects: The changes the action makes to the world state upon execution. For example, NavigateTo(location) or OpenValve(id) are primitive tasks with specific preconditions and effects.

A Method (or Decomposition Method) is a schema that defines a possible way to decompose a specific compound task into a network of subtasks. Each method has:

• Applicability Conditions: Preconditions that must hold for this decomposition to be valid.
• Subtasks: The network of (compound or primitive) child tasks.
• Ordering Constraints: Temporal relations between the subtasks (e.g., sequential, parallel). A planner selects among competing methods based on the current world state.

A Task Network is a directed graph representing the current set of tasks to be accomplished, along with the ordering constraints between them. It evolves during planning:

• Initial Task Network: Contains the top-level goal compound tasks.
• Intermediate Task Networks: Contain a mix of compound and primitive tasks as decomposition proceeds.
• Final Task Network: Contains only primitive tasks in a valid order, constituting the solution plan.

The Domain Description is the complete formal specification of an HTN planner's knowledge. It is a Task Library containing:

• Task Schemas: Templates for all compound and primitive tasks.
• Method Library: All available decomposition methods.
• Operator Definitions: All primitive actions with their preconditions and effects. This description is domain-specific (e.g., logistics, manufacturing, IT orchestration) and is separate from any specific problem instance.

A Planning Problem instance is defined by three inputs to the HTN planner:

1. Domain Description: The library of tasks and methods.
2. Initial State: A complete snapshot of the world before plan execution (e.g., RobotAt(Home), ValveStatus(Closed)).
3. Initial Task Network: The high-level goal tasks to be achieved (e.g., [MaintainSystemPressure]). The planner's job is to process this problem and output a solution plan—a sequence of executable primitive actions.

A Primitive Task is a task in an HTN that corresponds directly to an executable action or operator in the planning domain. It is the terminal leaf in a decomposition tree and cannot be broken down further by an HTN method.

• Key Role: Represents the atomic, executable units of a plan.
• Contrast with Compound Tasks: While compound tasks are abstract goals requiring decomposition, primitive tasks are the concrete steps a system (like a robot or software agent) can perform.
• Example: In a logistics domain, Drive(Truck-A, Warehouse-1, Warehouse-2) or Load(Package-23, Truck-A) would be primitive tasks.

A Compound Task is a high-level, abstract goal in an HTN that must be decomposed into a network of subtasks before it can be executed. It defines what needs to be achieved, not how.

• Decomposition Required: A compound task is a placeholder that is replaced by a subtask network via an applicable method.
• Hierarchical Structure: Compound tasks enable the representation of complex goals at multiple levels of abstraction.
• Example: DeliverPackage(Package-23, Customer-45) is a compound task. Its decomposition might involve subtasks like LoadPackage, TransportPackage, and UnloadPackage.

A Method is a schema that defines a possible way to decompose a specific compound task into a network of subtasks, provided its preconditions are satisfied. Methods encode the procedural knowledge of how to achieve an abstract goal.

• Structure: A method typically includes: 1) A head (the compound task it decomposes), 2) Preconditions (logical conditions that must be true), and 3) A task network (the set of subtasks and ordering constraints).
• Choice Point: Multiple methods can exist for the same compound task, giving the planner options. The planner selects a method whose preconditions match the current world state.
• Example: For the compound task BrewCoffee, one method's preconditions could check if BeansAvailable is true, and its subtask network might be [GrindBeans, HeatWater, PourWater, Serve].

Task Decomposition is the core recursive process in HTN planning where a compound task is replaced by a network of subtasks using an applicable method. This process continues until the entire plan consists solely of primitive tasks.

• Recursive Algorithm: The planner searches through the space of possible decompositions, not sequences of actions.
• Result: Produces a Decomposition Tree (or hierarchical plan) that visually maps high-level goals to low-level actions.
• Contrast with State-Space Search: Unlike classical planning which searches through world states, HTN planning searches through task hierarchies, often making it more efficient for complex, structured domains.

SHOP is a seminal, forward-chaining HTN planning algorithm that performs task decomposition in a depth-first manner, interleaving planning with state progression. It assumes tasks within a method are totally ordered.

• Algorithm Principle: SHOP starts with the initial task network and state. It selects the first task in the network; if it's primitive, it's added to the plan and its effects are applied to the current state; if it's compound, an applicable method is chosen and its subtasks are inserted in place.
• Efficiency: By progressing the world state as it plans, SHOP can use current state information to prune irrelevant method choices early.
• Legacy: SHOP and its successor SHOP2 are foundational references in automated planning and influenced modern agent and game AI systems.

A Skeletal Plan is a partially specified, abstract plan generated during the intermediate stages of HTN planning. It contains a mix of compound tasks (awaiting decomposition) and primitive tasks.

• Intermediate Artifact: Represents the planner's current, incomplete solution. It becomes more concrete through successive plan refinement steps.
• Utility: Provides a high-level blueprint that guides further decomposition. It allows for reasoning about abstract plan structure before committing to all low-level details.
• Evolution: A skeletal plan is progressively refined until no compound tasks remain, at which point it becomes a fully executable solution plan.