Reducing Collision Checking for Sampling-Based Motion Planning Using Graph Neural Networks
Authors: Chenning Yu
Sicun Gao
Venue: NeurIPS 2021 Poster (2021)
Keywords: Graph Neural Networks
Graph
Motion Planning
Collision
Collision Checking

Abstract: Sampling-based motion planning is a popular approach in robotics for finding paths in continuous configuration spaces. Checking collision with obstacles is the major computational bottleneck in this process. We propose new learning-based methods for reducing collision checking to accelerate motion planning by training graph neural networks (GNNs) that perform path exploration and path smoothing. Given random geometric graphs (RGGs) generated from batch sampling, the path exploration component iteratively predicts collision-free edges to prioritize their exploration. The path smoothing component then optimizes paths obtained from the exploration stage. The methods benefit from the ability of GNNs of capturing geometric patterns from RGGs through batch sampling and generalize better to unseen environments. Experimental results show that the learned components can significantly reduce collision checking and improve overall planning efficiency in challenging high-dimensional motion planning tasks.

Reducing Collision Checking for Sampling-Based Motion Planning Using Graph Neural Networks
Chenning Yu
Sicun Gao
Computer Science and Engineering UC San Diego
Computer Science and Engineering UC San Diego si sicunguusd.edu
chy010@ucad. edu
Abstract
Sampling- based motion planning is popular approach in robotics for finding paths in continuous configuration spaces. Checking collision with obstacles is the major computational bottleneck in this process. We propose new learning-base -bsee methods for reducing collision checking to accelerate motion planning by training graph neural networks (GNNs) that perform path exploration and path smoothing. Given random geometric graphs (RGGs) generated from batch sampling, the path exploration component iteratively predicts collision-free edges to prioritize their exploration. The path smoothing component then optimizes paths obtained from the exploration stage. The methods benefit from the ability of GNNs of capturing geometric patterns from RGGs through batch sampling and generalize better to unseen environments. Experimental results show that the learned components can significantly reduce collision checking and improve overall planning efficiency in challenging high dimensional motion planning tasks.
Introduction
Sampling-basee planning is popular approach high- digh-dimensional continuous motion planning in
robotics [36] 14] 31 27 19 533 35]. The idea is to iteratively sample configurations of the robots and construct one or multiple exploration trees probe the free space, such that the start and goal states are eventually connected by some collision-free path through the sampled states, ideally with path cost minimized. This motion planning problem hard, theoretically PSPACE-complete (48). and existing algorithms are challenged when planning motions of robots with few degrees of freedom 34 [5] 39 g [5). particular, the planning algorithms need repeatedly check whether an edge connecting two sample states is feasible, i.e., that state along the edge collides with any obstacle. This collision checking operation is the major computational bottleneck in the planning process and by itself NP-hard in general 28 77. For instance, consider the 7D Kuka arm planning problem in the environment shown in Figure 1. The leading sampling-
planning algorithm BIT [19] spends about 28.6 seconds to find a complete motion plan for the robot, in which 20.2s (70.6% of time) is spent on collision checking. comparison, it only takes 0.06s (0.2% of time) for sampling all the probing states needed for constructing random graphs for completing the search.
Learning-base based approaches have become popular for accelerating motion planning. Many recent approaches learn patterns of the configuration spaces to improve the sampling of the probing states, typically through reinforcement learning or imitation learning (29 25
g] For instance, Ichter et al. 25 and motion planning networks [47] apply imitation learning collected demonstrations to
bias the sampling process. The NEXT algorithm [8] provides state-of-the-an design for embedding nigh-dimensional continuous state spaces into low-dimensional representations, while balancing exploration and exploitation in the sampling process. It has demonstrated clear benefits of using learning-based components to reduce samples and accelerate planning. However, we believe two
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

