Hierarchical Task Decomposition¶
Planning method — instantiates Recursive Problem Decomposition
Repeatedly expands a compound task into a smaller network of same-kind subtasks, stopping only when every open task is a primitive the executor can perform directly.
Hierarchical Task Decomposition is a method — a repeatable expansion process — for turning a goal that is too abstract to act on into a network of concrete, executable actions. It takes a compound task, applies a decomposition rule that replaces it with an ordered set of smaller subtasks of the same planning kind, and repeats until every remaining task is a primitive that some executor can carry out without further planning. Its defining discipline, and the thing that separates it from an ordinary indented to-do list, is the same-kind test: each expansion must produce subtasks that are themselves planning problems solvable by the same method, and it must certify that each subtask is a legitimate reduction of its parent, not a loosely associated activity. It is a downward-facing method: it produces the tree, but says nothing about how results travel back up.
Example¶
A warehouse-robotics team needs their picking robot to "fulfil an order." That is a compound task no motor can execute, so the planner expands it. fulfil-order decomposes into navigate-to-shelf, retrieve-item, and deliver-to-packing — same-kind subtasks, each still a planning problem. retrieve-item is itself compound, so it expands again into align-to-bin, grasp, and withdraw; align-to-bin expands into wheel and arm movements. Every expansion carries a boundary: grasp requires the gripper to be empty and the item's pose to be known, and it produces the item held. The recursion terminates when every open task is a primitive the controller can drive directly — a single joint command, a wheel velocity — and no compound tasks remain. The check that keeps it honest is applied at each step: is align-to-bin really a smaller instance of the same "position the effector" planning problem, or has the planner smuggled in an unrelated activity? Only when every expansion passes that test is the resulting network a valid decomposition rather than a wish list.
How it works¶
- Expand compound tasks by a decomposition rule. Each compound task has one or more methods that replace it with an ordered subtask network. Applying a method is the recursive step.
- Attach a boundary to every subtask. Each subtask declares its preconditions (what must hold before it starts), its effects (what it makes true), and the ordering constraints that link it to its siblings.
- Certify same-kind reduction. Before accepting an expansion, confirm the subtasks are genuine smaller planning problems of the parent's kind — not a change of subject. This is what makes the decomposition recursive rather than merely nested.
- Stop at primitives. The process halts when no compound task remains open — every leaf is directly executable. That halting test, not a size count, is the termination rule.
Tuning parameters¶
- Method library breadth — how many alternative decomposition methods each compound task offers. More methods make the planner flexible but enlarge the search and invite backtracking.
- Primitive granularity — how low "directly executable" is set. Coarse primitives keep trees shallow but push complexity into the executor; fine primitives make trees deep and precise.
- Ordering strictness — whether subtasks are totally ordered, partially ordered, or unordered. Looser ordering exposes parallelism and reuse but complicates constraint checking.
- Same-kind tolerance — how strictly the equivalence test is enforced. A strict test guarantees clean recursion but rejects pragmatic shortcuts; a loose test admits hybrids that may not decompose further.
- Expansion depth cap — a hard limit on how deep decomposition may go before the planner declares a task un-plannable, guarding against runaway expansion when no primitive path exists.
When it helps, and when it misleads¶
Its strength is that it bridges the gap between an unactionable goal and machine- or human-executable steps, and it makes the plan auditable: every action can be traced up through the compound tasks that justify it. Because subtasks carry explicit preconditions and effects, the method also catches ordering errors before execution. This is the logic behind hierarchical task network (HTN) planning, widely used in robotics and game AI.[1]
Its failure mode is false self-similarity: a subtask that looks like a smaller version of its parent but actually requires different assumptions or a different method. Treat the two as identical and the plan works locally but fails to generalize. The classic misuse is decomposing a compound task by how a person would describe it rather than by a method that truly reduces it — producing an indented outline with none of the reduction guarantees, so leaves never quite bottom out in primitives. The guarding discipline is to make the same-kind reduction an explicit, checked step at every expansion and to require that each leaf be a certified primitive, rejecting any "leaf" that still hides planning.
How it implements the components¶
recursive_step— applying a decomposition method to replace a compound task with a smaller same-kind subtask network.subproblem_boundary— each subtask's declared preconditions, effects, and ordering constraints, which let it be planned locally without hiding what it needs.termination_condition— the process halts when no compound task remains open, i.e. every leaf is a directly executable primitive.subproblem_equivalence_rule— the certified same-kind test that confirms each expansion yields genuine smaller instances of the parent planning problem.
As a downward method it does not specify how subtask results roll back up (result_propagation_path) or how solved leaves are integrated into a parent solution (recombination_rule) — that upward machinery belongs to Recursive Planning Tree and Recursive Design Breakdown.
Related¶
- Instantiates: Recursive Problem Decomposition — supplies the disciplined downward expansion that reduces a goal to executable primitives.
- Sibling mechanisms: Divide-and-Conquer Algorithm · Legal Issue Tree · Recursive Planning Tree · Recursive Delegation Protocol · Recursive Design Breakdown · Fault Tree Analysis
Editorial Notes¶
Form Classification¶
Form family: Analysis, Modeling & Optimization
Rationale: The planning method recursively models a compound task as a network of smaller subtasks until every leaf is directly executable.
Nearest alternative: Protocol, Workflow & Routine — The result can guide execution order, but the mechanism's operative work is analytical task decomposition rather than enactment of that workflow.
Review outcome: Adjudicated after independent review; high confidence.
Origin Attribution¶
Primary origin: Computer Science & Software Engineering
Origin pattern: Single lineage
Present-day reach: Multi-domain
Rationale: Hierarchical Task Network planning is a named AI-planning lineage that recursively expands compound tasks into primitive actions.
Related originating lineages:
- Operations Research — Work breakdown and hierarchical planning in operations and scheduling materially shaped real-world decomposition practice.
Review resolution: Both reviewers independently assign computer_science as the primary originating domain, so that shared primary is retained. Alternate domains are the union of reviewer-identified formative or independently originating lineages; later application settings alone are excluded. The evidence describes one principal historical lineage. It has established independent use across several domains, but that does not make it domain-free. The encyclopedia entry generalizes the established mechanism without creating a new composite lineage.
Review outcome: Reconciled after independent review; high confidence.
References¶
[1] Nau, D. S., Au, T.-C., Ilghami, O., et al. "SHOP2: An HTN Planning System". Journal of Artificial Intelligence Research 20, 379–404 (2003). Describes HTN planning as planning by decomposing compound tasks into executable subtasks. registry ↩