Motion Planning Transformers: One Model to Plan them All
Authors: Jacob John Johnson
Linjun Li
Ahmed Qureshi
Michael C. Yip
Venue: ICLR 2022 Submitted (2022)
Keywords: Motion Planning
Attention Networks

Abstract: Transformers have become the powerhouse of natural language processing and recently found use in computer vision tasks. Their effective use of attention can be used in other contexts as well, and in this paper, we propose a transformer-based approach for efficiently solving complex motion planning problems. Traditional neural network-based motion planning uses convolutional networks to encode the planning space, but these methods are limited to fixed map sizes, which is often not realistic in the real world. Our approach first identifies regions on the map using transformers to provide attention to map areas likely to include the best path and then applies traditional planners to generate the final collision-free path. We validate our method on a variety of randomly generated environments with different map sizes, demonstrating reduction in planning complexity and achieving comparable accuracy to traditional planners.


Under review as a conference paper at ICLR 2022
MOTION PLANNING TRANSFORMERS: ONE MODEL TO PLAN THEM ALL
Anonymous authors Paper under double-bling review
ABSTRACT
Transformers have become the powerhouse of natural language processing and recently found use in computer vision tasks. Their effective use of attention can be used in other contexts well, and in this paper, we propose transformer- -based approach for efficiently solving complex motion planning problems. Traditional neural network-based motion planning uses convolutional networks to encode the planning space, but these methods are limited to fixed map sizes, which is often not realistic in the real-world. Our approach first identifies regions on the map using transformers to provide attention map areas likely to include the best path, and then applies traditional planners to generate the final collision path. We validate method variety of randomly generated environments with different map sizes, demonstrating reduction in planning complexity and achieving comparable accuracy traditional planners.
INTRODUCTION
Motion planning is integral component of any 2D navigation stack. It is an age-old problem with more than few decades of innovative solutions. By far the most popular recent methods involve constructing trees graphs in the planning space by randomly sampling points (La Valle & James J. Kuffner 2001] Kavraki et al. 1996) or discretizing the space into grids (Hart et al. 1968).
Although these methods pro- vide theoretical guarantees, they do not scale well to problems with larger planning spaces and crowded environments. This is frequent problem for robots in large warehouses and house- hold cleaning robots. Re- cently, learning-based methods that leverage environment struc- ture from the given data have been proposed for these kind of problems. They combine con- volution neural networks (CNN) and multi-layer perceptrons (MLP) to predict where samples should be generated to construct trees Qureshi al. 2019 Johnson al. 2020 Kumar et al. 2019), but do not extend maps of larger sizes. Methods such as Value Iteration Network (IN)(TTmaa et al.) 2016). which do extend to maps of different sizes, perform poorly with larger maps (Nardelli et al.) 2018). Hence, our ever-expanding pursuit of automation, we need planning algorithms that can scale up while effectively keeping the planning problem's 's complexity and computation time in check.
Figure I: Given a planning problem (left), we propose hierar- chical approach to planning. In our method, the MPT proposes a region where a valid path might exist (center). sampling- based planner is used to find collision-fres path (right) given the proposed region.
The trajectory of a local plan is influenced by the orientation of far-away obstacles, similar to language models where the semantics a sentence inferred only by reading the entire sentence. The ability of transformers to understand the syntactic and semantic structure of sentences was shown in Vaswani et al. (2017). Thus the capacity of transformers to learn such connections efficiently is the motivation of this work. Our model plans in two-stage approach (Fig. D first transformer-bast based region proposal network recommends a region where potential path can exist. We refer to this module as the Motion Planning Transformer (MPT). Next, sampling-based motion planner (SMP) tries to plan

---

Under review as a conference paper at ICLR 2022
path given the proposed region. Since the inputs to the transformers are sets rather than vectors, maps of different sizes can be used, and by reducing the search space, SMP can generate solutions much faster with fewer nodes.
We assess the performance of MPT augmented SMPs (Karaman & Frazzoli 2011 Gammell et al. 2014) on synthetic and real-world dataset comprising different map sizes in cluttered environments for point-mass and non-holonomic car models. Our results indicate that MPT augmented planners achieve 7-28% improvement in accuracy over recent learning- based planners, while matching the accuracy to traditional planners. MPT planners also reduce both planning time by 7-25 times and the vertices on the planning tree by 2- times compared traditional planners. We also propose a new training routine to allow for MPT to generalize to maps of different sizes while maintaining accuracy and reducing both planning time and vertices in the planning tree. We also show that MPT maintains the same qualities to real-world environments without fine-tuning or additional training. The diversity of environments represented, from block obstacles to narrow passage mazes speak to the potential general application of the MPT approach across multiple environment types and domains.
2 RELATED WORK
The most relevant work to our transformers- region proposal network for motion planning is perhaps the guided compling-based motion planning methods. They analytically or through learned heuristics determine a subset in robot space that probably contains path solution. For instance, (Queshh & Ayaz 2016 Tahir et al. 2018) employ Artificial Potential Fields (APF) within sampling- based methods such as RRT* (Karaaan& & Frazzoli (001 and Bidirectional RRT* (Qureshi & Ayaz, 2015) to guide a subset of random samples towards promising regions that possibly contain an optimal path solution. In contrast, Informed RRT* (IRRT*) (Gammell et al. 2014) depends on initial path from an RRT* algorithm to compute an ellipsoidal region probably containing an optimal path solution. However, in most plamning problems finding an initial path solution is itself challenging. In a similar vein, Batch Informed Trees (BIT*) (Gammell et al. 2015) begins from an elliptical region formed by a straight line path ignoring all obstacles and incrementally expand it until an initial path solution is found. Once an initial path is determined, it is further optimized by adapting the precomputed ellipsoid and generating new samples within that space. Despite all advancements, these methods only consider geometric planning, i.e., path planning under pollision-avoidann constraints. They are yet to be evaluated in practical problems with complex constraints such as kinodynamic or non-holonomic constraints for autonomous car navigation tasks.
Many have also used learning- based methods to reduce search spaces. Williams 1992)) used the REINFORCE algorithm to guide the underlying SMP planner on discretized workspace. others use a learned value function to guide the graph search (Choudhury et al.) 2018 Chen et al. 20200) while Kumar et al. (2019) learned generative model to sample points along bottleneck regions. Similarly, Value Iteration Networks (VIN) (Tamar et al. 2016) also discretizes the space and learns a value map to guide path planning. Universal Planning Networks (UPN) (Srinivas al., 2018) extends VIN to spaces./Chaplot
continuous control spaces. [Chpllt et al. (202I) proposed one of the few works that use transformers
to learn value function. Other works employ latent representation of state-spaces to generate plan (Banino et al.) 2018 Emmons et al. [2020) lchter & Pavone 2019). These methods are often difficult to train and interpret, and many of them are yet to be evaluated in real world navigation tasks.
Although there exist random sampling-based approaches such as RRT (Karaman & Frazzoli 2011 Arslan et al. 2017) and SST (Li et al.) 2016) that explore the robot state space and satisfy vanae constraints, they suffer from the curse of dimensionality and take a considerable computational time in cluttered spaces. Neural Motion Planning (Qureshi et al., 2020: Ichter al. 2018) has recently emerged as promising tool for solving a wide range of planning problems under various task constraints, ranging from non-holonomic (Johnson et af.) 2020 Li et al. 2021 to advanced manifold kinematic constraints (Qureshi et al.) (2020), with high computational speed. These methods learn sampling distributions from expert demonstrations and, on execution, generate samples for an under- lying planner forming subset that potentially contains path solution. However, these approaches assume a fixed size input environment map and often require redefining network architectures and retraining for different map sizes. However, recent developments in deep learning, primarily through Transformers (Dosovitskiy et al. 2021 Liu et al., (021). have provided us with ways to relax such assumptions. Our proposed approach leverages these developments and introduces a region proposal
2

---

Under review as a conference paper at ICLR 2022
Input Map (m.) & Goal Map (m),)
W:
d
H
Wi
Position Encading
H
FCN
m
d
HA
Hi. Wi
Transformer Encoding
Classifier
Hi W.
Output Map
Region Proposal
Figure 2: Overview of MPT Module. (Start from the top left and move clockwise) The input map, and the start (green) and goal (red) encoded map are concatenated together and passed as inputs the model. The Fully Convolution Network (FCN) passes sliding window of size x p over the input and encodes each patch into latent vectors of dimension d. After reshaping, fixed positional encodings are added to the latent vectors to inject spatial location. The modified latent representation is used by the transformer module to identify patches through which a path might exist. This information is encoded into latent vector of size d, which is used by classifier provide the probability that path might pass through the patch. The patches with probability greater than 0.5 are used to create the mask for the map. The light green shading highlights the flow of information for single patch from the input to the output of the model.
framework that can work with variable map sizes and enhances underlying motion planners solve complex problems in cluttered env environments.
METHOD
The set of motion planning problems that MPT aims to solve is of 2D navigation. Given start (x:)) and goal (Ir,) state, the objective is to propose a sequence of states x; E for E (0, 1.....) n) such 2n E Xgaal and the trajectories joining these states should be both kinematically feasible and collision free. Here, X' represents the robot state space and X, - {x || - zgll S e, x X for a user defined threshold (e). Since we focus on solving the motion planning problem for 2D mobile systems, X' E {R² (2))) MPT proposes promising regions in X' where the underlying planners can search for path solutions. In the following sections we describe our method in detail.
that
3.1 MOTION PLANNING TRANSFORMER (MPT)
The MPT module is a region proposal network, similar to Faster R-CNN (Ren et al. 2015). but uses transformer network identify regions of interest. An overview of the model is shown in Figure 2 The input to the model a representation of the planning scene, and an encoding of the start and goal points. The planning scene represented using an occupancy matrix, me IR HxW where an element with 1 indicates an occupied space and denotes free space. In some navigation problems, these representations are also called costmap and have additional cost terms associated safety and robot constraints. The start- goal encoding of the planning problem is formed by highlighting patches of size p X p on tensor of size H W with values -1 and for the start and goal point respectively. These two matrices are concatenated to form tensor and passed to the feature extractor.
The feature extractor Fully Convolution Network (FCN) that encodes the environment and the given planning problem into latent space. As shown in prior works (Dosovitskiy et al. 2021 Ren et al. 2015), the feature extractor reduces the dimensionality of the input space by using series of convolution, ReLU, and MaxPool layers. The FCN passes sliding window of size p x over m to generate an output of size H₁ x W; x d, where H; and Wi is determined by the size of the costmap and the FCN, and d is the latent dimension of the transformer encoder. Each patch that the sliding window moves over is parameterized by an anchor point similar to Faster R-CNN (Ren al. 2015). We choose the 2D co-ordinate corresponding the center pixel of the patch as
Feature Extractor:

