A Decomposition Tree is a directed, acyclic graph structure that results from the task decomposition process in HTN planning. It begins with a root compound task representing the overall goal. Each node is a task, and edges represent decomposition relationships, where parent tasks are recursively broken down into child subtasks via applicable methods until all leaf nodes are primitive tasks (executable actions). This tree explicitly captures the 'how' of achieving a goal, unlike a flat action sequence.
Reference
Decomposition Tree
A Decomposition Tree is a hierarchical, tree-like data structure that visually represents the recursive breakdown of a high-level, abstract task into its constituent subtasks and primitive actions during Hierarchical Task Network (HTN) planning.
HIERARCHICAL TASK NETWORKS
What is a Decomposition Tree?
A Decomposition Tree is the visual or structural output of Hierarchical Task Network (HTN) planning, representing the complete hierarchical breakdown of a high-level objective into executable actions.
The tree is constructed by a planner like SHOP, which selects decomposition methods based on preconditions in the current world state. It embodies the hierarchical plan, showing ordering constraints between sibling tasks. This structure is fundamental for agentic cognitive architectures, providing a transparent blueprint for complex, multi-step reasoning that can be monitored, debugged, and adapted through replanning if execution fails.
HIERARCHICAL TASK NETWORKS
Key Components of a Decomposition Tree
A Decomposition Tree is the visual artifact of Hierarchical Task Network (HTN) planning, representing the recursive breakdown of an abstract goal into executable actions. Its structure is defined by specific formal elements.
01
Root Node (Initial Task)
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).
02
Compound & Primitive Task Nodes
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.
03
Methods (Decomposition Rules)
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.
04
Ordering & Causal Links
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 precedeOpenDoor()). - 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.
05
State Annotations
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).
06
Leaf Sequence (Solution Plan)
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.
HIERARCHICAL TASK NETWORKS
How a Decomposition Tree is Built
A Decomposition Tree is constructed through the recursive application of decomposition methods to a high-level goal task, forming a hierarchical structure that maps abstract objectives to executable actions.
The construction begins with an initial task network, typically containing a single high-level compound task. The HTN planner selects an applicable decomposition method for this task, a rule that replaces it with a network of subtasks. This process repeats recursively for any new compound subtasks, expanding the tree downward. The recursion terminates when all leaf nodes are primitive tasks—directly executable actions with defined preconditions and effects—resulting in a complete, hierarchical plan.
The tree's structure is dictated by the planner's search strategy, such as the depth-first approach of the SHOP algorithm. At each step, the planner must verify that a method's preconditions are satisfied by the current world state. This interleaving of decomposition with state tracking ensures the final sequence of actions is logically sound. Ordering constraints between sibling subtasks are enforced during construction, defining the plan's temporal flow. The resulting tree is a visual and formal representation of the task decomposition process central to HTN planning.
DECOMPOSITION TREE
Frequently Asked Questions
A Decomposition Tree is the core data structure in Hierarchical Task Network (HTN) planning, visually mapping how a complex objective is broken down into executable steps. These questions address its mechanics, applications, and role in agentic systems.
A Decomposition Tree is a hierarchical, tree-like data structure that visually represents the recursive breakdown of a high-level, compound task into a network of smaller subtasks and, ultimately, into primitive tasks (executable actions) within a Hierarchical Task Network (HTN) planning system. Each node in the tree represents a task, with the root being the initial goal. Branches are created by applying decomposition methods, which are rules that define how an abstract task can be expanded given certain preconditions. The leaves of the tree form the executable solution plan.
For example, the high-level task "Prepare Business Report" might decompose into subtasks like "Gather Sales Data," "Analyze Trends," and "Write Summary." The "Gather Sales Data" subtask could further decompose into primitive actions like "QueryDatabase(SalesQ4)" and "ExportToCSV()." The tree makes the planning process transparent and auditable.