Abstract
We present a multi-scale forward search algorithm for distributed agents to solve single-query shortest path planning problems. Each agent first builds a representation of its own search space of the common environment as a multi-resolution graph, it communicates with the other agents the result of its local search, and it uses received information from other agents to refine its own graph and update the local inconsistency conditions. As a result, all agents attain a common subgraph that includes a provably optimal path in the most informative graph available among all agents, if one exists, without necessarily communicating the entire graph. We prove the completeness and optimality of the proposed algorithm, and present numerical results supporting the advantages of the proposed approach.
Introduction
Path planning in large-scale environments presents a fundamental trade-off: high-resolution maps offer the precision necessary for feasibility but are computationally expensive to search, while coarse maps enable rapid computation at the risk of missing optimal or even traversable paths. Multi-resolution techniques, such as quad-trees, mitigate this by focusing detail where it is most needed. However, a single agent's perspective is often spatially biased—possessing high detail near its origin but coarse data near distant goals.
The challenge in multi-agent systems is to synthesize the "best" information from every participant to find a global optimum without incurring the massive communication overhead of broadcasting entire high-resolution maps. This paper introduces Multi-Agent Multi-Scale A (MAMS-A), a distributed algorithm that achieves this synthesis through targeted information sharing.
The MAMS-A* Algorithm
MAMS-A* combines multi-resolution world representations with a distributed search logic. The process follows four key stages:
- Multi-resolution Graph Construction: Each agent constructs a $2^d$-tree (e.g., a quad-tree in 2D) where resolution is highest near the agent's starting position and becomes progressively coarser with distance.
- Distributed Forward Search: Agents perform local A* searches. Upon expanding a vertex, an agent broadcasts a message containing the vertex ID, its cost-to-come ($g$-value), and its heuristic estimate ($h$-value).
- Dynamic Refinement: When an agent receives a message, it compares the incoming vertex resolution to its local map. If the received data is finer, the agent "prunes" its coarse representation and integrates the finer vertices into its local graph.
- Optimality and Completeness: The algorithm is mathematically proven to find the optimal path available in the "merged graph"—the theoretical union of the finest data known by any agent—and is guaranteed to terminate in finite steps.
Key Insights: "Resolution Infection"
A core innovation of MAMS-A* is its "need-to-know" communication model. Agents do not share their entire maps; they only share information about the vertices they actually explore. This keeps communication costs proportional to the search effort rather than the total map size.
As agents search, finer-grained information "infects" the network. For instance, if Agent A identifies a narrow passage that Agent B perceives as a solid wall due to coarse abstraction, Agent B will eventually receive that detail and update its path accordingly. This makes the system robust to initial abstraction settings, as the collective knowledge of the swarm compensates for individual coarse views.
Experimental Evaluation
The algorithm was evaluated using custom 2D labeled maps with varying risk levels (costs) and implemented within the Robot Operating System (ROS) framework.
Key Results
- Efficiency: MAMS-A discovered paths up to three orders of magnitude (1000x) faster than standard A running on a full-resolution, non-abstracted grid.
- Scalability: As the number of agents increased, the cost of the discovered path decreased, converging toward the true resolution-optimal solution.
- Communication Savings: Global optimality in the merged graph was achieved without ever explicitly constructing or transmitting the full high-resolution map.
Conclusion and Future Work
MAMS-A* provides a scalable solution for distributed path planning in complex environments. While highly effective, the authors note that the current model assumes all-to-all communication, which may become a bottleneck in very large swarms. Future work will explore sequential message-passing to reduce load and extending the algorithm to dynamic environments where obstacles move in real-time.
Summary updated