Hierarchical Task Network (HTN) Planning

A Task is the fundamental unit of work in HTN planning, representing an activity to be performed. It is the node in the hierarchical network.

• Primitive Tasks: These are directly executable actions, equivalent to operators in classical planning (e.g., PickUp(BlockA), NavigateTo(Room2)).
• Compound (Abstract) Tasks: These are high-level goals that cannot be executed directly and must be decomposed into subtasks (e.g., BuildHouse, DiagnoseFault). The planner's job is to recursively decompose compound tasks into networks of primitive tasks.

A Method is a recipe for decomposing a compound task into a partially ordered network of subtasks. It defines a way to achieve a high-level goal.

• Preconditions: Logical conditions that must be true in the world state for the method to be applicable.
• Subtasks: The network of (compound or primitive) tasks that, if accomplished, will complete the parent compound task.
• Task Network: The set of subtasks with optional ordering constraints (e.g., SubtaskA before SubtaskB). A single compound task often has multiple methods, allowing the planner to choose the most appropriate decomposition for the current situation.

An Operator defines the preconditions and effects of a primitive task, detailing how it changes the world state. It is the atomic, executable step.

• Preconditions: Facts that must be true for the operator to be legally applied.
• Effects: Add and delete lists that specify how the operator modifies the state when executed (e.g., Add: Holding(BlockA), Delete: OnTable(BlockA)).
• Operators are grounded and instantiated from primitive tasks during planning. They provide the planner with a formal model of action semantics, enabling state progression and goal checking.

The Planning Domain is the declarative knowledge base that defines the universe of possible actions for the planner. It is the reusable library of tasks, methods, and operators for a specific problem class.

• Contains all operators (for primitive tasks) and methods (for compound tasks).
• Encodes the how-to knowledge for an application area (e.g., logistics, manufacturing, robotics).
• Separates domain knowledge from the specific planning problem, promoting reusability. A well-designed domain is critical for efficient and effective HTN planning.

A Planning Problem is a specific instance to be solved, defined within a given planning domain. It provides the initial state and top-level goal task.

• Initial State: A complete snapshot of the world before planning begins, expressed as a set of logical facts (e.g., At(Robot, Dock), Connected(Room1, Room2)).
• Initial Task Network: The high-level compound task(s) that constitute the planning goal (e.g., Deliver(Package123, Room5)).
• The planner's objective is to find a sequence of primitive operators, derived by decomposing the initial task network, that is executable from the initial state.

The Plan is the output of a successful HTN planning process: a totally ordered sequence of grounded primitive operators that is executable from the initial state and achieves the top-level task.

• It is derived by recursively applying methods to decompose compound tasks until only primitive tasks remain, then ordering those primitives while respecting all constraints.
• HTN plans are often more structured and hierarchical than classical plans, as they preserve the intent of the decomposition methods.
• Plan validity requires that all operator preconditions are met at execution time and that the final state satisfies the logical conditions implied by the successful decomposition of the initial task network.

In real-time strategy (RTS) and simulation games, HTN planners generate believable, goal-directed behavior for non-player characters (NPCs) and factions.

• Dynamic Strategy Formulation: A high-level task like 'Defeat Enemy Faction' is decomposed into methods for 'Build Economy', 'Scout Territory', and 'Launch Attack'. Each method further decomposes into unit production, resource gathering, and tactical squad commands.
• Reactivity: While plan generation is deliberative, the planner can be frequently re-invoked to handle game events (e.g., a key unit is destroyed), leading to dynamic re-planning.
• Industry Adoption: This approach is used in commercial game engines and AI middleware to create opponents that exhibit coherent, long-term strategic reasoning rather than scripted behaviors.

HTN planning automates complex workflow orchestration in smart factories and supply chains, translating production orders into machine-specific operations.

• Process Decomposition: An order for 'Assemble Product X' is decomposed via methods into sequences for 'Fabricate Component A', 'Paint Subassembly B', and 'Quality Test Final Product'.
• Resource and Constraint Management: Methods encode constraints on machine capabilities, tool availability, and temporal deadlines. The planner ensures the final sequence of primitive actions (e.g., CNC mill operation, robotic arm weld) is feasible.
• Integration Point: The plan's primitive actions become jobs for a Manufacturing Execution System (MES) or a Warehouse Management System (WMS), coordinating autonomous mobile robots, conveyor systems, and robotic arms.

Within a Multi-Agent System, an HTN planner often acts as a central or hierarchical coordinator, decomposing global missions and allocating subtasks to specialized agents.