---

Under review as a conference paper at ICLR 2022
the anchor point. The output of the FCN is reshaped to size (H₁ Wi) x d and fed to the position encoder. Each row vector of this matrix corresponds to an anchor point on the input map.
Position Encoding: Transformer and convolutional models agnostic to the spatial location of their inputs Dosovitskiy et al. (202T). A common solution to add learned or fixed vectors to encode the position of each imput (Gehring al. 2017). For testing our model we used the same position encoding as Vaswani et al. (2017). but for training, we use the following position encoder:
k +
k +J
PE 20) = sin
PE(J, 2i + 1) = cos
1100002//a
1000 1)/d
where & is uniformly sampled from discrete set of integer numbers 2, j is the index of the anchor point, and is the index of latent vector. This modification enables us to generalize to maps of different sizes. For maps larger than the training data, observed that the position encoder from Vaswani et al. (017)) created a bias that prevented MPT from selecting regions of the state space outside the training region. To overcome this bias, leverage the fact that proposed plan is invariant to linear translation of the state space, and train our model by randomly shifting the position encoder. This ensures that the model is not biased by the position encoder. For further details refer to Section C
in the Appendix. The modified latent vector is then passed to the transformer encoder.
The transformer module is responsible for learning the connections between the different local regions on the map for given planning problem. It infers these connections by passing the latent vectors through a series of multi-headed self-attention (MSA) and multi-layer perceptron (MLP) blocks. Between every MSA and MLP block we apply Dropout, Layer Norm and residual connections similar to Vaswani al. (207)) and Dosovitskiy et al. (202T). We also add gradient checkpoints (Chen et al. 2016) after the MSA blocks to be more memory efficient. Hence by attending all patches, the network encodes the importance of each patch the given planning problem in its output.
Transformer Encoder:
Classifier:
Using the encoded importance, the classifier predicts each of the anchor point of
interest to the current planning problem. This is efficiently implemented using 1 x convolution layer, similar to Faster R-CNN (Ren et al. 2013). A mask generated by setting p p patch, centered around selected anchor points, to matrix of size H x W.
3.2
PATH PLANNING
Any traditional or learning-based planner can be used to find the path by searching the masked region. In this work, we use variations of the Rapidly Exploring Random Trees (RRT) algorithm, that
guarantee optimality (Karaman & Frazzoli 2011 Li al. 2016 Gammell al. 2014), find the path.
Hybrid planning: In rare occasions, due to mis-classifications, MPT guided planners fail generate solution. To overcome these errors, we alternate between searching the masked (exploitation) and unmasked (exploration) regions of the map. We show that this technique is able to preserve the benefits of MPT guided planners while achieving higher efficiency in planning.
EXPERIMENTS AND RESULTS
We evaluated the planning capabilities of MPT aided SMPs and compared them with both traditional and learning-base based planners. In the following section, we will go over our environment and robot setup, model training, and results.
4.1 SETUP
Environments: To test the planning capabilities of our method, we evaluated the model on randomly generated maps from two different classes of environments. The first environment is called the Random Forest, where circular and square objects are randomly placed on the map. It simulates real world scenes with narrow passages and crowded spaces. The second environment is called the Maze environment. Each map is a perfect maze, generated using randomized depth- depth-first first search. characteristic of perfect maze is that any start and goal pairs on this map reachable by
4

---

