A central agent divides the global task into subtasks, which are assigned in some way to the robotic agents, who each find solutions for their subgoals. When the sub-plans are complete, the central agent uses them as heuristics in building a complete, final plan, which the agents then execute. If the costs of splitting a global goal into subgoals and of merging subplans together into a global plan are small, however, we can do much better. The robotic agents solve their subplans in parallel, leading to a running time of , where i is the number of robotic agents. Each individual robotic agent derives a set of subplans that solve its goal.
Every action has a cost.
For each possible choice of the next action, each agent announces its estimate of the amount of time it would take to finish its subgoal. These estimates are summed, and the result used as the estimated aggregate cost of the next action. Despite the intuitive appeal of hierarchically organized cooperating systems, in practice they have several disadvantages. Reasoning about other agents is desirable, but difficult in the framework of multi-agent planning.