aspects in NEXT can be improved. if we shift the focus from reducing sample complexity to reducing collision checking. First, instead of taking the grid-based encoding of the entire workspace as imput, we can use the graphs formed by batches of samples from the free space to better capture the geometric patterns of an environment. Second, having access to the entire graph formed by samples allows us to better prioritize edge exploration and collision checking based on relatively global patterns, and avoid getting stuck in local regions. In short, with reasonably relaxed budget of samples taken uniformly from the space, we can better exploit global patterns to reduce the more expensive collision checking operations instead. Figure | and more thorough comparisons are provided in the experimental results section.
shows a typical example of how the trade-off benefits overall planning,
We design two novel beaming-based components that utilize Graph Neural Networks (GNNs) to accelerate the search for collision-free paths in batch sampling- based motion planning algorithms. The first com- ponent the GNN Path Explorer, which trained to find collision-free paths given the environment configuration and a random geometric graph (RGG) formed by probing samples. The second component is the GNN Path Smoother, which learns to optimize the path obtained from the explorer. In both models, we rely on the expressiveness and permutation invari- ance of GNNs as well as attention mechanisms to identify geometric patterns in the RGGs formed by samples, and accelerate combinatorial search.
Figure I: Performance 7D Kuka arm. Left: Trajectory generated by the proposed GNN- based approach. Right: NEXT getting stuck at a local region. Both methods were trained on the same training set.
The proposed tearning-based components can accelerate batch sampling- based planning algorithms without compromising probabilistic completeness properties. The methods achieve higher success rate, much lower rate of collision checking, and accelerate the overall planning compared to state-of- the-art methods. We evaluate the proposed approach in variety of planning environments from 2D mazes to 14D dual KUKA arms. Experiments show that our method significantly reduces collision checking, improves the overall planning efficiency, and scales well to high-dimensional tasks.
The paper is organized as follows. We review related work and preliminaries Section 2 and 3. We describe the detailed design of the GNN architectures in Section 4, followed by the training of GNN explorer and smoother in Section 5. We discuss experimental results in Section 6.
2 Related Work
Learning-based Motion Planning. Learning-based approaches typically consider motion planning as a sequential decision- making problem. which could be naturally tackled with reinforcement learning or imitation learning. With model-based reinforcement learning, DDPG-MP (29 integrates the known dynamic of robots and trains policy network. Strudel et al. [54] improves the obstacle encoding with the position and normal vectors. OracleNet [2] learns via oracle imitation and encodes the trajectory history by an LSTM 23 Other than predicting nodes which are expected to greedily form a trajectory, various approaches have been designed to first learn to sample vertices, then utilize sampling- based motion planning for further path exploration through these samples. L2RRT 24 first embeds high-dimensional configuration into low- -iw-dimensiona representation, then performs RRT Rd on top of that. Ichter et al. (25 uses conditional VAE to sample nodes. Zhang et al. (65) learns rejection sampling distribution. Madaan 40 encodes the explored tree with an RNN. Motion Planning Networks [47] utilizes the ceppout-based stochastic auto-encoder for biased sampling. NEXT 8 projects the high-dimensional planning spaces into low-dimensional embedding discrete spaces, and further applics Gated Path Planning Networks 37 to predict the samples.
-based
Existing learning- approaches have considered improving collision detection. Fastron [3 and ClearanceNet (6] learn function approximators as a proxy to collision detection, which is disparate from our focus on reducing the steps that are needed to the collision checker, and can be improved further potentially if combined together. Another recent line of work focuses on learning to explore edges given fixed graph. Value Iteration Networks (55) and Gated Path Planning Networks (37 apply convolutional neural networks (CNN) on discrete maps, then predict the policy with a weighted attention sum over neighborhoods. Generalized Value Iteration Networks 44 and Velickovic et al.

---

[60] extend this approach for nontrivial graph by replacing CNN with GNN. However, the construction of such graphs requires ground-trun -ruth collision status for every edge on the graph at inference time.
It should be noted that other than sampling-based approaches, trajectory optimization [3) 68, (7
51 67]. and motion primitives [3 66 are standard choices for more structured problems such as for autonomous cars and UAVs, while caupling-based methods are important for navigating high-dimensional cluttered spaces such as for manipulators and rescue robots.
Graph Neural Networks for Motion Planning. Graph neural networks are permutation invariant to the orders of nodes on graph, which become natural choice for learning patterns in graph problems. They have been successfully applied in robotics applications such as decentralized control [38. For sampling-bar based motion planning, Khan et al. [3] utilizes GNN to identify critical samples. We focus on the different aspect of collision checking with given random geometric graphs, and can be combined with existing techniques without affecting probabilistic completeness. More broadly, GNNs have been used for learning patterns in general graph-structured problems, e.g. graph-based exploration [12 [52]. combinatorial optimization [32] [6] [5]. neural algorithm execution [60] 61 63 59] Other than to use GNN for high-dimensional planning, several works propose first learn neural metries, then build explicit graphs upon the learned metric which is used later to search the path [50 [8 17 64). While sharing similar interests, our work specifically focuses on how to reduce the collision checking steps for sampling-bass -baled motion planning.
Informed Sampling for Motion Planning. A main focus in motion planning is on developing problem-independent heuristic functions for prioritizing the samples or edges to explore. Approaches include Randomized A [4), Fast Marching Trees (FMT*) (27). Sampling- A* (SBA*) 45),
Batch Informed Trees (BIT*) [19]. These methods orthogonal our learning-basee based approach, which can further exploit the problem distribution and recognize patterns through offline training to improve efficiency. Recent work in motion planning has made significant progress in reducing collision checking through batch sampling and incremental search, such as in BIT* [19] and AIT (53) The idea is start with batches of probing random samples in the free space, and focus on reducing collision checking to edges that are likely on good paths to the goal, which also inspires our work.
Lazy Motion Planning. Lazy motion planning also focuses on reducing collision checking, typically with hand-crafted heuristics or features. LazyPRM and LazySP [4] 21 construct an RGG first and check the edge lazily only if that edge is the global shortest path the goal. Instead of calculating a complete shortest path, LWA* uses one-step lookahead to prioritize certain edges [TI. LRA" " interleaves between LazySP and LWA*, with predefined horizon to lookahead [41] These approaches use hand-crafted heuristics and do not utilize data-dependent information from specific tasks. Recently, GLS and StrOLL 42 B] leverage experiences learn to select the edge check with either fixed graphs or hand-crafted features. Our GNN-based approach proposes the use of new representations for the learning- based components, with the goal of directly recognizing patterns using samples from the configuration space.
3 Preliminaries
Motion Planning. We focus on motion planning in continuous spaces, where the configuration space C' C R". The configuration space includes all degrees of freedom of robot (e.g. all joints of a robotic arm) and is different from the workspace where the robot physically resides in, which is at most 3-dimensional. For planning problem on a graph G = (V. E), we denote the start vertex and goal vertex as Us, Ug E C. A path from C2 to 2gg is finite set of edges π = {e; (v,, 2/) hejjo such that 0o- U, v/2 Vg- and vy = 1 for all i E [0, k 1]. An environment for a motion planning problem consists of a set of obstacles Cobe S C and free space Ofree = C Cohe. Note that Cobe is the projection of 3D objects in the digees-dim configuration space. and typically has complex geometric structures that can not be efficiently represented. A sample state a C' in the configuration space is free if E Cfree, i.e., it is not contained in any obstacle. An edge connecting two samples is free if C Cree. Namely, for every point e on the edge e, v E Cfree. A path π free if all its edges are free. A random geometric graph (RGG) is r-disc or k-nearest-neighbor (k-NN) graph G 20 62]. where nodes are randomly sampled from the free space Crree. In this paper we consider the RGG as a k-NN graph. Given a random geometric graph G and a pair of start and goal configuration (v., Ug). the goal of agent is to find a free path æ from n, to Vy. Without loss of generality, we consider the cost of path to be the total length over all edges in it.
3

---

Graph Neural Networks and Attention. Let G = (V, be a finite graph where each vertex U. labeled by data z; E IR. A graph neural network (GNN) learns the representation h; of node os by aggregating the information from its neighbors (wx). Given fully-connected networks f and g.
typical GNN encodes the representation h! ((++1) of the node v; after aggregation as:
c: = = ( ( ,n/") (ex, 22) E EE) and h ((++1) = g(h; (K)
(1)
where (n 24 and + is some cormuuaationinvariinn aggregation function sets, such as max, mean, or sum. We will also use the attention mechanism when we need to encode a varied number of obstacles inputs. Suppose there corresponding value V E Raxd, Given m query vectors Q Rmmxd,, we use typical attention function Att K, Q, V) for each query as Att K, Q, V) = softmax (oaaa//KT//// [58]. The function is also cermutationninvariian
keys each with dimension dg: K E RBxde each key
the order of obstacles does not affect the output.
4
GNN Architecture for Path Exploration and Smoothing
4.1
Overall Approach
At a high level, motion planning with batch sampling typically proceeds as follows [1]] We first sample a batch of configurations in the free space, together with the start and goal states, and form random graph (RGG) by connecting neighbor states (such as k-NN). A tree is then built in this graph from the start towards the goal via heuristic search. The tree can only contain collision-fie freee edges, so each connection requires collision checking. When path from start to goal is found, it is stored as a feasible plan, which can be later updated to minimize cost. After adding all collision-free edges in the current batch in the tree, new batch will be added and the tree is further expanded. The algorithm keeps sampling batches and expanding the tree until the computation budget is reached. It then returns the best path found so far, or failure if none has been found.
We use GNN models to improve two important steps in this planning procedure: path exploration and path smoothing. The GNN path explorer finds feasible path π from start to goal given randomly batch-sampled RGG, with the goal of reducing the number of edges that need to be checked for collision. The GNN path smoother then takes the path found by the explorer and attempts to produce another feasible path with less cost. In both tasks, the GNN models aim to recognize patterns and learn solutions to the combinatorial problems and save computation. In Figure 2, we illustrate the main steps for the overall algorithm. First, in (a-c), we generate an RGG composed of the vertices randomly sampled from the free space without collision checking edges. This graph will provide patterns that the GNN explorer later uses to only prioritize certain edges for collision checking. In (d), the graph is the input to the GNN path explorer, which predicts the priority of the edges explore and only the proposed edges are checked for collision. (e): We iteratively query the path explorer with collision checking to expand tree in the free space until the goal vertex is reached, and sample new batches when no path is found in the current graph. (f): Once a path is provided by the path explorer, it becomes the input (together with the current RGG) to the GNN path smoother component, which outputs a new path that reduces path cost via local changes to the vertices in the input path.
4.2 GNN Architecture
We write the GNN path explorer as Nr and the GNN path smoother as Ns. Both models take in a sampled random geometric graph G = (V, E). For an n-dimensional configuration space, each vertex 8, E RT+3 contains an n-dimensional configuration component and a 3-dimensional one-hot label. There are 3 kinds of labels for the explorer: (i) the vertices in the free space, (ii) the vertices with collision, and (iii) the special goal vertex. There are also 3 kinds of labels for the smoother: (i) the vertices on the path, (ii) the vertices in the free space, and (iii) the vertices with collision.
The vertices and the edges are first embedded into a latent space with x E RRIV/dd , E R [R)d, where d, is the size of the embedding. The embeddings for the GNN explorer and smoother are different, which will be discussed later in this section. Taking the vertex and edge embedding x, y, the GNN aggregates the local information for each vertex from the neighbors, by performing the

---

a. New Task
Sample Nodes
c. Build RGG
Goal O
Goal
Goal
O Start
Start
Start
Predict Edge Priority
Path Exploration
f. Smooth Explored Path
Pizsgge Plouuitg
<V, E>
<V, E>
GNN Explorer
GNN Smoother
Figure 2: Left: GNN architecture shared by the path explorer and the path smoother. Right (a-f): Main steps in planning with GNNs, as explained in Section 4.1
following operation with 2 two-layer MLPs fa and fy:
r; g (si, max 2i, Ii Fi,, v1 el (vi, vy) E)), Vu, e V = max(u:, fZ - z;, Ty x))), Ve, (2,, E
(2)
Note that here we use max as the aggregation operator to gather the local geometric information, due to its empirical robustness to achieve the order invariance [46]. The edge information is also incorporated by adding yI as the input to fa. The update function g is implemented two different ways for the GNN explorer and smoother. Specifically, 9 equals to the max operator for the GNN explorer, and g(m;; xia) = [ (m,) + xy as the residual connection for the GNN smoother, where Sa is two-layer MLP. We choose max operator for the explorer, due to its inductive bias to imitate the value iteration, as mentioned by Velickovic et (60). The residual connection is applied the smoother, since intuitively the residual provides a direction for the improvement of each node on the path in the latent space, which fits our purpose to generate a shorter path for the smoother.
We also note that Equation 2 directly updates on the x and y and is homogeneous function similar to Tang et al. [56]. which allows us self-iterate x and y over multiple loops without introducing redundant layers. Both the GNN explorer and smoother leverage this property. After several iterations, with two MLPs fqp Ju. outputs the priority 1) = [n( for each edge, and N/s outputs potentially shorter path x = (us, u4), u; (xx)) for Us
Special design for the GNN path explorer. The path explorer uses the embedding of the vertices of the form x = hr (v. ggg (w- v2y) v ty)), where hi is two-layer MLP with batch normalization [26]. Here we append the L2 distance and the difference serve as heuristics for the GNN to be more informed about which node is more valuable. The it is simply computed as y1 = (V, - 0i, Uj vz), where by also two-layer MLP with batch normalization. Optionally, it is helpful for the explorer to incorporate the configuration of obstacles O = {o) TR| [x][X2n inputs, when embedding the vertices and edges. Since the obstacles of the environment has variable numbers, we utilize the attention mechanism here to update the æ and y, named as obstacle encoding, as illustrated in Figure 2 Further details are provided in the Appendix.
the goal to the vertex embedding, which
Special design for GNN path smoother. The GNN smoother embeds vertices with = (v)(v). where h2 is two-layer ML. with batch normalization. The y is computed yr = hy(u; U; 1/ v.). where hy is two-layer MI.P with batch normalization. Each time a and are updated by Equation 2 the GNN smoother will output new smoother path n'' {(u, [())) where u; fu (ax), Vo: т, given an MLP fa. The up and ut are manually replaced by and Eg. to satisfy the path constraint. We assume the n' has the same number of nodes as n. Since the GNN smoother could gain novel local geometric information with the changed vertices of the new path, we dynamically update G = (V. E)) via (i) replacing those nodes labeled as path nodes in V by the nodes on new path, (ii) replacing by generating k-NN graph on the updated V. With the updated graph G, we repeat the above operation. During training, the GNN smoother outputs n', after a random number of iterations (between and 10). During evaluation, the GNN smoother outputs T after only one loop for each calling.
5

---

5
Training the Path Explorer and Smoother
Due to space limitation we provide the pseudocode for all algorithms in the Appendix.
5.1 GNN Explorer NE: Training and Inference
The path explorer constructs a tree through sampled states with the hope of reaching the goal state in finite number of steps. We initialize the tree To with the start state v, its root. Every edge en, in the tree Ti exists only if éT, is in the free space Cfrea- Given an RGG G = (V, F),, Our goal is to find tree containing the goal configuration Vg by adding edges from E to the tree, with few collision checks as possible. We write the edge on frontier of the tree as F (T) = {(1, uf) o E VT, og & VT We denote the set of edges with unknown collision status time step as E,.
Training procedures. Each training problem consists of a set of obstacles O, start vertex Us. goal vertex Ug. we sample k-NN graph G = (V, E), where V is the random vertices sampled from the free space combined with {U,, }- The goal is to train N to predict exploration priority 1) E R Al
A straightforward way for supervision is to use the Dijkstra's algorithm to compute the shortest feasible path from Ug V'g, and maximize the corresponding values of 1) at the edges of this path, via cross entropy loss or Bayesian ranking [49]. However, it does not provide useful guidance when the search tree deviates from the ideal optimal path at inference time. Instead, we first explore the graph using 1) with i steps, which forms a tree T, where i a random number. The oracle provides the shortest feasible path n in this tree and connects one of the nodes T; to the goal vertex Vg- We formulate this optimal path as ny = (eN, (YN,, 'N, ('N,)e joe where UN E VT, "N, = -/g- We train the explorer to imitate this oracle. Namely, the explorer will directly choose eN, E n as the next edge to explore, among all possible edges on the frontier of Tú, i.e. Es n (T.).. We maximize the vN, among the values of {T e, E, (T.) using the following cross entropy loss:
e
LNz= = - log Yoo. where 7/k-
EejEB Enyy" VeL E (T)
(3)
Inference procedures. Given the GNN NE. the current explored tree To at step i, the RGG G (V, E) including u and Ug. environment configuration O, GNN path explorer aims to maximize the probability of generating feasible path by adding e, from E; to tree T, as:
e; =
argmax Ne(mk V,E,O)
(4)
EEEE:nE,(T))
where 7 is the output of NE for the edge eg. After e; is proposed by GNN using Equation 4 we check the collision eg. If e, is not in collision with the obstacles, we add the edge 6, to the tree Tr, and remove e; from E,, i... ET.,, ET, U {e,), and E,+1 E, {ez}. If e, is in collision with obstacles, we query the path explorer for the next proposed edge using Equation where E; is updated E, E, \ }. The loop terminates when find collision-fre free edge. or when E, n (T.) = 0. When the latter happens, we re-sample another batch of samples, add new samples to vertices V. re-construct k-NN graph G, re-compute 1), and continue to explore the path this new graph with the explored nodes and edges.
The exploration GNN only proposes ordering on the candidate edges, and all possible edges may still be collision checked in the worst case. Thus, if there exists any complete path in the RGG, the algorithm always finds it. Therefore, the proposed learning-based component does not affect the probabilistic completeness of sampling-bass planning algorithms [10].
5.2
GNN Path Smoother Ng: Training and Inference
The GNN Ns for path smoothing takes an RGG and path x proposed by the explorer, and aims to produce shorter path n'. Specifically, the input a graph G (V. E), where V = V V,, U V.. E E U Efe. Here, V, and V. are reused as the same vertices in the GNN explorer, without introducing extra sampling complexity. E,, is composed of those pairs of the adjacent vertices on w, and Efe connects each vertex in V, to their k-nearest neighbor in Vy U V.. Intuitively, aggregating information from V,UV, can allow GNN to identify local regions that provide promising improvement on the current path, and avoid those that may yield potential collision.

---

Training procedures. We train the GNN path smoother Ns by imitating a smoothing oracle S similar to the approach of gradient-informed path smoothing proposed by Heiden et al. [22]] To prepare the training set, we iteratively perform the following two operations path. Given feasible path x predicted by Ne, the smoothing oracle first tries to move the nodes on the path with perturbation within range 6. If the new path иM is feasible and has cost less than т, then S will continue to smooth on TM Otherwise, will continue smoothing on и via random perturbation. After several perturbation trials, the oracle further attempts to connect pairs of nonadjacent nodes directly by a line segment. If such a segment is free of collision, then the original intermediate nodes will be moved this linear segment. Further details in the Appendix.
each training sample
After S reaches maximum iteration, the oracle will return the smoothed path RM = {w,, (e To generate training data, we first run our trained GNN explorer for each training problem to get the initial path и. Then the oracle path RM and the predicted path x' are computed, and finally the GNN is trained via minimizing the MSE loss TNN & Σ iE 1.44
[[Wss (u: V, F)) wall2. 112
Inference procedures. The GNN Ns for path smooth- ing takes an explored path {(e,, vejo.. sam- pled graph G, and outputs a potentially shorter path o': {mu, uf) (E(E)A)) which has the same number of edges as æ. It is not always guaranteed that x' is collision-fite However, such n' still indicates directions for shortening the path, so we can improve и towards x' an incremen- tal way. The GNN smoother will try to move every node 2 towards the target position Ue with a small step size For each time that all the vertices are moved with small step, we check whether each edge still holds collision-free. If not, then the vertices the edge will undo the move- ment. Otherwise, the new configuration the vertex will replace its old configuration iterated over several times, until the maximum iteration is reached, or no edges on π can be moved further. We can then repeat the process by feeding the updated back to the GNN Ns for further improvement. The intuition here is that there might still be chances to improve upon the updated π, by aggregating new information from its changed neighborhoods. This has shown empirical advantage in our experiments.
Explored Path
Smooth Path with GNN Smoother
CP
Figure GNN path smoother the 2D maze problem. It learns to improve the explored path and achieves lower cost.
This operation will be
UR5 (6D)
Kuka (7D)
Snake (7D)
Extended Kuka (13D)
Figure 4: Demonstrations for some of our environments from UR5 to 13D.
6
Experiments
6.1 Overall Performance
We compare our methods with the sampling- based planning baseline RRT* samppssa based method BIT* [19), the lazy motion planning method LazySP [2]] and the
31 the state-of-the-art
state-off sate-of-theearr learning- based method NEXT [ NEXT has been shown in (8] to outperform competing learning-base
approaches. We conduct the experiments on following environments:
(i) a 2D point-robot in 2D workspace, (ii) a 6D UR5 robot in 3D workspace, (iii) 7D snake robot in 2D workspace (the z-axis is fixed), (iv) a KUKA arm in a workspace, (v) an extended 13D KUKA arm in 3D workspace, (vi) and pair of 7DoF KUKA arms (14 DoF) in 3D workspace.

---

For each environment, we randomly generate 2000 problems for training and 1000 problems for testing. Each problem contains different
random obstacles, and a pair of feasible vs and ggg- We run all experiments over 4 random seeds. The averaged results are illustrated in Figure S For the 2D environment, we directly take the training set provided by NEXT to train our GNN. We use two test sets for the 2D environment: "Fasy2D" is the original test set used for evaluating NEXT in the original paper [ and "Hard2D" is a new set of tests we generated by requiring the distance between the start and goal to be longer than the easy environments. The goal is to test whether the learned models can generalize to harder problems without changing the training set. Further details on the environments and hyperparameters provided in the Appendix.
GNN Obstacle Encoding
BIT
GNN Smoother
GNN w/o Obstacle Encoding Smoother
NEXT
LazySp*
Success Rate
Callision
Path Cost
Total Time (seconds)
10m
Prymierrin 1P8
Solle wasto 140
Any.70Her 6m
Gade Eeom
183
140
Vile Kavm 191 145
Todeo EarTh 1ND
Figure 5: Comparison performances on all environments from 2D to 14D, averaged over 4 random seeds. From left to right: (a) Success rate. (b) Collision checks. (c) Path cost. (d) Total planning time.
GNN Easy
NEXT Easy
NEXT on Hard
GNN Easy
NEXT Easy
GNN on Hard
NEXT-6k on Hard
NEXT- 10k w/b RRT Hard
GNN on Hard
NEXT on Hard
Figure 6: We test the generalization capability of GNN-based approaches and NEXT by constructing pairs of problems that have small but important difference in connectivity. The GNN models find paths both environments quickly, while NEXT gets stuck in hard instances because of the lack of access to the graph structure provided by probing samples. The explored vertices of GNN on URS environment colored in blue, and the edges on the path colored in red.
Success rate. As shown in Figure 5 (a), our method finds complete paths at 100.0% problems on both 2D Easy and 2D Hard, and at 97.18%. 99.85% 99.20%. 99.15% and 99. 1.%% problems from UR5 to 14D, which is comparable to handcrafted heuristics used in BIT (100.0%. 100.0% 99.25%, 99.85%, 99. 19.65% 99.929.99999 99.9%, 99. 9.%%% on each environment). The learning- planner NEXT performs well on easy 2D problems (99.37% success rate), but drops slightly to 97.10% on harder 2D problems, and 36.80% 71.80% 87.9%, 60.52%, 66.57% environments in higher dimensions.
Collision checking, In Figure 5 (b), we see significant reduction of collision checking using the proposed approach, in comparison to other approaches especially in high- dige-simnniooal problems. The average number of collision checks by the GNN explorer 336.3, 715.7, 2474.0, 1602.2, 350.5, 521.7, 487.0 on the environments, whereas BIT needs 1 12%, 175%. 164%, 101 101%, 557%, 226%, 263% times as many collision checks as our method requires on each environments. LazySP needs 105%, 1 114%, 111%, 100%, 105%, 105%. 124% times as many collision checks as GNN requires on each environments. NEXT requires 270.23 checks on Easy2D and increases to 1206.1 on Hard2D. On the 14D environment, method uses 17.4% of the collision checks as what NEXT requires.

---

Path cost. We show the average path cost over all problems where all algorithms successfully found complete paths. With the smoother and obstacle encoding, our GNN approach provides the best results from URS to 14D, and generates comparable results for the 2D Fasy and 2D Hard, where NEXT is 1.02, 1.71, and GNN 1.18, 2.05. We find that although the GNN explorer does not yield shorter path with obstacle encoding, these explored paths can be improved further with the smoother. The reason may be that with additional obstacle encoding, the GNN explorer tends to explore edges with less probability of collision and provides more space for the smoother to improve the paths.
Planning time. A common concern about learning- based methods is that their running cost due to the frequent calling of large neural network model at inference time (as seen for the NEXT curve). We see Figurd5(d) that the wall clock time of using the GNN models comparable to the standard heuristic-based LazySP, BIT* and RRT*, when all algorithms can find paths. The main reason is that the reduction in collision checking significantly reduces the overall time. We believe the GNNs can be further optimized to achieve faster inference as well.
In summary, experimental results show that the GNN-based approaches significantly reduce colli- sion checking while maintaining high success rate, low path cost, and fast overall planning. The performance scales well from low-dimensional to high-dimensional problems.
6.2 Generalizability of Collision Reduction
A major challenge of learning-based approaches for planning is that small changes of the geometry of the environment can lead to abrupt change in the solutions, and thus lead the difficulty of generaliza- tion. In Figure 6 we provide evidence that the GNN approach can alleviate this problem because of its access to the graph structures formed by samples uniformly taken from the space. In the 2D maze environment, the top one is easy while the bottom one is much harder, although the difference is just whether a narrow corridor is present to the left of the start state. For the URS with pads and poles, to solve the hard one, the robot and then rotate it back to fit the goal configuration. These problems are especially challenging for generalizing learned results to unseen environments.
needs to first rotate itself around the z-axis bypass the small pads,
We observe that the GNN-based components can handle the transition from the easy to hard problems consistently. In both environments, the GNN components find paths quickly, with 9 and 236 edges explored for 2D maze, and with I and 256 edges explored for URS. contrast, the NEXT model trained on the same training sets, quickly find a path in the easy problem, but gets stuck in the hard one. Since the two problems are close to each other in the input space for NEXT, it is not surprising
this difficulty of generalization. In fact, the only case where NEXT can eventually find a path on 2D Maze after more than 6K edge exploration is when the algorithm delegates 10% operations to standard RRT* Without delegating to RRT*, NEXT gets stuck in local regions after 10K exploration steps on 2D and 1K steps on URS.
explores edges Lazy5P explores edges Colliion Check Collision 434
explores edges LazySP edges Collitio
expiores LazySP explores edges Collsion Check
Collision
Collsion
Figure 7: Comparison of performances with LazySP across different batch samples. The final path is colored red, and the other explored edges are colored green. From left to rightm we show examples of the search results with the hatch size heing 100, 200, and 300, respectively. We show obstacles of different thickness because the in-collision samples are also part of the inputs the GNN planner, which can provide useful information about the topology of the environment.
6.3 Further Comparison with Lazy Motion Planning
We compare GNN with the lazy motion planning method LazySP 21]. the collision checking edges that are part of the shortest paths in the RGG, which is strategy that can often see good performance especially on randomly generated graphs. However, as lazy planning uses the fixed heuristic of prioritizing certain paths, it is easy come up with environments where
Lazy approaches prioritize

---

this heuristic becomes misleading. Our proposed learning- based approach, instead, uses GNN to discover patterns from the training set, and can thus be viewed as data-dependent way of forming heuristics for reducing collision checking.
Consider U-shaped obstacles, with the start state close the bottom of the U-shape, shown in Figure 7 It is standard environment that is particularly hard for the standard lazy approach, which prioritize the edges that directly connect the start and goal states, as they are close in the RGG that does not consider obstacles. Indeed, the lazy approach needs to check most of the edges that cross the obstacles before the path for getting out of the U-shape can be found. We train the model on these environments and observe clear benefits of learning- -aase components in avoiding this issue. Figure shows the difference between the two approaches several examples of the 2D environment using different sizes of sample batches, where the GNN-base approach can typically save 50% of collision checking on edges compared to the lazy approach.
6.4 Ablation Study: Probing Samples
2D Easy - 2D Hard
- URS -
Snake
Kuka7D -
13D - 14D
Success Rate
Collisian Check
Path Cost
Total Time
146
125
106
0.6
1020
530
02
0-
203
400
100
.000
1000
53
103
25D
303
$20
1000
53
100
300
3003
500
1030
200
000
000
1003
Figure 8: Comparison of performances for different probing samples from 2D to 14D problems.
We perform ablation studies of varying different parameters in our approach. The full details are provided in the Appendix. For instance, we use RGGs with different number of vertices from the free space, using 100, 200, 300, 500, 1000 samples, as illustrated in Figure [8] The success rate increases when there are more probing samples, which is consistent with the resolution-complete property of campling-based planning. The path cost stays nearly the same for all settings, indicating robustness of the smoother models. The collision checks and planning time grows linearly with the probing samples. The reason is that the number of edges of k-NN RGG increments linearly with vertices, the input to the GNN grows linearly, thus the computation cost increases linearly on both CPU and GPU.
7 Conclusion
We presented a new learning-based approach to reducing collision checking in sampling-based motion planning. We train graph neural network (GNN) models to perform path exploration and path smoothing given the random geometric graphs (RGGs) generated from batch sampling. We rely on the ability of GNN for capturing important geometric patterns in graphs. The learned components can significantly reduce collision checking and improve overall planning efficiency in complex and high-dimensional motion planning environments.
Acknowledgments and Disclosure of Funding
This material is based upon work supported by the United States Air Force and DARPA under Contract No. 118750-18-C-0090 AFOSR YIP FA9550-19-1-0041, NSF Career CCF 2047034, and NSF NRI 1830399. We thank the anonymous reviewers for various important suggestions, such as for the comparison with lazy planning approaches.
References
[1] J. Barraquand and J. Latombe. Nonholonomic multibody mobile robots: Controllability and motion planning in the presence of obstacles. Algorithmica, 10(2-4):121-155, 1993. doi: 10.1007/BF0189 URL 00//11..100//5FF118111877
1007
10

---

[2] M. J. Bency, A. H. Qureshi, and M. C. Yip. Neural path planning: Fixed time, near-optimal path generation via oracle imitation. In 2019 JEEE/RSJ International Conference on Intelligent Robots and Systems, IROS 2019, Macau, SAR, China, November 3-8, 2019, pages 19965-3972 IEEE, 2019. doi: 00.100//RR004409220009999 89680999,9998,,, URL https:://oi..rgg/// 1109/ IROS40897 896808999888
[3] M. Bhardwaj. S. Choudhury, Boots, and S. Srinivasa. Leveraging experience in lazy search. In A. Bicchi, H. Kress-Gazit, and S. Hutchinson, editors, Robotics: Science and Systems XV. University of Freiburg. Freiburg im Breisgau, Germany, June 22-26, 2019, 2019. doi: (0.15607/RSS.2111 201..00.99..... URL htt.h:t/tp://llo org/10. 15607 /RSS. 2019. X50
[4] R. Bohlin and L., E. Kavraki. Path planning using lazy PRM. In Proceedings of the 2000 IEEE International Conference on Robotics and Automation, ICRA 2000, April 24-28, 2000, San Francisco, CA, USA, pages 521-522 IEEE, 2000. doi: (0.100//ROB0.2200..444 https://doi. org/ 10g 1109/R0B0TT 200.B00T..000.44110000 844107
URL
[5] X. Bresson and T. Laurent. The transformerr network for the traveling salesman problem. CoRR, abs/2 0ass2103.0300 2021. URL httpps://axxii..rgg
org/ http://iiiirrg/a///////a// aa////////210/ 03012
[6] J. Chase Kew, B. Ichter, M. Bandari, T.-W. E. Lee, and A. Faust. Neural collision clearance estimator for batched motion planning. In S. M. LaValee M. Lin, T. Ojala, D. Shell, and J. Yu, editors, Algorithmic Foundations of Robotics XIV, pages 73-89, Cham, 2021. Springer International Publishing. ISBN 978-3-0330-66723-88
[7] B. Chazelle. Convex partitionn of polyhedra: A lower bound and worst-case optimal algorithm. SIAM J. Comput., 130))488-507, 1984. doi: 10.1137/0213031. /ntpss//:/// org/10
1137/0213031
[8] B. Chen, B. Dai, Q- Lin, G. Ye, H. Liu, and L.. Song. Learning plan in high dimensions via neural exploration-exxlooiaaiio trees. In 8th International Conference on Learning Represen- tations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020. URL https://openreviet net/ pett/forum?iderrggDAAW...
[9] M. Cherif. Kinodynamic motion planning for all-terrain wheeled vehicles. In 1999 IEEE International Conference on Robotics and Automation, Marriott Hotel, Renaissance Center, Detroit, Michigan, USA, May 10-15, 1999, Proceedings, pages 317-322. IEEE Robotics and Automation Society, 1999. doi: 1..109/ROBOT..1999.66999 URL httpsttps://doi org/10
1109/R0E0T, 1999. 769998
[10] H. M. Choset, K. M. Lynch, S. Hutchinson, G. Kantor, W. Burgard, Kavraki, S. Thrun, and R. C. Arkin. Principles of robot motion: theory, algorithms, and implementation. MIT press, 2005.
[11] B. J. Cohen, M. Phillips, and M. Likhachev. Planning single-arm manipulations with n-arm robots. In D. Fox, L. E. Kavraki, and H. Kurniawati, editors, Robotics: Science and Systems X, University of California. Berkeley, USA, July 12-16. 2014, 2014. doi: 10. 1..5677/S..2014..... URL http::// hectp://www.r http://wwww.boicccppeeeeeeagg// wwwpor/gg///////// html
[12] H. Dai, L. C. Wang. R. Singh, P. Huang, and P. Kohli. Learning transferable graph exploration. In H. M. Wallach, H. Larochelle, A. Beygelzimer, F. d' Alché-Buc, E. B. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 25 2514-2525, 2019. URI Utt.htttss:/pproeeediii
neur heurips... cc/ccccpp//accccccccccccccc /209/ html
hash/afe4300 2aaaa//eee.530222000000000002223
[13] N. Das and M. Yip. Learning-bar based proxy collision detection for robot motion planning applications. IEEE Transactions Roboties, (064)):099611144 2020.
[14] R. Diankov and J. Kuffner. Randomized statistical path planning. 2007 IEEE/RSJ Inter- national Conference Intelligent Robots and Systems, October 29 November 2, 2007, Sheraton Hotel and Marina, San Diego California, USA, pages 1 1-6. IEEE, 2007. doi:
10.1109/IRO.200 200. 4399557. URL http:: //doi. org/ 110.11109/1IG IROS. 2007 4399557
11

---

[15] B. R. Donald, P. G. Xavier, J. F. Canny, and J. H. Reif. Kinodynamic motion planning. J. ACM. 4048) 1066, 1993. doi: 10.1 10.1145/74114..741555 URL URL httpp:://oii...... org/ 12////1111 1
174147. 174150
[16] Drori, A. Kharkar, W. R. Sickinger, Kates, Q. Ma, S. Ge, E. Dolev, B. Dietrich, D. P. Williamson, and M. Udell. Learning to solve combinatorial optimization problems real-world graphs in linear time. In M. A. Wani, F. Luo, X. A. Li, D. Dou, and F. Bonchi, editors, 19th Machine Learning and Applications. ICMLA 2020, Miami, FL, USA, December 14-17, 2020, pages 19-24. IEEE, 2020, doi: 10. 109/CMMA5129442000 00013. UtLhtttp:://de org/ 10. 1109/ ICMLA51294 2020 00013
IEEE International Conference
[17] S. Emmons, A. Jain, M. Laskin, T. Kurutach, P. Abbeel, and D. Pathak. Sparse graph- ical memory for robust planning. In H. Larochelle, M. Ranzato, R. Hadsell, M. Bal- can, and H. Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6- 12, 2020, viriual, 2020. URL https: pttpppppp.ppooocddiiii.....es nww.nnig............mmmm..mr.... wtt.lcccpppppeeee ppaper/2020/// h2sh//hahh/ 0a122222352222262266622228832282
Abstract.
[18]
B. Eysenbach, R. Salakhutdinov. and S. Levine. Search on the replay buffer: Bridg- ing planning and reinforcement learning. In H. M. Wallach, H. Larochelle, A. Beygelz- imer, F. d' Alché-BBuc E. B. Fox, and R. Garnett, editors, Advances in Neural Infor- mation Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 15220-15231, 2019. URL https://proceeding neurips. httpaaapp..cpppppe/////////// wtt.c//ppppee/1///neaaaa wee.eeeeeaaeeeee--bbbbrreaeeeet www.rbat..tt....
[19] D. Gammell, S. S. Srinivasa, and T. D. Barfoot. Bit#; Batch informed trees for optimal sampling-basse based planning via dynamic programming implicit random geometrie graphs. CoRR, abs/1 ftss/1405.584,, 2014. http::// //tttp//arxiv... ooexvv.orr//ooo abs/1405..00
[20] E. N. Gilbert. Random plane networks. Journal of the sociery for industrial and applied mathematics, 944:5333-543, 1961.
[21] N. Haghtalab, S. Mackenzie, A. D. Procaccia, O. Salzman, and S. Srinivasa. The provable virtue of laziness in motion planning. In S. Kraus, editor, Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI 2019, Macao, China, August 10-16, 2019, pages 6161-6165. ijeai.org. 2019. doi: 10.24963/iccai.20198555 URL https //doi.org// 10. (4993/iijcai 2019/855
[22] F. Heiden, I.. Palmieri, S. Koenig, K. O. Arras, and G. S. Sukhatme. Gradieettinformed path smoothing for wheeled mobile robots. In 2018 IEEE International Conference on Robotics and Automation, ICRA 2018, Brisbane, Australia, May 21-25, 2018, pages 1710-1717. IEEE, 2018. doi: 20.1 8460888. 8460818
URL hittps://don org/ 100 1119/119IRRAAA 2018
[23] S. Hochreiter and J. Schmidhuber. Long Short-Term Memory. Neural Computation, 98): 1735-1780. 11 1997. ISSN 0899-7667.
doi: 19w.///9c..199.9.9866
URL https
//doi. 100 w161/eeco.... 1997 8.8.
[24] B. Ichter and M. Pavone. Robot motion planning in learned latent spaces. IEEE Robotics Autom. Lett., 433):2407-241,, 2019. doi: 10. RA11009..2.....0000 29019999999 URL htt/htttt////ooorrg
1109/LRA. 2019. 2901898
[25] B. Ichter, J. Harrison, and M. Pavone. Learning sampling distributions for robot motion planning. In 2018 IEEE International Conference on Robotics and Automation, ICRA 2018, Brisbane, Australia, May 21-25, 2018, pages 7087-7094. IEEE, 2018. doi: 11110///AA..21...44000 8460730. URL https://doi. org/ 10. 110.1119/10IT 1111//////IAAA.. ICRA. 2018. 8460730
[26] S. loffe and C. Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International conference on machine learning, pages 448-456. PMLR, 2015.
12

---

[27] L. Janson and M. Pavone. Fast marching trees: a fast marching sampling based method for optimal motion planning in many dimensions extended version. CoRR, abss/336..3532 2013.
URI. http::ttt:::artt org/ abs/ 3532
[28]
Jiménez, F. Thomas, and C. Torras. Collision detection algorithms for motion planning. In Robot motion planning and control, pages 305-343. Springer, 1998.
[29] T. Jurgenson and A. Tamar. Harnessing reinforcement learning for neural motion planning.
In A. Bicchi, H. Kress-Gazit and S. Hutchinson, editors, Roboties: Science and Systems XV. University of Freiburg, Freiburg im Breisgau, Germany, June 22-26, 2019, 2019. doi: 10.1 2019.XV.026. URL https:ttt:///// /dotpss:/doi.... orgoorg//// 1...1..00//.. /SS 2019 XV 026
[30] M. Kalakrishnan, S. Chitta, E. Theodorou, P. Pastor, and S. Schaal. Stomp: Stochastic trajectory optimization for motion planning. In 2011 IEEE international conference on robolics and automation, pages
IEEE, 2011.
[31] S. Karaman and E. Frazzoli. Sampling-bas based algorithms for optimal motion planning. Int.
J. Robotics Res., 30(7):846-894, 2011. doi: 10.11770078554911146660 URL https
//doi. org. 017111117700077349444440900
[32] E. B. Khalil, H. Dai, Y. Zhang, B. Dilkina, and L. Song. Learning combinatorial optimization algorithms over graphs. In I. Guyon, U. von Luxburg, S. Bengio, H. M. Wallach, R. Fergus, S. V. N. Vishwanathan, and R. Garnett, editors, Advances Neural Information Processing Systems 30: Annual Conference on Neural Information P Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pages 6348-6358, 2017, /ttp:///.RRRttttpp/rreeeedeeeeaa
neur
[33] A. Khan, A. Ribeiro, V. Kumar, and A. G. Francis. Graph neural networks for motion planning. CoRR, 0ttss2000.062444 2020. URL https://aarsitti org/ abs/aabb....///////////////aaa 06248
[34] K. Kondo. Motion planning with six degrees of freedom by multistrategic bidirectional heuristic free-space enumeration. IEEE Trans. Robotics Autom 7(3):667-277, 1991. doi: 10. 109/70.
88136. URL.btts:://oo: httpi/oo...rr///// 1t////00..10///0 881366
[35] S. M. La Valle. Planning Algorithmss. Cambridge University Press, 2006. ISBN 9780511546877. doi: 10. 10.1017/CB0978051154444
URL http:tt//p//amnnggg . www..iuc...... edu/
[36] S. M. Valle and J. J. K. Jr. Randomized kinodynamic planning. In 1999 IEEE International Conference on Robotics and Automation, Marriott Hotel, Renaissance Center, Detroit, Michigan, USA, May 10-15, 1999, Proceedings, pages 473 479. IEEE Robotics and Automation Society, 1999. doi: 1..110/ROBBOT.19997777000 770022
URL https:://doii org/ 1109/ROBOT 1999
[37] L. Lee, E. Parisotto, D. S. Chaplot, E. P. Xing, and R. Salakhutdinov. Gated path planning networks. In J. G. Dy and A. Krause, editors, Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmssässeen, Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pages html
PMLR, 2018.
URL SoLLhttppp/proceedinn
mlr. wwwp://www....s/////e/eeeeeee
[38] Q. Li, F. Gama, A. Ribeiro, and Prorok. Graph neural networks for decentralized multi- path planning. CoRR, 1ess/992..609... 2019. URL httphhtt///aaae http:://arrxiv.orr//bbb///////// ht/////////99/ 1wtpp/11911..0999515
[39] K. M. Lynch and M. T. Mason. Stable pushing: Mechanics, controllabilliyy, and planning. Int.
J. Robotics Res., 15(6)533--556 1996. doi: 10. 10.117702273344999011006666
URL https
//doi org 1171 (1117700778364999 11777772278999900000000
[40] S. O. B. S. S. Madaan, R. Learning adaptive sampling distributions for motion planning by self-imitation. Workshop on Machine Learning in Robot Motion Planning, IEEE IROS, 2018.
[41] A. Mandalika, O. Salzman, and S. Srinivasa. Lazy receding horizon a for efficient path planning in graphs with expensive- toonniive----valateee edges. In M. de Weerdt, S. Koenig, G. Rôger, and M. T. J. Spaan, editors, Proceedings of the Twenty-Eightt International Conference on Automated Planning and Scheduling, ICAPS 2018, Delft The Netherlands, June 24-29, 2018 pages 476-484, AAAI Press, 2018
URL. https:/ /aaaai //aaaaaaa.rr//aa/aa/a//..//.. orgg/cs// ocs/ index.ddxx/// php/ICAPS/
CCAPP///paper//iies///
13

---

[42] A. Mandalika, S. Choudhury, O. Salzman, and S. S. Srinivasa. Generalized lazy search for robot motion plamning: Interleaving search and edge evaluation via event-based toggles. In J. Benton, N. Lipovetzky, F. Onaindia, D. E. Smith, and S. Srivastava, editors, Proceedings of the Twenty-Ninth International Conference on Automated Planning and Scheduling, ICAPS 2018, Berkeley, CA, USA, July 11-15, 20/9, pages 745 AAAI Press, 2019. URLhttps
7 //aaai.org// wwtp:///////////ooeeeeeeeee..eoe www//idex..i/eeeeieoiieeeeeeiiim phpp CCCoPP/artiileeviieree
[43] M. W. Mueller, M. Hchn, and R. D' Andrea. A computationally efficient motion primitive for quadrocopter trajectory generation. IEEE Transactions on Robotics, 31(6):1294-1310, 2015.
[44] S. Niu, S. Chen, H. Guo, C. Targonski, M. C. Smith, and J. Kovacevic. Generalized value iteration networks: Life beyond lattices. In S. A. Mcllraith and K. Q. Weinberger, editors, Proceedings of the Shiirty-eecod AAAI Conference on Artificial Intelligence, (AAAI-18), the 30th innovative Applications of Artificial Intelligence (IAAI-18), and the 8th AAAI Symposium on Educational Advances in Artificial Intelligence (EAAI-18), New Orleans, Louisiana, USA, February 2-7, 2018, pages 6246-6253, AAAI Press, 2018. URL/tttps: /wwww/wwwwwww/.. aaai org/ ocs/index. http://AAAAAAAIB///pp///////////
[45] S. M. Persson and I. Sharf. Sampling-based a* algorithm for robot muth-planning. Int. J. Robotics Res., 33(13):1683- 1708. 2014. doi: 10.177702783649144477777 URL https 7/doi.org
1177 11777007736441744777777777
[46] C. R. Qi H. Su, K. Mo, and J. Guibas. Pointnet: Deep learning on point sets for 3d classification and segmentation. In 2017 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2017, Honolulu, HI, USA, July 21-26, 2017, pages 77-85, IEEE Computer Society, 2017. doi: 10.1109/CVR.2207..UU URL https://doi org/ 10. 10011/109PPPP 2017
16
[47] A. H. Qureshi, Y. Miao, A. Simeonov, and M. C. Yip. Motion planning networks: Bridging the gap between learning- based and classical motion planners. IEEE Transactions on Robotics, 37 (1):48-66 66, 2021. doi: 10.1 (09/TRO.2000.30000000
[48] J. H. Reif. Complexity of the mover's problem and generalizations. In 20th Annual Symposium on Foundations of Computer Science (sfcs 1979), pages 421-427, 1979. doi: 1009/SSSS 1979.10.
[49] S. Rendle, C. Freudenthaler, Z. Gantner, and L. Schmidt-Thiema BPR: bayesian per- sonalized ranking from implicit feedback. In J. A. Bilmes and A. Y. Ng, editors, UAI 2009, Proceedings of the Twenty-Fifih Conference on Uncertuinty in Artificial In- telligence, Montreal, QC, Canada, June 18-21, 2009, pages 452-461. AUAI Press, 2009.
http:///lpppt...orrr//////aaaaaa 2karticle htt.:cceee.--1600pprrreeeeeeieie 1d=22
jsp? httrmmmmummmmmm
[50] N. Savinov, A. Dosovitskiy, and V. Koltun. Semi- parametric topological memory for navigation. In 6th International Conference Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceedings. OpenReview.net, 2018. URL attps://openrevvee. net/ wtt.:ooormmdiimi/ SyggwwwGRR
[51] J. Schullan, Y. Duan, J. Ho, A. Lee, I. Awwal, H. Bradlow, J. Pan, S. Patil, K. Goldberg, and Abbeel. Motion planning with sequential convex optimization and convex collision checking. The International Journal of Robotics Research, 33(9); 2014.
[52] D. Shah, Eysenbach, N. Rhinehart, and S. Levine. RECON: rapid exploration for open-world navigation with latent goal models. CoRR, abs/2104.05859, 2021. UtLpttts:///axx org/ abs/2104.05853
[53] M. P. Strub and J. D. Gammell. Advanced bit (abit*): Sampling based planning with advanced graph-searde techniques. 2020 IEEE International Conference on Robotics and Automation,
ICRA 2020, Paris, France, May 31 August 31, 2020, pages 130-136. IEFE, 2020. doi: 10. /01101////4994.5220000 010094552222091955500 URIpst //tp:::///ooooooooo org/10 1109 0A0009/ICRA4445555 2020
9196580
14

---

[54] R. A. M. Strudel, R. Garcia, J. Carpentier, J. Laumond, I. Laptev, and C. Schmid. Learning obstacle representations for neural motion planning. CoRR. abs/2008.111777 2020. URL https://arxiv. org/ abs/2008. 11174
[55] A. Tamar. S. Levine, P. Abbeel, Y. Wu, and G. Thomas. Value iteration networks. In D. D. Lee, M. Sugiyama, U. von Luxburg. Guyon, and R. Garnett, editors, Advances in Neural Information Processing Systems 29: Anmual Conference on Neu- ral Information Processing Systems 2016, December 5-10, 2016, Barcelona, Spain. pages 2146-2154, 2016. URL https::/ https://rrcceeddngg www.oiiiinnnnnnnnnneeeeeeeeeeeee neurips cwtnrpps.cpppp.. ctlpcc//ppppp.. http/appp////// ppaper/206/hhah// Abstract.
[56] H. Tang, Z. Huang. J. Gu, B.-L. Lu, and H. Su. Towards scale-invariant graph-related problem solving by iterative homogeneous gmns. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors. Advances in Neural Information Processing Systems, volume 33, pages 1581 1-5822. Curran Associates, Inc., 2020. URL /ttp:://///ooceeiiggggg neurips cc/ pdf
[57] M. Toussaint. Logic-geometric programming: An optimization approach combined task and motion planning. In IJCAI, pages 1930-1936, 2015.
[58] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. Kaiser, and I. Polo- sukhin. Attention is all you need. In I. Guyon, U. von Luxburg, S. Bengio, H. M. Wallach, R. Fer- gus, S. V. N. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pages 5998 5998-6008, 2017. URL URt/attss:// htt///aahh//// cc httppp//00.///////e./.36//666660
neurips wwtaaaattsttrtttttttaaaa
[59] P. Velickovic, L. Buesing, M. C. Overlan, R. Pascanu, O. Vinyals, and C. Blundell. Pointer graph networks. In H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems 33: Annual Con-
ference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6- 12, 2020, virtual, 2020. URL httpss//pproceeeinngg ierpiiiinnnnnneuurieee httpppppcccpppapp//ppp/eee 1766666096aaaeb11333000033333333 Abstrefbbbbbbtbtt......mo html
[60] P. Velickovic, R. Ying. M. Padovano, R. Hadsell, and C. Blundell. Neural execution of graph algorithms. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.ner, 2020. URL. net/forrum?dd-SkgKKOK
[61] K. Xu, J. Li, M. Zhang. S. S. Du, K. Kawarabayashi, and S. Jegelka. What can neural networks reason about? In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020. URL httpss///openreviee
net/forum?id rdbbrdderrJs
[62] Xue and P. R. Kumar. The number of neighbors needed for connectivity of wireless networks. Wireless networks, 16(2):169-181, 2004.
[63] Y. Yan, K. Swersky, D. Koutra, P. Ranganathan, and M. Hashemi. Neural execution en- gines: Learning to execute subroutines. In H. Larochelle, M. Ranzato, R. Hadsell, M. Bal- can, and H. Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6- 12, 2020, virtual, 2020. URL https: / http:///ewcccc...o/o//o nwwripseerppp.... cc/ Saaper2020/haaz Abstract.htt
[64] G. Yang, A. Zhang, A. S. Morcos, J. Pineau, P. Abbeel, and R. Calandra. Plan2vec: Unsupervised representation learning by latent plans. In A. M. Bayen, A. Jadbabaie, G. J. Pappas, P. A. Parrilo, B. Recht, C. Tomlin, and M. N. Zeilinger, editors, Proceedings of the 2nd Annual Conference on Learning for Dynamics and Control, LADC 2020, Online Event, Berkeley, CA, USA, 11-12 June 2020, volume 120 of Proceedings of Machine Learning Research, pages 935-946. PMLR, 2020. URL http:://proeeedings mlr...ss..r.......m.... mlr press/ w120 haw.2///yaagg.....m html
15

---

[65] C. Zhang. J. Huh, and D. D. Lee. Learning implicit sampling distributions for motion planning. In 2018 IEEE/RSJ International Conference Intelligent Robots and Systems, IROS 2018, Madrid, Spain, October 1-5, 2018, pages 3654-3661, IEFF, 2018. doi: 10.1109/1ROS 201 8. 8594028. URL htl.sttps::/doo org 10. 2010/99RRRSS.. 2018. 8594028
[66] B. Zhou, Gao, L. Wang, C. Liu, and S. Shen. Robust and efficient quadrotor trajectory generation for fast autonomous flight. IEEE Robotics and Automation Letters, 4(4):3529-352) 2019.
[67] Z. Zhu, E. Schmerling, and M. Pavone. A convex optimization approach to smooth trajectories for motion planning with car-like robots. In 2015 54th IEEE conference decision and control (CDC), pages 835-842. IEEE, 2015.
[68] M. Zucker, N. Ratliff, A. D. Dragan, M. Pivtoraiko, M. Klingensmith, C. M. Dellin, J. A. Bagnell, and S. Srinivasa. Chomp: Covariant hamiltonian optimization for motion planning. The International Journal of Robotics Research, (0(9-10):166) 1193, 2013.
16


Reviews:
[{"review_id": "zsCOIDeu-do", "reviewer": "Reviewer_vokm", "summary": "This paper proposes a learning-based algorithm for reducing the planning time for collision-free robot motion planning problems. The author rightly notes that the bottleneck for motion planning is collision checking, especially along the vertices on the edges of a search tree, and proposes to learn a function, called GNN Path Explorer, that prioritizes the edges to check collisions. Based on this priority information, the algorithm builds a path from a start to a goal, while checking collisions only on the edges that have the highest priority out of the ones that have not been considered so far. This tree is then fed to a GNN Path Smoother, which processes the path and modifies it to one that has a lower cost. Training data is generated by past planning experience, in which the oracle is used to compute the optimal path on the current search tree. It is demonstrated on several domains, ranging from 2D environments with narrow passages and a point robot, to domains with high dimensional configuration spaces (c-space). \n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper has a clear motivation that stems from a correct understanding of the bottleneck in motion planning. I agree that the main shortcoming of the previous works, as the author notes, is the fact that they focus on reducing sample complexity rather than collision checking.\n\nThe technical aspect of the paper is sound. The idea of using the graph of vertices sampled from the c-space and edges constructed by the k-nearest-neighbor algorithm is much more plausible than the past works that use the workspace as inputs, and the use of GNN to process such input is appropriate. I also found the interaction between the Path Explorer and the planner to be interesting, novel, and useful. Unlike most algorithms that try to either learn a sampler or directly predict a path, iteratively adding edges from the RRG and to the tree not only speeds up planning but also preserves probabilistic completeness guarantee. \n\nThe experiments are convincing. The proposed algorithm reduces the number of collisions while improving the path cost in a variety of domains.\n\nI have a couple of suggestions to improve the paper. The first is regarding the visualizations of the empirical results. The use of line-connected plots in Figure 5 (a) and (d) is inappropriate, as there is no trend across the x-axis that the figure is trying to illustrate. A bar graph seems more appropriate here. Also, instead of Figure 5(d), I would like to see a bar graph that shows the breakdown of the total planning time - how much it is due to collision checking, GNN prediction, etc. Lastly, the confidence intervals on Figures 5(b) and 5(c) would be needed.\n\nThe second is on the description of technical details. In 4.1, the paper states that GNN Path Explorer finds a feasible path (L157), but this is not true, and the GNN simply outputs the priority on the edges. The feasible path is built based on this priority prediction. I also had to read the paper a couple of times to understand the interaction between the RGG <V, E> and the tree T_i that it builds (I still don’t understand what E_i is). The description is rather scattered between sections 4.1 and 5.1, and the paper would benefit from pseudocode that describes the interaction.\n\nI also have a couple of questions:\n\n- Why does the Path Explorer use only V, E, and O? It seems it could also benefit from T_i as well\n- Why do you only sample edges from the frontier of the tree? Isn’t there a chance of finding a solution by sampling edges to the internal node of the tree? Perhaps I misunderstood the term frontier - it typically refers to the leaf nodes of a tree. Here, it is referring to the edges. Can you define what frontier means?\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "Did not count"}, "extra_text": {}}, {"review_id": "w6STCWWkXG", "reviewer": "Reviewer_FpjY", "summary": "At a high-level, this work proposes GNNs as models for biasing the sampling of edges and nodes to connect in a random geometric graph. The chief goal is to reduce the amount of collision-checking necessary to plan a path from a start to a goal. Two models are presented: one that performs the above, and another that then smooths the returned path in order to further reduce path cost.\n\nSpecifically, the proposed approach first constructs a random geometric graph (RGG) by sampling points from free space. Then, a GNN-parameterized policy iteratively guides the selection of RGG edges for collision-checking. A collision-free path is found when the start and goal nodes are connected on the RGG. The algorithm then leverages another GNN to smooth the solution path. Both GNNs are learned by imitating the solutions of existing oracles. The proposed approach achieves higher success rates, lower collision checks, and comparable path costs on a set of benchmark motion planning tasks compared to existing traditional and learning-/sampling-based algorithms.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n\n- This paper tackles a problem with high importance, focusing on collision-checking (a critical component in sampling-based motion planning algorithms) and how it can be improved (i.e., reducing how many times it is necessary) by learning-based techniques.\n\n- Using GNNs to smooth discrete paths appears to this reviewer to be a novel technique.\n\n- The theoretic probabilistic completeness of the underlying sampling-based motion planning algorithm is maintained even when combined with the GNN-based learning components.\n\n- The experiments demonstrate that the proposed method is capable of reducing collision checks without compromising much in terms of solution quality.\n\nMajor Weaknesses: \n- The writing has typos and is unpolished/imprecise in some areas. The paper would benefit from another editing pass. Some examples are: \n    - Line 2 - \"Checking collision\" vs \"Collision-checking\" or \"Checking collisions\"\n    - Line 20 - It is slightly unclear what \"with a few degrees of freedom\" means (it is also imprecise). Does it mean a small amount of degrees of freedom? If so, a slightly more precise way of writing this is \"with few degrees of freedom\"? Even better, stating how many degrees of freedom (roughly, is it 2-5, 10-20, 100?)\n    - Line 71 - \"which could be naturally incorporated with reinforcement learning or imitation learning.\" What does \"incorporated\" mean here? Would a better phrase be \"naturally tackled with\" or \"where reinforcement learning or imitation learning could naturally be applied\"?\n    - Line 107 - \"specifically focus\" should be \"specifically focuses\"\n    - Line 142 - \"a typical attention function\", there are many types of attention, and a citation should probably be present here referring to which exact type is being used. Also, the writing does not explicitly indicate that this is the exact attention mechanism used in this work.\n    - Line 198 - Is the L2 distance actually what is appended? The L2 distance is usually indicated like $\\parallel v - v_g \\parallel_2$ rather than parentheses.\n    - This is not an exhaustive list. In general, impreciseness makes it hard for readers to grasp the concepts being discussed.\n\n- Motion planning has a rich set of prior literature and, as a result, it is difficult to capture all of the relevant work in the field in a paper with space constraints. However, related work such as (Mandalika et al. in ICAPS 2019) should be included and briefly discussed as they also addresses the issue of reducing edge evaluations in a large graph.\n\n- The text on some of the figures (e.g., 2, 3, 5, and 7) is hard to read because of its small size. \n\n- The rationale behind the design choices of the proposed algorithm are not explained very clearly. A lot of algorithm components are merely presented as-is. There is no insight or intuition as to why things are being done this way, what it enables, or how it addresses the problem. Some examples:\n    - Line 198, why are these features chosen specifically? What is it about the L2 distance between a node and the goal that is more informative than the difference between them? \"serve as heuristics for the GNN to be more informed about which node is more valuable\" does not provide much information. Further, why does $y_l$ not use the same L2 distance feature? \n    - How are obstacles encoded? Line 203 seems to indicate that they are boxes and the obstacle information is the extremal vertices? Is that correct?\n    - Why does the method use a GNN smoother for post-processing? Why not use the gradient-informed path smoothing described in Section 5.2 instead? The experiments mainly show that smoothing in general is helpful for reducing path cost (although at the cost of increasing collision checks, sometimes significantly so), and it is difficult to identify if it is this _specific_ GNN-based smoother that is necessary or if another method such as the gradient-informed path smoothing described in Section 5.2 or simple rewiring (as in RRT*) would work just as well with the GNN-based path explorer.\n\n- There are also a few questions about the experiments. Chiefly,\n    - Why does RRT* fail about 20-40% of the time in higher-dimensional settings? Is it timing out?\n    - Why does RRT* have way more collision checks in 2D compared to NEXT but way less in high-dim environments?\n\nMinor Comments:\n\n- Figure 5 (d) should probably use a logarithmic y-axis scale, since the slow NEXT values dominate the graph.\n- Related to the comment about writing above, typos should also be removed such as the space between * and ( at the end of line 111.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "There are some questions raised in the main review which apply as limitations.\n\nRegarding societal impact, however, the Broader Impact section (Line 375 and onwards) does not really address the broader societal impact of advancements in motion planning. Motion planning is a fundamental capability of robotics in general, and so any advancements benefit both positive and negative societal impacts. The authors did mention safety, biases, and interpretability, although these topics should probably have received more of a discussion (especially so for motion planning where a robot is basing its motion around other humans, for example, based on a neural network output). ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}, {"review_id": "vXT9p68VxBe", "reviewer": "Reviewer_fGnh", "summary": "The paper leverages graph based learning to improve sampling based motion planning, specifically on reducing edge evaluations and also on smoothing computed paths for reducing path length.", "questions": "", "limitations": "", "rating": 7, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper's idea of using graph NN for finding patterns from an initial sample of nodes in the workspace is very interesting. The key motivation for the paper to pursue this work is to address the expensive collision checking operations by reducing the number of evaluations. However, the paper neglects the existing field of lazy motion planning which addresses the same problem as this paper[lazy_prm,lazy_sp, gls] . Methods have shown to use much lower number of edge evaluations to find the path~[gls] and also have leveraged learning to improve lazy planning [lazy_experience]. For e.g. [lazy_experience] can solve the 7d manipulator problem within 35 edge evaluations while the proposed method takes 350 evaluations (though on different environments]. The proposed method needs to evaluated with existing lazy motion planning methods to show if the proposed method will benefit the community.\n\nLearning based motion planning also enables using sensory perception directly without requiring models of the environment. If the proposed method cannot compare to lazy motion planning methods, showing the method working with vision based collision avoidance~[object_collision] could open up some application areas for the approach and be a useful contribution. \n\n\n\n\nReferences:\n\n[lazy_prm] Bohlin, Robert, and Lydia E. Kavraki. \"Path planning using lazy PRM.\" Proceedings 2000 ICRA. Millennium Conference. IEEE International Conference on Robotics and Automation. Symposia Proceedings (Cat. No. 00CH37065). Vol. 1. IEEE, 2000.\n\n[lazy_sp] Haghtalab, N., Mackenzie, S., Procaccia, A., Salzman, O., & Srinivasa, S. (2018, June). The provable virtue of laziness in motion planning. In Proceedings of the International Conference on Automated Planning and Scheduling (Vol. 28, No. 1).\n\n[gls] Mandalika, A., Choudhury, S., Salzman, O., & Srinivasa, S. (2019, July). Generalized lazy search for robot motion planning: Interleaving search and edge evaluation via event-based toggles. In Proceedings of the International Conference on Automated Planning and Scheduling (Vol. 29, pp. 745-753).\n\n[lazy_experience] Bhardwaj, M., Choudhury, S., Boots, B., & Srinivasa, S. (2019). Leveraging experience in lazy search. arXiv preprint arXiv:1907.07238.\n\n[object_collision] Danielczuk, M., Mousavian, A., Eppner, C., & Fox, D. (2020). Object rearrangement using learned implicit collision functions. arXiv preprint arXiv:2011.10726.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper seeks to improve the computational efficiency of sample-based motion planning by reducing the number of collision checks. The paper proposes an algorithm that learns to prioritize the order in which edges in a sample-based planning graph are checked for collision. Following this prioritization, a path is generated between the start and goal nodes and then smoothed to reduce cost. Results on a variety of different planning domains demonstrate that the proposed approach is more computationally efficient than contemporary methods, while still providing paths with similar cost.

The paper considers an important problem in sample-based robot motion planning, namely reducing the computational cost associated with collision checking. The reviewers agree that the work is well motivated and that the proposal to use graph neural networks to guide edge evaluations is technically sound, novel, and principled. The experiments effectively convey the advantages of this strategy. The reviewers raised some initial concerns, notably those related to the merits relative to lazy motion planning strategies, most if not all of which were adequately addressed in the author response and discussion phase. The authors are encouraged to make sure that the next revision of the paper reflects this discussion.
Decision: Accept (Poster)