Under review as a conference paper at ICLR 2022
Ground Truth Path
Predictions Probability
MPT-RRT- Path
14
-22
Ground Truth Path
Predictions Probability
MPT-RRT Path
-66
CH
CA
Figure 3: Planned paths for two different planning problems. Top Row: Random Forest environment. Bottom Row: Maze environment. Left Column: The ground truth path for given start (green) and goal (red) point from the validation data. Center Column: The prediction probability from the MPT. Right Column: The masked map and the planned trajectory for the given start (green) and goal (red) point using RRT*.
collision-free path. These maps mimic long-horizen horizhoizzon planning problems because even if the start and goal are geometrically close, the planner would have take circuitous path to reach the goal. We also tested our method on the map of building 079 University of Freiburg constructed from publicly available 2D lidar scan data.
An integral component of any motion planner is the ability to check if the robot is in collision with any obstacles. This can be accomplished using geometric methods such as the Gilbert-oohnon- (GJK) algorithm other learning based approaches (Chase Kew et al. 2021). We use the occupancy map to check if the robot is in collision with the obstacle; hence we use a high resolution of 5cm per pixel for our maps.
Robot Models We test our algorithm on two kinds robotic systems that encapsulate a large set of mobile systems. The first is simple Point Robot Model that can move in any direction in its state-space X' = TR.2. Solutions for this model can easily extended and outdoor robots. A simple example is robots with circular footprints. For such robots, inflating the obstacles by the robot's 's radius reduces its footprint to a point (Choset et al., 2005). It is also common in 2D navigation to bound the non-circular footprints using circle for path planning (van den Berg et al. 2011 Marder- Marder-Eppstein et al.) (2100). The other robot we tested a Dubins Car Model with state-space X (2),), controlled using wheel velocity and steering angle. This robot model represents class of mobiles systems such as cars, bikes and even needle-steering in surgeries (Alterovitz al. 2008).
large number of indoor
4.2 TRAINING
The MPT model is trained an end-to-end fashion under supervision similar to Girshick (0015). Each mini-batch is formed from single planning problem containing positive and negative anchor points. We define positive anchor points as those within 0.7m distance to the trajectory, while all the others considered negative samples. For training, negative anchor points are randomly chosen such that we at least have ratio of 1:1 of positive and negative samples. For the Dubins Car Model, considered only the robot's 2D coordinates identify the positive and negative anchor points.
5

---

