Hierarchical Task Network (HTN) Planning

A task is the fundamental unit of work in HTN planning, representing something to be accomplished. There are two primary types:

• Primitive Tasks: These are directly executable actions, analogous to operators in classical planning (e.g., pick-up(blockA), drive-to(warehouse)). They have preconditions and effects.
• Compound (or Abstract) Tasks: These are high-level objectives that cannot be executed directly and must be decomposed into subtasks (e.g., build-house, deliver-package). They are defined solely by the methods that decompose them.

A method is a domain-specific recipe that defines how a compound task can be accomplished. It specifies a set of subtasks and ordering constraints. A method is applicable only if its precondition is satisfied in the current state.

Structure: Method: <compound-task-name>

• Precondition: Logical conditions that must hold.
• Subtasks: A network (often a partial order) of subtasks, which can be primitive or compound.

Example: A method for travel-to(office) might have subtasks [walk-to(garage), start-car, drive-to(office)] with ordering constraints between them.

Operators define the primitive, executable actions in the domain. They are identical to actions in classical planning frameworks like STRIPS.

Structure: Operator: <action-name>

• Precondition: Facts that must be true for the action to be legal.
• Effect: Changes to the state, typically an add list (facts made true) and a delete list (facts made false).

Operators form the leaves of the task decomposition tree. The planner's goal is to reduce all compound tasks to a sequence of operators that is executable from the initial state.

The task network is the core data structure during planning. It is a directed graph where nodes are tasks (primitive or compound) and edges represent ordering constraints (e.g., Task A must be completed before Task B).

• Initial Network: Often contains a single top-level compound task.
• Planning Process: The planner repeatedly selects a compound task in the network, chooses an applicable method, and replaces that task with the method's subtask network.
• Solution: A plan is found when the network contains only primitive tasks (operators) and all ordering constraints and preconditions are satisfied.

HTN planning is a decomposition-driven search process. The search space is defined by choices of which method to apply for each compound task.

• Forward Decomposition (Task Reduction): The standard algorithm. It starts with the initial task network and recursively reduces compound tasks until only primitives remain.
• Backward Decomposition: Searches from the goal task network, integrating it with the initial state.
• Search Control: Domain knowledge encoded in method preconditions prunes the search space dramatically compared to blind state-space search, making HTN planners highly efficient for complex, structured domains.

An HTN planning problem is formally defined by two parts:

• Domain Definition:

  • A set of operators (primitive tasks).
  • A set of methods for decomposing compound tasks.
  • Predicates describing properties of the world.

• Problem Instance:

  • An initial state (a set of ground facts that are true).
  • An initial task network, usually a single top-level compound task (the goal).

The separation of domain knowledge (methods/operators) from problem specifics (initial state/task) is key to HTN's reusability and power.

HTN planners are central to robotic task and motion planning (TAMP), where a high-level mission like "Assemble Product X" is decomposed into a network of subtasks (e.g., "Fetch Component A", "Insert Component B"). Each subtask is further refined into primitive actions for grippers and arms. This hierarchical approach is foundational in software-defined manufacturing and heterogeneous fleet orchestration, enabling robots to flexibly adapt procedures based on sensor feedback and available tools.

Military command and control systems use HTN planning for complex, multi-agent operations. A goal like "Secure Area Z" is decomposed into coordinated subtasks for different units (e.g., "Reconnaissance Team: Scout perimeter", "Assault Team: Establish position"). The planner integrates domain knowledge about unit capabilities, terrain, and rules of engagement. This application directly relates to contingent planning and multi-agent system orchestration, as plans must account for uncertainty and dynamic coordination.

HTN planning creates believable, goal-directed behavior for NPCs in video games and simulations. Instead of scripting every action, developers define high-level tasks (e.g., "Patrol the fortress") and methods for decomposing them (e.g., Walk to Waypoint A -> Inspect Suspicious Noise -> Return to Route). This allows NPCs to exhibit proactive behavior and recover from interruptions dynamically. The technique is more flexible than finite-state machines for complex narratives, bridging automated planning systems and embodied intelligence systems.

