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.
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.
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.
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
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.
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
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.
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.
Jingtian Yan, Shuai Zhou, He Jiang +2
This paper was produced by the IEEE Publication Technology Group. They are in Piscataway, NJ.
Efficient routing of mobile robot fleets requires roadmaps with high redundancy, short path lengths, and sufficient node and edge clearance for conflict-free operation. Existing grid-based methods sacrifice geometric fidelity and impose Manhattan-distance path length constraints, whereas existing continuous-space methods neglect minimum distance constraints and transport demand. This paper proposes a continuous-space roadmap generation method that addresses this gap by placing nodes at convex corner points of the free space and at station interaction points, discretizing free space via local grid expansion, enforcing minimum inter-node and node-edge distance constraints derived from robot dimensions, and applying transport demand-driven K-shortest path pruning. The method is evaluated across three intralogistics environments using two multi-agent pickup and delivery (MAPD) solvers against three baselines: a reaction-diffusion sampling method (GSRM), an 8-connected grid, and random sampling. Under Priority Inheritance with Backtracking (PIBT), the proposed method outperforms GSRM by 1.2-23.4 % at maximum fleet size, the grid by at least 9.1 %, and random sampling by more than 10.4 % across all environments, with a space-time A* solver confirming these results. It further attains near-optimal normalized path lengths of 1.03-1.05 and the highest inter-station connectivity at comparable roadmap complexity.
Marvin Rüdt, Constantin Enke, Kai Furmans
Institute for Material Handling and Logistics, Karlsruhe Institute of Technology, Karlsruhe, Germany.
Automated fulfillment warehouses must continuously assign and execute pickup-and-delivery work while avoiding congestion. In many-to-many Multi-Agent Pickup and Delivery (MAPD), a request specifies a stock-keeping unit rather than fixed endpoints, requiring the controller to select an agent, source, and destination before path planning. Existing graph-guidance methods primarily influence routing after goals are fixed, leaving endpoint instantiation uninformed by recent traffic. We introduce Stigmergic Graph Memory (SGM), a bounded, decaying memory layer that records recent execution signals on warehouse nodes and directed edges to rank feasible endpoints and route preferences without altering collision constraints or planner validity. Across paired request streams on five layouts, three load levels, and 25 seeds per condition, SGM outperforms two reconstructed many-to-many allocation baselines in all 15 map-load conditions, with paired throughput gains of 20.5-36.7%. These results show that recent execution memory can improve warehouse throughput by shaping which feasible goals enter the planner, not only how agents travel to already fixed goals.
Aditya Dutta, Joon-Seok Kim
Emory University 201 Dowman Drive Atlanta, GA 30322 USA