Under review as a conference paper at ICLR 2022
Figure 4: (From left) Path planned by RRT*, IRRT*, MPT-RRT*, and MPT-IRRT* for the same start (green) and goal (red) positions. MPT aided planners are able to reduce significantly the number of vertices (orange) required to search for a path.
Honee
0.0
38
102 MPM
NETORT
SIT-RR APT-ART-EE EZ
327
HFTORY
NFT-RR VETARE-EE
Figure 5: Planning statistics for the Point Robot Model. Left: The planning time for traditional and learning-bas -baen planners. Right: Number of vertices in the planning tree for traditional and learning-based planners. MPT aided planners consistently reduce the planning time and the vertices in the planning tree, resulting in a lower variance of these statistics for these planners.
We trained the network by minimizing the cross-entropy loss using the Adam optimizer (Kingma & Ba 2015) with B1 = 0.9, B2 = 0.98, and = 1e 1e-9. We varied the learning rate as proposed in Vaswani et al. (017) with warm-up steps of 3200. Each model was trained for 1000k epochs with batch size of 128. The models were trained on one machine with 4 NVIDIA 2080GTX graphics card.
The MPT model for the Point Robot took 2hhrs and for the Dubins Car took 12hrs train.
We trained an MPT model for the Point Robot on 1750 randomly generated maps from each environment mentioned above. For each map, 25 paths were generated using the RRT* planner. Similarly we trained an MPT model for the Dubins Car on 1000 randomly generated maps from the Random Forest environment. We collected 50 paths from each map using the SST planner 2016). All the maps used were of size 480 x 480.
Datasets:
(Li et
4.3 POINT ROBOT MODEL
For the Point Robot Model, we compared MPT-aided planners with traditional and learning-bai based planners. We also looked at the capabilities of other image segmentation approaches such as UNet (Ronneberger et al. (015) to highlight the area where a potential path might exist. We choose UNet because, like MPT, it can generalize to maps of different sizes. We call the aided planners Y-X, where Y is the underlying method used to generate the mask and X is the SMP planner. MPT-RRT*-ED represents the MPT aided RRT* planner with the exploration and exploitation strategy (hybrid planning).
The first set of experiments examined the network's ability to generalize unseen maps of the same dimension as the training data. We compared the planners on 2500 random start and goal pairs for maps from the Maze and Random Forest environment. For each planner, we report the 1. Accuracy the percentage of planning problems the planner solves, 2. Time (sec)- the amount of time it takes to generate the mask (if applicable) and plan a path shorter than a path from the RRT planner searching for a fixed time, and 3. Vertices the number of collision-free states sampled by the planner to construct the planning tree. The summary statistics of the experiment are reported in Table I We see that MPT aided planners reduce the planning time and vertex count of the planning tree substantially. In Fig. 3 we show two examples of a planned path from this experiment. In Fig. [ we show the vertices used by the planning tree for various planners for a single planning problem.

---

Under review as a conference paper at ICLR 2022
Table Comparing planning accuracy, and median time and vertices for the Point Robot Model on unseen environments of the same size as the training data.
Random Forest
Maze
Algorithm
Accuracy
Time (sec)
Vertices
Accuracy
Time (sec)
Vertices
RRT
100%
5.448
3228
100%
5.364
2042
IRRT
100%
0.425
267
100%
3.139
1394
UNet-RRT
30.27%
0.167
168
21.4%
0.346
277
UNet-RRTT-EE
100%
2.58
1913
100%
4.133
2139
MPNet
92.35%
0.296
63
71.76%
1.727
1409
MPT-RRT* (ours)
99.40%
0.194
233
99.16%
0.870
626
MPT-IRRT* (ours)
99.40%
0.087
136
99.16%
0.784
566
MPT-RRT*-EE (ours) 100%
0.211
247
100%
0.869
585
To better understand the advantages of MPT, we visualize the distribution of the planning time and vertices in Fig. for the Random Forest and Maze environment using Letter-value plots (Hofmann et al. 2011). These plots help to observe the tail of the distribution of the metrics. Naive RRT has heavier tail distribution than MPT-RRT* because for start and goal pairs further away from each other, the planner needs to generate denser graph to search larger space, requiring more time and vertices. On other hand, MPT-aided planners focus their search near regions highlighted by the model, and result, they plan faster with fewer vertices. We see thin tail distribution for MPT-RRT* and MPT-IRRT* planners for the random forest environment. This is because the planner only terminates when the cost of the path is below certain threshold. Even if solution is found, MPT planners continue to search to reduce the path length, resulting in longer planning times and vertex count for few trajectories. The number of such problems accounts for less than 0.75% of the planning problems.
We also observe that IRRT performs consid- erably better than R in the Random Forest environment and achieves similar planning time and planming tree vertices compared to the aided planners. This is because IRRT*, like MPT's, reduces the planning search space once an initial solution is found by bounding the initial path with an Ellipse. Such heuristics do not work for long-horizon problems like the Maze envi- ronment, and MPT aided planners outperform traditional methods.
360x240
780x780
480x240
The MPT model also outperforms other learning- based approaches. Planners that used UNet to propose patches performed poorly. We believe this is because the convolution layers can only learn the connections between local patches, and deeper networks would be required to learn global connections. As a result, fails to high- light the area of interest for the given planning problem. MPNet, on the other hand, performs considerably better than UNet-RRT* for both environments, but not well MPT planners. We attribute the weak generalization the lack training data. Qureshi et al. (2019), the authors used nearly 400k trajectories train their model, whereas only provided around 88k trajectories for our models.
Figure 6: Plot of paths for Random Forest envi- ronments of different size. The architecture of the MPT Model allows flexibility in planning for environments of different sizes.
Due to classification errors, MPT fails around 1% of maps (Some of these paths are plotted in the Appendix). Nevertheless, by randomly exploring the map for few samples outside the segmented region, MPT-RRT* + can solve these problems while UÑet-RRT*.ED has similar statistic RRT* The distribution of planning time and vertices for MPT-RRT*-EE are much tighter compared to traditional planners and MPT planners without exploration.
7

---

Under review as a conference paper at ICLR 2022
Figure 7: Path generated by MPT-RRT*
Figure 8: MPT can also be trained to aid SMP planners for non-holonomic robots. Left and Right: Planned paths Freiburg using model trained only on on Random Forest environment using MPT-SST. MPT simulated environments.
on random start and goal pair on the map of building 079 at University of
identifies regions through which a non-holonomic path exists.
The following experiment we conducted evaluated MPT's ability to generalize to map sizes that were not part of the training data. We tested the model four different map sizes, 360 480x 240, 560x560, and 780x780 of the Random Forest environment on 1000 randomly generated maps while maintaining the density of obstacles. We used the same MPT model without any re-training or fine-tuming and compared the same metrics with traditional planning techniques. We did not compare against learning- beaneing-based planners because these planners either performed poorly in our previous experiment or were not generalizable to maps of different sizes without modifications. The planning statistics are summarized in Table and three successfully planned paths using MPT are shown in Fig. [6] Training the model by randomly shifting position encoding was instrumental in improving the accuracy of the planner for maps of larger sizes. Without it, the planner was able to achieve only 75.6% accuracy maps of size 560 x 560. It also improved overall accuracy by 1-4% on other maps as well. The complete statistics are reported in the Appendix
We notice that the MPT aided planners, similar to our previous experiments, achieve lower planning time and vertices count than traditional planners without additional training or fine-tuning. IRRT* achieves similar performance to MPT-aided planners for smaller-sized maps. As the map sizes grow, the time taken by IRRT* grows because of the more prominent search space. While for larger maps, MPT aided planners can find a solution faster and outperform IRRT*
The final experiment we performed was to test the MPT model on a real-world map. We obtained a map of building 079 University of Freiburg from publicly available 2D lidar scan data. We again used the MPT model from our previous experiments without any additional training or fine-tuning. The results are summarized in T We plot one of these trajectories Fig. The ability of MPT to generalize to real world maps without any additional training or fine tuning is exciting because it can be trained on simulated environments and transferred to real world applications with minimal effort.
4.4 DUBINS CAR MODEL
To examine if the MPT can aid in the planning of non-holonomic systems, we trained new MPT model to plan for Dubins Car robot. We tested the trained model on 1000 Random Forest environments and compared the metrics with those from the naive SST planner. The metrics report is similar to the point robot, but the time we report is the interval that the planner takes to find valid path. SST aided by MPT is called MPT-SST and the hybrid planner is called MPT-SST-EE. Two trajectories from this experiment is plotted in Fig. g We can observe that the MPT highlights regions so that SST can generate a kinematically feasible path. Planners such SST. which sample in the control space, do not scale well to larger planning spaces, and MPT can help with reducing the search space. The timing results reported in Table 4 support this claim. MPT helps in reducing the planning time and vertices for the underlying SST planner.
5 DISCUSSION
Graph-bace based search methods such as * can also be used to solve the given planning problem using the costmap, but in order to do real time planning, these methods often require sub-sampling of the
8

---

Under review as a conference paper at ICLR 2022
Table 2: Comparing planning accuracy, and median time and vertices for Point Robot on maps the different sizes of the Random Forest environment.
Map Size Obstacles)
RRT
IRRT
MPT-RRT*
MPT-IRRT*
MPT-RRT *-E
Accuracy
100%
100%
99.20%
99.20%
100%
360x240
Time (sec)
5.926
0.286
0.248
0.054
0.297
(35)
Vertices
3660
257
354
106
382
Accuracy
100%
100%
98.5%
98.5%
100%
x80x240
Time (sec)
6.308
0.394
0.265
0.073
0.302
(50)
Vertices
3480
291
319
131
362
Accuracy
100%
100%
99.7%
99.7%
100%
x60
Time (sec)
6.725
0.283
0.181
0.083
0.217
(100)
Vertices
3854
203
218
112
237
Accuracy
100%
100%
99.5%
99.5%
100%
780
Time (sec)
8.095
0.476
0.297
0.152
0.285
(200)
Vertices
4292
255
241
161
238
Table 3: Comparing planning accuracy, and me-
Table 4: Comparing planning accuracy, and me-
dian time and vertices for the Point Robot Model dian time and vertices for Dubins Car Model for on real world map.
the Random Forest Environment.
Planner RRT
Accuracy
Time (sec)
Vertices
Planner
Accuracy
Time (sec)
Vertices
20/20
2.507
1630
SST
100%
3.313
1200
MPT-RRT*
17/20
0.538
455
MPT-SST
87.6%
2.617
932
MPT-RRT
20/20
0.946
804
MPT-SST-EE
100%
2.712
1150
costmap provide solutions in real time. Further hand-tuned heuristics required restrict the planning space for kinematically constrained systems (Dolgov et al.) 2010) otherwise they get stuck in local minima VLaValle & James J. Kuffner (200T). We have shown through our experiments that the MPT aided planners require no such sub-sampling, and can learn to restrict search spaces by leveraging data. Since MPT is agnostic to the underlying planner, graph-based searches also be used to search the highlighted space.
Prior learning based methods that predicts value such VIN Taamar al. 2016), shown be difficult to train for larger maps (Nardelli et al. (018)) because of the depth of layers that is required to propagate the reward. Unlike the other transformer based planner (Chaplot al.) 2021). as have shown randomizing the positional encoding is critical to be able to generalize the planner to maps different sizes. The map sizes that are used in our method nearly 10 times larger than the ones shown use in Chaplot et al. (2021). Moreover, MPT combines best of both worlds by learning from data the space where a plan exists and using an optimal planner get the exact path.
CONCLUSION
In the future, extending MPT to higher dimensional robots such as robotic arms or drones is an interesting problem with many real-world applications. For mobile robots in 3D space, the use of sparse Transformer models(Roy et al., 202T Beltagy al., 2020) would be better suited because of the dimensionality of the space. While for manipulation systems in 3D since the task and joint space do not overlap. the extension of method is more challenging.
In this work, we have shown application of the transformer model for 2D navigation tasks. Unlike prior methods that need to retrain models for maps of different sizes, we leverage the ability of transformers handle sequences of different lengths and parallelize long-term dependencies without recursions for planning problems with different map sizes. By combing MPT with SMP, we could generate paths faster, with fewer tree nodes for different environments and robot models.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Ron Alterovitz, Michael Branicky, and Ken Goldberg. Constant-Curvature Motion Planning Under Uncertainty with Applications in Image-Guided Medical Needle Steering, pp. 319- 334. Springer Berlin Heidelberg, Berlin, Heidelberg, 2008. ISBN 978-3-540-6840522 doi:
Oktay Arslan, Karl Berntorp. and Panagiotis Tsiotras. Sampling- based algorithms for optimal motion planning using closed-loop prediction. In 2017 IEEE International Conference on Robotics and Automation (ICRA), pp. 4991-4996, 2017. doi: A.1109/CCAA.211..7999999
Andrea Banino, Caswell Barry, Benigno Uria, Charles Blundell, Timothy Lillierap, Piotr Mirowski, Alexander Pritzel, Martin Chadwick, Thomas Degris, Joseph Modayil, Greg Wayne, Hubert Soyer, Fabio Viola, Brian Zhang, Ross Goroshin, Neil Rabinowitz, Razvan Pascanu, Charlie Beattie, Stig Petersen, and Dharshan Kumaran. Vector-based navigation using grid-like representations in artificial agents. Nature, 557, 05 2018. doi: 10.1038/41186-018-001100
Iz Beltagy, Matthew E. Peters, and Arman Cohan. Longformer: The long-document transformer, 2020.
Devendra Singh Chaplot, Deepak Pathak, and Jitendra Malik. Differentiable spatial planning using transformers. Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference Machine Learning. volume 139 of Proceedings of Machine Learning Research, pp. 1485-1495. PMLR, 18-24 Jul 2021.
J. Chase Kew, Brian Ichter, Maryam Bandari, Tsang- Wei Edward Lee, and Aleksandra Faust. Neural collision clearance estimator for batched motion planning. In Algorithmic Found. of Robot. XIV, pp. 73-89, 2021.
Binghong Chen, Bo Dai, Qinjie Lin, Guo Ye, Han Liu, and Song. Learning to plan in high dimensions via neural exploration-cxploitatonn trees. In 8th International Conference Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020.
Tianqi Chen, Bing Xu, Chiyuan Zhang, and Carlos Guestrin. Training deep nets with sublinear memory cost, 2016.
Howie Choset, Kevin M. Lynch, Seth Hutchinson, George Kantor, Wolfram Burgard, Lydia Kavraki, and Sebastian Thrun. Principles of Robot Motion: Theory, Algorithms, and Implementations. MIT Press, May 2005, ISBN 0262033275.
Sanjiban Choudhury, Mohak Bhardwaj. Sankalp Arora, Ashish Kapoor, Gireeja Ranade, Sebastian Scherer, and Debadeepta Dey. Data-driven planning via imitation learning. The International Journal of Robotics Research, 37(13-14):1332-162) 2018. doi: 10.1177/028836491157 1001.
Dmitri Dolgov, Sehastian Thrun, Michael Montemerlo, and James Diebel. Path planning for au- tonomous vehicles in unknown semi-structured environments. The International Journal of Robotics Research, 29(5):48--501, 2010. doi: 10.1177/0778344999999200
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby. An image is worth 16x16 words: Transformers for image recognition at scale. In International Conference on Learning Representations, 2021.
Scott Emmons, Ajay Jain, Misha Laskin, Thanard Kurutach, Pieter Abbeel, and Deepak Pathak. Sparse graphical memory for robust planning. In H. Larochelle, M. Ranzato. R. Hadsell, M. F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 5262. Curran Associates, Inc., 2020.
Jonathan D. Gammell, Siddhartha S. Srinivasa, and Timothy D. Barfoot. Informed r:::: Optimal sampling baaeel path planning focused via direct sampling of admissible ellipsoidal heuristic. In 2014 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 2997-3004,
2014. doi: 10.1 109//RRSS.2014..99222
10

