Can one task have several decompositions?

Yes. Alternative methods can apply under different conditions or offer different ways to achieve the task.

Does decomposition mean delegating to several agents?

Not necessarily. One planner can perform hierarchical decomposition without multiple agents or concurrent execution.

Are all hierarchical plans globally optimal?

No. A best plan among allowed refinements may be more expensive than a plan excluded by the hierarchy.

AI Glossary / Graphs and symbolic AI / Intermediate

Hierarchical decomposition

Definition

Hierarchical decomposition breaks a complex task into smaller tasks arranged across levels of detail. In AI planning, a high-level task is refined through permitted methods until the plan contains actions that the system can execute. The hierarchy supplies structure for finding a solution, but the decomposed parts must still fit together and satisfy their requirements.

What it means

A request such as prepare a shipment leaves many operational choices unspecified. A hierarchy can represent it through tasks such as prepare the item, package it, and arrange transfer. Some of those tasks can be decomposed further, and there may be several alternative methods for completing the same task.
This is more than splitting a paragraph into a checklist. A formal planning hierarchy defines when a method applies, what subtasks it introduces, and how those subtasks relate. The chosen methods restrict the candidate plans that the system considers. A useful hierarchy can reduce search, but an incomplete one can exclude a feasible or cheaper solution.

How it works

Begin with the current state and a task or task network. Select an applicable method for a nonprimitive task and replace it with the method's subtasks, preserving required ordering and constraints. Continue refining while checking that the resulting actions can be supported by the modeled state transitions.
When a decomposition fails, a planner may try another method rather than assuming the overall task is impossible. The process ends successfully when an executable primitive plan satisfies the relevant task requirements. Different hierarchical planning systems vary in ordering, expressiveness, and search control, so no single implementation detail should be treated as universal.

Three practical examples

A planning exercise decomposes a delivery task into preparation, transport, and confirmation steps with explicit prerequisites.
A workflow prototype offers separate methods for collecting an item locally or requesting a transfer from another location.
A robotics simulation refines a move-object task into navigation, grasping, transport, and placement actions, checking the requirements at each level.

Think of it this way

Think of planning a meal by first deciding on dishes and then expanding each dish into preparation steps. This reduces the need to consider every hand movement at the outset. The analogy is limited because formal decomposition needs explicit conditions and interactions; the headings in a recipe do not automatically prove that ingredients, equipment, timing, and subtasks are compatible.

Worked example

Define a toy top-level task DeliverBox. One method, Local, requires StockAtA and refines into PackAtA, MoveAtoB, and ConfirmAtB. Give these primitive actions costs 2, 5, and 1, for a total of 8. Another method, Transfer, requires StockAtC and refines into RequestTransfer, PackAtA, MoveAtoB, and ConfirmAtB, with costs 4, 2, 5, and 1, totaling 12.
If the initial state has StockAtA but not StockAtC, Local is applicable and Transfer is not. The planner still needs to check the primitive actions' preconditions and effects; method applicability alone is not the whole execution proof.
Now suppose the actual modeled action space also permits a direct courier action costing 6, but the hierarchy contains no method that uses it. A planner restricted to the two methods may return the cost-8 plan as the best permitted refinement. That can be hierarchically optimal while failing to be globally optimal over every available action sequence. The example separates useful search restriction from an unjustified claim that the hierarchy preserves every best solution.

Illustrative case study

In a fictional logistics lesson, Oak Plans initially supplies only a local-stock method for DeliverBox. When the stock moves to another site, the planner cannot find a permitted decomposition. A reviewer checks the methods before interpreting the failure as proof that delivery is impossible.
The class adds an appropriate transfer method and validates its action sequence against the initial state. The invented case illustrates maintaining planning knowledge when operating conditions change. It does not claim that adding methods always improves efficiency or that a larger hierarchy is automatically better.

Common misconceptions and mistakes

Decomposed subtasks are not necessarily independent. They can compete for resources, require a specific order, or change conditions needed elsewhere in the plan. Solving each subtask in isolation can therefore fail to solve the whole task.
Hierarchical decomposition also does not guarantee optimality, completeness over all possible plans, or reduced runtime in every domain. The method library and algorithm determine what is considered. Finally, a high-level task name is not an executable instruction by itself. It needs a meaningful refinement or another justified execution mechanism, plus conditions under which that refinement is valid.

Business use

The approach can make complex planning models easier to organize, explain, and reuse. A project can encode recurring procedures as methods while allowing alternatives for different situations. This gives reviewers a clearer account of why a plan contains particular groups of actions.
Document assumptions at each level, including resource use and ordering. Test methods against small cases and explicit failure conditions. When the system finds no plan, distinguish failure within the supplied hierarchy from impossibility in the broader world. If cost optimality matters, assess whether the hierarchy excludes actions or sequences that could produce a better result.

Check your understanding

Why can the cost-8 Local plan be hierarchically optimal even when a cost-6 courier action exists?

Answer: The hierarchy may not permit any refinement using the courier action. The best allowed plan is then not necessarily the best plan in the unrestricted action space.

Related terms

High-level action
hierarchical task network
refinement
planning method
primitive action
task network
hierarchical optimality
automated planning

Learn next

Draw the two delivery methods as a task hierarchy and annotate every applicability condition. Then add a shared resource between subtasks and check whether the original order still works. Compare the set of permitted refinements with the full action space before discussing optimality.

Action space

Sources

Sources: University of Maryland SHOP project, hierarchical task decomposition: https://www.cs.umd.edu/projects/shop/description.html Marthi, Russell, and Wolfe, Angelic Hierarchical Planning: https://aima.cs.berkeley.edu/~russell/papers/icaps08-hla.pdf

Previous: Hierarchical Data Model Next: Hierarchical hidden Markov model