GraphMP: Graph Neural Network-based Motion Planning with Efficient Graph Search
Authors: Xiao Zang
Miao Yin
Jinqi Xiao
Saman Zonouz
Bo Yuan
Venue: NeurIPS 2023 poster (2023)
Keywords: graph neural network
deep learning

Abstract: Motion planning, which aims to find a high-quality collision-free path in the configuration space, is a fundamental task in robotic systems. Recently, learning-based motion planners, especially the graph neural network-powered, have shown promising planning performance. However, though the state-of-the-art GNN planner can efficiently extract and learn graph information, its inherent mechanism is not well suited for graph search process, hindering its further performance improvement. To address this challenge and fully unleash the potential of GNN in motion planning, this paper proposes GraphMP, a neural motion planner for both low and high-dimensional planning tasks. With the customized model architecture and training mechanism design, GraphMP can simultaneously perform efficient graph pattern extraction and graph search processing, leading to strong planning performance. Experiments on a variety of environments, ranging from 2D Maze to 14D dual KUKA robotic arm, show that our proposed GraphMP achieves significant improvement on path quality and planning speed over the state-of-the-art learning-based and classical planners; while preserving the competitive success rate.

GraphMP: Graph Neural Network-based Motion Planning with Efficient Graph Search
Xiao Zang'
Miao Yin Jinqi Xiao Saman Zonouz Bo Yuan'
Department of Electrical and Computer Engineering, Rutgers University
Department of Computer Science and Engineering, The University of Texas at Arlington
SSchool of Cybersecurity and Privacy, Georgia Institute of Technology [xz514, jx257, ereen.ecerrrutgen edu " "miao.yin@uus yinuuta.eduuu "szonouz6@gatech.co edu
Abstract
Motion planning, which aims find a high-quality collision-free path in the configuration space, is fundamental task in robotic systems. Recently. learning- based motion planners, especially the graph neural network-pows poweer., have shown promising planning performance. However, though the state-of-the-an GNN planner can efficiently extract and learn graph information, its inherent mechanism is not well suited for graph search process, hindering its further performance improvement. To address this challenge and fully unleash the potential of GNN motion planning, this paper proposes GraphMP, neural motion planner for both low and high-dimensional planning tasks. With the customized model architecture and training mechanism design, GraphMP can simultaneously perform efficient graph pattern extraction and graph search processing, leading to strong planning performance. Experiments to 14D dual KUKA robotic arm, show that our proposed GraphMP achieves significant improvement on path quality and planning speed over state-of-the wef-the-art art learning-bann based and classical planners; while preserving competitive success rate.
variety of environments, ranging from 2D Maze
Introduction
Motion planning aims find a high-quality collision-fres path connecting the start and goal states in the configuration space of a robot. As fundamental cognitive task in robotic systems, motion planning plays critical role in many practical applications, such as autonomous driving, in- warehouss package handling and assisted surgery, etc. A motion planning problem can be solved from different perspectives. Sampling-basee
solutions, c.g., RRT and its variants [1 2 randomly sample the configuration space to build a space-filling tree, which grows towards connecting the start and goal configurations. Search-based approaches, such as A * and Dijkstra 3 d. interpret the planning as graph search problem, and they then find the feasible path via traversing the graph.
Recently, learning-basee planners have obtained substantial attention because of their comparable or superior performance to classical planners. In general, such data-driven strategy can efficiently learn the patterns in the configuration space and/or the behaviors of the oracle planners, optimizing the important operation (e.g., sampling mechanism) in the planning process, and thus reducing the unnecessary collision check with the improved path quality. To date, various neural network- powered motion planners, including multilayer perceptron (Mb.e) [5), convolutional neural networks (CNN)-based [6], recurrent neural network (RNN) 77] and graph neural network (GNN)-based g 9 have been proposed in the literature. Among these different choices, the GNN- based neural planner is the most promising approach because of its unique advantages processing
"This work was done when the author was with Rutgers University.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Input The Right
Predicted Edge Priurity
GNN-Exxplorr
Edge Prierity
Path
Puth cost - ................................
Goal
Explore
Obstacle
g: Edge Weight
Raw RGG
Predicted Collision-free RGG
Predicted Heuristic Values GraphMP
Path 3
Search
Figure I: The comparison between the key ideas of GNN-Explorer and our GraphMP. The finally identified paths are marked as green lines. The GNN-Explorer first predicts the exploration priority of all edges and then incrementally expands the exploration tree with collision- free edges in sorted order. On the other hand, our GraphMP predicts both the collision status of edges and the heuristic values of all nodes using two neural networks, and utilizes the edge weights to perform the A search. For each step of the A * search, we mark the connection to the candidate nodes with red lines. It is seen that our method fully leverages the information of real accumulated costs during the search procedure, leading to a higher quality of the searched path.
challenging high-dimensional planning tasks. By sampling the continuous configuration space and generating the random geometric graph (RGG), the equipped GNN, which is naturally powerful for learning graph patterns, can applied to predict the priority of nodes (configurations) [9] or edges (robot movement) [8) improving the efficiency and quality of path exploration. In particular, GNN- Explorer [8] as the most recent and representative GNN planner, has demonstrated superior planning performance in series of low and high-dimensional planning tasks than various learning-basee and
classical planners.
However, we believe the potential of GNN-based motion planners is not fully unleashed and the state-of-the-arr solution can be further improved. Our key observation that the edge priority-based path exploration, by its nature, is not the optimal choice for solving graph search problems. For instance, as illustrated in Figure [ neither the edge priority generation nor the path construction process fully considers the impact on the total path cost when selecting a new edge to the current path. In other words, the critical information of the accumulated cost is not properly represented, leveraged or maintained in the existing GNN-based planners, thereby limiting the quality of the finally searched path. On the other hand, the classical graph search approaches, such as A*, can provide the near-optimal solution for finding the shortest path over the weighted graph, if the suitable heuristic function can be identified. Essentially, the key factors for the success of *-lkiee approaches in the graph search task are 1) they fully explore the graph structure via routinely visiting the neighboring nodes; and 2) they formally consider the impact of the accumulated cost during path exploration: and these two features are exactly what the existing GNN and most of other learning-based planners lack.
Motivated by these insights, in this paper we propose to simultaneously leverage the advantages of GNN and graph search algorithm, leading to an efficient neural motion planner, namely GraphMP. GraphMP first effectively extracts and learns the important patterns in the configuration space via its GNN modules, and then identifies the near-optimal path over the processed RGG using its low-cost graph search component. More specifically, to enable this processing pipeline, a GNN-based neural collision checker and neural heuristic estimator are proposed to extract key graph information from input RGG and provide it to A* module, which is also reformulated in the differentiable way to facilitate end-to-end training. More details of GraphMP is shown in Figure 2 and described in Section 3 We evaluate GraphMP and other Icarning-baac based and classical planners in a variety of environments, ranging from 2D Maze to 14D dual KUKA robotic arm. Experimental results show that our proposed GraphMP achieves significant improvement on various planning performance metrics (i.e., path quality and planning speed) over the state-of-the of-the-art planning methods; while preserving the competitive success rate.
2 Related Work
Today's 's most popular motion planners are either search- or sampling- based. Search-based planners, including BFS [0) Dijkstra [4], and A * 33 are typically used for finding optimal paths in low-dimensional environments. Different from BFS and Dijkstra that are significantly slow in large maps, A is an informed search algorithm that uses a heuristic function to guide the search towards the goal, significantly reducing the search space and improving the search efficiency.
Classical Planners.
2

---

