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

Brandon Ho; Nikola Rogers; Seung-Kyum Choi

cs.AIOct 6, 2026

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

Authors: Brandon Ho, Nikola Rogers, Seung-Kyum Choi

Organizations: Institute of Robotics and Intelligent Machines (IRIM), Georgia Institute of Technology, Atlanta, GA, USA

Abstract

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.

Figures & tables

Fig. 1 : Overview of the proposed learning-based roadmap evaluator and reconstruction framework for multi-agent path planning (MAPP). Given a new problem instance, a dense roadmap is generated from any roadmap generator and is then evaluated by the trained GNN. A thresholding function classifies vertices as selected or discarded waypoints. The selected nodes form a reconstructed roadmap, which is subsequently used by a MAPF/MAPP algorithm to compute the final solution.

Panel of Figure 2 — Fig. 2 : Comparison of the original map (Fig. 2(a) ) and the roadmaps ( 2(b) - 2(d) ). The red and blue represent the start and goal points, respectively.

Fig. 3 : Offline training process. For each new problem instance in the dataset, randomized start-goal assignments are generated to create multiple permutations of the same problem instances. These permutations are then solved to generate solution trajectories, which are then aggregated into an occupation-density heatmap. This density map provides supervision to train a graph neural network (GNN) to predict node importance value.

Panel of Figure 4 — Fig. 4 : These 32 x 32 validation scenarios show the GNN evaluator’s ability in selecting which nodes to be used for reconstruction in (a) single agent scenarios and (b) multi-agent scenarios. The underlying heatmap highlights the agent paths found by CBS for multiple permutations of the same MAPF problem instances. The red and blue are the start and goal locations for this specific MAPF problem instance permutation.

Panel of Figure 5 — Fig. 5 : The colorful lines are the path in the solution for each agent in the PRM reconstructed map in a 64x64 square map.

