MAMS-A*: Multi-Agent Multi-Scale A

Jaein Lim, Panagiotis Tsiotras

TL;DR

MAMS-A* is a distributed path-planning algorithm that allows multiple agents to find the shortest path in a shared environment using multi-resolution graphs. By communicating only the results of their local searches, agents dynamically refine their own maps with finer-grained data from others, ultimately finding a provably optimal path without the massive overhead of sharing entire high-resolution maps.

What Problem Does This Paper Address?

Path planning in large-scale environments presents a classic trade-off: high-resolution maps provide accuracy but are computationally expensive to search, while coarse maps are fast but can miss optimal (or even feasible) paths.

While multi-resolution techniques (like quad-trees) help by focusing detail only where it's needed, a single agent's "view" is often limited—it might have high detail near its start position but very coarse data near the goal. In multi-agent systems, the challenge is to combine the "best" information from every agent to find the global optimum. However, simply broadcasting entire high-resolution maps between agents creates a communication bottleneck that defeats the purpose of using efficient abstractions.

Methods

The authors introduce Multi-Agent Multi-Scale A (MAMS-A), which combines multi-resolution world representations with a distributed search logic.

  1. Multi-resolution Graph Construction: Each agent builds a graph where the resolution is high near the agent and becomes progressively coarser further away. This is modeled using a $2^d$-tree (a quad-tree in 2D).
  2. Distributed Forward Search: Agents run an A*-like search locally. When an agent expands a vertex, it broadcasts a message containing the vertex ID, its cost-to-come ($g$-value), and its heuristic estimate ($h$-value).
  3. Dynamic Refinement: When an agent receives a message, it checks if the incoming vertex is at a finer resolution than its own local representation. If it is, the agent "prunes" its coarse vertex and adopts the finer vertices into its local graph.
  4. Optimality and Completeness: The authors provide mathematical proofs showing that this distributed process will always find the optimal path available in the "merged graph" (the theoretical graph containing the finest resolution data known by any agent) and will terminate in a finite number of steps.

Datasets

The algorithm was evaluated using:

  • Custom 2D Labeled Maps: The environment was represented as a grid where each cell has a "risk level" (cost) between 0 and 1.
  • ROS Framework: The system was implemented using the Robot Operating System (ROS), where each agent functioned as a separate node communicating via standard ROS messaging.
  • Baseline: Results were compared against a "regular" A* algorithm running on a full-resolution, non-abstracted grid.

Key Insights and Ideas

  • "Need-to-Know" Communication: Agents don't 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 map size.
  • Resolution "Infection": As agents search, finer-grained information "infects" the network. If Agent A has a high-detail view of a narrow passage that Agent B sees as a solid wall, Agent B will eventually receive that detail and update its path accordingly.
  • Robustness to Abstraction: In single-agent multi-scale planning, the quality of the path is highly sensitive to the abstraction parameter ($\alpha$). The paper finds that adding more agents makes the system much less sensitive to these settings, as the collective "knowledge" compensates for individual coarse abstractions.

Key Results

  • Massive Speedup: MAMS-A found abstract paths up to three orders of magnitude (1000x) faster than standard A on a full-resolution grid.
  • Improved Quality with Scale: As the number of agents increased, the cost of the discovered path decreased, moving closer to the true resolution-optimal solution.
  • Communication Efficiency: The algorithm achieves global optimality in the merged graph without ever explicitly constructing or transmitting that full graph.

Limitations and Future Work

  • Resolution Completeness: While the path is optimal relative to the available merged graph, that graph is still an abstraction. The authors mention a backtracking scheme to ensure "resolution completeness" (finding a path in the absolute finest possible grid), but this adds complexity.
  • Broadcasting Overhead: The current model assumes every message reaches every agent. In very large swarms, this "all-to-all" communication could become a bottleneck. The authors suggest exploring sequential message-passing (Agent 1 $\to$ Agent 2 $\to$ Agent 3) to reduce this load, though it may slightly degrade path optimality.
  • Static Environments: The paper focuses on single-query planning in static environments. Extending this to dynamic environments where obstacles move would be a significant next step.

Summary updated

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.
BibTeX
@inproceedings{lim2020mams,
  author = {Jaein Lim and Panagiotis Tsiotras},
  title = {{MAMS-A*: Multi-Agent Multi-Scale A}},
  booktitle = {IEEE International Conference on Robotics and Automation},
  year = {2020},
  doi = {10.1109/icra40945.2020.9197045},
}

Loading related content...

Figure