Message-Aware Graph Attention Networks for Large-Scale Multi-Robot Path Planning

Qingbiao Li, Weizhe Lin, Zhe Liu, Amanda Prorok

This paper, published by researchers at the University of Cambridge, introduces a novel approach to one of the most challenging problems in robotics: coordinating hundreds or thousands of robots in a shared space without a central "brain" telling them what to do.

TL;DR

The authors present MAGAT (Message-Aware Graph Attention neTwork), a decentralized path-planning framework that uses a key-query attention mechanism to help robots prioritize the most relevant information from their neighbors. By learning who to listen to, MAGAT achieves a 47% improvement in success rates over standard benchmarks and generalizes to swarms 100x larger than those it was trained on.

What Problem Does This Paper Address?

Multi-Robot Path Planning (MRPP) is essential for automated warehouses and urban mobility. Centralized solvers (like ECBS) can find near-optimal paths but become computationally "frozen" as the number of robots grows. Decentralized methods, where each robot makes its own decisions, are the scalable alternative.

However, decentralized robots usually rely on local communication. In a crowded environment, a robot might receive messages from dozens of neighbors. Standard Graph Neural Networks (GNNs) often aggregate these messages using simple averages or distance-based weights. This creates a "noise" problem: a robot might be distracted by a neighbor moving away from it while ignoring a critical neighbor on a collision course. The challenge is enabling robots to dynamically attend to the most task-relevant messages.

Methods

The core innovation is the Message-Aware Graph Attention neTwork (MAGAT). It builds on the authors' previous work with GNNs but adds several sophisticated layers:

  1. Key-Query Attention: Inspired by Transformers, MAGAT computes attention weights based on the actual content of the messages. A robot (the "query") compares its state against the features of a neighbor (the "key") to determine how much weight to give that neighbor's information.
  2. Permutation Equivariance & Time Invariance: The authors provide mathematical proofs that the model's output remains consistent regardless of the order in which robots are indexed or when the simulation starts—crucial properties for reliable robotics.
  3. Bottleneck Skip-Connections: To handle limited communication bandwidth, the authors tested reducing the size of shared features. They introduced a skip-connection that allows a robot to "remember" its own intent even when the incoming "social" information is heavily compressed.
  4. Imitation Learning with an Online Expert: The model is trained to mimic a centralized expert (ECBS). To improve robustness, they use an "online expert" strategy: if the decentralized model fails during training, the expert is called in to provide a correction, which is then added back into the training data.

Datasets

The researchers used synthetic 2D grid worlds with a 10% obstacle density.

  • Training Set: 30,000 cases featuring only 10 robots on 20x20 maps.
  • Testing/Generalization: The model was tested on much harder scenarios, including:
  • Increasing Density: Up to 100 robots on 50x50 maps.
  • Massive Scale: Up to 1,000 robots on 200x200 maps (a 100x increase in robot count from training).

Key Insights and Ideas

  • Content over Distance: Traditional GNNs often assume the closest neighbor is the most important. MAGAT proves that the content of the message (where the neighbor is going) is a better metric for attention than simple physical proximity.
  • Zero-Shot Scaling: The most striking insight is that a policy learned by watching 10 robots can effectively guide 1,000 robots. This suggests the model is learning fundamental "social rules" of navigation rather than just memorizing specific map layouts.
  • Multi-Head Benefits: Using multiple "attention heads" allows a robot to focus on different types of threats simultaneously—for example, one head might track robots coming from the left while another tracks those from the right.

Key Results

  • Performance: MAGAT-F-128 significantly outperformed vanilla GNNs and standard GAT (Graph Attention Network) baselines in success rate and "flowtime" (the total time robots take to reach goals).
  • Scalability: In the 1,000-robot scenario, the centralized expert (ECBS) took roughly 34,000 seconds to find a solution. MAGAT found a solution in just 1,286 seconds (roughly 1/30th of the time) while maintaining a high success rate.
  • Success Rate: In very large-scale instances, MAGAT achieved a 47% improvement over the baseline success rates. Even in cases where it didn't reach a 100% success rate, over 98.6% of the individual robots successfully reached their goals.

Limitations and Future Work

  • Discrete Space: The current work is limited to 2D grid worlds. Real-world robots operate in continuous space with complex dynamics (momentum, friction).
  • Static Obstacles: The maps used static obstacles. Future iterations would need to account for dynamic obstacles or moving humans.
  • Map Diversity: While the model scales well, it was primarily tested on random obstacle distributions. The authors plan to test on more structured environments like "maze" or "warehouse" layouts in the future.
  • Physical Deployment: The results are currently simulation-based; the next step is validating these attention mechanisms on real physical robot swarms.

Summary updated

Abstract

The domains of transport and logistics are increasingly relying on autonomous mobile robots for the handling and distribution of passengers or resources. At large system scales, finding decentralized path planning and coordination solutions is key to efficient system performance. Recently, Graph Neural Networks (GNNs) have become popular due to their ability to learn communication policies in decentralized multi-agent systems. Yet, vanilla GNNs rely on simplistic message aggregation mechanisms that prevent agents from prioritizing important information. To tackle this challenge, in this letter, we extend our previous work that utilizes GNNs in multi-agent path planning by incorporating a novel mechanism to allow for message-dependent attention. Our Message-Aware Graph Attention neTwork (MAGAT) is based on a key-query-like mechanism that determines the relative importance of features in the messages received from various neighboring robots. We show that MAGAT is able to achieve a performance close to that of a coupled centralized expert algorithm. Further, ablation studies and comparisons to several benchmark models show that our attention mechanism is very effective across different robot densities and performs stably in different constraints in communication bandwidth. Experiments demonstrate that our model is able to generalize well in previously unseen problem instances, and that it achieves a 47% improvement over the benchmark success rate, even in very large-scale instances that are ×100 larger than the training instances.
BibTeX
@article{li2021message,
  author = {Qingbiao Li and Weizhe Lin and Zhe Liu and Amanda Prorok},
  title = {{Message-Aware Graph Attention Networks for Large-Scale Multi-Robot Path Planning}},
  journal = {IEEE Robotics Autom. Lett.},
  year = {2021},
  doi = {10.1109/lra.2021.3077863},
}
Figure