Divide and Conquer in Multi-Agent Planning

Eithan Ephrati, Jeffrey S. RosenscheinAAAI 1994

Abstract

Multi-agent planning often suffers from state-space explosion, where centralized planners face exponential complexity. This paper introduces a "divide and conquer" approach that decomposes global goals into agent-specific subgoals. By treating locally generated sub-plans as heuristics for a global $A^*$ search, the system effectively merges conflicting plans into a near-optimal global solution. Experimental results in the Slotted Blocks World demonstrate significant reductions in computational complexity while maintaining plan quality.

Introduction: The Complexity of Multi-Agent Planning

In classical AI, planning is typically modeled as a search through a state space. For a single agent, the complexity is $O(b^d)$, where $b$ is the branching factor and $d$ is the solution depth. However, in multi-agent environments, this complexity explodes to $O(n \times b)^d$ because a centralized planner must account for every possible action of every agent at every time step.

While decomposing a large goal into smaller subgoals is intuitive, these subgoals are rarely independent. One agent's actions may interfere with another's, leading to the "merging problem": how to combine individual plans into a coherent global strategy without reverting to exhaustive exponential search.

Methodology

The proposed framework leverages parallelism and local knowledge through a four-stage process:

  1. Decomposition: The global objective is partitioned into $n$ subgoals.
  2. Parallel Local Planning: Agents independently generate sub-plans to achieve their assigned subgoals.
  3. Heuristic Merging via $A^*$: A global $A^*$ search finds the final plan using an evaluation function $f' = g + h'$. Here, $g$ represents the actual cost of actions taken, and $h'$ is a heuristic estimate provided by agents based on the cost to complete their remaining sub-plans.
  4. Least Commitment Planning: Agents communicate via "essential propositions" (required states) rather than rigid operator sequences, allowing flexibility during the merging process.

Evaluation: Slotted Blocks World

The approach was evaluated using the Slotted Blocks World domain, a benchmark where multiple agents move blocks to form specific structures.

Figure 1: Initial state (left) and goal state (right) for an arch-building task involving three agents and four blocks.

This domain highlights the challenges of subgoal interference—for instance, building a supporting column might block the path for an agent tasked with placing the lintel.

Key Insights

  • Sub-plans as Navigational Beacons: Rather than being static components, sub-plans serve as highly accurate "bottom-up" heuristics that prune the global search space more effectively than generic top-down heuristics.
  • Exploiting Positive Interactions: The $A^*$ merging process can identify "favor relations," where agents' plans overlap beneficially, potentially resulting in global plans that are more efficient than the sum of individual efforts.
  • Interleaved Planning and Execution: The system supports dynamic environments by allowing agents to plan a few steps ahead, execute, and then refine their plans based on the updated state.

Results and Discussion

The authors demonstrate that if sub-plans are sufficient, the merging algorithm is guaranteed to find an optimal multi-agent plan. The complexity of this merging process is $O(q \times d)$, where $q$ represents the degree of interaction between subgoals—a major improvement over centralized exponential search.

Figure 3: A five-step sequence showing the interleaved planning and execution process as agents coordinate to build the target structure.

In dynamic scenarios, the resulting plans are shown to be $\delta$-optimal, remaining within a bounded distance of the true optimum relative to the look-ahead horizon.

Limitations

Despite its efficiency, the method relies on an a priori decomposition of the global goal, a process not yet automated within this framework. Additionally, while $A^*$ typically requires admissible heuristics for optimality, overlapping sub-plans can occasionally lead to overestimation, requiring extended search times. Finally, the coordination overhead in high-latency communication environments remains a factor for future study.

Summary updated

BibTeX
@inproceedings{ephrati1994divide,
  author = {Eithan Ephrati and Jeffrey S. Rosenschein},
  title = {{Divide and Conquer in Multi-Agent Planning}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1994},
}
Figure