• Hierarchical Delegation: A 'Monitor City District' task is decomposed into 'Patrol Area A', 'Analyze Traffic Feed B', and 'Report Anomalies'. These subtasks are assigned to drone, CCTV analysis, and reporting agents, respectively.
• Conflict Resolution: The hierarchical structure allows for constraint checking at each decomposition level, preventing resource conflicts (e.g., two agents assigned to the same physical space).
• Pattern Synergy: This use case frequently combines with coordination patterns like the Contract Net Protocol, where the HTN planner defines the tasks to be announced for bidding by contractor agents.

HTN planning provides a rigorous framework for automating complex, knowledge-intensive business processes that involve multiple decision points and exception handling.

• Procedure Automation: A process like 'Onboard New Enterprise Client' is decomposed into parallel and sequential subtasks for legal compliance (KYC check), IT provisioning (account creation), and finance setup (invoice scheduling).

• Exception Handling as Methods: Unusual conditions (e.g., 'Client Fails KYC') trigger alternative decomposition methods that branch the process to a manual review workflow, demonstrating the planner's ability to manage non-linear procedures.

• Advantage over Static Workflows: Unlike rigid BPMN workflows, HTN can dynamically select the most appropriate method sequence based on runtime context, leading to more flexible and intelligent automation.

The collaborative process where a group of agents formulates a sequence of actions to achieve shared or individual goals. Unlike HTN's top-down decomposition, MAP often involves negotiation and merging of distributed, potentially interdependent plans.

• Key Distinction: HTN is a specific method for planning, while MAP describes the broader problem of collaborative plan generation.
• Centralized vs. Decentralized: MAP can be centralized (a single planner for all agents) or decentralized (agents plan locally and coordinate).
• Interaction Handling: A major challenge is managing the interactions, conflicts, and synergies between agents' sub-plans.

A decentralized task allocation mechanism inspired by economic contracting. A manager agent announces a task, contractor agents submit bids, and the manager awards the contract to the most suitable bidder.

• Phases: 1) Task Announcement, 2) Bidding, 3) Awarding, 4) Execution & Reporting.
• Flexibility: Well-suited for dynamic environments where agent capabilities and workloads change.
• Contrast with HTN: HTN decomposes tasks procedurally using pre-defined methods. Contract Net allocates tasks declaratively via a market mechanism. They can be combined, using HTN to decompose a high-level task and Contract Net to allocate the resulting subtasks.

A coordination approach where agents exchange and merge their local plans to identify and resolve potential interactions, forming a non-centralized, partial view of the global plan.

• Process: Agents create local plans, communicate key elements (goals, actions, expected results), and then modify their plans to avoid conflict or enable cooperation.
• Partial View: No single agent has a complete global plan; coordination is achieved through incremental plan alignment.
• Relation to HTN: PGP operates at a higher level of coordination between agents that already have planning capabilities (which could be HTN-based). It focuses on the integration of multiple pre-existing plans.

A modular, hierarchical model for designing agent behaviors using a tree of nodes that control execution flow. Widely used in robotics and game AI for reactive and proactive coordination.

• Structure: Composed of control flow nodes (Sequence, Selector, Parallel) and execution nodes (Action, Condition).
• Reactivity: Can quickly re-evaluate and switch tasks based on changing environmental conditions.
• Comparison to HTN: Both are hierarchical. Behavior Trees are primarily for reactive behavior execution and selection, while HTN is for proactive task decomposition and plan generation. An HTN planner could generate a plan that is then executed by a Behavior Tree.

A framework for modeling problems where a set of agents must assign values to variables to optimize a global objective, subject to constraints, with decisions and computations distributed among the agents.

• Formalization: Defines variables, domains, constraints, and a global utility function to be maximized.
• Algorithms: Solved using distributed algorithms like ADOPT or DPOP.
• Orchestration Role: Excellent for coordinating agents where the primary challenge is satisfying interdependent constraints (e.g., sensor network scheduling, meeting planning). Contrasts with HTN, which is focused on the procedural decomposition of tasks into executable actions.

A software model for intelligent agents based on practical reasoning, where an agent's behavior is driven by its Beliefs (world model), Desires (goals), and Intentions (committed plans).

• Reasoning Loop: 1) Perceive (update Beliefs), 2) Deliberate (select Desires/Goals), 3) Plan (generate Intentions via a planner), 4) Act.
• HTN Integration: HTN planning is a natural fit for the "Plan" stage within a BDI agent. The agent uses its Beliefs and current Intentions (goals) to trigger HTN methods for plan generation.
• System Level: BDI provides the overall agent architecture; HTN provides one possible planning engine for it.