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:
- Decomposition: The global objective is partitioned into $n$ subgoals.
- Parallel Local Planning: Agents independently generate sub-plans to achieve their assigned subgoals.
- 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.
- 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.
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.
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