Hierarchical Task Network (HTN)

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.

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.