---

Under review as a conference paper at ICLR 2022
Jonathan D Gammell, Siddhartha S Srinivasa, and Timothy D Barfoot. Batch informed trees (bit*): Sampling-basee optimal planning via the heuristically guided search of implicit random geometric graphs. In 2015 IEEE international conference on robotics and automation (ICRA), pp. 3067-3074.
IEEE, 2015.
Jonas Gehring, Michael Auli, David Grangier, Denis Yarats, and Yann N. Dauphin. Convolutional sequence to sequence learning. In Proceedings of the 34th International Conference on Machine Learning Volume 70, (CML'177, pp.
Jor.Rorg. 2017.
Ross Girshick, Fast r-cnn. In Proceedings of the IEEE international conference on computer vision, pp. 1440-1448, 2015.
Peter F. Hart, Nils J. Nilsson, and Bertram Raphael. formal basis for the heuristic determination of minimum cost paths. IEEE Transactions Systems Science and Cybernetics, 4(2):100-107, 1968. doi: 10.1109/SSC.1198..000
Heike Hofmann, Karen Kafadar, and Hadley Wickham. Letter-value plots: Boxplots for large data. Technical report, had.co.nz, 2011.
Brian Ichter and Marco Pavone. Robot motion planning learned latent spaces. IEEE Robotics and Automation Letters, 4(3):2407-2414, 2019. doi:
Brian Ichter, James Harrison, and Marco Pavone. Learning sampling distributions for robot motion planning. In 2018 IEEE International Conference on Robotics and Automation (ICRA), pp. 7087-7094. IEEE, 2018.
Jacob J. Johnson, Linjun Li, Fei Liu, Ahmed H. Qureshi, and Michael C. Yip. Dynamically constrained motion planning networks for non-holonomic robots. In 2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 0943,,943, 2020. doi: 10.1109) 000545743.202..94111
Sertac Karaman and Emilio Frazzoli. Sampling- algorithms for optimal motion planning. The international journal of robotics research, 30(7):846 894, 2011.
L.E. Kavraki, P. Svestka, J.-C. Latombe, and M.H. Overmars. Probabilistic roadmaps for path planning digh-diimesiooal configuration spaces, IEEE Transactions on Robotics and Automation, 12(4):566-580 1996.
Diederik Kingma and Jimmy Ba. Adam: method for stochastic optimization. In Yoshua Bengio and Yann LeCun (eds.), 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Truck Proceedings, 2015.
Rahul Kumar, Aditya Mandalika, Sanjiban Choudhury, and Siddhartha S. Srinivasa. Lego: Leveraging experience roadmap generation for sampling-based planning, 2019.
Steven M. Valle and Jr. James J. Kuffner. Randomized kinodynamic planning. The International
Journal of Robotics Research, 20(5):378-400 2001. doi: 10. 10.1177027833401206645..
Linjun Li, Yinglong Miao, Ahmed H Qureshi, and Michael C Yip. Mpc-mpnet: Model-predictive motion planning networks for fast, near-optimal planning under kinodynamic constraints. IEEE Robotics and Automation Letters, 6(3):4496 4503, 2021.
Yanbo Li, Zakary Littlefield, and Kostas E. Bekris. Asymptotically optimal sampling-basee kino- dynamic planning. The International Journal of Robotics Research, 25(5):528-566) 2016. doi: 10.117700278364115614333
Ze Liu, Yutong Lin, Yue Cao. Han Hu, Yixuan Wei, Zheng Zhang, Stephen Lin, and Baining Guo. Swin transformer: Hierarchical vision transformer using shifted windows, 2021.
Eitan Marder-Eppsteer Eric Berger, Tully Foote, Brian Gerkey, and Kurt Konolige. The office marathon: Robust navigation in an indoor office environment. In 2010 IEEÉ International Conference Robotics and Automation, pp. 300-307, 2010. doi: 10. 00.100000080022205509955..
11

---

