Initial Task Network

The ITN contains one or more compound tasks representing the high-level objectives to be achieved. These are abstract, non-executable tasks that serve as the root nodes for the decomposition process.

• Example: In a logistics domain, the goal task could be DeliverPackage(Package_A, Warehouse_B).
• The planner's job is to recursively decompose these goal tasks using available methods until only primitive tasks (executable actions) remain.

The ITN is not just a list of tasks; it is a partially ordered network. This structure defines ordering constraints (temporal precedences) and causal links between the initial goal tasks.

• Key Property: The network is initially sparse, containing only the high-level goal tasks and any known constraints between them.
• Purpose: This structure provides the skeleton that the planner will flesh out through decomposition, preserving necessary task orderings (e.g., SecureFunding must occur before InitiateConstruction).

An ITN is defined within the broader HTN Domain Description. It is a tuple, often notated as (T, <), where:

• T is a set of tasks (initially the goal tasks).
• < is a set of strict partial order constraints over T.
• This formal definition allows the planner to reason algorithmically about task decomposition and ordering.

A critical conceptual separation: the Initial Task Network specifies what needs to be done, while the Initial State describes the starting world conditions in which it must be done.

• Initial State: A set of grounded propositions (facts) true at the start (e.g., RobotIsAt(ChargingStation), BatteryLevel(High)).
• Interaction: The planner uses the initial state to evaluate the preconditions of methods and operators during decomposition. The ITN and initial state together fully define the planning problem.

The ITN is the input to the HTN planner. The planner's algorithm (e.g., SHOP) performs a recursive task decomposition:

1. Select a non-primitive (compound) task from the current task network.
2. Choose an applicable method whose preconditions hold in the current state.
3. Replace the compound task with the method's subtask network.
4. Repeat until the network contains only primitive tasks, resulting in a solution plan. The ITN is thus progressively refined into an executable sequence.

Consider an ITN for automating a deployment:

• Goal Tasks: {DeployMicroservice(AuthService), RunIntegrationTests}
• Ordering Constraint: DeployMicroservice(AuthService) < RunIntegrationTests

The planner must decompose DeployMicroservice using methods that might add subtasks like BuildContainerImage, PushToRegistry, UpdateK8sManifest, and RolloutDeployment. The ITN provides the target structure the planner must create.

A planning formalism that decomposes high-level, abstract tasks into networks of subtasks using decomposition methods until primitive, directly executable actions are reached. It is the overarching framework within which an Initial Task Network is defined and processed.

• Core Concept: Represents problems as hierarchies of tasks rather than flat state-space searches.
• Key Advantage: Encodes domain-specific knowledge about how to achieve goals, making planning more efficient for complex, structured domains like logistics, manufacturing, and autonomous agent behavior.

A high-level, abstract task in an HTN that cannot be executed directly. It must be decomposed into a network of subtasks (which can be other compound tasks or primitive tasks) using an applicable method. The Initial Task Network is typically composed of one or more compound tasks representing the top-level goals.

• Example: DeliverPackage(PackageA, CityB) is a compound task. It requires decomposition into subtasks like LoadTruck, DriveRoute, and UnloadPackage.

A task in an HTN that corresponds directly to an executable action or planning operator in the domain. It is a leaf node in the decomposition tree with defined preconditions and effects. The planning process is complete when the Initial Task Network has been fully decomposed into a sequence or network of primitive tasks.

• Contrast with Compound Task: A primitive task is an operator (e.g., PickUp(Object)), while a compound task is a goal (e.g., ClearTable()).
• Role in Planning: Forms the executable steps of the final solution plan.

A decomposition schema that defines a possible way to break down a specific compound task into a network of subtasks. A method is only applicable if its preconditions are satisfied by the current world state. The planner selects among applicable methods to decompose the tasks in the Initial Task Network.

• Structure: Method(Task, Preconditions, SubtaskNetwork).
• Example: A method for BrewCoffee() might have the subtask network [GrindBeans(), HeatWater(), PourWater(), Wait(5min)] with a precondition Has(CoffeeBeans) == true.

The core algorithmic process in HTN planning where a compound task is recursively replaced by a network of subtasks using an applicable method. This process begins with the Initial Task Network and continues depth-first or breadth-first until only primitive tasks remain.

• Mechanism: Transforms the abstract initial network into a concrete, executable plan.
• Output: Creates a decomposition tree that records the hierarchical breakdown, providing traceability from high-level goals to low-level actions.

A seminal, forward-chaining HTN planning algorithm that performs task decomposition in a depth-first manner, interleaving planning with state progression. It is particularly efficient because it commits to decompositions early, using the current world state to prune irrelevant options. SHOP takes a Domain Description, Initial State, and an Initial Task Network as input.

• Key Feature: Processes tasks in the order they will be executed, making it intuitive and fast for many practical domains.
• Influence: The basis for modern planners like SHOP2 and JSHOP.