Hierarchical Task Network (HTN) Planning

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 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.

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.