Under review as a conference paper at ICLR 2022
Nantas Nardelli, Gabriel Synnaeve. Zeming Lin, Pushmeet Kohli, Philip HS Torr, and Nicolas Usunier. Value propagation networks. arXiv preprint arXiv: 2018.
A. H. Qureshi, J. Dong, A. Choe, and M. C. Yip. Neural manipulation planning on constraint manifolds. IEEE Robotics and Automation Letters, 5(4):6089-6066 2020.
Ahmed H. Qureshi, Anthony Simeonov, Mayur Bency, and Michael Yip. Motion planning networks. In 2019 International Conference on Robotics and Automation (ICRA), pp. 2118-22111 2124, 2019. doi: 10.1 10..1./...222 87938899
Ahmed Hussain Qureshi and Yasar Ayaz. Intelligent bidirectional rapidly-- random trees for optimal motion planning in complex cluttered environments. Roboties and Autonomous Systems, 68:1-11, 2015.
Ahmed Hussain Qureshi and Yasar Ayaz. Potential functions based sampling heuristic for optimal path planning. Autonomous Robots, 4066):1079-1093, 2016.
Ahmed Hussain Qureshi, Yinglong Miao, Anthony Simeonov, and Michael Yip. Motion plan- ning networks: Bridging the gap between learning-based and classical motion planners. IEEE Transactions on Robotics, 2020.
Shaoqing Ren, Kaiming He, Ross Girshick, and Jian Sun. Faster r-cnn: Towards real-time object detection with region proposal networks. In C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 28. Curran Associates, Inc., 2015.
Olaf Ronneberger, Philipp Fischer, and Thomas Brox. U-net: Convolutional networks for biomedical image segmentation, 2015.
Aurko Roy, Mohammad Saffar, Ashish Vaswani, and David Grangier. Efficient content-based sparse attention with routing transformers. Transactions of the Association for Computational Linguistics, 9:53-68, 02 2021. doi: 10.1 (0.1162/tel...00353.
Aravind Srinivas, Allan Jabri, Pieter Abbeel, Sergey Levine, and Chelsea Finn. Universal plan- ning networks: Learning generalizable representations for visuomotor control. In International Conference on Machine Learning, pp. 4732-4741. PMLR, 2018.
Zaid Tahir, Ahmed H Qureshi, Yasar Ayaz, and Raheel Nawaz. Potentially guided bidirectionalized rrt for fast optimal path planning in cluttered environments. Robotics and Autonomous Systems, 108:13-27, 2018
Aviv Tamar, Yi Wu, Garrett Thomas, Sergey Levine, and Pieter Abbeel. Value iteration networks. In Advances in Neural Information Processing Systems, pp. 2164-2162, 2016.
Jur den Berg, Pieter Abbeel, and Ken Goldberg. Lęg-mp: Optimized path planning for robots with motion uncertainty and imperfect state information. The International Journal of Robotics Research, 30(7):895-913, 2011, doi: 10.1117/02773669914466 14065666.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus. S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
Ronald J Williams. Simple statistical gradient algorithms for connectionist reinforcement learning. Machine learning, 8(3-4):229-22) 1992.
12

---

Under review as a conference paper at ICLR 2022
A APPENDIX
B NETWORK ARCHITECTURE
B.I MPT
Table 5: Network architecture of the Fea- ture Extractor
In this section, we detail the network architecture used in for MPT in our experiments. The Transformer architecture is similar to the ones proposed in Vaswani et al. (2017). We used 6 layers of encoder block, each consisting of heads. The dimension of the keys and queries was set at 512, and the dimension the value was set at 256. The architecture of our feature extractor is given in Table 5 For the convolution layer, the dimensions in the brackets represent [Input Channel Size, Output Channel Size, Ker- nel Size, Stride], and for the Maxpool layer, it represents the Kernel Size
Layer
Dimension
2D Convolution
[2, 6, 5, 0]
2D Maxpool
[2]
ReLU
2D Convolution
[6. 16, 0] [2]
2D Maxpool
ReLU
Convolution
[16, 512, 5,
B.2 UNET
The UNet architecture use is similar to the one used by Ronneberger et al. (2015). The network consists of 4 blocks of down convolution, and 4 blocks of up convolution. Each down convolution block consists of 3 3 convolution, followed by batch norm, ReLU and 2 of max pool layer. The up convolution block consists of bilinear up sampling block, followed by 3 x 3 convolutions, and ReLU. The final layer is
followed by batch details for the exact channel size used for each convolution please refer to our code.
to classify each latent vector. For more
X
X
X
X
To encode the (x) y) position of each pixel in the world co-ordinate add fixed position vectors. Left: Region proposed by an MPT model trained with position encoding proposed in Dosovitskiy et (202T) for a map larger than the training dataset. The blue box marks the size of the training dataset and the red box marks the size of test dataset. The model fails to predict regions near the boundary the training map. Right: A training map, randomly shifted world coordinates. Randomly adding offsets to position encoding has the same effect as translating the map in world co-ordinates.
Figure 9:
13

---

