# Shared-Roadmap Generation and Evaluator for Multi-Agent Path Planning Using Heterogeneous Graph Neural Network

arXiv: https://arxiv.org/abs/2610.09034 · HTML: https://mlsanity.com/paper/2610.09034/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 14 of its 32 references that are in the map.
- First posted on arXiv 6 Oct 2026.

## Builds on (most cited first, 14 of 14)

- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Decoupled Weight Decay Regularization](https://mlsanity.com/paper/1711.05101/) (2017)
- [Focal Loss for Dense Object Detection](https://mlsanity.com/paper/1708.02002/) (2017)
- [GResNet: Graph Residual Network for Reviving Deep GNNs from Suspended Animation](https://mlsanity.com/paper/1909.05729/) (2019)
- [Laplacian-Steered Neural Style Transfer](https://mlsanity.com/paper/1707.01253/) (2017)
- [Reducing Collision Checking for Sampling-Based Motion Planning Using Graph Neural Networks](https://mlsanity.com/paper/2210.08864/) (2022)
- [Let's Think in Two Steps: Mitigating Agreement Bias in MLLMs with Self-Grounded Verification](https://mlsanity.com/paper/2507.11662/) (2025)
- [Improving Continuous-time Conflict Based Search](https://mlsanity.com/paper/2101.09723/) (2021)
- [CTRMs: Learning to Construct Cooperative Timed Roadmaps for Multi-agent Path Planning in Continuous Spaces](https://mlsanity.com/paper/2201.09467/) (2022)
- [Optimized Directed Roadmap Graph for Multi-Agent Path Finding Using Stochastic Gradient Descent](https://mlsanity.com/paper/2003.12924/) (2020)
- [Safe Interval Path Planning With Kinodynamic Constraints](https://mlsanity.com/paper/2302.00776/) (2023)
- [Towards Learning Scalable Agile Dynamic Motion Planning for Robosoccer Teams with Policy Optimization](https://mlsanity.com/paper/2502.05526/) (2025)
- [pc-dbCBS: Kinodynamic Motion Planning of Physically-Coupled Robot Teams](https://mlsanity.com/paper/2505.10355/) (2025)
- [db-LaCAM: Fast and Scalable Multi-Robot Kinodynamic Motion Planning with Discontinuity-Bounded Search and Lightweight MAPF](https://mlsanity.com/paper/2512.06796/) (2025)

## Abstract (arXiv)

Multi-agent path planning (MAPP) in continuous environments often relies on roadmaps to balance safety and search efficiency. However, traditional roadmap generation methods, such as lattice grids or standard sampling-based approaches, frequently face a trade-off between graph density and the likelihood of finding feasible, high-quality solutions. In this paper, we propose a scalable heterogeneous Graph Neural Network (GNN) framework for the automated generation and evaluation of shared multi-agent roadmaps. Our model covers the representation of waypoints, agent locations, and task locations as distinct nodes in a heterogeneous graph, allowing it to reason over global connectivity and inter-agent interactions. By training on occupation density maps aggregated and collected from expert solver trajectories, the GNN learns to identify critical points of interest and prune redundant nodes and edges. This process produces a compact, coordination-aware roadmap that is invariant to task permutations and is reusable for multi-agent pick and delivery tasks. Experimental results demonstrate that our framework can reduce planning effort and can potentially find better solutions, reaching at least 40% reduction in runtime and in graph size for dense roadmaps.