Decomposition Tree

The topmost node of the tree, representing the original high-level compound task or goal that initiates the planning process. This is the entry point for the HTN planner, which must recursively decompose this node until only primitive tasks (executable actions) remain at the leaves. For example, in a logistics domain, the root could be DeliverPackage(P1, CityA, CityB).

The fundamental building blocks of the tree's hierarchy.

• Compound Task Nodes: Represent abstract, non-executable objectives (e.g., NavigateTo(Destination)). They are internal nodes that must be decomposed by applying a method.
• Primitive Task Nodes: Represent directly executable actions or operators (e.g., TurnOn(Engine), CallAPI(endpoint)). These form the leaf nodes of the tree, constituting the executable plan.

The rules that define how a compound task is broken down. A method is applied at a compound node, replacing it with a network of child subtasks. Each method has:

• Preconditions: Logical conditions that must be true in the current world state for the method to be applicable.
• Subtasks: The ordered or partially-ordered set of child tasks (which can be compound or primitive) that achieve the parent task. A single compound task may have multiple applicable methods, leading to different possible decompositions and plan variations.

The edges and annotations that define the plan's logical and temporal structure.

• Ordering Constraints: Arrows or partial orders between sibling subtasks, specifying that one must be completed before another can begin (e.g., UnlockDoor() must precede OpenDoor()).
• Causal Links: Implicit or explicit annotations showing that the effect of one task satisfies the precondition of a later task, ensuring the plan is causally sound.

Snapshots of the predicted world state at various points in the tree. As the planner decomposes tasks forward from the initial state, it simulates the effects of primitive actions. These annotated states are used to evaluate the preconditions of subsequent methods and operators, ensuring the decomposition is feasible. This interleaving of planning with state progression is a hallmark of algorithms like SHOP (Simple Hierarchical Ordered Planner).

The ordered list of primitive task nodes, read from left to right according to the tree's ordering constraints. This sequence is the final, executable solution plan generated by the HTN planner. The validity of this plan is guaranteed by the decomposition process, which respects all preconditions, effects, and constraints defined in the domain description.

The planning formalism that generates a Decomposition Tree. An HTN is a structured representation where high-level compound tasks are recursively broken down into subtasks using decomposition methods until only primitive tasks (executable actions) remain. It is the core model used by autonomous agents for goal-directed reasoning and is fundamental to Automated Planning Systems.

The core algorithmic process that builds the Decomposition Tree. It is the recursive procedure where a planner takes a compound task and applies an applicable method to replace it with a network of subtasks. This process continues depth-first or breadth-first until the plan consists solely of primitive actions. It is the engine behind generating Skeletal Plans and final Solution Plans.

The two fundamental node types in a Decomposition Tree.

• Compound Task: An abstract, high-level objective (e.g., 'Ship Product') that cannot be executed directly. It must be decomposed via methods.
• Primitive Task: A directly executable action or operator (e.g., 'Print Shipping Label') with defined preconditions and effects. The leaves of the tree are always primitive tasks.

A schema or rule that defines one possible way to decompose a specific compound task. A method contains:

• Preconditions: Logical conditions that must be true for the method to be applicable.
• A subtask network: The set of (compound or primitive) tasks it decomposes into, along with ordering constraints between them. A single compound task often has multiple methods, creating branching points in the Decomposition Tree.

The Simple Hierarchical Ordered Planner, a seminal and widely implemented HTN planning algorithm. SHOP performs task decomposition in a forward-chaining, depth-first manner, interleaving planning with simulated state progression. It is known for its efficiency and is a practical reference implementation for engineers building Agentic Cognitive Architectures that require deterministic planning.

Key concepts in the iterative construction of a Decomposition Tree.

• Skeletal Plan: A partially specified plan containing abstract tasks. It represents an intermediate state of the tree before full decomposition.
• Plan Refinement: The iterative process of replacing abstract tasks in a skeletal plan with more concrete subtasks or primitive actions. This continues until the plan is fully executable, culminating in the complete Decomposition Tree and final action sequence.