Under review as a conference paper at ICLR 2022
Table 7: Comparing planning accuracy, planning time, and number of vertices in the tree for the Point Robot on down sampled Maze Environment
Algorithm
NEXT-KS
Accuracy
28.28% %
Figure 10: Plots of two paths for the modified maze envi- romment using the NEXT-KS planner. The yellow circles indicate the sampled points by the planner. The planner able to solve for simple problems (Left) while for long horizon problems it gets stuck in local minimums.(Right
Time (sec) 3.021
Vertices
387
C POSITION ENCODING
We observed that the MPT model trained on the position encoding proposed by Vaswani et al. (2017) showed signs of overfitting. The model fails to highlight the region near the boundary of the training map size (See Fig (Left)). One way to resolve this overfitting is to train maps of various sizes ensure that the network observes different position encoding. How- ever, this procedure is often compu- tationally expensive, especially for larger maps. We propose to ran- domly translate the planning space by randomly offsetting the position encoding values. The MPT model trained with the randomized posi- tion encoding overcomes the overfit- ting. Results for the model trained without randomized position encod- ing are given in Table 2 We ob- serve that the MPT model trained with randomized position encoding perform better overall, but for larger maps achieve nearly 24% more accuracy.
Table 6: Comparing planning accuracy, planning time, and number of vertices in the tree for Point Robot on maps of the different sizes of the Random Forest environment for model trained without random shifting of positional encoding.
Map Size (# Obstacles)
MPT-RRT*
MPT-IRRT*
Accuracy
97.4%
97.4%
360x240
Time (sec)
0.265
0.062
(35)
Vertices
377
118
Accuracy
96.3%
96.3%
480x
Time (sec)
0.268
0.072
(50)
Vertices
348
129.5
Accuracy
98.96%
98.96%
480x480
Time (sec)
0.235
0.092
(100)
Vertices
251
133
Accuracy
75.6%
75.6%
560x560
Time (sec)
0.253
0.082
(100)
Vertices
262
101
D COMPARISON WITH NEXT PLANNER
To provide context for aalue-based planners in solving long horizon problems we compared against the recently proposed Neural Exploration-Exploitaiie Exploitation Tree with kernel smoothing (NEXT- KS) (Chen et al. 2020) on a simplified Maze environment. The same validation set from Table was used, but the map size was reduced from 480 pixels to 16x 16 pixels. The results for this experiment are summarized in Table 7 The drop performance can be attributed to the value function proposing samples that are locally optimum. See Fig 10 (Right) for example of failed plan. In addition, because the recursive nature of the planner, the timing for planning is similar to that of * We do not compare the planners performance the forest environment because reducing the map size reduces the distance resolution from 0.05meter/pixel to 0.75meter/pixel, which if applied to the Forest environment would oversimplify collision free regions.
14

---

Under review as a conference paper at ICLR 2022
E SUCCESSFUL TRAJECTORIES
In this section we plot few more successful trajectories of fixed map sizes for the Random Forest and Maze environments Fig. 12 and [4 respectively. In Fig. and 13 we plot the vertices sampled by the different planners to construct their planning trees.
Figure 11: (From left) Path planned by RRT*, IRRT*, MPT-RRT* and MPT-IRRT for the same start (green) and goal (red) positions for the Random Forest environment. MPT aided planners are able reduce significantly the number of vertices (orange) required to search for path.
Uround trait nah
Prsiitions hudussliy
YPTLAN! Put
Grouss Trth hath
Preditioon hobbeiiity
VOT Pats
12
34
Douud Tuth hut
Preditions hubeelitty
VET-ATT" Pat:
11
-11
Figure 12: Three different trajectories planned successfully using MPT on the Random Forest environment. Left Column: The ground truth path the validation dataset. Middle Columm: The probability estimate made by the MPT. Right Column: The planned path using RRT* on the region proposed by the MPT.
15

---

Under review as a conference paper at ICLR 2022
Figure 13: (From left) Path planned by RRT* IRRT* MPT-RRT*, and MPT-IRRT for the same
start (green) and goal (red) positions for the Maze environment. MPT aided planners are able to reduce significantly the number of vertices (orange) required to search for path. The IRRT* planner has to search the entire space for these kinds of maps.
DoutdTrsth Path
Predctions Tetbaciity
VET-ORT- PNT
STE
Groued Fratt Auth
Weditions Fubbaility
MIPLANI PATT
34
Ground Rat
Pedittion Fubbeility
KPT.SRTH Patt
33
Figure 14: Three different trajectories planned successfully using MPT the Maze environment.
Left Column: The ground truth path the validation dataset. Middle Column: The probability estimate made by the MPT. Right Column: The planned path using RRT* the region proposed by the MPT.
16

---

Under review as a conference paper at ICLR 2022
F
DISTRIBUTION OF METRICS FOR MAPS OF DIFFERENT SIZES
The distribution of metrics reported in Table 2 is given Fig. 15
360X240
480x240
40
560x560
780x780
30
Time (sec)
20
10
RRT
IRRT*
MPT-RRT*
MPT-IRRT*
MPT-RRT-EE
Planner
360x240
35
480x240
560x560
30
780x780
Vertices (x1000)
25
20
15
10
5
0
RRT
IRRT*
MPT-RRT* Planner
MPT-IRRT*
MPT-RRT
Figure 15: The distribution of metrics for maps of different sizes. Top: The distribution of planning time for different algorithms for maps of different sizes. Bottom: The distribution of the number of vertices in the planning tree for different algorithms for maps of different sizes. MPT aided planners can achieve faster planning times and lower variance in the metrics across maps of different sizes, which were not part of the training data.
17

---

Under review as a conference paper at ICLR 2022
G FAILED TRAJECTORIES
In Fig. 16 and 17 we visualize some of the trajectories that MPT could not solve for the Random Forest and Maze environment, respectively. These failures were mainly caused by a single patch that was not classified as part of the path, resulting in map with no valid paths.
Ground Truth Poth
Prodictions Probabiity
HPTARTT Path
008
-14
-03
Ground Truth Futh
Fred ctians Probability
NPS Nath
-08
08
04
-02
Ground
Prod Prodictions Probabilty
-6
Figure 16: Three different trajectories planned unsuccessfully using MPT on the Random Forest environment. Left Column: The ground truth path the validation dataset. Middle Column: The probability estimate made by the MPT. Right Column: The planned path using RRT* on the region proposed by the MPT. We observe that in all three cases the failure to predict a few patches resulted in scenario with valid paths.
18

---

Under review as a conference paper at ICLR 2022
Ground
Prodictions Probabiity
STU
T4
G
NCA
-02
ZH
STU
GS
WCA
Figure 17: Three different trajectories planned unsuccessfully using MPT on the Maze environment. Left Column: The ground truth path in the validation dataset. Middle Column: The probability estimate made by the MPT. Right Column: The planned path using RRT* on the region proposed by the MPT. We observe that in all three cases the failure to predict a few patches resulted in a scenario with valid paths.
19


Reviews:
[{"review_id": "qwrobVHTVZ", "reviewer": "Reviewer_JNUy", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "Strengths:\n+ Reduced planning time over traditional approaches (there are some issues here that I talk about in the weaknesses).\n+ Improved performance over learning based approaches.\n+ Method does not need fixed input size as other learning based approaches.\n+ Well written paper.\n\nWeaknesses / Comments / Questions:\n\n- Time to pass through MPT:\nThe key weakness in this work is not counting the time it takes to MPT as the total processing time. The authors argue that this can be seen as a preprocessing step, however, I think this may not be a valid argument. The entire method should be timed in order to compare to the other baselines to have a fair comparison. I would like to see these times to conclude whether this method in fact pushes the envelope against traditional methods. If the baselines have pre-processing steps, these times should be included as well for fairness.\n\n- Using the hybrid approach with learning based baselines:\nThis author proposes the use of a hybrid approach to addressed any trajectories that miss reaching the goal. The authors use this with their proposed method, however, it is not used with the other learning based approaches. I think this experiment is necessary for completeness to see whether the MPT is a key component in the performance and it could not just be replaced, say, with the MPnet or UNet baselines.\n\n\n- Sampling k during training:\nI don't quite get the reasoning behind sampling k for the positional encodings other than to make the training noisy, and thus, difficult for the model to memorize the positions in the grid. If this is the case, I would encourage the authors to investigate this further and maybe find a more mathematical explanation for this type of regularizer which obviously seems to work.\n\n\n- Method marginally outperforms baselines in the \"Dubins car model\" experiments (Table 4).\nThis goes back to measuring the time it takes to run MPT. What happens if this time is included? Is the baseline faster than the proposed method?", "summary_of_the_paper": "This paper proposes a transformer based trajectory estimator for 2D navigation. The proposed method is shown to not be limited by input size as other learning based approaches. In the experimental section, the authors show that their estimated trajectories result in speed up and performance boost for planning in comparison to traditional and other learning approaches.", "summary_of_the_review": "I personally like this approach, but I feel that there are key missing questions that the paper does not answer in order to determine whether the claims are successfully substantiate or not. I am willing to increase my score depending on whether the author's response address my questions.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "mhxH4LBRGwL", "reviewer": "Reviewer_WoFc", "summary": "", "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": "There are two important aspects of this method. First is to get a region so that a sampling based method can derive the path within that region to save time in the path planning. Second due to the transformer this method can scale to different resolution of map. \nThe neural guided RRT is not new.  Like \"Neural RRT*: Learning-Based Optimal Path Planning\" also aim to get a guidance. Similarly \"Path Planning using Neural A* Search\" which uses different planner but similar philosophy. It would be better to position the advantage of the current method for a fix resolution against these similar existing method which share same philosophy. \nThe resolution invariant property is nice. It will be good to see the generalisation of this method as it uses a classifier to train. In the paper it is mentioned that the training used both maze and random forest and test on both. To understand what the network learns can we see the result trained on maze and test on random forest or train on both and test on different map with different densities? If the maze has higher density  (means very narrow path/free space) does the method without further training work? Any classification inaccuracy may lead to a completely different and longer path which the author also shows in appendix. So a study on the generalisation ability out of distribution would be good given the IRRT* performance.\nIn the Table 1, the time exclude the MPT planner which I think is not correct because MPT planner is the key to reduce the RRT* time. The time should be the total time of MPT based mask generation + RRT* planning. Also the path length should also be compared across method. A comparison of time and path length with \"Learning to Plan in High Dimensions via Neural Exploration-Exploitation Trees\" will be better in a single resolution.\nThe authors mention about a few choices of the position encoding of the transformer. This is an important choice to take care and a detail ablation of this with the resulted path can be useful to the reader to understand what is happening there.", "summary_of_the_paper": "This paper proposes a transformer based method for 2D motion planning. The aim of the method is to work in any resolutions of the 2D map and the attention of the transformer enable to get the best possible regions through which the desired path should exist. A  traditional planners is then used given the extracted region to generate the final collision-free path. The results shows the efficacy of the transformer guided path planning using RRT* in different resolution of maps.", "summary_of_the_review": "The method is good as a pipeline but it needs few careful experiments to position the claims with respect to state-of-the-arts. While part of the method's philosophy is already existed like neural guided path planner, the other part where the resolution invariant is being claimed is good. Some of the comparisons are important to position the entire pipeline against SoA  and few metrics needs to be shown (like the time) to understand the computational complexity.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "bpyG-ZTTIEg", "reviewer": "Reviewer_jDfv", "summary": "", "questions": "", "limitations": "", "rating": 3, "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 tackles an important problem of learning to plan which is of interest to the machine learning community and has important applications in robotics. The writing quality is good and the paper is easy to follow.\n\nThe authors conduct experiments with large map sizes and show effectiveness of the proposed approach. The performance of the method drops significantly when map sizes are increased, which indicates that the method is not scalable. This weakness in itself is not very significant as prior work has experimented with much smaller map sizes.\n\nThe bigger weakness is that the proposed method is not differentiable, which is one of the main benefits of prior learning-based planning methods such as VINs over traditional planners. Differentiability allows the planning models as a component in larger end-to-end models (for example in CMP (Gupta et al., CVPR 2017)). It seems that the only benefit of the proposed approach over traditional planners is that it is faster. However, the lack of differentiability combined with poor scalability means that the proposed approach is only useful for real-time planning on small maps, and even in this case, the proposed approach performs slightly worse than traditional planners (100% vs 99.2%). This makes the significance of the approach very low in my opinion. Traditional planners would be still be preferred over the proposed method when maps are large or when performance is more important than runtime.\n\nThe use of Transformers for planning is not well motivated in the submission. Prior work has utilized convolutional neural networks and convolutional LSTMS for this problem, but the authors have not provided empirical comparisons to those methods. If the motivation is to tackle variable map sizes, why not use recurrent neural networks? Comparison with recurrent and convolutional neural networks is important to establish the significance of Transformers for this problem. The authors have added a convolutional network-based baselines (UNet) in certain experiments but there are no details available on how this baseline is implemented. \n\nThe authors only conduct experiments for 2D navigation tasks. It is unclear whether the approach would scale to manipulation tasks with higher degrees-of-freedom.", "summary_of_the_paper": "This paper proposes a learning-based method to solve planning problems. The approach first identifies regions on the map using transformers to provide attention to map areas likely to include the best path, and then applies local planners to generate the final collision-free path. Experiments show that the proposed method can achieve performance comparable to the traditional planners with lower planning time for smaller maps, but the performance drops significantly as the map sizes increase.\n\nNote that I previously reviewed this paper for NeurIPS 2021. The authors have made a few changes since the NeurIPS version and I have updated my review accordingly.", "summary_of_the_review": "Although the paper tackles an important problem, it has several weaknesses in terms of motivation and missing baselines. Lack of differentiability and poor scalability severely limits the applications of the proposed approach.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "HgJxzPcIcJ9", "reviewer": "Reviewer_J9BR", "summary": "", "questions": "", "limitations": "", "rating": 6, "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 is well written, clearly presented and well-motivated. The proposed approach combines learning-based and sampling-based planning approaches using the strength of each approach to solve the task it is best suited to. The authors present several important contributions, from using transformers to ensure the planner can attend the entire map in deciding which areas to sample from, to using positional encoding in a way that allows them to generalise to unseen maps. Furthermore, the approach is presented in a way that makes it reasonable to assume it will generalise to significantly larger maps.\n\nThere are a couple of concerns. Firstly, the evaluation presents 2 planning scenarios: point-robot and Dubins car. The results on the point-robot are well presented and thorough, however I was less convinced by the Dubins-path results. It seems like what the MPT has to learn is very similar in both cases, and there is very little evidence that the MPT network is learning any kinematic-specific strategies. It would be interesting to explore this area further, perhaps with maps that have both kinetically feasible and unfeasible trajectories. Ideally, a point-robot MPT would choose trajectories regardless of kinematic feasibility, whereas the Dubins car model would choose the kinematically feasible one. Secondly, the approach seems to be limited to 2D. While I understand that this is a large domain in-and-of itself, it is important to notice that RRT* and its variants are designed for higher-dimensional spaces and can be outperformed by simple A* in 2D grids. It would be interesting to see if the approach can generalise to higher dimensions, making it feasible for robotic arms and more complex planning spaces. It seems like the windowed approach should be extendable to higher dimensions? Finally, the authors do not compare against learning-based planners because they did not perform well, however it would be interesting to see the results for context.\n\nA few minor things:\n-Page 4: “For maps larger than then the” -> remove then\n-Page 5: “For Dubins Car Model” -> “For the Dubins Car Model”\n-Figure 5, consider re-moving RRT* to make the other approaches more easy to read. RRT* is not constrained in sampling, so it makes sense. \n-Page 6: Figure 4 is referenced before 3, might be worth re-ordering figures. and 4 are referenced in", "summary_of_the_paper": "The paper presents a Transformer-based planning approach that attempts to use an attention mechanism to reduce the search-space of a traditional planner such as RRT*. Approaches such as Informed RRT* constrain the search space of the planner, which allows much faster convergence time. In a similar way, the authors present an approach that uses attention on a 2D map to create a \"mask\" for a standard planner to draw samples from. The proposed Motion Planning Transformer (MPT) works by using sliding window on the original map, creating features that are then positionally encoded (which helps with generalisation) and then put through a transformer encoder and classified. The result is a prediction, for each patch, as to whether a planner should draw samples from it. When combined with a planner it is able to achieve state-of-the-art results in a reduced time.", "summary_of_the_review": "The paper presents a solid approach to pathplanning that solves the problem in an interesting way. There is a good amount of novelty and  experimental evidence and the approach is technically sound.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes a planning framework that uses a transformer-based architecture as an attention mechanism that guides the search of a traditional sample-based planner (e.g., RRT*). More specifically, features extracted from a sliding window over the 2D search space serve as input to a transformer that produces a mask indicating where to draw samples from. By constraining the search space for the sample-based planner, the method reduces the time required for planning. The method is compared to both traditional and learning-based planners on different 2D navigation tasks and found to improve sample complexity (and, in turn, computation time), while also being capable of generalizing to unseen and real-world maps.

The manner by which the method combines the advantages of sample-based planning with an attentional mechanism as a way to constrain the sampling process is interesting. As the reviewers emphasize, the experimental evaluation shows that this approach results in performance gains over both traditional (sample-based) and learning-based planners, while also being able to scale to larger maps as well as better generalize to out-of-distribution settings (compared to learning-based methods). These results support the value of both the overall approach as well as the architectural components (e.g., the transformer and the use of positional encoding). The reviewers initially raised a few concerns with the paper, the most notable of which are the need to include preprocessing in the overall computation time, the accuracy of some of the claims in the paper (e.g., with regards to generalizability), generalization to higher-dimensional domains, and the performance on the Dubins car domain. The authors responded to each of the reviews and updated the submission to address many of these concerns. However, questions still remain regarding whether or not the approach can be adapted to state/configuration spaces with more than two dimensions, something that traditional planners are readily capable of, and the unconvincing results on the Dubins car domain.

Overall, the paper proposes an interesting approach to an important problem that is relevant to the robotics and machine learning communities. The paper makes promising contributions to improve the efficiency of planning, however the significance of these contributions needs to be made clearer.
Decision: Reject