Neural Collision Checker (NCC)
Edges
Obstacles
Nodes
Training
Raw ROG
Predicted RGG
Omcile Collision-fres free RGG
Start Goal
Back-gropagation
NCC
NCC
Loss
g: Edge Weight
Afterton
Afterton
n: Predicted Value
Edge
Node
Collision- free RGG
Predicted Houristic Values
Explored Nodes
Nodes Optimal Path
Emnhedding
MLP
Embockling
NHE
NHR
Differentiable. A
Loss
Predicted Collision Probability
Neural Heuristic Estimator (NILE)
Edges
Guaal
Nodes
Inference New Task
b. Sampled Nodes
Raw RGG
d. Predicted RGG
O
Sample
K-NN
NCC
Message Passing
Node
GraphMP
c. Predicted Heuristic Values
f. Searched Path
Final Path Lory zode
Embedding
[Loll Classical
2 L LaxyNodeRemoval
NHE
MLP
Predicted Heuristic Valaes
Figure 2: (Left): The architectures of neural collision checker (NCC) and neural heuristic estimator (NHE). The neural collision checker takes a raw RGG and obstacles as input and predicts the collision status of all edges. The neural heuristic estimator takes the collision-free RGG and the goal input and predicts the heuristic values of all nodes. (Top right): The independent training phases of NCC and NHE. Notice that here design and utilize a differentiable graph-based A concatenated to NHE, enabling their joint training in an end-to-end manner. (Bottom right): The main steps of the inference phase solve the planning task. Once a valid solution is found, we perform the lazy node removal to further reduce the path cost.
Motivated by this benefit, many variants of A have been developed, such as D* 11 WA* * 12 and Hybrid-A* [13. The heuristic functions adopted in these methods are typically admissible hand-craft versions, such as Euclidean distance and Manhattan distance.
Unlike sourch-based planners, sampling -ased planners probe the high-dimensionas configuration space with random sampling. alleviating the exponential complexity growth incurred by the increasing number of dimensions. In general, this type of planner first constructs a randomly sampled graph, and then explores the feasible path over the sampled graph. One important sub-category of sampling- based planner is tree-based solution, including RRT [.. RRT [14] and Informed-RRY) [15] etc.
Some other popularly used sampling-bass based planners include PRM [6]. BIT 2 and LazySP 17.
Learning- based Planners. Recently, a series of learning-based methods further extend the search- based planners by producing better heuristics guide the search. For instance, SAIL [18] trains heuristic policies by imitating clairvoyant oracles and demonstrates the capability of reducing search effort. [19 and (20) Iearn the heuristic functions using the U-Net [2] and transformer [22] architecture, respectively. On the other hand, VIN (3 and SPT (24) learn the planning policy directly, and (25) develops the differentiable solvers for integer linear optimization problems by treating them as black boxes. Furthermore, Neural Weighted A (26) learns the image-format graph costs and heuristics simultaneously via being supervised under the planning examples. Neural A* (2 proposes to reformulate the entire procedure of the canonical A search algorithm to be differentiable, enabling the end-to-ending training of a guidance map for 2-D path planning tasks. However, this method still relies on hand-crafted heuristic function and can only be applied to 2D images, hindering its applications.
In addition, a variety of deep learning-powered sampling-based planners have also been proposed in the literature. Fastron [28] and ClearanceNet (29 Iearn the function approximators to facilitate collision detection. On the other hand, LEGO (30] and (31) predict the high-quality sampling distribution using conditional variational auto-encoder (CVAE), reducing the exploration effort. MPNet [5] and STP-Net 77 predict the next sample directly by encoding the environments together with the configurations via the contractive nuto-encoder (CAE) and convolutional layers, respectively. In particular, motivated by their powerful capability of learning the topology of environments of any dimension, the application GNNs in motion planning has gained popularity in recent years. [9] introduces a GNN-based sampler to predict the critical node in randomly generated graph, showing promising performance for identifying the optimal samples in high-dimensional tasks. (8] proposes GNN- GNN-Explorer which prioritizes the exploration of graph edges in the planning process. Since the planner can now focus on the most promising paths first, the planning efficiency of GNN-Explorer is significantly improved, outperforming various classical and learning-bass planners.
3

---

3 Our Approach: GraphMP
3.1 Preliminaries
Consider motion planning problem defined in the d-dimensional continuous configuration space X, where Xasa is the obstacle space and Xree X' \ Xots the free space. Given an RGG G = (V.E) V. where V is the set of nodes sampled from Xreee and E is the set of weighted edges constructed by K-nearest neighbors (KNN). A motion planner aims to find a collision-fii path that connects the source node Us and goal node Ui by collision-free path. The prior work GNN-Explorer [8] initializes an exploration tree T rooted from Us, and visits edges e E E sorted by their predicted priorities. Each visit performs the accurate collision check on the edge and tries to append it into T, until 8g is reached. Here the search of GNN- -xpllorrr relies on the predicted edge priorities without fully exploring graph structure and formally consider the impact of accumulated path cost during the path exploration, thereby hampering the path quality. On the other hand, graph-based A+ computes the path from Us by iteratively selecting the best candidate Usel arg min (v() + f(v)) from the open list O. Here, (v) accumulates the actual cost from Vn to v and f()) estimates the heuristic value of the cost from e Ug. Once Use! selected, each of ites reachable neighboring nodes Undr E Vaet is checked and updated. By using this way, A* can better explore graph stcuture and perform cost-aware search, but it requires manual design of high-quality heuristic function h(v). which is a challenging task for high -igh-dimensional tasks. Also, visiting the neighboring nodes can be time- consuming because the accurate collision check must be performed on each edge ev.nt. To overcome these limitations of prior works. GraphMP proposes to use GNN to extract and learn the important patterns of RGG, and then identifies the near-optimal path using learnable graph search component. More specifically, a neural collision checker and a neural heuristic estimator are proposed to extract key graph information from input RGG and provide to the proposed reformulated differentiable A* module for end-to-end training. Therefore, the path planning is now graph structure- and cost-aware process with powerful graph pattern extraction capability and learnable heuristics function, making it can achieve high planning performance and suitable for both low and high-dimensional tasks.
3.2 Overall Framework
Fig. 2 shows the overall architecture of the proposed GraphMP. In the training phase. a neural collision checker takes the raw RGG and obstacle information as input and predicts the collision status of all edges. The difference between the estimated and ground-truth collision-free RGGs serves as the training loss to improve the prediction quality of the neural collision checker. Meanwhile, neural heuristic estimator is also individually trained to assign the proper heuristic value to each node in the ground- truth bollision-free RGG, making the graph search-based planning become possible. Here in order to make the neural heuristic estimator learnable, its predicted heuristic values are sent * module to generate a list of nodes that should be visited. The difference between this predicted node list and the optimal path is then calculated as the training loss, guiding the update of neural heuristic estimator. Notice that the A * module in the training phase is designed in differentiable way to enable the backward propagation of gradients. More details will be described in Section 3.5
After individually training neural collision checker and neural heuristic estimator, these two modules are then concatenated in the inference phase. More specifically, neural collision checker first predicts the potential collisions existed in the RGG and generates predicted collision-fres RGG. The neural heuristic estimator then assigns the estimated heuristic value to each node of this roughly collision- free RGG, enabling the graph search-based planning via A module. Notice that because in the inference phase the input RRG of A* is only approximately collision-free without guarantee, non-differentiable classical A* is adopted here to incorporate the potentially additional collision check during the search procedure. After the nodes of a collision-free path are finally identified, a lazy node removal (details in Section 3.5 is performed to further improve path quality.
3.3 Neural Collision Checker
Because detecting the potential collision of an edge, by it nature, can be interpreted as a binary classification problem, we build neural network-based collision checker to roughly predict the collision status of the edge esj in the input RGG G = (V,g) with obstacle information Xass:
True
if PZ(eg) > 0.5 otherwise,
Bgj is collision-free
(1)
False
4

---

Step
Step 2
Step
Step
10111
11010
2
2
01101
01010
4
4
02200
3
4
3
4
3
4
3
20342
W
04202
23020
2
2
3
2
2 Goal reached
02020
Duc (85360)
p000
00
Selected Node &
Vee
Vacl
Vobr
Explore Neighbors
DyT
0
00
0
Update Daces
bace
No
Dace
Dacc
Vsel
O, & C
Start mude:
Goal mude:
Selected node
O Node in the closed list
Connection to explored mode
Figure 3: An example of performing the differentiable graph- a to find path from node to node 4. Given a weighted graph, A, W and bheu are the corresponding binary adjacency matrix, weighted adjacency matrix and the heuristic values, respectively. At each step, we first compute the lowest-cost candidate Vael according to Eq. 3nd explore its neighboring nodes Vnbr via Eq, [5] The accumulated cost bace is updated via Eq. 7 Besides, we keep track of the nodes to be visited and have been visited by updating o and via Eq. 4 and Eq. 8 Once the goal is reached, all the visited nodes are recorded in the closed list vector c.
where I(es)) is the function that gives the index of Eij in the edge set E, and p (po. PL. PIe..- is the collision-free probability vector that can be calculated as: p (proosSae (V, E, Xobs)) ). Here
foe is the attention-ben based iterative obstacle encoder [8] that encodes the information of input RGG and obstacles to concatenated embedding vector (z)") 2)) x =) Miy (t) for each edge eij.
(1)
(1) where x!!") and V.y denote the node embedding of o and edge embedding of esy the 1-th iteration of obstacle encoding. respectively. is then processed by three-layer MLP fyrob to calculate the collision-free probability for each edge eiy. More details foe and fpros are in the Appendix.
Training Procedure. In the training phase the neural collision checker is individually trained on
batches of collision check problem instances ((V()) 2'(0) where the collision-free probabili- ties of all the collision-fre edges in the i-th problem instance is set as I, otherwise 0. The accurate labeling on the training data is provided by the oracle collision checker. The difference between the estimated collision-free probability vector and the binary representation of the ground-trui label, is measured via calculating binary cross-entropy (BCE) loss and minimized during the training procedure to improve the prediction quality of neural collision checker.
3.4 Neural Heuristic Estimator
Given the input collision-free free RGG Grree EVeErree) and goal node ug. the neural heuristic estimator is constructed as a graph neural network (GNN)-based module to predict the heuristic value bhea,; for each v; V. To that end, two MLPs (detailed in the Appendix) are first used to embed the information of U; and eij to latent space as qi
(0) E &R and i E R24, respectively, where da is the embedding size, and then the GNN iteratively updates the node and edge embeddings via aggregating the local information of each node from its neighbors (wv))) = {uyleis E Effree as follows:
(1) = max max (15a(0:) -3 23 m
FTg)l 1es (N(m)))) (+1) = g(o: mm (0),) di
Vu, E E
11 (I+1) = max(r!) (g
(1)
(1) 1 1
1), Veig E E
Here, 9. fg and fr are two-layer MLPs with output dimension dr. After L iterations, the heuristic value of node is calculated via encoding the node embedding q. (L) as bhen, = Soat ()) where foot is layer MLP.
5

---

3.5 Differentiable Graph-based A
In order to ensure that the neural heuristic estimator can provide good estimation of heuristic value for graph search-based planning, in the training phase it is concatenated to the A module, allowing the final planning result to directly guide the training procedure. However, challenging issue for enabling such end-to-end learning is the con-differnntiabiliyy of A*, incurred by the discrete nature of its incremental search procedure. Notice that though [27] proposes a differentiable rriddbased A this existing solution can only work for 2-D grid search and planning; while addressing the non-differentiabiiiy of the more general graph-based A which is used for our proposed GraphMP towards high-di nigh-dimensiona planning, is non-trivial and not explored yet.
Next we describe the key reformulation for differentiable graph A*, which is illustrated in Fig. 3 Recall that the essence of A on free = (V, 17,&fre)) is to iteratively select and move the node associated with the lowest path cost from open list O which contains all the currently candidate nodes, to the closed list C that stores the visited nodes, and explore the neighbors of the selected nodes to expand O (More details of A are described in the Appendix). To make this
procedure differentiable, we first use two binary vectors E [0, 1]ly and E [o, 1]MM to represent the nodes information in O and C, respectively, where the 1 entries indicate the contained nodes. Also, the accumulated costs and the estimated heuristic values of all the nodes in V are denoted (bhea. bhea, .... (/eu, respectively, where bncn. is predicted by the neural heuristic estimator. Then, the operations of selecting the lowest-cost node in O and moving it from O to C can be vectorized via using a one-hot vector Vsel E [0, 1] as follows:
as real-valued bace= (baer,0; b ...y [VI_) and bben
exp( (Dace + b 1/2) 2
Vsel Imax
(3)
exp( (ap(--bacc + bheu)/ )/
0 Vsel: C = c + Vsel-
(4)
Here similar to [27]. element-wise product @ is used to mask the nodes in C, and À and Imax (-) are the pre-set parameter and the function returns a one-hot vector with the "I" entry associated with the lowest path cost (baco, + i). Vsel is then further used to vectorize the neighborhood exploration process. To be specific, let A E {0, 10,1)
x VI and W E IR [V|[VV] denote the unweighted and the weighted adjancency matrix of & frees respectively. Accordingly, the neighboring nodes that should be explored can be represented as
Vnbr Avsel @ (1 c).
(5)
where Vabr E [0, 1][M| is the binary vector marking the entries corresponding to the neighboring nodes as ones, and 1 is the all-one vector. Notice that here the indices of the neighboring nodes that are already in the closed list C are masked out via using (1 - c). Upon the identification of these newly explored neighboring nodes, the accumulated costs g and the vectorized open list are further updated as:
acc bacc C Vsel + W
(6)
((1-00) + (bace bace)) @ Vnbr, bace = bace ① (1- - b)) + bacc O d
(7)
o = o + (1 o)Vnnr:
(8)
where bree denotes the accumulated costs of the nodes that are associated the path containing the selected node. The operation bace > b'es compares the node-wise accumulated costs and yields a binary vector of length [V]. More specifically, bace O Vael extracts the accumulated cost of the currently selected node, and W represents the distance from the selected node to each of its neighbors. Notice that as shown in Eq. 7 the accumulated cost of neighboring nodes are updated in two cases: (1) the nodes do not exist in O; and (2) the nodes are in O but its current accumulated cost is already smaller than the updated one. The identification of such two types of nodes are realized by binary vector Φ. After updating the accumulated costs, the open list O is expanded by adding newly explored neighboring nodes ().
End-to-End Training. With the differentiability of graph-based A neural heuristic estimator and graph search planning can be now jointly trained in an end-to-end way, providing better guidance of learning heuristic values. [ the overall training procedure.

---

Algorithm End-to-End Training Framework
Input: Full training set Pheu. neural heuristic estimator Sheu (V, Uy @hou) with weights hea.. the max iteration mon, learning rate y
1: for (V(9), ,&free: Us (6) g 1/g c(()) in Dheu do g(5)
2: Predict bheu Sneu (2(6), freet v/y (8)
hheu) Predict the heuristic values.
3: bace + 0, O t V. c 5+-0. O.
maaz do 5: Select Veel via Eq. [q
4: for = 1,
6: if Vaal Vg then Break Vg the one-hot vector representing the goal v/
if sum
then Break Early stopping when the open list is empty.
o f o - Vsel. c t c Vsel-
9:
Vnbr + Avsel @ [1 - c).
10:
bace + bace @ (1 + + Dace 2 + (Eq.
11:
+ ++ (1 Vnbr.
12:
end for
(())) is [ binary vector marks nodes along the optimal path as ones.
14: Compute the loss Cuen +- ||e(t) clh-
Update weights h t- hea 7 V Chew.
16: end for
Lazy node
Path 4,37
Path
Path 13.55
Puth 8.90
(a) Key idea of LNR. Figure 4: The key idea of lazy node removal (LNR) and the examples of applying LNR on maze and 7D KUKA environments. We compare the paths before LNR (left) and after LNR (right).
(b) 2D
(c) 7D KUKA.
3.6 Inference Procedure for Online Planning
As illustrated in Fig. 2 when GraphMP performs online planning (detailed in the Appendix) for the new task, non-differentiabee classical A module adopted to perform graph search on approximated collision-fiee RGG prepared by the neural collision checker. Here the heuristic values desired in the search procedure is predicted by the neural heuristic estimator. Notice that in order to reduce the computational cost and path cost, the following two optimization operations adopted in the inference procedure.
In-Search Collision Check. Due to the approximation property of neural networks, some edges in the approximated collision-free RGG may collide with the obstacles. We integrate the accurate collision check into A* search that only occurs necessary edges with low prediction confidence. specifically, we perform the time-consuming accurate collision check only when (1) the neighbor of one selected node is explored, and (2) the collision-free probability of the corresponding edge is lower than a threshold 0. Such operation balances the trade-off between the planning efficiency and the path safety.
Lazy Node Removal. After * finishes the path search, lazy node removal is performed further reduce path cost. As illustrated in Fig. 4 within the planned path, the pairs of the nodes that are directly connected are iteratively checked see whether if the potential direct connection new edge) is collision-fres and brings shorter path. If so, the two nodes can be connected and the nodes between them are removed as "lazy nodes". In general, the worst time complexity of lazy node removal is O(T²), where 7' is the number of nodes in the path found by A Since the searched path typically contains only few nodes (T is small), this technique effectively reduces the path cost with minor computing overhead.

---

Prediction acouracy and confidencee (%)
cosl per graph (ms)
Path cost
100
Acouridy
Conficonee
20:
A1 with NIE
Vam
Snaker
Maned
Sraka7 KUKAIDKUNA14
Meano
URS
Stake? KUAAT KUKASBKLKACE
(a) Performance of NCC.
(b) Performance NHE.
Figure 5: (Lefft): The performance neural collision checker (NCC) on 1000 raw RGGs with 300 nodes and K-value of 10 (K-NN). (Right): The comparison between A with the heuristic function of neural heuristic estimator (NHE) and vamilla A#, with respect to the mean path cost. More numerical results are the Appendix.
Results
4.1 Dataset and Experimental Setup
We demonstrate the effectiveness of our algorithm in six types of planning tasks the same in g
(1) Maze2: 2 DoF point-robot in 2D maze workspace of dense obstacles, (2) Ur5: a 6 DoF UR5 robot in 3D workspace, (3) Snake7: DoF snake robot in 2D workspace, (4) Kuka7: 7DoF KUKA
arm in 3D workspace. (5) Kukal3: a 13 DoF Kuka arm in 3D workspace, and (6) Kukal4: pair of
7DoF KUKA arms in 3D workspace.
For each environment, we prepare two different training datasets each of which consists 2000 different workspaces, train the neural collision checker and heuristic estimator separately. For each workspace, we randomly construct 20 RGGs by sampling a random number of nodes ([100, 200, 300, 400]) and random value of KNN ([5, 10, 15, 20]). Specifically, for the neural collision checker, each problem contains the raw RGG built on a set of randomly sampled free states and the different set of obstacles, while the ground-truth is the collision-free RGG obtained the oracle collision checker. For the neural heuristic estimator, each problem contains a feasible pair of U, and Bg. the exactly collision-free graph, and the ground-trute is the optimal path computed by Dijkstra. We also use 500 problem instances as the validation set. We keep the weights of heurisitic estimator which yields the smallest average path cost on the validation set. After the training, GraphMP is evaluated in an end-to-end manner on 1000 problem instances with unseen workspaces. Each input of the testing problems contains pair of U and lgg. and set of obstacles.
Our neural collision checker adopts 3 iterations of obstacle encoding with an output dimension of 64, and the neural heuristic estimator has loops of message passing in Eq. with the output dimension of 32. For both training of these two models, we select ADAM 32 as the optimizer and set the learning rate 1e-3 The training epoch is 400 and the batch size is in the in-search collision check as 80%. The number of graph nodes per sampling is 100 and the K value K-NN 10. The experiments are conducted on a computere quipped with an AMDEPYC 74202P24-Core Processor and an NVIDIA RTXA6000 GPU.
8. We set the threshold
Baselines. We evaluate the performance of GraphMP by comparing it with three classical planners (BIT*, RRT* and LazySP) and one state-of-the-ar learning-bait based planner addition, the Smoother proposed in serves an additional step to reduce the path cost of the
In
Table 1: The overall success rate 1000 testing problems for each environment. GraphMP archives nearly 100% success rate across all environments, being competitive with other baseline planners.
Maze2
UR5
Snake7
KUKA7
KUKA13
KUKA14
BIT
1.00
1.00
1.00
1.00
1.00
1.00
R
0.54
0.39
0.69
0.83
0.67
0.70
LazySP
1.00
0.99
1.00
1.00
0.99
0.99
GraphMP
1.00
0.99
1.00
0.99
1.00
0.99
GNN-Explorer
1.00
0.98
1.00
0.99
1.00
0.99
GraphMP with Smoother
1.00
0.99
1.00
0.99
1.00
0.99
GNN-Explorer with Smoother
1.00
0.98
1.00
0.99
1.00
0.99

---

Table 2: Mean path cost on 1000 testing problems for each environment. GraphMP with Smoother achieves the lowest path cost across all environments, compared to the baselines with similar success rate. (The success rate of RRT* on Maze2 is 54%.)
Maze2
UR5
Snake7
KUKA7
KUKA13
KUKA14
BIT
2.52
11.20
5.96
7.59
12.07
12.05
RRT*
1.82
10.35
5.06
7.07
10.03
10.65
LazySP
2.63
11.81
6.52
9.49
16.72
16.82
GraphMP
2.33
8.09
5.68
7.01
13.57
12.22
GNN-Explorer
2.80
12.61
6.50
9.15
16.75
16.50
GraphMP with Smoother
1.96
7.73
5.02
6.27
9.26
9.89
GNN-Explorer with Smoother
2.36
8.87
5.31
6.55
9.92
10.01
Table 3: The mean time cost (ms). GraphMP demonstrates the fastest planning speed, among 4 of environments.
Maze2
UR5
Snake7
KUKA7
KUKA13
KUKA14
BIT
125.2
541.2
161.1
407.0
352.6
205.2
RRT* SP
200.4
432.0
436.5
175.3
506.4
423.7
GraphMP 334.0
921.8
144.7
401.8
224.5
404.9
124.5
192.6
211.6
59.3
116.3
95.5
LONN-Explrce
155.5
332.9
222.9
93.3
101.9
120.3
GraphMP with Smoother
140.9
363.0
268.1
65.6
142.7
120.4
GNN-Explorer with Smoother
175.7
529.3
293.0
107.3
136.2
150.7
computed path. Therefore, we also compare the performance of GraphMP with Smoother and GNN-Explorer with Smoother.
Ablation study. Details are reported in the Appendix.
4.2 Comparison With Baselines
Experimental results show that our GraphMP achieves 98.6% 100% success rate across all the environments, being competitive to the state-of-the-art planners (Table [.. Table ? shows that GraphMP achieves 16.79% 35.84% 12. 12.62% 23.39%, 18.99 18.99% and 25.94% shorter paths than GNN- Explorer, on Maze2, UR5, Snake7, KUKA7, KUKA13 and KUKA14, respectively. Furthermore, the GraphMP with the path smoother has the lowest path cost compared to all baselines with competitive success rate. Table compares the time cost of all the motion planners. Compared to GNN-Explorer GraphMP finds valid solutions with 19. 944, 14%, 5.07%, 36.44% and 20.62% lower time cost Maze2, UR5, Snake7, KUKA7 and KUKA14, respectively. Overall, the results indicate that GraphMP outperforms all baseline planners by producing high-quality paths with the fastest planning speed and nearly 100% success rate in most of the planning tasks from 2D to 14D.
4.3 Study of Individual Modules of GraphMP
The Performance Neural Collision Checker. We first evaluate the neural collision checker by reporting the mean prediction accuracy, confidence score and time cost. Specifically, the mean prediction accuracy and confidence are measured by averaging over all the edges from the test graphs, and the mean time cost represents the latency of predicting all edges per testing graph. Fig, 5 shows that our neural collision checker can perform super fast and accurate prediction on the graph-level collision check with high prediction confidence, in all the environments.
The Performance Neural Heuristic Estimator. We then evaluate the performance the neural heuristic estimator by comparing the A* with different hcuristic functions. To be specific, equip A with our neural heuristic estimator and the Euclidean function which serves as the commonly used heuristic function to solve planning tasks, respectively. From Fig. 5 it is shown that the A* with our neural heuristic predictor significantly outperforms the vanilla A by producing solutions of lower path cost. The advantage of neural heuristic predictor also grows quickly with the increasing dimensions of the planning tasks. The results illustrate that the neural heuristic estimator learns and performs better search guidance, especially in the configuration space of higher dimensions.
The Impact of In-Search Collision Check (ICC) and Lazy Node Removal (LNR). We further analyze the impact of the ICC and LNR modules GraphMP, to justify their necessity in improving

---

Table 4: The comparison of the path cost and time cost (ms) between different versions of GraphMP. To be specific, the GraphMP w/o ICC uses accurate collision check only. GraphMP achieves the significantly lower path cost compared to the one without LNR with limited time increase, and achieves reduced time cost compared the one without ICC.
Maze2
URS
Snake7
KUKA7
KUKA13
KUKA14
Path
Time
Path
Time
Path
Time
Path
Time
Path
Time
Path
Time
GraphMP w/o LNR
2.82
106.75
9.76
183.84
5.94
208.27
8.83
54.57
15.82
104.29
14.32
88,18
GraphMP wio ICC
2.33
167.85
8.09
258.27
5.68
286.54
7.01
104.94
13.57
162.44
12:24
137.70
GraphMP
2.33
124.47
8.09
192.55
5,68
211.66
7.01
59.34
13:57
116.29
12.24
95.47
the planning performance. Table 4 compares GraphMP with the version without ICC and the one without LNR, with respect to the path cost and time cost, respectively. While all these planners achieve 98.6% 6% 100% success rate across different environments, GraphMP outperforms the version without LNR by yielding 17.38%, 17.11 7..1%, %, 4.38%, 21.92%, 14.22% and 14.53% shorter paths with a limited increase the time cost, on Maze2, UR5, Snake7, KUKA7, KUKAI3 and KUKAI4, 14, respectively. Besides, compared to the one that uses accurate collision check (GraphMP w/o ICC), GraphMP achieves the same path quality with significantly smaller time cost. Overall, it seen that ICC and LNR are effective in improving planning speed and path optimality, respectively.
5 Limitations
Despite its good empirical performance across different tasks, GraphMP still has some limitations. First, it does not provide probabilistic completeness when the collision check threshold 100%. That means, the collision status of some edges is determined by the neural collision checker (NCC), even if the prediction accuracy of NCC high and a collision-free path exists in the input RGG, GraphMP still cannot guarantee to find the feasible solution asymptotically. Notice that though the probabilistic completeness can be achieved when setting 0 100%, the planning time will accordingly increase due to the extra costs incurred by performing accurate collision check on all the explored edges. Second, it does not offer asymptotical optimality. GraphMP performs the graph search on an implicit RGG which is incrementally expanded with more batches of nodes. Once path found, GraphMP validates its legality and returns the solution. Because 1) this mechanism naturally leads that the quality of the sampled RGGs has a heavy impact on the path cost - the waypoints along the paths are restricted to be subset of the existing nodes of RGG, but RGG itself cannot be guaranteed to contain the optimal path; and 2) the search process will be terminated once the path is found, without further seeking better solutions, GraphMP cannot thcoretically guarantee to find the optimal path asymptotically. Third, its efficiency is still limited by inefficient RGG construction. More specifically, 1) the uniform sampling nodes disregards the environmental topology, causing some unnecessary node exploration; and 2) the construction of raw edges is also involved with unnecessary edge generation, thereby limiting the further runtime speedup provided by the proposed approach.
6 Acknowledgement
This work is partially supported by National Science Foundation under Grant CCF-2239945, National Science Foundation CPS and SaTC programs.
7 Conclusion
This paper proposes GraphMP, neural motion planner for both low and high-dimensional planning tasks. With the customzied model architecture and training mechanism design, GraphMP can efficiently learn the graph pattern and process graph search, enabling strong planning performance. Experiments on a variety of environments show that GraphMP achieves significant planning speed-up and higher path quality than the state-of-the-at learning- based and classical planners.
10

---

References
[1] Steven M LaValle et al. Rapidly-exploring random trees: A new tool for path planning. 1998.
[2] Jonathan D Gammell, Timothy D Barfoot, and Siddhartha S Srinivasa. Batch informed trees (bit*): Informed asymptotically optimal anytime search. The International Journal of Robotics Research, 39(5)543-5567, 2020.
[3] Peter Hart, Nils J Nilsson, and Bertram Raphael. formal basis for the heuristic determination of minimum cost paths. IEEF transactions on Systems Science and Cybernetics, 4(2):100-107 1968.
[4] Edsger W Dijkstra. A note on two problems in connexion with graphs. In Edsger Wybee Dijkstra: His Life, Work, and Legacy, pages 287-290. 2022.
[5] Ahmed H Qureshi, Anthony Simeonov, Mayur J Bency, and Michael C Yip. Motion planning networks. In 2019 International Conference on Roboties and Automation (ICRA), pages 2118-2124 IEEE, 2019.
[6] Tomas Kulvicius, Sebastian Herzog, Timo Lüddecke, Minija Tamosiunaite, and Florentin Wörgötter. One-shot multi-path planning for robotic applications using fully convolutional networks. In 2020 IEEE International Conference Robotics and Automation (ICRA), pages 1460-1466. IEEE, 2020.
[7] Xiao Zang, Miao Yin, Lingyi Huang. Jingjin Yu, Saman Zonouz, and Bo Yuan. Robot motion planning as video prediction: A spatio-temporal neural network-base -based motion planner. arXiv preprint arXiv: 11287, 2022.
[8] Chenning Yu and Sieun Gao. Reducing collision checking for sampling- based motion planning using graph neural networks. Advances in Neural Information Processing Systems, 34:4274- 4289, 2021.
[9] Arbaaz Khan, Alejandro Ribeiro, Vijay Kumar, and Anthony G Francis. Graph neural networks for motion planning. arXiv preprint arXiv:2006.0624: 2020.
[10] Charles E. Leiserson and Tao B Schardl. A work-efficient parallel breadth-first search algorithm (or how cope with the nondeterminism of reducers). In Proceedings of the !wenty-second annual ACM symposium on Parallelism in algorithms and architectures, pages 303-314, 2010.
[11] Anthony Stentz et al. The focussed d algorithm for real-time replanning. In IJCAI, volume 95, pages (652-1659, 1995.
[12] Ira Pohl. Heuristic search viewed as path finding in graph. Artificial intelligence, 1(3-4):193-
204, 1970.
[13] Dmitri Dolgov, Sebastian Thrun, Michael Montemerlo, and James Diebel. Practical search techniques in path planning for autonomous driving. Ann Arbor, (48100500) 80, 2008
[14] Sertac Karaman and Emilio Frazzoli. Sampling-based algorithms for optimal motion planning. The international journal of robotics research, 30(7):846-89) 894, 2011.
[15] Jonathan D Gammell, Siddhartha S Srinivasa, and Timothy D Barfoot. Informed r: Optimal sampling-based path planning focused via direct sampling of an admissible ellipsoidal heuristic. In 2014 JEFF/RSJ International Conference on Intelligent Robots and Systems, pages 2997- 3004. IEEF, 2014.
[16] Lydia E Kavraki, Petr Svestka, J-C Latombe, and Mark Overmars. Probabilistic roadmaps for path planning in high-dimensional configuration spaces. IEEE transactions Robotics and Automation, 12(4):566-58) 1996.
[17] Nika Haghtalab, Simon Mackenzie, Ariel Procaccia, Oren Salzman, and Siddhartha Srinivasa. The provable virtue of laziness in motion planning. In Proceedings of the International Conference Automated Planning and Scheduling, volume 28, pages (06-113, 2018.
11

---

[18] Mohak Bhardwaj, Sanjiban Choudhury, and Sebastian Scherer. Learning heuristic search via imitation. In Conference on Robot Learning, pages 271 271-280. PMLR, 2017.
[19] Takeshi Takahashi, He Sun, Dong Tian, and Yebin Wang. Learning heuristic functions for mobile robot path planning using deep neural networks. In Proceedings of the International Conference on Automated Planning and Scheduling, volume 29, pages 764-772, 2019.
[20] Daniil Kirilenko, Anton Andreychuk, Aleksandr Panoy, and Konstantin Yakovlev. Transpath: Learning heuristics for grid- briddbased pathfinding via transformers. arXiv preprint arXiv:2212.11730, 2022.
[21] Olaf Ronneberger, Philipp Fischer, and Thomas Brox. U-net: Convolutional networks for biomedical image segmentation. In International Conference on Medical image computing and computer-assisted intervention, pages 234 241. Springer, 2015.
[22] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, tukasz Kaiser, and Illia Polosukhin. Attention all you need. Advances neural information processing systems, 30, 2017.
[23] Aviv Tamar, Yi Wu, Garrett Thomas, Sergey Levine, and Pieter Abbeel. Value iteration networks. Advances in neural information processing systems, 29, 2016.
[24] Devendra Singh Chaplot, Deepak Pathak, and Jitendra Malik. Differentiable spatial planning using transformers. In International Conference Machine Learning, pages 1484-1495 PMLR, 2021.
[25] Marin Vlastelica Pogančić, Anselm Paulus, Vit Musil, Georg Martius, and Michal Rolinek. Differentiation of blackbox combinatorial solvers. In International Conference on Learning Representations, 2019.
[26] Alberto Archetti, Marco Cannici, and Matteo Matteucci. Neural weighted a#: Learning graph costs and heuristics with differentiable anytime a. In International Conference on Machine Learning, Optimization, and Data Science, pages 596-610 Springer, 2021.
[27] Ryo Yonetani, Tatsunori Taniai, Mohammadamin Barekatain, Mai Nishimura, and Asako Kanezaki. Path planning using neural a search. In International conference on machine learning, pages 12029-12039. PMLR, 2021.
[28] Nikhil Das and Michael Yip. Learning- based proxy collision detection for robot motion planning 2020.
applications. IEEE Transactions on Robotics,
[29] J Chase Kew, Brian Ichter, Maryam Bandari, Tsang- Wei Edward Lee, and Aleksandra Faust. Neural collision clearance estimator for batched motion planning. In International Workshop on the Algorithmic Foundations of Robotics, pages 73 73-89. Springer, 2021.
[30] Rahul Kumar, Aditya Mandalika, Sanjiban Choudhury, and Siddhartha Srinivasa. Lego: Lever- aging experience roadmap generation for sampling-bast based planning. In 2019 JEEE/RSJ International Conference Intelligent Robots and Systems (IROS), pages 1488-1495. IEEE, 2019.
[31] Brian Ichter, James Harrison, and Marco Pavone. Learning sampling distributions for robot motion planning. In 2018 IEEE International Conference on Robotics and Automation (ICRA), pages 7087-7094. IEEE, 2018
[32] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint 1rXiv:1412.000 6980, 2014.
12


Reviews:
[{"review_id": "WYAfsQ7JVJ", "reviewer": "Reviewer_3bor", "summary": "This paper presents GraphMP, a neural motion planner that uses GNNs and graph search techniques to do motion planning in various scenarios. GraphMP has two components: a neural collision checker that estimates the collision status of edges in a randomly sampled graph, and a neural heuristic estimator that assigns heuristic values to nodes for directing the graph search. This paper also develops a graph-based A* algorithm that allows end-to-end learning of the neural heuristic estimator. Thi paper evaluates GraphMP on six planning tasks with dimensions from 2D to 14D and demonstrates that it performs better than several classical and learning-based planners in terms of path quality, planning speed and success rate. ", "questions": "- For A* to work provably, how to ensure that the neural heuristic estimator produces admissible or consistent heuristic values?\n- How to handle non-reachable goal states?\n- Can a discussion about different design choices in the algorithm be included?\n", "limitations": "Please include a limitation section", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- This paper provides extensive experiments and comparisons with baselines on various environments and metrics. It shows strong experimental results in many planning settings. \n- The paper leverages the advantages of both GNNs and graph search algorithms to improve performance over existing methods like GNN-Explorer. \n- Effective techniques like in-search differentiable graph-based A*, collision check and lazy nod removal are added to improve the performance of GraphMP.\n", "weaknesses": "- This paper does not study or show how different factors and design choices affect the performance of the proposed GraphMP algorithm, including\n  - number of neighbors (K) in K-NN (was set to 10 and 20 in different experiments)\n  - the graph size\n  - the in-search collision check threshold\n- This paper does not mention the challenges or drawbacks of GraphMP, such as how it deals with dynamic or uncertain settings, or how it adapts to more complicated tasks.\n- It will be helpful to provide more information about how the neural heuristic estimator and the neural collision checker are trained.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate the reviewer's very constructive comments and suggestions. The following is our response in order of questions and comments raised.\n\n>Q1: Impact of K, graph size and $\\theta$.\n\nThank you for pointing it out. **Fig. 2-4 in Sec. 6 (Ablation Study) of Supplementary Material** report the impacts of these design choices on performance. Detailed analysis is also discussed in that section. More specifically, for **varying threshold $\\theta$** of in-search collision check, evaluation results show that time cost keeps increasing with a greater $\\theta$, because more accurate collision check is performed during the graph search; and success rate increases first and then becomes steady when approaching $80\\%$. Therefore, we set $\\theta$ as $80\\%$ to achieve good balance between planning speed and success rate. For **varying $K$ value of KNN**, we report the mean path cost, time cost, and success rate with a fixed batch size of node sampling as $100$. It is seen that the path cost and time cost first decreases and then become stable as $K$ increases. This is because denser graph edges are more likely to compose a shorter path and more connections can improve the exploration efficiency. Meanwhile, success rate first increases and then become stables as $K$ approaches 10. So in our experiments $K$ is set as 10. Note that $K=20$ in Fig. 5 of main paper is only used to show the good performance of NCC, we have updated this figure in **Fig. R2 of Global Response**. For **varying graph size**, we evaluate the performance of GraphMP with respect to different number of nodes per sampling, which corresponds to the incremental graph size. Here the max budget of sampled nodes (maximum graph size) is set as $1000$. It is seen that the time cost becomes the lowest when the number of nodes equals $100$ and then grows with more nodes. This is because too few nodes incur the extra sampling batch, while too many nodes are more than necessary to compute a valid solution. The success rate and path cost achieve the best result when the sampling size is $100$. These figures are also reported in **Global Response (Fig. R3-R5)**.\n\n\n>Q2: Potential limitation, e.g., cannot work in dynamic settings?\n\nThanks for the valuable comments. The limitation of our approach is analyzed in **Sec. 2 of Supplementary Material**. GraphMP may suffer from inefficient construction (uniform node sampling and KNN-based edge connection) of raw input RGG. Without leveraging workspace topology and spatial relationship between the start/goal states, the raw RGG requires more than necessary nodes and edges to cover the configuration space. Our future work will explore how to directly learn the biased node sampling and construct necessary edges.\n\nWe believe it is feasible to extend GraphMP for dynamic changing environment. Considering the obstacle's movements are typically predictable, instead of predicting a single-value collision probability for each edge, NCC can learn to predict a vector of probabilities where each entry represents the probability at the corresponding time window. The A* search then looks up the edge probabilities at each timestamp, and plans over an updated collision-free RGG without heavy collision checks, making GraphMP adaptive for dynamic planning.\n\n\n>Q3: More information on training NHE and NCC.\n\nThanks for the suggestion. The training data consists of 2000 different workspaces for both NCC and NHE. For each workspace, we randomly construct 20 RGGs by sampling a random number of nodes ([100, 200, 300, 400]) and a random $K$ value of KNN ([5, 10, 15, 20]). Adam optimizer is used for both training of NCC and NHE, and the learning rate, training epoch and batch size are set as $1e^{-3}$, $400$ and $8$, respectively.\n\n**For NCC training**, given the input data as the raw RGG and the ground-truth output as the collision status of all edges, NCC predicts the probabilities of being collision-free for all edges in parallelism, and the binary cross-entropy loss is adopted. **For NHE training**, as shown in **Algorithm 1**, given a collision-free RGG $G = (V, E_{free})$ and start/goal nodes ($v_s$, $v_g$), the ground-truth output is a length-$|V|$ binary vector ($\\hat{\\mathbf{c}}$), denoting the optimal path computed by Dijkstra. NHE predicts a length-$|V|$ vector $\\mathbf{b_{heu}}$ where each entry denotes the heuristic value of the corresponding node. Differentiable A* performs A* search to calcualte $\\mathbf{c}$, a length-$|V|$ binary vector that is repeatedly updated by marking the explored nodes as ones. The difference (L1 loss) between $\\mathbf{c}$ and $\\hat{\\mathbf{c}}$ is measured as training loss. \n\n>Q4: Admissibility/consistency of NHE.\n\nThank you for valuable comments. Empirical evaluations show that NHE exhibits admissibility and consistency. Denote $f(v_i)$ be the heuristic value of node $v_i$ and $c(v_i, v_j)$ be the actual cost between $v_i$ and $v_j$. As shown in the left figures (heatmaps) from **Fig. R1(a)(b) of Global Response**, $|f(v_i) - f(v_j)| - c(v_i, v_j)$ for each edge $e_{ij} \\in E$ is non-positive for most cases, indicating good consistency for NHE. The right figures in Fig. R1(a)(b) also show that $f(v_i)$ estimated by NHE is constantly smaller than actual cost $c(v_i, v_g)$ ($v_g$ is goal node), indicating good admissibility of NHE.\n\n\n>Q5: How to handle non-reachable goal states?\n\nThanks for pointing this out. GraphMP uses batched sampling strategy for the case when goal is not reached. As shown in  **Algorithm 4 of Supplementary Material**, GraphMP first constructs a raw RGG using a single batch of nodes and searches for the collision-free path. If the path is not found, i.e., the goal state is not reached, another batch of nodes are sampled and appended to the graph. The above procedure is repeated until the collision-free path is found or the maximum budget of samples is reached. Accurate collision check is performed  on the final computed path to verify the legality."}, {"review_id": "wsbr13S3Ob", "reviewer": "Reviewer_KcNw", "summary": "The paper extends the previous GNN-Explorer work and replaces its greedy search strategy with A* search using a neural heuristic. Furthermore, it utilizes the neural collision checker and lazy node removal to improve the success rate and path cost. The result is evaluated based on a benchmark from 2D maze to 14D dual arms and shows that it outperforms the baselines.", "questions": "1. I wonder how sensitive the algorithm is to the hyperparameter θ. As claimed in the paper, this parameter balances the trade-off between the planning efficiency and the path safety. So could you please give an ablation study on how robust the algorithm is to the choice of θ?\n\n2. Do you mind providing the TP, TF, NP, NF scores for Figure 5 (Left)? I would love to know more about whether this neural collision checker is overestimating or underestimating the collision risk.\n\n3. During training, does the NHE take the graph input that is predicted and filtered by the NCC, or does it completely take a collision-free RGG? If it is the later one, then there might be some distribution shift happening during inference.", "limitations": "Please discuss the limitations, since I do not see the texts mentioning the limitations. An obvious limitation is that the algorithm is not complete. For example, it is possible that the neural network predicts an edge to be collision-free with very high confidence (say 90%), and the algorithm could find a path that is actually in collision because of it.\n\nI do not see any noticeable negative societal impact.", "rating": 7, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. The approach is clear and easy to understand.\n2. The extensive results on 6 environments seem thorough and show the soundness of the approach. Especially for UR5, the planning time is fast.\n3. The ablation studies show the effectiveness of each key component.", "weaknesses": "1. The novelty is incremental. All the key components can be found in previous works, including graph-based search (from GNN-Explorer), neural heuristic and differential training (from neural A*), neural collision checker (from Fastron and ClearanceNet), and lazy node removal (from Motion Planning Networks). \nHowever, combining them and showing validness is also important, therefore, I recommend borderline acceptance.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate the reviewer's very constructive comments and suggestions. The following is our response in order of questions and comments raised.\n\n>Q1: Technical novelty.\n\nThanks for the valuable comments. As we state in the Related Work Section, neural network-enabled motion planning is an active research field in recent years, and different components of planners have been studied from learning-based perspective in the literature. Compared with the existing efforts, GraphMP has several technical contributions.\n\nFirst, as analyzed in Introduction section, GNN-Explorer essentially uses GNN to identify edge priority to grow the exploration tree. Due to its tree exploration-based planning strategy, the mechanism of GNN-Explorer mainly focuses on finding edge priority (a type of \"hard\" information). Instead, GraphMP does not use tree-based exploration and the GNN in GraphMP serves to learn the graph information to estimate heuristic values. Therefore, GraphMP fully explores graph structure and properly considers the impact of critical accumulated cost (a type of \"soft\" information) in the planning phase, providing better planning performance (success rate, path cost and planning speed) than GNN-Explorer.\n\nSecond, as mentioned in Section 3.5,  Neural A* is a work focusing 2D planning task. More specifically, it estimates the cost from the source to all nodes instead of learning heuristic values of each node. Also, it uses convolutional layers to process the input image information, limiting to the grid-based 2D planning task. On the other hand, the GNN-based model structure and the differentiable training of GraphMP is designed for graph input and can be applied to planning tasks of any dimensions. \n\nThird, both Fastron and ClearanceNet are designed for predicting whether a single node (robot state/configuration) is in the obstacle space or not. To check the collision status of the edge (robot movement), these two methods need to discrete the edge to a set of points and then examine each point. Instead, GraphMP uses neural collision checker (NCC) to learn the collision status of edges, therefore it can directly check the clearance of all edges in the graph without discretizing edges into points.\n\nAlso, we agree that removing redundant nodes/states to improve path quality is a common post-processing practice in the motion planning literature, and the shortcutting methods in our work and MPNet can be viewed as the simplified version of the path smoothing with shortcutting heuristic. This operation makes trade-off between path quality and planning time and can be optionally used if required. We will add the related path smoothing literature and discussion in the updated version.\n\n\n>Q2: Sensitiveness of $\\theta$.\n\nThanks for pointing this out. Ablation study on the impacts of $\\theta$ on planning time and success rate are reported in **Fig. 2 of Supplementary Material**. It show that larger $\\theta$ brings higher time cost due to the increasing demand of accurate collision checks. On the other hand, the success rate first increases with larger $\\theta$, since smaller $\\theta$ causes more aggressive approximated collision check, potentially bringing collision-existed solution. Considering when $\\theta$ is approaching 80%, the success rate becomes steady across different environments. therefore we adopt $\\theta$=80% in our experiments to make good balance between planning speed and success rate. These figures are also reported in **Fig. R3 of Global Response**.\n\n>Q3: TP/FP/TN/FN scores of NCC.\n\nThanks for the suggestions. The following table R1 reports TPR/FPR/TNR/FNR of NCC for Fig. 5. It is seen that NCC has sufficiently large TPR and TNR and small FPR and FNR, demonstrating good prediction capability. Based on this well-performed NCC, the success rate of GraphMP is 99%-100% across different tasks (reported in **Table 1 of main paper**). \n\n**Table R1. TPR, TNR, FPR, FNR of NCC.**\n|     | Maze2 | UR5   | Snake7 | KUKA7 | KUKA13 | KUKA14 |\n|-----|-------|-------|--------|-------|--------|--------|\n| TPR | 98.84 | 93.15 | 96.41  | 94.29 | 93.73  | 91.86  |\n| TNR | 98.93 | 93.17 | 96.35  | 94.37 | 93.77  | 91.92  |\n| FPR | 1.07  | 6.83  | 3.65   | 5.63  | 6.23   | 8.14   |\n| FNR | 1.16  | 6.85  | 3.59   | 5.71  | 6.27   | 8.08   |\n\n>Q4: Input graph for NHE training.\n\nThank you for this valuable question. In the training process the input of NHE is the completely collision-free RGGs instead of predicted RGGs from NCC. The reason why we make this design choice is that the predicted RGGs generated by NCC can potentially contain collided edges, and hence using this noisy training data may affect the performance of NHE. Instead, training NHE using completely collision-free RGGs can better help NHE to learn a more suitable heuristics function. As shown in the experimental results, GraphMP can achieve strong planning performance with this input difference for NHE between inference and training phases.\n\n>Q5: Potential Limitation, e.g., final found path may not be collision-free?\n\nThank you for the comments. In **Sec. 2 of Supplementary Material**, we discuss the limitation of our approach and potential research direction. More specifically, the construction of raw input RGG may be inefficient because of the uniform node sampling and KNN-based edge connection. Without fully leveraging the specific prior spatial information, such straightforward RGG building method is involved with many non-necessary nodes sampling and edge construction, affecting construction efficiency. \n\nFor the legality of final found path, GraphMP guarantees that the final path, if found, is collision free. As described in **Algorithm 4 of Supplementary Material**, accurate collision check will be performed on the final computed path. Based on this mechanism and the good prediction performance of NCC, the success rate of GraphMP for finding collision-free paths achieves 99%-100% across different tasks."}, {"review_id": "axcf7pihKd", "reviewer": "Reviewer_Dhw9", "summary": "This paper presents an improved graph searching technique, called GraphMP. The algorithm consists of two modules, the neural collision checker and the neural heuristic estimator, which are utilised by a differentable graph-based A* module for path planning. ", "questions": "I hope the authors can answer my comments above, and tell me how they will improve the manuscript. ", "limitations": "I don't think the paper has a potential negative societal impact. I hope the authors can summarise the limitation and briefly talk about the future of their work. ", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The algorithm is presented in detail, supplemented by toy-case studies shown in Fig.1 and Fig.2. They are illustrative. \n2. The structure of Secion 3 is good. Each module is explained. \n3. The proposed algorithm is compared to multiple existing algorithms, including non-learning-based algorithms. ", "weaknesses": "1. I think Section 3.1 needs be further polished. Currently, it only states the problem to be solved. Necessary knowledge about how prior works finished the task, and which parts in the existing framework are to be improved are missing. (I can see some of the information in the supplementary file. But I suggest put them in the main text. )\n\n2. Table 1 is not illustrative. The algorithms such as BIT* and RRT* have probabilistic completeness, hence the success rate is high if the computational time is sufficiently long. Currently we cannot appreciate the goodness of the proposed algorithm regarding the completeness. I suggest the authors present the set time limit for the experiments in Table 1 (I didn't find it in Section 4.2). Then, as such, the authors should reduce the time limit to its 75% and show the algorithms' performance. Some of the existing algorithms will not have such good results as shown in Table 1 now. \n\n3. Just a minor comments: It looks like in Section 3.1 the problem is stated in the similar form to what RRT* did, but the algorithm is claimed as a searching-based algorithm. This is a little bit strange, because if the RGG is pre-constructed before running the path searching algorithm, then the presentation can safely start from \"give a graph, ..\". \n \n4. I didn't understand the \"lazy node removal\" module. Why is it required? The performance of the algorithm without LNR is not explained well in Section 4.3. \n\n5. The meaning of the terms \"w/\" and \"w/o\" are not intuitive. I suggest change them. \n ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate the reviewer's very constructive comments and suggestions. The following is our response in order of questions and comments raised.\n\n>Q1. Polishing Section 3.1.}\n\nThanks for the valuable comment. Given an RGG $G=(V,E)$, source node $v_s$ and goal node $v_g$, the prior work GNN-Explorer initializes an exploration tree $T$ rooted from $v_s$, and visits edges $e_{free} \\in E$ sorted by their predicted priorities. Each visit performs the accurate collision check on the edge and tries to append it into $T$, until $v_g$ is reached. Here the search of GNN-Explorer relies on the predicted edge priorities without fully exploring graph structure and formally consider impact of accumulated path cost during path exploration, thereby hampering the path quality. On the other hand, graph-based A* computes the path from the source node $v_s$ via iteratively selecting the best candidate $v_{sel} = argmin_{v \\in O} (g(v) + f(v))$ from the open list $O$. Here, $g(v)$ accumulates the actual cost from $v_s$ to $v$, and $f(v)$ estimates the heuristic value of the cost from $v$ to goal $v_g$. Once $v_{sel}$ is selected, each of its reachable neighboring nodes $v_{nbr} \\in \\mathcal{N}(v_{sel})$ is checked and updated. By using this way, A* can better explore graph structure and perform cost-aware search, but it requires manual design of high-quality heuristic function $h(v)$, which is a challenging task for high-dimensional tasks. Also, visiting the neighboring nodes can be time-consuming because the accurate collision check must be performed on each edge $e_{v_{sel}, v_{nbr}}$. To overcome these limitations of prior works, GraphMP proposes to use GNN to extract and learn the important patterns of RGG, and then identifies the near-optimal path using learnable graph search component. More specifically, a neural collision checker and a neural heuristic estimator are proposed to extract key graph information from input RGG and provide it to the proposed reformulated differentiable A* module for end-to-end training. Therefore, the path planning is now a graph structure-aware and cost-aware process with powerful graph pattern extraction capability and learnable heuristics function, making it can achieve high planning performance and suitable for both low and high-dimensional tasks. We will update Section 3.1 to include this discussion and analysis.\n\n\n>Q2: The time limit of planning.\n\nThank you for the valuable suggestion. Following the same setting used in Graph-Explorer, in our experiments the time budget is in the format of maximum number of the sampled nodes (as $1000$) for all the planners. By taking your suggestion, we report the success rates of all planners by setting the time limit using wall-clock time (as 400 ms and 300 ms) in the table below. It is seen that under the same wall-clock time budget, GraphMP achieves the highest success rates in almost all the tasks.\n\n**Table R2. The success rates when the time limit is 400 ms and 300 ms, respectively. Results for 300 ms are shown in the parenthesis.**\n|              | Maze2       | UR5         | Snake7      | KUKA7       | KUKA13      | KUKA14      |\n|--------------|-------------|-------------|-------------|-------------|-------------|-------------|\n| GraphMP      | 98.5 (97.1) | 91.1 (88.4) | 99.3 (99.3) | 98.9 (98.6) | 96.1 (95.8) | 97.5 (97.2) |\n| GNN-Explorer | 98.2 (96.6) | 86.3 (81.7) | 99.2 (99.1) | 98.3 (98.2) | 96.4 (95.9) | 97.2 (96.9) |\n| RRT*         | 61.7 (53.3) | 27.8 (14.8) | 47.5 (28.0) | 80.0 (79.6) | 57.2 (49.9) | 65.3 (58.1) |\n| BIT*         | 90.9 (83.4) | 80.9 (76.1) | 98.9 (98.5) | 97.8 (97.1) | 96.1 (94.3) | 95.1 (94.6) |\n| LazySP       | 92.7 (91.7) | 83.3 (78.5) | 99.3 (99.3) | 98.4 (97.6) | 97.6 (97.1) | 97.4 (96.5) |\n\n>Q3: Starting problem statement in Section 3.1.\n\nThanks for point it out. We will follow your suggestion to revise this part.\n\n>Q4: Lazy node removal.\n\nThank you for the question. \nThe lazy node removal (LNR) aims to reduce path cost by eliminating redundant nodes along the computed path. Specifically, LNR repeatedly attempts to connect each pair of disconnected nodes from both ends of the path via a collision-free edge. All the intermediate waypoints between the connectable nodes will be removed. **Fig. 4(a)** shows an example. The LNR detects that node 0 and 2 can be connected directly, so node 3 is pruned from the path. Our experiments show that LNR can reduce the average path cost by 21.92\\% at most on various types of planning tasks. As shown in Table 4, GraphMP without using LNR can achieves faster planning speed with a bit path cost overhead. So whether to use LNR or not is a design choice depending on the specific performance requirement in the application scenarios (path cost-sensitive or time cost-sensitive).\n\n>Q5: \"w/\" and \"w/o\".\n\nThanks for pointing it out. We will use the full forms in the revised version.\n\n\n>Q6: Limitation and future work.\n\nThank you for the comments. We discuss the limitation and future work in **Sec. 2 of Supplementary Material**. GraphMP may suffer from the low quality of the raw RGGs due to the uniformly sampled nodes and KNN edges. Such RGG construction strategy neglects the workspace topology and the specific task information, which may waste resources in the exploration of space that is unable to yield optimal paths. Therefore, in our future work, we plan to investigate more efficient graph construction methods, e.g., graph generative model to generate node and edges simultaneously, to construct high-quality RGGs with fewer and only necessary nodes and edges for finding the optimal paths. "}, {"review_id": "Ob9OOOSoye", "reviewer": "Reviewer_Akwa", "summary": "The paper studies learning-based motion planners with GNNs. To improve the performance of GNN-based previous work, this paper proposes the GraphMP, possibly applied to low and high-dimensional planning tasks. The important idea is using (1) using predicted heuristic values, (2) NCC (Neural collision checker), and (3) differentiable A* modules (encoded with matrix operations) for efficient motion planning. The experimental results in Sec.4 showed that the proposed GraphMP performs better with limited computational times.", "questions": "I can follow the concept and descriptions in the submitted version, and feel that the contributions are solid. Here are some comments and questions to clarify the paper.\n\n- (Related to the curse of dimensionality?): In the results in Table 1, KUKA7 seems to have a bit worse success rate than those KUMA14. Do you have any reasons for them? I feel that the problems having a larger DoF are harder than those with a lower DoF.\n    - Regarding this point, Table 2 and Table 3 are reasonable for me because they have more DOFs. However, only for the success rates in Table 1, the results should be explained in my opinion (maybe, they are some random effects? If so, it is better to mention them, e.g., random seeds, trials, etc.).\n- (About the environment $G$): In the setting, RGG $G$ seems to be given and updated lazily. Can we learn G itself together with other learnable modules?\n    - In the reported results, LNR seems to be effective in refining paths after A* is finished. Since the current LNR seems independent from the learning part, I guess that the performance depends on the given RGG; therefore, I conjecture that learning representations on graphs is an interesting direction (e.g., learning a mask matrix to prune nodes).\n- (About the learning setting): How can we set the max transition time $T_\\mathrm{max}$ in the end-to-end learning procedure? What happens if $T_\\mathrm{max}$ is not set adequately?\n    - I feel that putting the larger $T_\\mathrm{max}$ is enough to find feasible solutions (i.e., a path that reaches $v_g$), though it may cause some inefficient phenomena in practice. Do you have any evaluations and discussions?\n- (Neural heuristic estimators): The comparison is a bit trivial because vanilla A* adopts the fundamental heuristic functions. Do you have any discussions on Maze2 (where Valina A* showed better path costs)? Do you have any findings of learning heuristic values in your domains?\n- Other minor comments:\n    - I prefer using explicitly an indicator vector $\\mathbb{I}[\\mathbf{b}_\\mathbf{acc} > \\mathbf{b}’_\\mathbf{acc}]$ to $\\mathbf{b}_\\mathbf{acc} > \\mathbf{b}’_\\mathbf{acc}$ for clarity and following other literature in the ML.\n    - $\\mathbb{1}$ should be with its dimension (e.g., $\\mathbb{1}_{|V|}$) for clarity.", "limitations": "I have no explicit concerns about the limitations.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The proposed concept using multiple components (e.g., learning modules, NCCs, differentiable A*) is clearly explained.  Figure 3 and Algorithm 1 are good for following the concept.\n- The solid experimental results in various motion planning domains.", "weaknesses": "- I have no ideas except some assumptions (the input RGC is given and how to set the upper bound Tmax for unfamiliar environments).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate the reviewer's very constructive comments and suggestions. The following is our response in order of questions and comments raised.\n\n>Q1: KUKA7 vs KUKA14 in Table 1.\n\nThank you for pointing it out. The reported a bit worse success rate for KUKA7 than KUKA14 is due to random effects. The current result is based on a single random seed -- GraphMP achieves 99.3\\% (round to 99\\%) and 99.5\\% (round to 100\\%) rates on KUKA7 and KUKA14, respectively. After averaging the results using four different random seeds, the success rates on KUKA7 and KUKA14 become 99.4\\% and 99.2\\%, respectively, being consistent with the trend when DoF increases. We will update the results in the revised version by running with different random seeds. We appreciate your valuable comments.\n\n>Q2: Can we learn RGG?\n\nThank you for the very valuable suggestion. We highly agree with that learning RGG is an interesting research direction. As we discuss in the limitation and future work **(Sec. 2 of Supplementary Material)**, the current RGG generation method is somewhat inefficient with involving unnecessary node and edge generation, bringing unnecessary exploration and affecting planning performance. In our future work, we plan to fully leverage the workspace topology and the spatial information to bias node sampling/edge construction and/or pruning the unnecessary nodes. One idea is to directly learn and predict the RGG with both nodes and edges, e.g., using generative model, conditioning on the workspace and start/goal states. We are cautiously optimistic and believe that this learning-based RGG construction strategy may help improve the performance of motion planners with respect to planning speed and path quality. \n\n>Q3: Setting of $T_{max}$.\n\nThanks for the question. In our experiments the value of $T_{max}$ is  simply set as the graph size (the number of nodes), and this setting is large enough to find feasible solutions. To improve the efficiency, in practice we also propose an early stopping mechanism, which checks the sums of all the elements of the open list vector $\\mathbf{o}$ within each iteration. Here because the binary vector $\\mathbf{o}$ marks all the nodes to be explored as ones, once $\\mathbf{o}$ sums up to zero, this means there is no more nodes to be explored and hence the search can be early terminated with avoiding inefficiency. We will include the details of this early stopping mechanism in the revised version. Thank you for pointing it out.\n\n>Q4: Learning heuristic values.\n\nThank you for the comments. Because it is less challenging to design a good heuristic function in low-dimensional task, A* with admissible heuristic function, e.g., Euclidean distance based, can find very high-quality path (optimal or near-optimal) in 2D maze task. As shown in **Fig. R1(a) of Global Response**, in such scenario the heuristic values generated by manual design is more close to the actual cost than the ones  estimated by learning-based method. This explains why vanilla shows slightly lower path cost than A* equipped with NHE in 2D maze tasks. Notice that this slight cost reduction is not free but with more search efforts.  As shown in **Table 1 in Supplementary Material**, A* with NHE requires smaller search space than vanilla A* with very similar path cost; therefore in overall NHE still shows very competitive overall planning performance as compared to manual heuristic function design in 2D Maze. For planning in high-dimensional cases, as illustrated in **Fig. R1(b) of Global Response**, learning-based solution provides better heuristic value estimations than manual design.\n\nIn addition, we have some findings for learning the heuristic values. First, \ntraining with diverse RGGs improves the generalization of NHE. Based on the observations that 1) the input RGG to NHE is filtered by a collision checker, indicating the uncertainty of the node degrees, and 2) the graph size may increase during the planning phase because extra batches of the sampled nodes would be added if a path can not be found, we construct diverse RGGs when preparing the training data. More specifically, we randomize both the graph sizes and $K$ values of KNN edge construction to ensure that NHE can be trained on different graph structures.\n\nSecond, it is important to inform all nodes of the goal information. Considering the heuristic value is to estimate the actual cost to the goal, we initialize the node features of each node by concatenating its own features, the goal features, and the distance to the goal features. Such operation is crucial to learn and predict the heuristic values properly.\n\nThird, The number of the loops of the message passing should be properly selected. The iterations of message passing decides how many hops of neighboring information will be seen from each node. It is important for nodes to receive the information of the whole graph so that high-quality heuristic values can be estimated based on the global information. Too few loops are insufficient to receive the global information while too many loops are likely to cause the over-smoothing issue. Therefore, a proper value of the message passing loop should be determined by the graph size and node degrees. In our work, considering the maximum graph size is 1000 and the $K$ value of KNN is 10, we empirically set the value of the message passing loop as 3.\n\n>Q5: Format of indicator and all-one vectors.\n\nThank you for pointing it out. We will correct these mathematical formats in the updated version."}]

Author rebuttal:
**We would like to thank all reviewers for the valuable comments and suggestions.**  In the attached PDF file, we include five figures as described as follows: the study on the admissibility/consistency of the neural heuristic estimator **(Fig. R1)**, the updated neural collision checker results on RGG when $K = 10$ **(Fig. R2)**. Besides, for the reviewer's convenience, we also put the ablation study on varying $\theta$ **(Fig. R3)**, varying sampling size **(Fig. R4)** and varying $K$ **(Fig. R5)**. 

Meta-review: The paper presents GraphMP, an approach for motion planning that uses a graph neural network to accelerate planning. It uses networks to predict both collision and heuristics to accelerate planning and proposes a training mechanism. Results over a variety of planning problems show impressive performance.

The reviewers all agreed the work should be accepted, and I concur. The paper is generally clear and thorough and has been improved through the rebuttal process and clarifications the authors provide.
Decision: Accept (poster)