Hierarchical Task Network (HTN)

The foundational structure of an HTN is a tree where the root is the high-level goal. This is decomposed into non-primitive (compound) tasks and, eventually, into primitive tasks (atomic actions). This hierarchy explicitly encodes the "how-to" knowledge for achieving goals, unlike classical planners that search through a space of possible actions.

• Example: A DeliverPackage task decomposes into NavigateToLocation, PickUpPackage, and NavigateToDestination.

Methods are the procedural knowledge that defines how a non-primitive task can be accomplished. Each method specifies:

• Task Head: The non-primitive task it decomposes.
• Preconditions: Logical conditions that must be true for the method to be applicable.
• Subtasks: The ordered (or partially ordered) list of subtasks that achieve the head task.

The planner selects and applies methods recursively until only primitive tasks remain, forming a plan.

Operators represent the executable, atomic actions in the world. They are the leaves of the task hierarchy. Each operator has:

• Preconditions: World states that must hold for the action to be performed.
• Effects: Changes to the world state (add/delete lists) that result from executing the action.

In an HTN plan, the sequence of operators is the final, executable output. This is directly analogous to actions in STRIPS-style planning.

HTN planners maintain a current world state, typically a set of logical propositions or facts. This state is:

• Updated by the effects of executed primitive tasks (operators).
• Checked against the preconditions of methods and operators during decomposition.
• Used to guide the search for applicable methods. The state provides the grounding context that determines which decomposition paths are viable.

HTN planning is a search process through the space of possible decompositions. The planner:

1. Selects a non-primitive task from the current task network.
2. Chooses an applicable method to decompose it.
3. Commits to that decomposition, updating the task network and state. If a dead-end is reached (e.g., a precondition fails), the planner backtracks to try an alternative method. Search control can be guided by heuristics.

A Task Network is a partially ordered set of tasks (both primitive and non-primitive) that the planner is working on. It is the intermediate representation during planning.

• Initial TN: Contains the top-level goal task.
• Evolution: As methods are applied, the TN expands with new subtasks and ordering constraints.
• Final TN: Contains only primitive tasks in a valid order, which constitutes the complete plan. This structure elegantly handles concurrent and ordered task execution.

The foundational process of algorithmically breaking down a complex, high-level objective into a structured set of smaller, manageable sub-tasks. While HTNs provide a formal method for this, decomposition is a broader concept that can also be achieved through other means like goal regression or case-based reasoning. It is the critical first step before any allocation can occur.

• Key Input: A complex, often abstract, goal statement.
• Key Output: A hierarchy or graph of interdependent sub-tasks.
• Relation to HTN: HTN is a specific, plan-based approach to decomposition, using pre-defined methods to reduce tasks recursively.

A visual and computational model, typically a Directed Acyclic Graph (DAG), that represents the precedence relationships between sub-tasks resulting from decomposition. Nodes are tasks, and directed edges indicate that one task must be completed before another can begin.

• Purpose: Enforces correct execution order and identifies parallelizable workstreams.
• Construction: Often generated automatically during the HTN planning process as decomposition methods are applied.
• Use in Orchestration: Served as the blueprint for workflow engines to sequence agent activation and manage state transitions.

A fundamental, indivisible unit of work within a decomposed plan. It is a primitive action that cannot be broken down further by the planning system and is directly executable by a single agent or system component.

• HTN Context: The leaf nodes in an HTN hierarchy are atomic tasks. The planning process completes successfully when all abstract tasks have been decomposed into a sequence of atomic tasks.
• Characteristics: Has well-defined preconditions (must be true to start) and postconditions (effects after execution).
• Example: Call_API(endpoint='https://api.example.com/data'), ReadSensor(id='temp_01').

The core runtime software component responsible for executing a defined workflow or plan. It manages the lifecycle of tasks (from the dependency graph), enforces execution constraints, dispatches tasks to agents, and coordinates their interactions.

• Input: A validated plan, often represented as a task dependency graph.
• Function: Acts as the central nervous system, translating a static plan into dynamic, monitored execution.
• Relation to HTN: The HTN planner generates the plan; the orchestration engine is responsible for its reliable execution, handling failures, and managing state across distributed agents.

The process of mapping the requirements of a task (especially an atomic task) to the advertised skills, resources, and competencies of available agents within the system. This is the bridge between a decomposed plan and its physical execution.

• Mechanism: Often uses a task ontology and an agent registry. The orchestration engine queries for agents whose capability profile satisfies the task's preconditions and required interfaces.
• Outcome: Determines which agent(s) are eligible to execute a given task, informing the subsequent allocation decision.
• Example: A task requiring Python SDK v2.1+ and GPU access is matched to agents advertising those exact capabilities.

A mathematical formalism used to model complex allocation and scheduling decisions. In multi-agent systems, CSPs frame task assignment by defining:

• Variables: Each task that needs an assignee.
• Domains: The set of agents capable of performing each task (from capability matching).
• Constraints: Hard rules (e.g., agent A can only do one task at a time) and soft preferences (e.g., prefer the agent with lowest latency).

Solving the CSP finds a valid assignment that satisfies all hard constraints, often while optimizing for soft ones. It provides a rigorous foundation for many allocation algorithms.