Shared-Roadmap Generation and Evaluation for Multi-Agent Path Planning with a Heterogeneous Graph Neural Network

Summary

Multi-agent path planning in continuous environments uses roadmaps to balance safety with search efficiency, but lattice and sampling-based methods can produce dense graphs without reliably improving solution quality. This paper presents a scalable heterogeneous graph neural network that automatically generates and evaluates shared roadmaps. It represents waypoints, agent locations, and task locations as different node types, enabling the model to reason about global connectivity and interactions among agents. The model is trained on occupation-density maps aggregated from expert solver trajectories, which it uses to identify important points and remove redundant nodes and edges. The resulting roadmap is compact, coordination-aware, invariant to task permutations, and reusable for multi-agent pick-and-delivery tasks. Experiments report reduced planning effort and the potential to find better solutions, with at least a 40% reduction in runtime and graph size for dense roadmaps.