Source-linked AI summary
Graph Neural Networks for Decentralized Multi-Robot Path Planning
Qingbiao Li, Fernando Gama, Alejandro Ribeiro, Amanda Prorok
TL;DR
Decentralized multi-robot path planning must coordinate robots with restricted observations and communication, yet the crucial information-sharing policy is unclear. The paper combines CNN feature extraction with GNN communication, trains the model by imitation, and deploys it using local information. Results are close to optimal-planner performance and generalize to previously unseen larger teams and environments.
Problem
Decentralized path planning requires effective information sharing despite robots having restricted observations and communication, while the crucial shared information and timing are not obvious.
Method
A CNN extracts features from local observations and a GNN communicates them among robots; the combined model is trained to imitate a centralized coupled expert for decentralized deployment.
Results
The model performs close to first-principles-based methods and generalizes to previously unseen cases involving much larger robot teams.
Takeaways & Limitations
The decentralized approach remains computationally feasible at team sizes that are intractable for coupled centralized solvers.
Takeaways & Limitations
The implementation assumes instantaneous communication, and inter-robot livelocks and position swaps remain challenges preventing 100% success.
Abstract
from arXiv · showhide
Effective communication is key to successful, decentralized, multi-robot path planning. Yet, it is far from obvious what information is crucial to the task at hand, and how and when it must be shared among robots. To side-step these issues and move beyond hand-crafted heuristics, we propose a combined model that automatically synthesizes local communication and decision-making policies for robots navigating in constrained workspaces. Our architecture is composed of a convolutional neural network (CNN) that extracts adequate features from local observations, and a graph neural network (GNN) that communicates these features among robots. We train the model to imitate an expert algorithm, and use the resulting model online in decentralized planning involving only local communication and local observations. We evaluate our method in simulations {by navigating teams of robots to their destinations in 2D} cluttered workspaces. We measure the success rates and sum of costs over the planned paths. The results show a performance close to that of our expert algorithm, demonstrating the validity of our approach. In particular, we show our model's capability to generalize to previously unseen cases (involving larger environments and larger robot teams).
1 INTRODUCTION
Multi-robot path planning seeks collision-free routes to destinations, but decentralized settings restrict robots to partial observations and communication. The paper proposes combining CNN-based local feature extraction with decentralized GNN communication to learn efficient path-planning policies.
- Multi-robot path planning generates collision-free paths from robots’ origins to designated destinations.
- Coupled approaches can ensure optimal and complete solutions but rely on centralized components and scale poorly with robot count.
- The proposed architecture uses a CNN to extract features from local observations and a GNN to communicate those features among robots.
- The model is trained to imitate an optimal coupled planner with global information available offline during training.
2 RELATED WORK AND CONTRIBUTION
Existing decentralized planners reduce centralized dependence but may not explicitly optimize global path efficiency, while learned communication remains insufficiently addressed. The paper introduces a localized CNN-GNN framework that learns relevant information sharing and approaches optimal-planner performance while generalizing to larger teams and environments.
- Related work: Decentralized approaches reduce computational overhead and dependence on centralized planning units by coordinating through immediate neighbors or no communication.
- Related work: Purely local objectives cannot explicitly optimize global objectives such as path efficiency.
- Related work: Learning-based methods handle high-dimensional joint state spaces by shifting online computational burden to offline learning.
- Contribution: GNNs model robots as graph nodes with communication links as edges, addressing the importance of information sharing for decentralized coordination.
- Contribution: The framework jointly trains a CNN and GNN to learn what information robots should share using only local relative positions and goals.
- Contribution: The model imitates a centralized coupled planner and uses online-expert dataset aggregation, achieving performance close to optimal planners while generalizing to larger teams and environments.
3 PROBLEM FORMULATION
The problem is formulated as decentralized sequential decision-making under local visual observations and a time-varying communication graph. A learned mapping selects actions that advance all robots toward destinations efficiently while avoiding collisions and communicating only through nearby robots.
- Observations: Each robot observes a local field of vision containing its surroundings and clipped target information, without global positioning.
- Communication network: The communication network is represented at time t by a graph G_t whose nodes are robots and whose edges specify permitted communication links.
- Communication network: Edge weights can represent communication strength or binary link presence, with communication possible when robots are within radius r_COMM.
- Decision problem: The task learns a mapping F from local maps and communication network G_t to each robot’s action u_t.
- Objective: Actions should move robots toward destinations in the shortest possible time while avoiding collisions with robots and obstacles.
- Objective: The learned mapping is restricted to communication among nearby robots as dictated by G_t, while matching a coupled centralized expert under partial observations.
4 GRAPH NEURAL NETWORKS
The framework uses a GNN to restrict robot communication to nearby agents while learning actions from locally observed features. Graph convolutions aggregate information over multi-hop neighborhoods through distributed, weight-shared operations.
- A GNN parametrizes the mapping from observations to actions so communication remains restricted to nearby robots.
- Graph signals and shifts: Each robot’s F observations form a graph signal, while the adjacency-based graph shift operator represents communication among neighboring robots.The shift operator combines neighboring node values according to the communication graph.
- Graph convolutions: Graph convolution combines shifted node signals with learnable F × G filter matrices to produce G observations per node.The filter bank combines observations within and across nodes under graph sparsity constraints.
- Graph convolutions: A k-hop shifted signal summarizes information from nodes reachable through k communication exchanges with 1-hop neighbors.
- Graph neural networks: A convolutional GNN cascades graph-convolution and nonlinear layers, transforming CNN observations into per-robot actions.The first layer receives Xt, and the final layer outputs Ut at the current time step.
- Graph neural networks: Because communication exchanges accumulate across layers and filter taps, the architecture should remain shallow with short filters.The total communication count is the sum over layers of Kℓ−1 exchanges.
5 ARCHITECTURE
The architecture processes each robot’s local map with a CNN, exchanges compressed features through a localized GNN, and predicts discrete navigation actions with a shared policy network.
- 5.1 Processing Observations: Each robot observes a limited local field of view containing static obstacles, its goal information, and nearby agents without global localization.The field of view is bounded by radius rFOV, and the robot is centered in its local observation.
- 5.1 Processing Observations: A CNN runs on each robot to convert its local input map into higher-level feature vectors describing observations, goals, and other robots.
- 5.2 Communication: The CNN-derived feature vector is transmitted to neighboring robots over a multi-hop communication network limited by K hops.
- 5.2 Communication: The communication GNN fuses each robot’s features with those of its K-hop neighbors, producing a hyper-representation for action prediction.
- 5.2 Communication: Each robot carries a local copy of the GNN, yielding a localized decision-making policy.
- 5.3 Action Policy: The action policy applies a shared MLP to aggregated GNN features and predicts one of five discrete motion primitives.The options are up, left, down, right, and idle, represented as one-hot vectors.
5.5 Learning from Expert Data
The models learn decentralized action policies from expert trajectories, combining local map processing with graph-based communication. The resulting parametrization remains independent of the number of robots and can be deployed with local communication, though training requires expert solutions.
- Expert-data training: Expert trajectories, local maps, and target actions form the supervised training data for learning the action mapping.The mapping is optimized with cross-entropy loss against expert actions.
- Expert-data training: The optimization learns both CNN filters for map processing and communication-GNN matrices.The learnable GNN parameters are the matrices indexed by communication layer and filter.
- Model parametrization: The number of model parameters is independent of the network size N.
- Model parametrization: After training, GNN models can operate across communication topologies, including larger robot teams, using exchanges with one-hop neighbors.
- Expert-data generation: Training cases are generated on obstacle-filled grid worlds, solved by Conflict-Based Search, and split into training, validation, and testing sets.Each specified grid-world and team-size setting contains 30,000 cases, with a 70%/15%/15% split.
5.7 Policy Execution with Collision Shielding
During execution, each robot repeatedly applies its local policy to updated observations and adjacency information. Collision shielding replaces unsafe actions, but this protection can leave robots idle until timeout.
- Collision shielding: Collision shielding replaces actions that would collide with another robot or an obstacle by idle actions.
- Policy execution: The execution loop repeatedly processes each robot’s local input tensor and adjacency matrix while goals remain unreached.Predicted actions are generated sequentially until all robots reach their goals or the timeout occurs.
- Policy execution: The procedure records updated robot positions and refreshes the input tensor and adjacency matrix after each action.
- Collision shielding: Robots can remain stuck in an idle state until timeout, and such cases are counted as failures.
- Training support: The training process includes dataset aggregation with randomly selected cases and expert intervention when failures occur.
5.8 Dataset Aggregation during Training
Dataset aggregation addresses deadlocks created by collision shielding by adding online-expert corrections during training. The method identifies stuck cases, obtains expert continuations, and incorporates them into subsequent learning.
- Deadlock recovery: Collision shielding can create deadlocks in which robots remain idle, motivating online-expert corrections during training.
- Deadlock recovery: Every C epochs, randomly selected training cases are checked for deadlocks and solved from the deadlock configuration by the expert.
- Dataset aggregation: The corrected expert trajectories are aggregated into the training data to improve subsequent policy learning.
6 PERFORMANCE EVALUATION
The evaluation measures complete-case success and flowtime increase in matched-size and unseen-team-size experiments. Performance generally benefits from communication and remains strong when models are tested on substantially larger teams.
- Experimental design: The experiments evaluate matched-size performance and generalization to previously unseen larger and smaller robot teams.
- Metrics: Success rate is the proportion of tested cases in which all robots reach their goals before timeout.
- Metrics: Flowtime increase compares the sum of executed path lengths with the expert path sum, using the timeout length for robots that fail to reach goals.
- Communication: For larger teams, performance drops more sharply with K = 1 than with communicating GNNs, while the framework generally outperforms Discrete-ORCA on success rate and flowtime increase.
- Generalization: Strong generalization is observed across train-test team-size combinations, with models trained on larger teams tending to perform better on unseen sizes.
- Generalization: A model trained on 10 robots scales to teams six times larger without performance degradation when map sizes preserve effective robot density.
- Large-team evaluation: In 97% of 60-robot test cases, more than 95% of robots reach their goals; the K = 3 model without OE reaches at least 54 goals in 99.5% of cases.
7 DISCUSSION AND FUTURE WORK
The decentralized framework generalizes across robot-team sizes and scales to substantially larger instances, while remaining computationally fast. An online expert improves success, but instantaneous communication and unresolved live-locks and position swaps limit the current implementation.
- Discussion and Future Work: 0.0019 ± 2.15e−4 s per forward pass enables localized action policies for real-world deployments.The expert algorithm is intractable for more than 14 agents in dense environments within the given timeout.
- Discussion and Future Work: Teams trained on larger robot groups generalize better across unseen team sizes than teams trained on smaller groups.Frameworks trained on n = 8, 10, 12 tended to outperform those trained on n = 4, 6 across unseen larger and smaller instances.
- Discussion and Future Work: The online expert increased the success rate of all 60 robots reaching goals when the framework was trained on 10 robots.It also contributed to a right-shift of the distribution.
- Discussion and Future Work: The implementation assumes instantaneous inter-robot communication, and live-locks and position swaps remain challenges preventing 100% success.Time-delayed aggregation GNNs and action penalties are proposed as future directions.
8 CONCLUSIONS
The paper addresses collision-free navigation with limited local sensing and communication by jointly learning local feature extraction and inter-robot information sharing. It reports performance close to first-principles methods, generalization to larger teams, and feasible scaling beyond coupled centralized solvers.
- Conclusions: The task is collision-free multirobot navigation under restricted observation and communication ranges without a global localization reference frame.
- Conclusions: The architecture combines a CNN for local-observation features with a GNN that communicates those features among robots.The two components are jointly trained to determine information relevant to the robot team.
- Conclusions: The model performs very close to first-principles-based methods and generalizes to previously unseen cases involving much larger robot teams.
- Conclusions: The decentralized system scales to sizes that are intractable for coupled centralized solvers while remaining computationally feasible.