Compound Task

A compound task represents a goal or intention, not a concrete action. It serves as a placeholder that must be resolved through task decomposition. For example, the task DeliverPackage is compound; it cannot be performed until it is broken down into subtasks like NavigateToAddress, ConfirmRecipient, and HandOverPackage. This abstraction allows planners to reason at multiple levels of detail.

The meaning of a compound task is defined entirely by the methods associated with it. A method is a schema that provides one possible way to decompose the task into a network of smaller subtasks (which can be compound or primitive).

• A single compound task often has multiple methods, representing different strategies.
• The planner selects a method based on preconditions that must hold in the current world state.
• For instance, the compound task Travel(Paris, London) could have methods for ByTrain, ByPlane, or ByCar, each with different preconditions (e.g., hasTrainTicket, hasValidPassport).

Compound tasks create the hierarchy in HTNs. A high-level compound task decomposes into a network that may contain other compound tasks, forming a decomposition tree. This mirrors how humans solve complex problems: we break a large goal (OrganizeConference) into sub-goals (SecureVenue, ArrangeSpeakers, ManageRegistrations), which are further decomposed until we reach actionable steps (SendEmail, SignContract). This structure makes planning more efficient by constraining the search space.

The specific decomposition of a compound task is not fixed; it is dynamically determined by the planning context. This includes:

• Current World State: What facts are true right now?
• Available Resources: What tools, budget, or agents are available?
• Ordering Constraints: Do some subtasks need to precede others?

This allows an HTN planner to generate highly situational plans. The compound task RespondToIncident might decompose into CallFireDepartment if fire == true, or into ApplyFirstAid if injury == true.

Early in the planning process, a solution may consist largely of compound tasks—this is called a skeletal plan. It outlines the major phases or components of the solution without specifying all low-level details. For example, a skeletal plan for BuildHouse might be: [ObtainPermits, ConstructFoundation, ErectStructure, InstallUtilities, FinishInterior]. Each of these is a compound task requiring further plan refinement. This top-down approach is a key advantage of HTN over classical planning.

Understanding compound tasks requires contrasting them with primitive tasks (or operators).

A plan is complete only when all compound tasks have been decomposed away, leaving a sequence of primitive tasks.

A primitive task is the fundamental, executable unit in an HTN. Unlike a compound task, it cannot be decomposed further and corresponds directly to an action or operator that can be performed in the world. It is defined by its preconditions (what must be true to execute it) and its effects (how it changes the world state).

• Key Contrast: A compound task is abstract and requires decomposition; a primitive task is concrete and directly executable.
• Example: In a logistics agent, 'NavigateTo(Location_A)' is a primitive task, while 'DeliverPackage(Package_1)' is a compound task that decomposes into navigation and hand-off primitives.

A method is the rule or schema that defines how a specific compound task can be decomposed into a network of subtasks. Each method is applicable only when its preconditions are satisfied by the current world state.

• Mechanism: Methods provide the 'recipes' for decomposition. A single compound task may have multiple methods, allowing the planner to choose the most appropriate decomposition based on context.
• Structure: A method typically specifies:
  • The compound task it decomposes.
  • A set of preconditions.
  • A subtask network (a partially ordered set of new tasks, which can be compound or primitive).

Task decomposition is the core algorithmic process in HTN planning. It is the recursive procedure of replacing a non-primitive (compound) task with a network of subtasks by applying an applicable method. This process continues until the entire initial task network is reduced to a sequence of executable primitive tasks.

• Process Flow: The planner starts with a high-level goal (a compound task), selects a method whose preconditions hold, and replaces the goal with the method's subtask network. This repeats for any new compound tasks in the network.
• Outcome: Successful decomposition produces a hierarchical plan that can be flattened into a linear sequence of actions for execution.

A Hierarchical Task Network is the overarching planning formalism and data structure. It represents a complex goal as a network of tasks connected by decomposition links and ordering constraints. The HTN itself consists of:

• A library of task schemas (for both compound and primitive tasks).
• A set of methods for decomposing compound tasks.
• A set of operators defining primitive actions.
• Purpose: HTNs provide a structured, knowledge-intensive approach to planning, making them highly effective for domains with well-understood procedures, such as manufacturing, logistics, and automated business workflows.

A skeletal plan is a partially specified, abstract plan generated during the intermediate stages of HTN planning. It contains a mix of compound tasks (awaiting further decomposition) and primitive tasks. It represents a high-level strategy before all details are resolved.

• Role in Planning: Skeletal plans are refined through successive task decomposition steps. They allow the planner to commit to a high-level approach (e.g., 'assemble product before packaging it') before finalizing low-level details (e.g., 'pick up screw S with robotic arm R').
• Utility: They enable least-commitment planning, where decisions are deferred until necessary, and facilitate replanning by allowing modifications at an abstract level.

SHOP is a seminal, forward-search HTN planning algorithm. It is notable for interleaving planning with state progression, making it highly efficient. SHOP performs task decomposition in a depth-first, ordered manner, simulating the execution of primitive actions as it plans to accurately track the evolving world state.

• Key Innovation: By progressing the state forward, SHOP can evaluate the preconditions of methods and operators directly against the current simulated state, avoiding the complexity of maintaining a full state history.
• Legacy: SHOP and its successors (SHOP2) established HTN planning as a practical technology for real-world applications, influencing modern agentic cognitive architectures and automated planning systems.