Source-linked AI summary
Message-Aware Graph Attention Networks for Large-Scale Multi-Robot Path Planning
Qingbiao Li, Weizhe Lin, Zhe Liu, Amanda Prorok
TL;DR
Large-scale decentralized multi-robot path planning must coordinate robots despite costly centralized computation and redundant or bandwidth-limited communication. The paper introduces MAGAT, which uses key-query-like attention to selectively aggregate neighboring messages, and reports strong generalization, including a 47% benchmark success-rate improvement on instances ×100 larger than training cases.
Problem
Centralized planning consumes substantial computation at scale, while vanilla decentralized GNNs and constrained communication limit effective prioritization of inter-robot information.
Method
MAGAT extends a decentralized GNN framework with key-query-like, message-dependent attention that selectively aggregates neighboring features.
Results
47% improvement over the benchmark success rate is achieved on a 200×200 map with 1000 robots, with test instances ×100 larger than training instances.
Takeaways & Limitations
MAGAT demonstrates generalization to unseen settings and strong scalability while training only on simple cases, including stable performance under reduced communication bandwidth.
Abstract
from arXiv · showhide
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 paper, 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 $\times$100 larger than the training instances.
I. INTRODUCTION
Multi-robot path planning requires collision-free coordination at scale, but centralized computation and decentralized communication constraints make efficient planning difficult. MAGAT addresses these challenges with attention-based message selection and demonstrates generalization to much larger instances.
- Multi-robot path planning generates collision-free paths from robot start positions to designated goals, supporting warehouse retrieval and mobility-on-demand services.
- Centralized approaches require global information gathering and substantial computation, motivating decentralized methods as robot systems scale.
- Concurrent, equivalent communication among many neighbors can be redundant, while limited bandwidth, data volume, and interference undermine reliable coordination.
- MAGAT combines a GNN with key-query-like attention to improve the effectiveness of inter-robot communication.
- A skip-connected bottleneck reduces shared-feature size while preserving self-information and maintaining model performance under reduced communication bandwidth.
III. PROBLEM FORMULATION
The paper formulates multi-agent path planning as decentralized sequential decision-making on a dynamic, distance-based communication graph. Graph operations aggregate local observations through repeated neighbor exchanges and convolutional layers to predict robot actions.
- III. PROBLEM FORMULATION: Each robot takes actions toward its goal at every time instant while following a collision-free path in a 2D grid world with static obstacles.
- III. PROBLEM FORMULATION: Robots lack global positioning and perceive local maps within rectangular fields of view; goals outside view are represented only by their direction.
- III. PROBLEM FORMULATION: Communication is restricted to adjacent robots and is modeled by a dynamic distance-based graph whose edges connect robots within a fixed communication radius.
- III. PROBLEM FORMULATION: The adjacency matrix encodes graph connectivity, while edge weights can additionally represent the relative importance of neighboring messages.
- IV. PRELIMINARIES: Graph shift operations compute each node’s feature from neighboring node features, using the adjacency matrix as the graph shift operator.
- IV. PRELIMINARIES: Graph convolution combines shifted graph signals with trainable filter matrices, with k communication exchanges providing k-hop neighborhood information.
- IV. PRELIMINARIES: A GNN stacks graph-convolution layers and pointwise nonlinearities to produce fused information from robot observations.
- IV. PRELIMINARIES: The final fused representation is used to predict each robot’s action at time t.
V. MESSAGE-AWARE GRAPH ATTENTION NETWORK
MAGAT extends graph convolution with message-dependent attention, allowing robots to selectively weight neighboring features. Its multi-head design and raw-feature attention distinguish it from the original GAT baseline.
- MAGAT assigns edge weights from relative node-feature importance, enabling each robot to selectively aggregate messages from neighboring robots.
- The attention matrix has the same dimensions as the communication matrix and is combined with it through element-wise multiplication.
- Attention scores are computed for each neighboring node using a key-query-like mechanism and normalized by softmax into [0, 1].
- MAGAT can concatenate outputs from multiple independent attention heads after applying a pointwise nonlinearity.
- The original GAT is evaluated as a baseline by replacing MAGAT’s core attention mechanism while leaving the rest of the framework unchanged.
- MAGAT computes attention from raw CNN-extracted features, freeing the aggregation matrix from simultaneously serving attention and feature-transformation roles.
A. Properties of MAGAT
The paper notes that changing communication topology motivates evaluating MAGAT under graph changes, but the supplied passage does not report the property’s result.
- Changing robot proximity can cause other robots to enter or leave communication range, frequently altering the communication graph topology.
- The paper therefore raises whether MAGAT performs graph convolutions consistently across agent permutations and time shifts.
1) Permutation Equivariance:
MAGAT is designed to remain consistent when robot indices are reordered, preserving the correspondence between graph features, attention weights, and convolution results.
- Permutation Equivariance: A permutation swaps robot indices and reorders their features through a corresponding permutation matrix.
- Permutation Equivariance: Permutation equivariance ensures MAGAT produces the same convolution results regardless of robot ordering.
- Permutation Equivariance: MAGAT attention weights depend on node features, so swapping robots correspondingly permutes the attention matrix and graph features.
- Permutation Equivariance: The equivariance proof treats the element-wise product of attention and communication features as the input to the GNN convolution.
2) Time Invariance:
MAGAT is intended to produce consistent outputs when the same situation occurs at different simulation times, provided its inputs and communication network are unchanged.
- Time Invariance: The same situation can therefore generate consistent actions across different simulation steps when its input tensor and communication network match.
- Time Invariance: Time invariance requires identical MAGAT outputs when Xt1 = Xt2 and St1 = St2 at different time steps.
- Time Invariance: The criterion is supported by imitation training that predicts expert actions from the current observation and communication network rather than the time instant.
VI. ARCHITECTURE
The architecture combines local visual perception, graph-based communication, and action decoding in a decentralized robot policy, with MAGAT selectively weighting neighbor messages.
- Dataset Creation: Training cases use grid worlds with random static obstacles, unique starts and goals, and solutions generated by the centralized ECBS expert.
- Observation Processing: Each robot converts its limited-FOV observation into a three-channel tensor representing static obstacles, robots, and goals.
- Observation Processing: When a goal lies outside the FOV, the goal channel marks the boundary direction so the robot retains only target-direction awareness.
- CNN-based Perception: A feature extractor uses three stacked residual blocks with skip connections, which the paper associates with reduced overfitting and improved performance.
- Graph-based Communication and Action Policy: Robots exchange compressed observation features with neighbors within communication radius rCOMM, then decode fused features into five motion primitives.
- Graph-based Communication: With L = 1 and K = 2, each robot communicates once and uses MAGAT to focus on relatively important information from neighboring messages.
D. Training and Online Expert
The model is trained by imitation on expert action data, with online expert augmentation adding new solutions for failed training cases.
- Training: The training set pairs processed observations with expert actions from centralized-controller trajectories.
- Training: Training uses instant observation-action pairs rather than time-sequence information, requiring reactions based on the situation at each step.
- Online Expert: After validation, the Online Expert samples nOE training cases and uses ECBS to generate replacement solutions for failed simulations.
- Online Expert: The new cases are appended to the training set, which is gradually augmented while the classifier is optimized with loss function L.
- Training: The communication network status Gt depends on the current situation and is incorporated into the training formulation.
VII. EXPERIMENTS
The experiments evaluate success rate and flowtime increase across generalization scenarios, robot densities, bandwidth settings, and large-scale maps. Models are trained on 20×20 maps with 10 robots and tested on broader scenarios, including instances with over 500 robots.
- Metrics: Success rate measures the proportion of tested cases where all robots reach their goals within the maximum allowed steps.The maximum makespan is normally set to 3TMP*, where TMP* is the expert solution’s makespan.
- Metrics: Flowtime increase measures the difference between predicted and expert total path lengths, penalizing robots that fail to reach their goals.A failed robot’s predicted path length is set to Tmax.
- Experimental setup: Training uses 20×20 maps with 10 robots, while other scenarios provide 1000 testing cases for generalization evaluation.The training scenario contains 30000 cases partitioned into training, validation, and test sets.
- Training: Experiments use Adam optimization with cosine-annealed learning rates from 10^-3 to 10^-6 over 300 epochs.Validation and online-expert updates occur every 4 epochs.
- Scenarios: Robot density is computed from robot count and map area, and the evaluation varies from matching training density to increasingly crowded environments.The Increasing Robot Density Set keeps map size fixed while increasing robot number; obstacle density is 10%.
- Large-scale evaluation: The large-scale test set contains over 500 robots on very large maps, with 50 test cases in each large-scale scenario.
D. Baselines
The study compares upgraded GNN and MAGAT models with earlier learning-based baselines and non-learning methods under varying map sizes, robot densities, and communication bandwidths. MAGAT generally maintains stronger success and flowtime performance, while reduced shared features degrade performance.
- Comparison with baselines: GNN-F-128 and MAGAT-F-128 both outperform their corresponding baseline models.The comparisons are against GNN_baseline-F-128 and GAT-F-128, respectively.
- Comparison with baselines: MAGAT-F-128 significantly outperforms GAT-F-128 in success rate and flowtime increase under both map sets.GAT-F-128 performs only close to MAGAT-F-16.
- Comparison with baselines: HCA performs well on simple cases but drops sharply from 40 robots and cannot find a solution for 100 robots.
- Effect of reducing the information shared among robots: 91%, 85%, 81%, and 78% are the MAGAT success rates at 65×65 with 100 robots for shared-feature sizes 128, 64, 32, and 16.Performance decreases for both GNN and MAGAT as shared-feature size is reduced, but MAGAT’s drop is less pronounced.
- Generalization under different robot densities: Most MAGAT models maintain success rates above 92% and flowtime increases below 10% as robot count rises from 10 to 60 on 50×50 maps.This result is reported for the Increasing Robot Density Set.
4) Effect of bottleneck architecture:
The bottleneck architecture preserves MAGAT’s generalization under reduced shared-feature bandwidth, while multi-head variants further improve performance across tested densities and map sizes. These design choices support strong large-scale performance despite training only on small instances.
- Bottleneck architecture: Around 8% higher success rate: GNN-B-64 outperforms GNN-F-64 on 65 × 65 maps with 100 robots.The bottleneck models share the same feature size as their corresponding full models.
- Bottleneck architecture: The bottleneck retains MAGAT-F-128’s performance when reducing success rate from 90% with 128 features to around 78% with 16 features.This result is reported for 65 × 65 maps with 100 robots.
- Multi-head attention: 95% success rate: both multi-head MAGAT models achieve this on 50 × 50 maps with 100 robots.Their flowtime increase remains below 0.065 under the Same Robot Density Set as robot numbers increase.
- Large-scale generalization: MAGAT-B-32-P4 exceeds 80% success rate on 200 × 200 maps with 1000 robots while using 1/30 of centralized expert computation time.The model was trained on 20 × 20 maps with 10 robots.
- Summary: A 47% improvement over benchmark success rate is achieved on 200 × 200 maps with 1000 robots, which are ×100 larger than training instances.The conclusion attributes this result to the trained MAGAT model’s generalization performance.
- Summary: MAGAT uses selective message-feature aggregation and demonstrates generalizability on unseen environments through decentralized graph attention.The conclusion describes both theoretical and empirical support for handling dynamic communication graphs.