Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: 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.
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.

Learning 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. 




References:

[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.

[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).

[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).

[lazy_experience] Bhardwaj, M., Choudhury, S., Boots, B., & Srinivasa, S. (2019). Leveraging experience in lazy search. arXiv preprint arXiv:1907.07238.

[object_collision] Danielczuk, M., Mousavian, A., Eppner, C., & Fox, D. (2020). Object rearrangement using learned implicit collision functions. arXiv preprint arXiv:2011.10726.
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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). 

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.

The 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. 

The experiments are convincing. The proposed algorithm reduces the number of collisions while improving the path cost in a variety of domains.

I 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.

The 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.

I also have a couple of questions:

- Why does the Path Explorer use only V, E, and O? It seems it could also benefit from T_i as well
- 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?


limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.

Specifically, 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.
main_review: Strengths:

- 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.

- Using GNNs to smooth discrete paths appears to this reviewer to be a novel technique.

- The theoretic probabilistic completeness of the underlying sampling-based motion planning algorithm is maintained even when combined with the GNN-based learning components.

- The experiments demonstrate that the proposed method is capable of reducing collision checks without compromising much in terms of solution quality.

Major Weaknesses: 
- The writing has typos and is unpolished/imprecise in some areas. The paper would benefit from another editing pass. Some examples are: 
    - Line 2 - "Checking collision" vs "Collision-checking" or "Checking collisions"
    - 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?)
    - 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"?
    - Line 107 - "specifically focus" should be "specifically focuses"
    - 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.
    - 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.
    - This is not an exhaustive list. In general, impreciseness makes it hard for readers to grasp the concepts being discussed.

- 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.

- The text on some of the figures (e.g., 2, 3, 5, and 7) is hard to read because of its small size. 

- 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:
    - 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? 
    - How are obstacles encoded? Line 203 seems to indicate that they are boxes and the obstacle information is the extremal vertices? Is that correct?
    - 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.

- There are also a few questions about the experiments. Chiefly,
    - Why does RRT* fail about 20-40% of the time in higher-dimensional settings? Is it timing out?
    - Why does RRT* have way more collision checks in 2D compared to NEXT but way less in high-dim environments?

Minor Comments:

- Figure 5 (d) should probably use a logarithmic y-axis scale, since the slow NEXT values dominate the graph.
- Related to the comment about writing above, typos should also be removed such as the space between * and ( at the end of line 111.
limitations_and_societal_impact: There are some questions raised in the main review which apply as limitations.

Regarding 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_title: null

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)