Enterprise agentic cognitive architectures use HTN planning to automate complex business processes. A goal like "Onboard New Client" is decomposed into subtasks for compliance checks, document generation, and system provisioning. Each subtask may be executed by different software agents or APIs. This application leverages HTN's strength in modeling procedural domain knowledge and is a core component of autonomous supply chain intelligence and clinical workflow automation, where processes are hierarchical and rule-based.

NASA and other space agencies use HTN-derived systems (like the Europa Planning System) to generate command sequences for spacecraft. A high-level science goal (e.g., "Map Ice Fractures on Moon Y") is decomposed into instrument calibrations, imaging sequences, and data downlinks. The planner ensures all temporal constraints and resource limits (power, memory) are satisfied. This is a premier example of temporal planning integrated with HTN, requiring robust plan validation before execution billions of miles from Earth.

Agentic threat modeling systems employ HTN planning for automated incident response. A goal like "Contain Network Breach" is decomposed using expert-defined methods into subtasks: Isolate infected segments -> Identify malware signature -> Deploy patch -> Restore services. The planner can dynamically select methods based on the attack type and available tools. This application highlights HTN's role in preemptive algorithmic cybersecurity, enabling rapid, structured autonomous response that would be too slow for human operators.

Automated planning is the computational process of generating a sequence of actions, known as a plan, that transforms an initial state of the world into a desired goal state. It is the overarching field that includes HTN planning as a specific methodology.

• Core Problem: Given a description of the initial state, available actions, and a goal condition, find a valid sequence of actions.
• Contrast with HTN: Classical planning searches over primitive actions, while HTN uses domain knowledge to decompose abstract tasks.
• Applications: Robotics, logistics, game AI, and business process automation.

PDDL is a standardized, first-order logic-based language used to formally define planning problems. It provides the syntax for specifying the actions, predicates, and objects within a domain, as well as the initial state and goal of a specific problem.

• Role in HTN: While classical PDDL defines primitive actions, extensions like PDDL3.0 or ANML are used to formally encode HTN methods and compound tasks.
• Components: A domain file (actions, predicates, types) and a problem file (objects, initial state, goal).
• Importance: Enables portability and benchmarking of planning systems across different research and industry applications.

STRIPS is the foundational formalism for representing planning problems, upon which PDDL and many modern planners are built. It defines states as sets of logical propositions and actions in terms of their preconditions, add effects, and delete effects.

• Action Representation: An action is defined by what must be true before it can execute (preconditions) and what it makes true (add) or false (delete) afterward.
• Relationship to HTN: HTN planning operates at a higher level of abstraction. The primitive actions at the leaves of an HTN decomposition are typically STRIPS-style actions.
• Legacy: Introduced the core computational model of state transition that underlies most automated planning.

Forward search is a fundamental planning algorithm that begins at the initial state and applies all applicable actions to generate successor states, searching forward through the state space until a goal state is reached.

• Process: Creates a tree or graph of possible future states. Algorithms like A* use a heuristic to guide this exploration.
• HTN Contrast: Standard HTN planning is primarily a form of backward search (task decomposition), but hybrid approaches may use forward search to evaluate the feasibility of partial decompositions.
• Challenge: The state space can grow exponentially with the number of propositions and actions, a problem known as combinatorial explosion.

Plan execution is the phase where a generated plan's sequence of actions is dispatched to actuators or simulators. Plan repair (or replanning) is the process of modifying a plan that has failed during execution due to unexpected state changes.

• Execution Monitoring: The system compares expected state changes to actual sensor feedback.
• Repair Strategies: Can range from re-invoking the planner from the current state to making local modifications to the existing plan.
• HTN Relevance: HTN's hierarchical structure can make repair more efficient, as the planner can re-decompose only the failed high-level task rather than the entire plan from scratch.

Temporal planning extends classical planning by dealing with actions that have explicit durations, allow concurrent execution, and have temporal constraints between events. Contingent planning generates conditional plans (e.g., trees) that specify different actions based on sensory observations made during execution.

• Beyond HTN: Basic HTN produces totally ordered sequences of primitive actions. Advanced HTN planners integrate temporal and contingent reasoning.
• Temporal HTN: Handles tasks with deadlines and durations.
• Contingent HTN: Creates decomposition methods that branch based on sensed conditions, crucial for robust operation in uncertain, real-world environments.