Paper deep dive
Shared-Roadmap Generation and Evaluator for Multi-Agent Path Planning Using Heterogeneous Graph Neural Network
Brandon Ho, Nikola Rogers, Seung-Kyum Choi
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 95%
Last extracted: 10/8/2026, 6:46:54 AM
Summary
This paper proposes a scalable heterogeneous Graph Neural Network (GNN) framework for the automated generation and evaluation of shared multi-agent roadmaps in continuous environments. The model represents waypoints, agent locations, and task locations as distinct nodes in a heterogeneous graph to reason over global connectivity and inter-agent interactions. By training on occupation density maps derived from expert solver trajectories, the GNN identifies critical points of interest and prunes redundant nodes and edges. This process produces a compact, coordination-aware roadmap that is invariant to task permutations and reusable for multi-agent pick-and-delivery tasks. Experimental results demonstrate at least a 40% reduction in runtime and graph size for dense roadmaps.
Entities (10)
Relation Signals (8)
Heterogeneous Graph Neural Network → usedfor → Multi-Agent Path Planning
confidence 98% · we propose a scalable heterogeneous Graph Neural Network (GNN) framework for the automated generation and evaluation of shared multi-agent roadmaps.
Brandon Ho → affiliatedwith → Georgia Institute of Technology
confidence 95% · Brandon Ho, Nikola Rogers, and Seung-Kyum Choi are with the Institute of Robotics and Intelligent Machines (IRIM), Georgia Institute of Technology
Nikola Rogers → affiliatedwith → Georgia Institute of Technology
confidence 95% · Brandon Ho, Nikola Rogers, and Seung-Kyum Choi are with the Institute of Robotics and Intelligent Machines (IRIM), Georgia Institute of Technology
Seung-Kyum Choi → affiliatedwith → Georgia Institute of Technology
confidence 95% · Brandon Ho, Nikola Rogers, and Seung-Kyum Choi are with the Institute of Robotics and Intelligent Machines (IRIM), Georgia Institute of Technology
Heterogeneous Graph Neural Network → prunes → Roadmap
confidence 95% · the GNN learns to identify critical points of interest and prune redundant nodes and edges. This process produces a compact... roadmap
Heterogeneous Graph Neural Network → containscomponent → Graph Attention Network
confidence 93% · node and edge embedding are passed into three residual multi-head Graph Attention Networks (GAT) operators
Heterogeneous Graph Neural Network → uses → Occupation Density Map
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
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.
Tags
Links
- Source: https://arxiv.org/abs/2610.09034v1
- Canonical: https://arxiv.org/abs/2610.09034v1
Trouble viewing inline? Open PDF directly →
Full Text
41,923 characters extracted from source content.
Expand or collapse full text
Shared-Roadmap Generation and Evaluator for Multi-Agent Path Planning Using Heterogeneous Graph Neural Network Brandon Ho Nikola Rogers Seung-Kyum Choi †thanks: Brandon Ho, Nikola Rogers, and Seung-Kyum Choi are with the Institute of Robotics and Intelligent Machines (IRIM), Georgia Institute of Technology, Atlanta, GA, USA bho36@gatech.edu 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%40\% reduction in runtime and in graph size for dense roadmaps. I Introduction Multi-agent path planning (MAPP) has been a central challenge in domains such as autonomous driving [1, 2], aerial swarms [3], and warehouse automation [4, 5], where overall system performance depends critically on both safety and efficiency. In real-world deployments, safety requirements typically take precedence over efficiency, often constraining agents to move along predefined edges and vertices within a structured environment, commonly referred to as a shared roadmap. A simple solution is a lattice grid, where autonomous agents or automated guided vehicles (AGVs) are restricted to moving between cardinal neighboring cells. However, unlike lattice grids, roadmaps that approximate continuous state spaces allow agents to move more flexibly and can yield more practical and higher-quality solutions. Such non-lattice roadmaps better capture the underlying geometry of real environments and reduce discretization artifacts. Nevertheless, roadmap generation itself is a non-trivial problem. Poorly constructed roadmaps can significantly degrade the performance of MAPP, underscoring the importance of principled methods for a shared multi-agent roadmap generation. The main challenge of roadmap generation lies in balancing graph density with the likelihood of finding a feasible solution [6]. A dense roadmap may better capture high-quality or even the optimal solution, but it enlarges the search space. Conversely, a sparse roadmap might expedite the search process but risk of finding a valid solution. A common approach for constructing effective roadmaps is a two-step iterative process: (1) use sampling-based motion planning (SBMP) [7] to generate multiple roadmaps and then (2) evaluate these roadmaps using a MAPP algorithm. Although this paradigm has been widely adopted for single-agent navigation [8, 9, 10, 11], extending it to multi-agent settings is non-trivial due to the inter-agent interactions. While prior work has explored roadmap generation for multi-agent scenarios [12, 13, 14], existing approaches impose certain constraints, such as generating non-shared roadmaps for each agent, limiting connectivity (e.g., non-bidirectional edges). Graph Neural Networks (GNNs) have shown promising results in scalable recommendation systems where information can be represented in a relational graph [15]. By coding individual entities as nodes and their interactions as edges, GNNs are able to learn structured representations that generalize to environments with a variable number of elements. Given an existing roadmap, we encode waypoints, agent locations, and task locations as nodes in a heterogeneous graph, while encoding spatial relationships and task-relevant information as edge features. On this structured representation, our heterogeneous GNN model evaluates roadmap quality and reasons over global connectivity and agent interactions. Additionally, the GNN learns to identify critical points of interest and prune less informative nodes or edges, thereby producing a refined roadmap that is both compact and better suited for efficient multi-agent coordination. Figure 1 showcases our proposed framework. Our contributions are as follows: • We propose a dynamic and scalable heterogeneous Graph Neural Network (GNN) framework for roadmap generation and evaluation. Our model identifies critical points of interest within an existing roadmap and prunes less informative nodes and edges, producing a more compact and coordination-aware graph. • We design our model to be task-agnostic for multi-agent path planning (MAPP) and readily extensible to multi-agent pickup and delivery (MAPD). By representing agent locations and task locations under the same node type as landmarks, the constructed roadmap becomes invariant to task configuration permutations, enabling flexible deployment across varying task assignments • We demonstrate the potential of our approach by training on MAPP instances up to four agents and testing up to 16 agents. Experimental results show that our GNN-based framework reduces planning effort, achieving at least a 40%40\% reduction in runtime and graph size for dense roadmaps, and can potentially find better solutions. 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. I Related Works I-A Multi-Agent Pathfinding (MAPF) Multi-agent pathfinding (MAPF), a problem of multi-agent path planning (MAPP) in discrete space, has been applied in various AI and robotics applications where the objective is to find a set of collision-free paths on a graph. Popular approaches include, but are not limited to, conflict-based search (CBS) algorithms [16], increasing cost tree search [17], and prioritized planning (e.g., HCA* [18], SIPP [19], etc. More recently, research demonstrates the potential in using machine-learning techniques for solving MAPF. These methods learns from either demonstrations collected offline for imitation learning, a sequence of observations for reinforcement learning, or using graph neural networks, leading to finding solutions in multi-agent path planning (MAPP). Despite such progress, many algorithms simplify the scope of their problem instances, typically in a grid map, where the spatial graph structure has uniform travel cost, and collisions only occur when point-particle agents occupy the same vertices or edges [18]. These assumptions restrict the algorithms’ capabilities to only discrete time and space, making their real-world applications limited. I-B Roadmap Generation Roadmap generation has been a research topic of interest mainly for single-agent cases, as it allows the agents to move in continuous space, leading to more practical and better solutions. A roadmap refers to an undirected connected graph that is either shared across agents or tailored for each agent. An ideal roadmap entails that any two points on the graph can be connected by at least one path, and the graph should be sparse as possible. Popular methods in generating a roadmap include, but not are not limited to, probabilistic roadmaps (PRMs) [20], constrained Delaunay Triangulation (CDT) [21], visibility graph [22], and rapidly exploring random graphs (RRGs). CDT and visibility graph construct a roadmap by utilizing the obstacle boundary as either constraints or points of interest, while PRM and RRG iteratively sample points in free space. Research on single-agent roadmaps studies how to densify the representation of the environment to balance optimality and density [8, 9, 10, 11]. For multi-agent roadmaps, most continuous MAPP methods [23, 24, 25, 26, 27] rely on some roadmap to operate. Their primary challenge lies in scaling to large numbers of agents in real time, as the search space grows significantly and collision checking must be performed at high frequency. In contrast, we investigate a complementary research direction: instead of improving the planner itself, we explore what types of roadmap representations are most effective for solving MAPP in continuous space. There have been relatively few studies on multi-agent roadmap generation and refinement. [14] constructs a shared roadmap with bias-based sampling, focusing on narrow passages, but is less suited for sparsely distributed obstacles. [13] employs a generative model to construct separate but not shared roadmaps per agent that incorporate inter-agent interactions. The most relevant work is [12], where they optimized already constructed roadmaps through online learning. However, their optimization is limited to directed edges and does not remove redundant or unnecessary vertices, thereby restricting the extent to which the roadmap can be structurally refined. In contrast, our method identifies critical points of interest within an existing roadmap and reconstructs a shared, refined graph. A shared roadmap provides constraints where safety can be better tracked as the agents follow on set guided paths. By labeling agents’ initial and task locations as landmarks, the model ensures connectivity among essential nodes, improving coverage, reusability, and generalization across varying multi-agent tasks, including pickup and delivery scenarios. I Problem Statement Problem Description: A MAPP problem instance I is defined as a tuple (,,A,C,R,,K)(G,Z,A,C,R,G,K). =(V,E)G=(V,E) is an undirected roadmap graph constructed in the state space C with vertices v∈Vv , representing position agents can occupy, and edge eij∈E:(vi,vj)e_ij :(v_i,v_j) indicating traversal connections between viv_i and vjv_j without collision, i.e., eij∈Cobse_ij∈ C__ obs. We consider a MAPP for a team of N agents A=a,…,aNA=\a,...,a_N\ in a 2D2D continuous space C⊆ℝ2C ^2, where Cobs⊆C__ obs C represents the obstacle set, and the remaining part is the free space Cfree⊂C bsC_free⊂ C C_obs. Each agent aia_i has a unique start position ziz_i and goal position gig_i, where :zii∈1,…NZ:\z_i\_i∈\1,...N\ and :gii∈1,…NG:\g_i\_i∈\1,...N\ represent the start vertices set and goal vertices set respectively. Each agent’s body is modeled as a ball with radius Ri(q)⊆CR_i(q) C around its position q∈Cq∈ C where R:Rii=1,…,NR:\R_i\_i=\1,...,N\ represents the space occupied by the agent . Each agent aia_i has its kinematic constraints K, e.g each agent has a maximum velocity or move distance where K=Ki=1,…,NK=\K\_i=\1,...,N\. A trajectory for agent aia_i is defined by a continuous mapping σi:[0,Ti]→C _i:[0,T_i]→ C where Ti∈ℝ>0T_i _>0. Note that the agent will stay in place after reaching the goal point, starting from t≥Tit≥ T_i, which means that σi(t)=σi(T)∀t≥Ti _i(t)= _i(T)∀ t≥ T_i. A solution for a MAPP problem instance is a set of N trajectories σ=σi,…,σN$σ$=\ _i,..., _N\ that satisfies the following conditions: 1. Endpoint: σi(0)=zi∧σi(T)=gi _i(0)=z_i _i(T)=g_i 2. Obstacles: σi(t)∈Cfree,0≤t≤T _i(t)∈ C_free,0≤ t≤ T 3. Inter-agent: Ri(σi(t))∩Ri(σj(t))=∅,0≤t≤TR_i( _i(t))∩ R_i( _j(t))= ,0≤ t≤ T 4. Kinematic-aware: σi _i satisfies constraint KiK_i Solution Cost: We defined the quality of the solution σ by sum-of-costs: ∑iTi _iT_i for i∈1,…,Ni∈\1,...,N\ which represents the sum of all time taken for each agent aia_i to reach their goal. IV Methodology In this section, we first describe the workflow of the heterogeneous graph neural network model, starting with the roadmap generation, then the model architecture, and its pruning and reconstruction process. IV-A Roadmap Generation We construct our homogeneous roadmap graph G using three generation strategies, as illustrated in Fig. 2. The first strategy is a lattice grid, in which vertices are uniformly distributed throughout the free space and edges connect neighboring vertices along Cartesian directions. The second strategy is a Probabilistic Roadmap (PRM), where vertices are randomly sampled in the free space and edges are created based on a maximum connection radius and a limit on the number of nearest neighbors. The third strategy is Delaunay triangulation, in which randomly sampled vertices are connected to form a planar graph composed of non-overlapping triangles. For all three constructions, each vertex vi∈v_i stores its global position a, and each edge eij∈e_ij is associated with a scalar weight wijw_ij, corresponding to the Euclidean distance between its incident vertices. (a) Map (b) Lattice Grid (c) PRM (d) Delaunay Triangulation 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. IV-B Model In this work, we formulate roadmap evaluation and generation as a binary node classification problem e.g (ϕ(vi|)→0,1φ(v_i|G)→\0,1\). We are given a collection of MAPP demonstrations, each consisting of a problem instance and its corresponding solution obtained through computationally intensive offline MAPF solvers operating on sufficiently dense roadmaps constructed via uniform random or grid sampling. Using these demonstrations as training data, we learn a predictive model that classifies each vertex according to whether it belongs to the solution set (class 1) or not (class 0). The trained model serves as a vertex evaluator that prunes a densely generated shared roadmap based on a decision threshold, producing a sparser yet solution-preserving graph that enables more efficient downstream planning. Figure 1 showcased our proposed framework. IV-B1 Architecture Graph Augmentation: The GNN evaluator ϕφ operates on an augmented heterogeneous graph augG_aug derived from the initial roadmap G. To make the network task-aware, node features in G are concatenated with two-bit binary encodings indicating membership in the start set S or goal set G. These encodings guide the GNN to identify critical landmarks. Furthermore, we introduce a global directed edge type for augG_aug that connects every landmark vi∈∪v_i to all other vertices vj∈v_j . Each new edge eij=(vi,vj)e_ij=(v_i,v_j) is weighted by the Euclidean distance between the vertices. This secondary connectivity layer provides the GNN with global contextual information, aiding in the identification of waypoints likely to belong to the optimal solution set. Model Layers: Before the GNNs, the node and edge features are first encoded into an embedding with two linear layers. Afterward, the node and edge embedding are passed into three residual multi-head Graph Attention Networks (GAT) operators [28, 29], followed by a leaky ReLU activation function. The vertex representation is then processed through another linear layer, followed by a sigmoid function. The output y=ϕ(aug)y=φ(G_aug) predicts a scalar value per vertex, representing the probability of how likely that vertex is used by the solution set. IV-B2 Training and Data Generation Ground Truth: Given a MAPF instance, we first apply Conflict-Based Search (CBS) to compute a feasible solution on a lattice-grid roadmap. Regardless of whether CBS successfully finds a solution, we generate additional training variations by randomizing the start and goal assignments within the same environment. For each modified MAPF instance, we again apply CBS to obtain a feasible solution when possible. This process is repeated until a sufficient number of feasible start–goal permutations are collected. After obtaining multiple solution trajectories, we aggregate the agents’ paths spatially to construct an occupation density map, which captures the frequency with which different regions of the roadmap are utilized across demonstrations. This occupation density map H serves as ground truth and a labeler for the data generation Data Generation: Given the same MAPF instance, we construct a roadmap G using PRM. Each vertex vi∈v_i is labeled according to its relevance to the occupation density H. If a vertex lies directly on the heatmap (i.e., it was visited in the aggregated demonstrations), it is assigned a label of 1. Otherwise, its label is determined based on proximity to labeled vertices through a nearest-neighbor propagation scheme. The labeler scoring function f is defined as: f(vi)=1vi∈Hmaxj∈(i)f(vj)1+dist(vi,vj)vi∉Hf(v_i)= cases1&v_i∈ H\\ _j (i) f(v_j)1+dist(v_i,v_j)&v_i∉ H cases (1) where (i)N(i) denotes the neighborhood of viv_i, and dist(v,v′)dist(v,v ) is in the Euclidean distance between vertices. This formulation assigns a high score to vertices frequently visited in the solutions while smoothing decaying the score for nearby vertices, creating a soft relevance signal over the roadmap. Training The objective of the model is to classify how likely the vertex belongs to the solution set. We learn the following loss function, which is a combination of the focal loss [30] and Laplacian loss [31]: L(,E,θ)=−1N∑i=1Nα(1−yi)γlog(yi)+λN∑i=1N∑j=1j∈(i)wij(yi−yj)2 -5.0ptL(G,E,θ)=- 1N _i=1^Nα(1-y_i)^γ (y_i)+ λN _i=1^NΣ^j (i)_j=1 -5.0ptw_ij(y_i-y_j)^2 (2) where γ and α are focal loss parameters, λ is a regularization term, pip_i are the output probabilities, θ is the GNN parameters. Since the dataset is imbalanced, as most vertices do not lie on the solution heatmap for a few agents, we employ focal loss to mitigate the dominance of easy negative samples and emphasize informative vertices. The Laplacian term encourages smoothness over the graph by penalizing large prediction differences between neighboring vertices, aligning with the spatial decay structure introduced during data generation. Figure 4 shows an example of our GNN evaluator in our validation scenarios. (a) Single Agent Validation (b) Multi-Agent Validation 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. IV-C Reconstruction In this subsection, we explain how to reconstruct a new roadmap using the GNN as a vertex evaluator. Algorithm 1 summarizes the proposed procedure, which takes a problem instance I as input and outputs a newly refined map newG_new. Figure 1 visualizes the process. First, we generate a dense shared roadmap G using a roadmap construction function conditioned on the problem instance I. The specific generation strategy is flexible (e.g. PRM), but it must provide a sufficiently dense representation of the environment to ensure coverage. Next, the roadmap G is augmented into a heterogeneous graph representation augG_aug suitable for input to the GNN ϕφ, as previously discussed in Section IV-B1. A forward pass through ϕφ produces vertex probability scores indicating the likelihood that each vertex belongs to the solution set. These probabilities are then passed to a threshold function to obtain a binary class assignment. The threshold value (τ) is defined as τ(,y)=min(mean(y),,0.5),τ(G,y)= (mean(y),,0.5), (3) where y denotes the set of predicted vertex scores. The reconstructed roadmap newG_new is then obtained by retaining the selected vertices VselectedV_selected and preserving all edges EselectedE_selected from the original roadmap G whose endpoints both belong to the selected vertex set. In other words, newG_new corresponds to the induced subgraph of G defined by the selected vertices. Algorithm 1 Roadmap Reconstruction 1: Input: Problem instance I, trained GNN evaluator ϕφ, threshold τ 2: Output Reconstructed roadmap newG_new 3: function ReconstructRoadmap(I,ϕ,τI,φ,τ) 4: ←GenerateDenseRoadmap(I)G (I) 5: aug←AugmentGraph()G_aug (G) 6: y←ϕ(aug)y←φ(G_aug) ⊳ Vertex importance scores 7: Vselected←∅V_selected← 8: for each vertex vi∈v_i do 9: if yi≥τ(,y)y_i≥τ(G,y) then 10: Vselected←Vselected∪viV_selected _selected∪\v_i\ 11: end if 12: end for 13: Eselected←∅E_selected← 14: for each edge eij∈e_ij do 15: if vi∈Vselected∧vj∈Vselectedv_i∈ V_selected v_j∈ V_selected then 16: Eselected←Eselected∪eijE_selected _selected∪\e_ij\ 17: end if 18: end for 19: new←(Vselected,Eselected)G_new←(V_selected,E_selected) 20: return newG_new 21: end function V Experiments In this section, we evaluate our roadmap evaluator and generation in various MAPP problems. V-A Experimental Design For all MAPP instances, we model the agent bodies R as disk with the same radius R in a 2D continuous space (C=[0,64]2C=[0,64]^2) for quick collision detection. We evaluate with two body-radius setting (OPENR∈0,1)R∈\0,1\)) and two kinematic settings: • continuous-time (ct): each agent can wait or move at the same fixed velocity of 1. • discrete-time (dt): each agent can wait or move to the neighboring vertex in one timestep. In both kinematic settings, agents move linearly along the roadmap edges. Under these settings, we generated 25 different MAPP instances with at most 10 randomized start-goal permutations for 1, 2, 4, 8, and 16 agents. For the MAPF/MAPP algorithm, we used Safety Interval Prioritized Planner (SIPP) [19] as it provides a quick but suboptimal solution and can be used in a discrete or continuous time-space domain. Roadmap Baselines: To evaluate the effectiveness of our reconstructed roadmaps, we compare across one dense roadmap generation (PRM) as our main results and two sparse roadmap generations (lattice-grid, PRM, and Delaunay Triangulation) as ablation studies. • PRM [20] (Dense): The number of samples was set to 2000 with a minimum and maximum edge length of 0.1 and 5.1, respectively. The maximum number of neighbors per vertex is 15. • Lattice Grid (Sparse): Conventional discretized roadmap used for MAPF with a grid size [32x32][32x32] • Delaunay Triangulation [21] (Sparse):The number of samples was set to 2000 with a minimum and maximum edge length of 0.1 and 5.1. V-B Evaluation Metric For the following metrics, we consider the percent increase of the MAPF/MAPP algorithm on our constructed roadmap compared to the original generated roadmap where MAPF/MAPP scenarios were successful on both roadmaps. • Sum-of Cost (SOC) Increase: Solution quality defined in Section I or the average sum of times taken for all agents to reach their tasks • Path Length: The average total travel distance for all agents to reach their tasks • Makespan: The average completion time for the last agent to finish (maxiTi _iT_i) • Runtime: The average execution time of running the MAPP/MAPF algorithm • Number of Nodes Reduction: The average number of nodes reduced or pruned by the roadmap evaluator. • Number of Edges Reduction: The average number of edges reduced or pruned by the roadmap evaluator. V-C Training Setup Our dataset comprises 1,800 problem instances on 32×3232× 32 maps with an obstacle density of 0.1, featuring scenarios with 1, 2, and 4 agents, where we use 1,620 problems for training and 180 for validation. The number of generated problem permutations per problem instance was at most 64 to create our occupation density map H. The roadmap generation was done with PRM, sampling 1000 waypoints with a minimum edge length of 0.1, a maximum edge length of 5.1, and a maximum limit of 13 neighbors per node. The architectural pipeline begins with two initial linear layers with 64 channels to encode the input, which consists of 4-dimensional node features and 1-dimensional edge features. This is followed by three residual Graph Attention Network (GAT) layers, each configured with 4 heads and 16 channels, using Leaky ReLU activation functions. A final linear layer with 32 channels reduces the dimensionality to a single scalar output representing the vertex probability score. The model is trained using the AdamW [32] optimizer with a learning rate of 0.00010.0001 and a weight decay of 5×10−45× 10^-4. We employ a batch size of 128 over 5,000 epochs, incorporating a Laplacian regularization term (λ) of 0.010.01 to ensure spatial smoothness across the roadmap. We utilize an Intel Ultra 7 265K (20 cores) processor and a single NVIDIA RTX 5090 GPU with 32GB of RAM, where the dataset generation took less than 5 minutes using 20-core multiprocessing, and the training process was completed in approximately 52 minutes. V-D Results Figure 6 and Table I present our main results. Examples of reconstructed roadmaps and their corresponding solutions are shown in Figure 4(a). Overall, our roadmap evaluator significantly reduces the search space and planning time for MAPF algorithms. Solutions found using the reconstructed PRM operate within a smaller search space compared to those generated using the original PRM. As shown in Table I, the roadmap evaluator reduces the number of nodes and edges by more than 40%40\% across all agent scenarios and configurations. Furthermore, planning time is reduced by at least 40%40\% for point-particle agents and by an average of 20%20\% for agents with a radius of 1. There were instances where the SOC, makespan, and path length were smaller in the sparse reconstructed roadmap than in the original dense roadmap, particularly in the 8-agent PRM scenarios shown in Figure 6 and the 2-agent lattice grid scenarios. From our observation, in the dense roadmap, some SIPP agents were required to wait for others before reaching their destinations. In contrast, in the reconstructed roadmap, the agents were able to proceed without waiting. However, since SIPP does not guarantee global optimality, this behavior may also arise from the non-optimal nature of the prioritized planning process. Nevertheless, the results suggest that the roadmap evaluator may implicitly identify and remove vertices that contribute to congestion or agent conflicts. We further evaluated the capability of the roadmap evaluator on already sparse roadmaps, including lattice grids and Delaunay triangulations, as shown in Figure 7. Our experiments show that MAPF algorithms operating on the reconstructed roadmaps are able to find solutions for up to four agents. While sparse roadmaps can significantly expedite the search process (Table I), they also reduce connectivity, which increases the likelihood of failing to find a feasible solution for a large number of agents. (a) Single Agent Reconstructed PRM Roadmap SIPP Solution (b) Multi-Agent Reconstructed PRM Roadmap SIPP Solution 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,16N=\1,2,4,8,16\. Results are shown for points particles (R=0R=0, and agents with a defined radius R=1R=1 under discrete time (dtdt) and continuous time (ctct) kinematics. While pruning introduces a solution coarseness that increases SOC and path length, it yields a drastic reduction in runtime—up to 80%80\% in high-agent scenarios. The 16-agent scenario with R=1.0R=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%40\% except for R=1.0R=1.0 for 16 agents due to no solution founded under the graph. (a) Lattice Grid Ablation (b) Delaunay Triangulation Ablation 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%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% 4 38.8% 36.8% 46.1% 41.7% TABLE I: The number of nodes and edges reduction reaches at least 30%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. V-E Limitation Although the proposed GNN-based roadmap evaluator is capable of identifying key regions of interest and pruning redundant waypoints to produce a sparser roadmap, it has a few limitations. First, if the initial roadmap is not sufficiently dense, the evaluator may prune vertices that are essential for connectivity, thereby eliminating feasible paths between start–goal pairs. Second, the reconstruction process relies on a thresholding function applied to the GNN output scores. This threshold acts as a tunable hyperparameter that directly controls the sparsity of the reconstructed roadmap. A higher threshold produces a sparser graph, reducing the search space but increasing the risk of removing critical vertices and destroying connectivity. Conversely, a lower threshold preserves connectivity more reliably but retains a larger search space, limiting computational gains. In practice, the effectiveness of the proposed method depends on selecting an appropriate threshold value that balances sparsity and connectivity. VI Conclusion We presented a heterogeneous Graph Neural Network (GNN) framework for roadmap generation and evaluation, introducing a novel graph representation tailored for shared-roadmap construction in multi-agent path planning. The proposed GNN-based roadmap evaluator assigns importance scores to vertices in an initially dense roadmap and prunes those deemed unnecessary via a thresholding function. Through its training procedure—leveraging multiple permutations of the same problem instance—and by encoding start and goal configurations as landmarks, the GNN captures structural patterns that generalize across agent assignments. As a result, the reconstructed roadmap is task-agnostic, enabling MAPF algorithm to reuse the same map under different task assignments, making it suitable for multi-agent pick-up and delivery (MAPD) tasks. We demonstrated that our roadmap evaluator reduced the search effort of MAPF/MAPP algorithms, reaching at least 40%40\% reduction in runtime and graph size for dense roadmaps, and potential remove points of congestion or conflict. In future work, we plan to replace the manually tuned thresholding mechanism with a learned thresholding function and extend the framework to explicitly address MAPD problems. Such an extension would enable adaptive, instance-aware pruning, reducing the likelihood of disconnecting critical regions of the roadmap and thereby minimizing the risk of infeasible solutions. References [1] D. González, J. Pérez, V. Milanés, and F. Nashashibi (2016) A Review of Motion Planning Techniques for Automated Vehicles. IEEE Transactions on Intelligent Transportation Systems 17 (4), p. 1135–1145. External Links: ISSN 1558-0016, Link, Document Cited by: §I. [2] M. Khayatian, M. Mehrabian, E. Andert, R. Dedinsky, S. Choudhary, Y. Lou, and A. Shirvastava (2020) A Survey on Intersection Management of Connected Autonomous Vehicles. ACM Transactions on Cyber-Physical Systems 4 (4), p. 1–27 (en). External Links: ISSN 2378-962X, 2378-9638, Link, Document Cited by: §I. [3] R. Kim, V. Madabushi, E. Dong, and A. Mazumdar (2021) Increasing Mobile Robot Efficiency and Versatility Through Manipulation-Driven Adaptation1. Journal of Mechanisms and Robotics 13 (5), p. 050906. External Links: ISSN 1942-4302, Link, Document Cited by: §I. [4] B. Ho, B. Altundas, and M. Gombolay (2025) Towards Learning Scalable Agile Dynamic Motion Planning for Robosoccer Teams with Policy Optimization. arXiv. Note: arXiv:2502.05526 External Links: Link, Document Cited by: §I. [5] M. Andrade, J. Cha, B. Ho, V. Srihari, K. Yadav, and Z. Kira (2025) Let’s Think in Two Steps: Mitigating Agreement Bias in MLLMs with Self-Grounded Verification. arXiv. Note: arXiv:2507.11662 External Links: Link, Document Cited by: §I. [6] J. Alkazzi and K. Okumura (2024) A Comprehensive Review on Leveraging Machine Learning for Multi-Agent Path Finding. IEEE Access 12, p. 57390–57409. External Links: ISSN 2169-3536, Link, Document Cited by: §I. [7] M. Elbanhawi and M. Simic (2014) Sampling-Based Robot Motion Planning: A Review. IEEE Access 2, p. 56–77. External Links: ISSN 2169-3536, Link, Document Cited by: §I. [8] R. Kumar, A. Mandalika, S. Choudhury, and S. Srinivasa (2019) LEGO: Leveraging Experience in Roadmap Generation for Sampling-Based Planning. In 2019 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), p. 1488–1495. Note: ISSN: 2153-0866 External Links: Link, Document Cited by: §I, §I-B. [9] D. Jia, C. Hu, K. Qin, and X. Cui (2014) Planar Waypoint Generation and Path Finding in Dynamic Environment. In 2014 International Conference on Identification, Information and Knowledge in the Internet of Things, p. 206–211. External Links: Link, Document Cited by: §I, §I-B. [10] Y. Zhou, Y. Lu, and L. Lv (2024) Grid-Based Non-Uniform Probabilistic Roadmap-Based AGV Path Planning in Narrow Passages and Complex Environments. Electronics 13 (1). External Links: ISSN 2079-9292, Link, Document Cited by: §I, §I-B. [11] C. Yu and S. Gao (2022) Reducing Collision Checking for Sampling-Based Motion Planning Using Graph Neural Networks. (en). External Links: Link Cited by: §I, §I-B. [12] C. Henkel and M. Toussaint (2020) Optimized Directed Roadmap Graph for Multi-Agent Path Finding Using Stochastic Gradient Descent. arXiv. Note: arXiv:2003.12924 External Links: Link, Document Cited by: §I, §I-B. [13] K. Okumura, R. Yonetani, M. Nishimura, and A. Kanezaki (2022) CTRMs: Learning to Construct Cooperative Timed Roadmaps for Multi-agent Path Planning in Continuous Spaces. arXiv. Note: arXiv:2201.09467 External Links: Link, Document Cited by: §I, §I-B. [14] F. F. Arias, B. Ichter, A. Faust, and N. M. Amato (2021) Avoidance Critical Probabilistic Roadmaps for Motion Planning in Dynamic Environments. In 2021 IEEE International Conference on Robotics and Automation (ICRA), p. 10264–10270. Note: ISSN: 2577-087X External Links: Link, Document Cited by: §I, §I-B. [15] L. Wu, P. Cui, J. Pei, and L. Zhao (Eds.) (2022) Graph Neural Networks: Foundations, Frontiers, and Applications. Springer Nature Singapore, Singapore (en). External Links: ISBN 9789811660535 9789811660542, Link, Document Cited by: §I. [16] G. Sharon, R. Stern, A. Felner, and N. R. Sturtevant (2015) Conflict-based search for optimal multi-agent pathfinding. Artificial Intelligence 219, p. 40–66. External Links: ISSN 0004-3702, Link, Document Cited by: §I-A. [17] T. T. Walker, N. R. Sturtevant, and A. Felner (2018) Extended Increasing Cost Tree Search for Non-Unit Cost Domains. p. 534–540. External Links: Link Cited by: §I-A. [18] D. Silver (2005) Cooperative Pathfinding. Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment 1 (1), p. 117–122. External Links: ISSN 2334-0924, 2326-909X, Link, Document Cited by: §I-A. [19] M. Phillips and M. Likhachev (2011) SIPP: Safe interval path planning for dynamic environments. In Proceedings - IEEE International Conference on Robotics and Automation, p. 5628 – 5635. External Links: Document Cited by: §I-A, §V-A. [20] L.E. Kavraki, P. Svestka, J.-C. Latombe, and M.H. Overmars (1996) Probabilistic roadmaps for path planning in high-dimensional configuration spaces. IEEE Transactions on Robotics and Automation 12 (4), p. 566–580. External Links: ISSN 2374-958X, Link, Document Cited by: §I-B, 1st item. [21] M. Kallmann, H. Bieri, and D. Thalmann (2004) Fully Dynamic Constrained Delaunay Triangulations. In Geometric Modeling for Scientific Visualization, G. Brunnett, B. Hamann, H. Müller, and L. Linsen (Eds.), Berlin, Heidelberg, p. 241–257 (en). External Links: ISBN 9783662074435, Document Cited by: §I-B, 3rd item. [22] H. Huang and S. Y. Chung (2004) Dynamic visibility graph for path planning. 2004 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) (IEEE Cat. No.04CH37566) 3, p. 2813–2818 vol.3. External Links: Link Cited by: §I-B. [23] A. Andreychuk, K. Yakovlev, E. Boyarski, and R. Stern (2021) Improving Continuous-time Conflict Based Search. arXiv. Note: arXiv:2101.09723 External Links: Link, Document Cited by: §I-B. [24] K. Wahba and W. Hönig (2025) Pc-dbCBS: Kinodynamic Motion Planning of Physically-Coupled Robot Teams. arXiv. Note: arXiv:2505.10355 External Links: Link, Document Cited by: §I-B. [25] Z. A. Ali and K. Yakovlev (2023) Safe Interval Path Planning With Kinodynamic Constraints. arXiv. Note: arXiv:2302.00776 External Links: Link, Document Cited by: §I-B. [26] K. Kasaura, M. Nishimura, and R. Yonetani (2022) Prioritized Safe Interval Path Planning for Multi-Agent Pathfinding With Continuous Time on 2D Roadmaps. IEEE Robotics and Automation Letters 7 (4), p. 10494–10501. External Links: ISSN 2377-3766, Link, Document Cited by: §I-B. [27] A. Moldagalieva, K. Okumura, A. Prorok, and W. Hönig (2025) Db-LaCAM: Fast and Scalable Multi-Robot Kinodynamic Motion Planning with Discontinuity-Bounded Search and Lightweight MAPF. arXiv. Note: arXiv:2512.06796 External Links: Link, Document Cited by: §I-B. [28] P. Veličković, G. Cucurull, A. Casanova, A. Romero, P. Liò, and Y. Bengio (2018) Graph Attention Networks. arXiv. Note: arXiv:1710.10903 External Links: Link, Document Cited by: §IV-B1. [29] J. Zhang and L. Meng (2019) GResNet: Graph Residual Network for Reviving Deep GNNs from Suspended Animation. arXiv. Note: arXiv:1909.05729 External Links: Link, Document Cited by: §IV-B1. [30] T. Lin, P. Goyal, R. Girshick, K. He, and P. Dollár (2018) Focal Loss for Dense Object Detection. arXiv. Note: arXiv:1708.02002 External Links: Link, Document Cited by: §IV-B2. [31] S. Li, X. Xu, L. Nie, and T. Chua (2017) Laplacian-Steered Neural Style Transfer. arXiv. Note: arXiv:1707.01253 External Links: Link, Document Cited by: §IV-B2. [32] I. Loshchilov and F. Hutter (2019) Decoupled Weight Decay Regularization. arXiv. Note: arXiv:1711.05101 External Links: Link, Document Cited by: §V-C.