Fig. 6 : Performance metrics comparing the reconstructed PRM against the original dense PRM across varying agent counts $N=\{1,2,4,8,16\}$ . Results are shown for points particles ( $R=0$ , and agents with a defined radius $R=1$ under discrete time ( $dt$ ) and continuous time ( $ct$ ) kinematics. While pruning introduces a solution coarseness that increases SOC and path length, it yields a drastic reduction in runtime—up to $80\%$ in high-agent scenarios. The 16-agent scenario with $R=1.0$ resulted in a failure to find a solution (N/A in Table I). This suggests that for large-bodied agents in high-density environments, the current thresholding mechanism may prune critical connectivity nodes required for collision avoidance.

Dense Roadmap	Number of Agents	Number of Nodes Reduction		Number of Edges Reduction
Dense Roadmap	Number of Agents	R = 0.0	R=1.0	R = 0.0	R=1.0
PRM	1	40.7%	38.0%	46.5%	42.0%
	2	41.5%	39.0%	48.0%	43.8%
	4	42.5%	39.6%	49.5%	44.3%
	8	44.2%	40.8%	51.9%	44.8%
	16	43.2%	N/A	50.9%	N/A

TABLE I : The number of nodes and edges reduction reaches at least

40\%

except for

R=1.0

for 16 agents due to no solution founded under the graph.

Panel of Figure 8 — Fig. 7 : The charts illustrate the trade-offs when applying the GNN-based roadmap evaluator to inherently sparse graph structures, specifically Lattice Grids (a) and Delaunay Triangulations (b). While solutions were found for up to 16 agents on PRMs, these sparse roadmaps were limited to 4-agent scenarios due to the loss of critical connectivity nodes. However, both sparse roadmaps experienced significantly shorter runtimes after reconstruction, with reductions reaching up to $80-90\%$ for single-agent cases. In the 2-agent Lattice Grid scenario, the reconstructed roadmap yielded lower SOC and path lengths.

Sparse Roadmap	Number of Agents	Number of Nodes Reduction		Number of Edges Reduction
Sparse Roadmap	Number of Agents	R = 0.0	R=1.0	R=0.0	R=1.0
Lattice Grid	1	33.7%	33.9%	34.5%	34.7%
	2	34.0%	33.7%	34.9%	34.5%
	4	33.1%	N/A	34.1%	N/A
Delaunay Triangulation	1	38.5%	36.2%	44.8%	40.3%
	2	38.8%	37.3%	45.5%	42.2%

TABLE II : The number of nodes and edges reduction reaches at least

30\%

for upto 4 agents as pruning on sparse graph can lead to no solutions with a large number of agents and indicated by N/A.

Explore similar work

From Discrete Plans to Real-World Execution: A World-Model-Driven Framework for Execution-Aware Multi-Agent Path Finding
Nov 26, 2025Jingtian Yan, Shuai Zhou, He Jiang +2Multi-Agent Path Finding Multi-Robot Motion Planning
This paper was produced by the IEEE Publication Technology Group. They are in Piscataway, NJ.
Continuous-Space Roadmap Generation for Mobile Robot Fleets with Distance Constraints and Geometry-Aware Discretization
Nov 10, 2025Marvin Rüdt, Constantin Enke, Kai FurmansShortest Paths Heterogeneous Robot Teams
Institute for Material Handling and Logistics, Karlsruhe Institute of Technology, Karlsruhe, Germany.
Stigmergic Graph Memory: An Environment-Aware Approach for Many-to-Many Multi-Agent Pickup and Delivery
Jul 16, 2026Aditya Dutta, Joon-Seok KimMulti-Agent Path Finding Warehouse Automation
Emory University 201 Dowman Drive Atlanta, GA 30322 USA

Nov 26, 2025, cs.ROJ/K move · Enter open · S save

From Discrete Plans to Real-World Execution: A World-Model-Driven Framework for Execution-Aware Multi-Agent Path Finding

Jingtian Yan, Shuai Zhou, He Jiang, Stephen F. Smith+1

This paper was produced by the IEEE Publication Technology Group. They are in Piscataway, NJ.

Multi-Agent Path Finding Multi-Robot Motion Planning Action Space

Open paper AskPDF arXiv

Multi-Agent Path Finding (MAPF) studies how to coordinate multiple agents to reach their goals without collisions and underpins a range of large-scale robotic systems, including automated warehousing and manufacturing. Recent advances enable MAPF solvers to compute high-quality plans for hundreds of agents. However, these plans are generated using simplified robot models with discretized time and action spaces. When they are deployed in physical systems, heterogeneous robot dynamics, asynchronous interactions, communication delays, and other real-world factors can lead to substantial deviations from planned performance. We bridge the gap between discrete planning and real-world execution through ExecTimeNet, a learned world model of MAPF execution that predicts how a discrete MAPF solution will unfold on physical robots, mapping each discrete action to its realized execution state, including its wall-clock completion time and the kinodynamic state in which it ends. Building on this capability, we first propose REMAP, an execution-aware MAPF framework that integrates execution-time estimation into planning, guiding the search toward MAPF solutions with improved execution performance. We also introduce ESADG, a post-planning optimization procedure that optimizes the execution schedule of a given MAPF solution while preserving path feasibility. We evaluate proposed frameworks in high-fidelity simulation with up to 300 agents and on physical robots. In simulation, ExecTimeNet predicts the execution state accurately and transfers to unseen maps and agent counts. Across simulation benchmarks spanning diverse map topologies, REMAP reduces delays by up to 21% over baselines, while ESADG achieves up to 40% normalized improvement. On physical hardware, the full pipeline reduces total execution time by up to 15.3%, demonstrating effective transfer from simulation to real-world deployment.

Abstract

Explore similar work

From Discrete Plans to Real-World Execution: A World-Model-Driven Framework for Execution-Aware Multi-Agent Path Finding

Continuous-Space Roadmap Generation for Mobile Robot Fleets with Distance Constraints and Geometry-Aware Discretization

Stigmergic Graph Memory: An Environment-Aware Approach for Many-to-Many Multi-Agent Pickup and Delivery