Differentiable Spatial Planning using Transformers
Authors: Devendra Singh Chaplot
Deepak Pathak
Jitendra Malik
Venue:  (2021)
Keywords: Planning
Spatial planning
Path planning
Navigation
Manipulation
Robotics

Abstract: We consider the problem of spatial path planning. In contrast to the classical solutions which optimize a new plan from scratch and assume access to the full map with ground truth obstacle locations, we learn a planner from the data in a differentiable manner that allows us to leverage statistical regularities from past data. We propose Spatial Planning Transformers (SPT), which given an obstacle map learns to generate actions by planning over long-range spatial dependencies, unlike prior data-driven planners that propagate information locally via convolutional structure in an iterative manner. In the setting where the ground truth map is not known to the agent, we leverage pre-trained SPTs to in an end-to-end framework that has the structure of mapper and planner built into it which allows seamless generalization to out-of-distribution maps and goals. SPTs outperform prior state-of-the-art across all the setups for both manipulation and navigation tasks, leading to an absolute improvement of 7-19%.

Under review as a conference paper at ICLR 2021
DIFFERENTIABLE SPATIAL PLANNING USING TRANSFORMERS
Anonymous authors Paper under double-blind review
ABSTRACT
We consider the problem of spatial path planning. In contrast to the classical solutions which optimize a new plan from scratch and assume access to the full map with ground truth obstacle locations, we learn a planner from the data in a differentiable manner that allows us to leverage statistical regularities from past data. We propose Spatial Planning Transformers (SPT), which given obstacle map learns to generate actions by planning over long-range spatial dependencies, unlike prior data-driven planners that propagate information locally via convolutional structure in an iterative manner. In the setting where the ground truth map is not known to the agent, we leverage pre-trained SPTs in end-to-end framework that has the structure of mapper and planner built into it which allows seamless generalization to -iitriiiiiiittiion maps and goals. SPTs outperform prior state- of-the-art across all the setups for both manipulation and navigation tasks, leading to an absolute improvement of 7-19%.
INTRODUCTION
The problem of path planning has been a bedrock of robotics. Given obstacle map of environ- ment and a goal location in the map, the task is to output shortest path to the goal location starting from any position in the map. We consider path planning with spatial maps. Building a top-down spatial map is common practice in robotic navigation as it provides a natural representation of physical space (Durrant- Whyte& & Bailey, 2006). In fact, even robotic manipulation can also naturally phrased via spatial map using the formalism of configuration spaces (Lozano-Peree
(a) Navigation
(b) Manipulation
Spatial Path Planning: The raw obser- vations (top left) and obstacles can be represented spatially via top-down map in navigation (left) and via configuration space in manipulation (right).
Figure 1:
1990), as shown in Figure 1. This problem has been studied in roboties for several decades, and classic goto planning algorithms involve Dijkstra et al. (1959), PRM (Kavraki et al., 1996), RRT (La Valle & Kuffner Jr, 2001), RRT* (Karaman & Frazzoli, 2011), etc.
Our objective is to develop methods that can learn to plan from data. However, a natural question is why do we need learning for problem which has stable classical solutions? There two key reasons. First, classical methods do not capture statistical regularities present in the natural world, (for e.g., walls mostly parallel scratch for each new setup. This also makes analytical planning methods to be often slow at inference time which an issue in dynamic scenarios where a more reactive policy might be required for fast adaptation from failures. A learned planner represented via neural network can not only capture regularities but is also efficient at inference as the plan is just a result of forward- saadd-passssss through the network. Second, critical assumption of classical algorithms is that global ground-truth obstacle space must be known to the agent ahead of time. This is stark contrast to biological agents where cognitive maps are not pixel-accurate ground truth location of agents, but built through actions in the environment, e.g., rats build an implicit map of the environment incrementally through trajectories enabling them take shorteuts (Tolman, 1948). A learned solution could not only provides the ability to deal with partial, noisy maps and but also help build maps on the fly while acting in the environment by backpropagating through the generated long-range plans.
perpendicular to each other), because they optimize plan from

---

Under review as a conference paper at ICLR 2021
Iterstions
i=
i=
i=4
i=
Goal
Obstacias
Local Value Propagation
C
C
c
C
C
Long distance Value Propagation
5
C
C
C
Map
Figure 2: Local vs Long-distance value propagation. Figure showing an example of number of iterations map using local and long-distance value propagation. The obstacle iterations is shown the
required to propagate distance values map and goal location shown the left and the distance value predictions right (distance values increase from blue to yellow). Prior methods based on convolutional networks use value propagation and require many iterations to propagate values accurately over the whole map (top right). Our method is based on long-dia distancee value propagation between points without any obstacle between them. This type of value propagation
the whole map in 3 iterations in this example (bottom right).
Several recent works have proposed data-driven path planning models (Tamar et al., 2016; Karkus al., 2017; Nardelli al., 2018; Lee al., 2018). Similar how classical algorithms. like Dijkstra et al. (1959), move outward from the goal one cell at time to predict distances iteratively based on the obstacles in the map, current learning-base in only local neighborhood using convolutional networks. This kind of local value propagation requires (M) iterations, where is the map dimension. theory, however, the optimal paths can be computed much more efficiently with total iterations that are the order of number of obstacles rather than the map size. For instance, consider two points with no obstacle between, an efficient planner could directly connect them with interpolated distance. Nonetheless, this possible only if the model can perform long-range reasoning in the obstacle space which is a challenge.
spatial planning models propagate distance values
In this work, goal is to capture this long-range spatial relationship. Transformers (Vaswani et al., 2017) are well suited for this kind of computation as they treat the inputs as sets and propagate information across all the points within the set. Building on this, we propose Spatial Planning Transformers (SPT) which consists of attention heads that can attend to any part of the input. The key idea behind the design of the proposed model is that value can be propagated between distant points if there are no obstacles between them. This would reduce the number of required iterations to O(no) where no is the number of obstacles in map. Figure shows simple example where long-distance value propagation can cover the entire map within 3 iterations while local value propagation takes more than iterations - this difference grows with the complexity of the obstacle space and map size. We compare the performance of SPTs with prior state-of-the the--o-tthhrrrrr art learned planning approaches, VIN (Tamar et al., 2016) and GPPN (Lee et al., 2018), across both navigation as well as manipulation setups. SPTs achieve significantly higher accuracy than these prior methods for the manipullare
same inference time and show over 10% absolute improvement when the maps are large.
Next, turn the case when the map not known apriori. This is practical setting when the agent either has access to a partially known map or just know it through the trajectories. In psychology, this known as going from roufe knowledge to survey knowledege (Golledge al., 1995) where animals aggregate the knowledge from trajectories into a cognitive map. We operationalize this setup by formulating end-to-end differentiable framework, which in contrast having generic parametric policy learning (Glasmachers, 2017). has the structure of mapper and planner built into it. We first pre-train the SPT planner capture generic data-driven prior, and then backpropagate through it to learn mapper that maps raw observations to obstacle map. This allows us to learn without requiring map supervision or interaction. Learned mapper and planner not only allow us to plan for new goal locations at inference but also generalize to unseen maps.
Our end-to-end mapping and planning approach provides a unified solution for both navigation and manipulation. We perform thorough experiments in both manipulation and real-world navigation maps as well as manipulation. Our approach outperforms prior state-of-the-an by a margin on both mapping and planning accuracy without assuming access to the map training inference.
2

---

Under review as a conference paper at ICLR 2021
Map See Licture
FC
FG
FD
Decoder D
Imput
Predicted distance
Lioodinn
Transformer Layer (fr.
Traneformer
2-tayer (1x11)
Inaratormss Layers
Transformer Layer (n.)
Fostional Eroxding
M.
Natinn
0.11891...
Encoder E
hout Brooding
Figure Spatial Planning Transformer (SPT). Figure showing overview of the proposed Spatial Planning Transformer model. consists modules: an Encoder encode input, Transformer network T responsible for planning, and Decoder D decoding the output of Transformer into action distances.
2 PRELIMINARIES AND PROBLEM DEFINITION
We represent the input spatial map as a matrix, m, of size M x with each element being denoting obstacles, or 0, denoting free space. The goal location is also represented as matrix, g. of size M x M with exactly one element being 1, denoting the goal location, and rest Os. The input to the spatial planning model, Iz consists of matrices and g stacked,
[m, g). where æ is of size 2 x M x M. The objective of the planning model is to predict which is of size M x M, consisting of action distances of corresponding locations from the goal. Here, action distance is defined to be the minimum number of actions required to reach the goal.
For navigation, is top-down obstacle map, and represents the goal position this map. For manipulation, m represents the obstacles in the configuration space of 2-dof planar arm with joint angles denoted by 02 and 0g2. Each element (i.j) )) in indicate whether the configuration of the arm with joint angles 01 = i and 0g of the arm. In the first set experiments, we will assume that m known and the second set of experiments, m is not known and the agent receives observations, o, from its sensors instead.
would lead to a collision. represents the goal configuration
METHODS
We design a spatial planning model capable of long-distance information propagation. We first describe the design this spatial planning module, called Spatial Planning (San))ormer(PPT), shown in Figure 3, which takes in map and goal as input and predict the distance to the goal from all locations. We then describe how the SPT model can used planning module to train end-to-end learning models, which take in raw sensory observations and goal location input and predict action distances without having access
map.
3.1 SPT: SPATIAL PLANNING TRANSFORMERS
To propogate information over distant points, we use the Transformer (Vaswani et al., 2017) architec- ture. The self-attention mechanism in Transformer can learn to attend to any element of the input. The allows the model to learn spatial reasoning over the whole map concurrently. Figure 3 shows an overview of the SPT model, which consists of three modules, Encoder E' to encode the input, Transformer network 7' responsible for spatial planning, and Decoder D) decoding the output the Transformer into action distances.
Encoder. The Encoder E computes the encoding of the input x: Σ1 = E(x). The input (0, 1 X consisting of the map and goal is first passed through 2-layer convolutional network (LeCun et al., 1998) with ReLU activations to compute an embedding for each input element. Both layers have kernel size of 1, which ensures that the embedding of all the obstacles is
3

---

Under review as a conference paper at ICLR 2021
Manipulation Mapper
SPT
Navigation
SPT
Mapper
Observation Space (o)
Predicted Map (m)
Spatia/ Planning (pp
Predicted Action Distances
Goal (g)
Mapping (fx)
Figure 4: End-to-end Mapping and Planning. Figure showing an overview of end-to-en mapping and planning model for both the navigation and manipulation tasks.
identical to each other, and the same holds true for free space and the goal location. The output of this convolutional network is of size d M x M, where is the embedding size. This output is then flattened to get 2 of size d x M and passed into the Transformer network.
Transformer. The Transformer network T converts the input encoding into the output encoding: 7xx)). ). It first adds the positional encoding to the input encoding. The positional encoding enables the Transformer model distinguish between the obstacles different locations. We use constant sinusoidal positional encoding (Vaswani et al., 2017):
P(2..) )
P(2+1J) = cos(j//aa/j)
where p E RdxM² is the positional encoding. j E (1.2...., M23 is the position of the input, i e {1,2,... ..., d/2]. and C' = M is constant.
The positional encoding of each element added to their corresponding input encoding to get Z p. Z is then passed through N identical Transformer layers (fn.) to get zo.
Decoder. The Decoder D computes the distance prediction ý from zo using a position wise fully connected layer:
ú. WTTT, DD
where 2T, Rdx1 is the input at position i 1,2, M WD Rdx1, E R parameters of the Decoder shared across all positions and 0; E R is the distance prediction at position The distance prediction all position reshaped into matrix to get the final prediction R M.M. The entire model is trained using pairs of input and output datapoints with mean-squared error as the loss function.
3.2 END-TO-END MAPPING AND PLANNING
The SPT model described above is designed to predict action distances given map input. However, in many applications, the map the environment is often not known. In such cases, an autonomous agent working realistic environment needs predict the map from raw sensory observations. While is possible to train separate mapper model to predict maps from observations, this often requires map annotations which are expensive to obtain and often inaccurate, demonstration trajectories consisting of observations and optimal actions are more readily available or easier to obtain many roboties applications. One the key benefits of learning- based differentiable spatial planning is that it can be used to learn mapping just from action supervision in an end-to-end fashion without having access to ground- -ruth maps. To demonstrate this benefit, we train an end- to-end mapping and planning model to predict action distances from sensor observations for both navigation and manipulation tasks.
contrast,
The end-to-end mapping and planning model consists of two modules, Mapper (fM) and Planner (fp), as illustrated in Figure 4. The Mapper is used to predict the map mn from sensor observations o and the Planner is spatial planning model predict action distances, ÿ. from the predicted map f:
i = fr(m)= = (o)
4

---

Under review as a conference paper at ICLR 2021
For navigation, is the set of first-person RGB camera images each of size 3 x H X W. We sample 4 images, one for each orientation, at each valid location in the map. For invalid locations, we pass an empty image of Os for all orientations. Thus, for map of size M M, observation consist of 4M2 images for all locations and 4 orientations similar to the setup in Lee et al. (2018). For manipulation, is top-down view of the operational space with obstacles of size P P, where each element is 1 or 0 denoting obstacles or free space. We use different Mapper architectures for navigation and manipulation experiments.
The Navigation Mapper module predicts a single value between 0 and for each image in o indicating whether the cell in the front of the image is an obstacle or not. The architecture of the Navigation mapper consists of ResNet18 convolutional layers followed by fully-connected layers (see Appendix for details). Each cell can have upto 4 predictions (from images corresponding to the four neighboring cells facing the current cell), which are aggregated using max pooling to get single prediction. This map prediction consisting of continuous values is passed the Planner module.
The Manipulation Mapper module needs to predict which configurations of the arm would lead to collision. To predict whether a particular configuration (0,, 02), the mapper module needs to check whether any point in this configuration consists of an obstacle. A Transformer-basee suited to learn this function as well as it can attend to arbitrary locations in the operational space to predict the obstacles in the configuration space. We the same architecture of the SPT model as the Manipulation Mapper as well, with the only difference being the encoder consisting of 3 x 3 kernel size convolutional layers instead of 1 x 1 to encode the P x P observation space M x M representation.
model is well
The Planner module is the entire SPT model with encoder, transformer and decoder units as described in the previous subsection. It is pretrained on synthetic maps and its weights are frozen during end-to-end training. We train the entire end-to-end Mapping and Planning model with pairs of input observations and output action distances y using standard supervised learning with the mean- squared error as the loss function: L E(E 9) L/IL|Ees (y ) where L the set of navigable locations. Since the planning module is pretrained and it expects structured map input, the mapper model needs to predict the map accurately such that the predicted map, when passed through the planner, minimizes the action level loss.
4 EXPERIMENTS & RESULTS: SPATIAL PLANNING
Datasets. We generate synthetic datasets for training the spatial planning models for both navigation and manipulation settings. For the navigation setting, we perform experiments with M x M maps with three different map sizes, M E {15, 30, 50). For manipulation, we experiment with two map sizes, M E {18, 36), corresponding to 20 and 10 bins for each link. In each map, we randomly generate Ominn = 0 to Omar = 5 obstacles. Dataset generation details are provided in the Appendix.
For both the settings, we generate training, validation, and test sets of size 100K/5K/5K maps. The set of maps in each set are distinct. For each map, we choose a random free space cell as the goal location. The action space consists of 4 actions: north, south, east, west. For the navigation task, the map boundaries are considered as obstacles, while for the manipulation task the cells on the left and right boundaries and top and bottom boundaries are connected to each other since angles are circular. The ground truth shortest path distances are calculated using the Dijkstra algorithm (Dijkstra et al., 1959). Unreachable locations and obstacles are denoted by 1 in the ground truth.
In addition to testing on unseen maps with the same distribution, we also test the spatial planning models on two types of -itto---istruutionn datasets: More Obstacles where we generate Omin 15 to Omez 20 obstacles per map, and Real-world where the top-down maps are generated from reconstructions of real-world scenes in Gibson dataset (Xia et al., 2018).
Hyperparameters and Training. For training the SPT model, we use Stochastic Gradient De- scent (Bottou, 2010) for optimization with a starting learning rate of 1.0 and a learning rate decay of 0.9 per epoch. We train the model for 40 epochs with batch size of 20. We use N = 5 Transformer layers each with à = 8 attention heads and a embedding size of d = 64. The inner dimension of the fully connected layers in the transformer is dye 512. We use the same architecture with the same hyperparameters for training the SPT model for both navigation and manipulation for all map sizes. We will open-source the code including dataset generation, model implementation and training.
5

---

Under review as a conference paper at ICLR 2021
Navigation M=30
Manipulation
Overall
Method
M=15
M=50
M=18
M=36
VIN
86.19
83.62
80.84
75.06
74.27
80.00
GPPN
97.10
96.17
91.97
89.06
87.23
92.31
SPT
99.07
99.56
99.42
99.24
99.78
99.41
Table 1: Generalization to in-distribution maps. Table showing the average planning accuracy of the proposed model Spatial Planning Transformer (SPT) as compared to the baselines on in-distribution test sets for both the navigation and manipulation experiments.
Navigation
Manipulation More Obstacles M-36
Overall
More Obstacles M=30
Real-World M=30
Method
M=15
M-50
M=15
M=50
M=18
VIN
49.05
62.05
70.64
49.91
56.67
71.16
65.27
59.81
60.57
GPPN
90.68
89.93
84.86
90.11
91.07
88.32
79.86
80.79
86.95
SPT
93.34
92.71
92.03
95.96
94.70
95.39
98.16
99.18
95.18
Table 2: Generalization to out-of-distribute maps. Table showing the average planning accuracy of the proposed model Spatial Planning Transformer (SPT) compared to the baselines out-of-distribution sets for both the navigation and manipulation experiments.
Baselines. We use prior spatial planning models baselines. These include Value Iteration Networks (VIN) (Tamar et al., 2016) and Gated Path-Planning Networks (GPPN) (Lee et al., 2018). For tuning consider all values
the hyperparameter (K) for the number of iterations in both the baselines, of in multiples of 10 such that the inference time of the baseline is comparable to the inference time of the SPT model (S 1.1 times). For each setting, we tune K and the learning rate to maximize performance on the validation set.
Metrics. We use average action prediction accuracy as the metric. Distance prediction is converted to actions by finding the minimum distance cell among the 4 neighboring cells for each location. When multiple actions are optimal. predicting any optimal action considered to be correct prediction. The accuracy is averaged over all free space locations over all maps in the test set.
The planning accuracy of all the methods for both the navigation and manipulation tasks on the in-distribution test sets are shown in Table I and on the out-of out-of-distriben distribution test sets are shown in Table The proposed SPT model outperforms both the baselines across all settings achieving an overall accuracy of 99 999.41% % vs 92.31 % (in (in-distribution) and 95.18% vs 86.95% (out-of-distribution) as compared to the best baseline. The performance of the SPT model is stable as the map size increases while the performance of the baselines drop considerably. We believe this is because both the baselines need to use a larger number of iterations to cover a larger map (K = 60 iterations for GPPN and K 90 iterations for VIN for M 50) since the information propagation is local in VIN and GPPN. The optimization becomes difficult for such deep models. In contrast, the SPT model uses constant N layers for all map sizes.
Results.
The improvement in the performance of SPT over the baselines is larger in the manipulation task because the baselines based convolution operations not well suited for propagating information looping over the edges of the map. In contrast, the SPT model can use self-attention to attend to any part of the map and learn to propagate information over the map edges.
Visualizations. In Figure 5, we show examples of predictions of the SPT model compared to the baselines for different input maps and goals from 3 different test sets. The examples show that the baselines are not able to predict the distances of distant cells accurately. This is because they propagate information in a local neighborhood that can not reach distant cells in the limited inference time budget (K 30 for VIN and K = 20 for GPPN). In contrast, the SPT is able to predict distances of distant cells more accurately with N layers indicating that it learns long-range information propagation. Additional examples are provided in the Appendix.
Runtime per map in ms
Method
M=15
M=30
M=50
Dijkstra A
4.17
43.82
371.05
3.02
35.38
294.70
SPT
2.44
4.72
18.35
Table 3: Runtime comparison. Com- parison of average runtime per map in milli seconds for different methods. values are averaged over 10000 maps.
Runtime Comparison. To demonstrate one of the benefits of learning-bart based planners over classical planning algorithms, compare the runtime of SPT to Dijkstra (Dijkstra al., 1959) and A (Hart

---

Under review as a conference paper at ICLR 2021
Input Map and Goal
VIN
GPPN
SPT
Ground Truth
Test Set
More Obstacles
Real World
Figure 5: Spatial Planning Examples. Figure showing examples of the input, the predictions using the obstacles shown leftmost input column. The predictions and ground
proposed SPT model the baselines, the ground truth map size M blue, free space purple and goal in yellow the rest of the column are color-coded from blue to ycllow to represent increasing action distance.
et al., 1968) algorithms in Table 3. The results indicate that SPT is 1.24x to 20.22x faster than classical planning algorithms with the runtime benefit improving with the increase map size.
5 EXPERIMENTS & RESULTS: END-TO-END MAPPING AND PLANNING
In the above experiments, we compared the planning performance different methods under perfect knowledge of the map In this section, test the efficacy of spatial planning methods when map m is unknown and needs to be predicted from sensor observations o.
Datasets. For manipulation,
generate synthetic datasets of size M 18 using the same process P image with P 90 which
as described in Section We discretize the operation space into used the observation The train/test sets are of size 100K/5K.
For navigation, we use the Gibson dataset (Xia et al., 2018) to sample maps of size M 15 where each cell is 0.25m area. We get the camera images at the navigable locations in all 4 orientations using the Habitat simulator (Savva et al., 2019). The set camera images each size x x W as the observation for the navigation task, where H/ W 128. The train and test consist of 72 and 14 distinct scenes identical to the standard train and val splits in the Habitat simulator. We sample 500 maps in each scene creating training/test of size 36K/7K. Each sampled map is rotated to random orientation.
Training. We load the weights different models trained on synthetic data from the previous section. We then train the end-to-end model using the same action distance prediction loss while keeping the planner weights frozen. The architecture the mapper module is identical across different planning methods. Metrics. We report both map accuracy and planning accuracy for both the tasks.
Baselines. addition using VIN and GPPN as baselines, we also use classical mapping and planning baseline for the navigation task. Since there is no depth input available, we used Monocular depth estimation model from Hu et (2019) for predicting the map which is then used for planning using Dijkstra suggested by Mishkin et al. (2019).
Results. Table 4 shows the end-to-end mapping and planning results. SPT outperforms both GPPN and VIN by large margin across both the tasks achieving overall plan accuracy of 82.29% vs 63.91%. Table 4 also shows that the mapper learnt using end-to-end training with pretrained SPT model is able achieve accuracy of 98.96% for manipulation and 82.58% for navigation, without receiving any map-level supervision. SPT also outperforms the classical mapping and planning baseline. These results demonstrate key benefit of leasningbbased differentiable planners
7

---

Under review as a conference paper at ICLR 2021
Navigation
Manipulation
Overall
Method
Map Acc
Plan Acc
Map Acc
Plan Acc
Map Acc
Plan Acc
Classical
64.43
45.20
VIN
60.92
47.77
81.25
66.45
71.08
57.11
GPPN
69.06
45.70
85.57
82. 13
77.31
63.91
SPT
82.58
66.16
98.96
98.42
90.77
82.29
Table 4: End-to-End Mapping and Planning Results. Table showing the average mapping and planning accuracy of the proposed model Spatial Planning Transformer (SPT) as compared to the baselines for end-to-end mapping and planning experiments.
as compared to classical analytical planning algorithms. As SPT outperforms VIN and GPPN at spatial planning, also leads to better map accuracy (90.77% vs 77.
5.1 SPARSE AND NOISY SUPERVISION
In the above experiments, we assumed access to perfect and dense practice, if we were to get supervision from human trajectories, the supersion could be sparse, we might not have access the optimal distance from all locations in the map, and noisy as humans might not take the optimal actions always and computing distances from human trajectories might be noisy. To study the effect of not having dense and perfect supervision for training the end-to-end mapping and planning model, consider three settings: Noisy supervision: We add zero mean gaussian noise to all ground-truti -tuuh distance values with standard deviation, = 1.
supervision. In
Sparse supervision: Instead of providing distances from all navigable locations in the ground truth, we provide distances for only 5 trajectories to the same goal in the training maps.
Noisy and Sparse supervision: We provide noisy distances for only 5 trajectories as supervision.
Figure shows an example of noisy and sparse supervision. The results are shown in Table 5. The SPT model maintains performance benefits over the baselines under all the settings. Interestingly, under sparse supervision, the map prediction accuracy drops, but the planning accuracy does not drop as much. This is because the model learns to predict minimum map required to predict the action distances all valid locations accurately as seen examples shown in Figure 15 in the Appendix.
6 RELATED WORK
Path planning in known or inferred maps, also known as motion planning in robotics, is a well explored problem led by the seminal papers (Canny, 1988; Kavraki et al., 1996; Valle & Kuffner Jr, 2001; Karaman & Frazzoli, 2011) 1). Although there are learned variants of motion planners proposed the literature using gaussian processes (ljspeert et al., 2013; Ratliff et al., 2018), data-driven motion planners using neural networks is recent direction (Qureshi et al., 2019; Bhardwaj et al., 2020; Qureshi et al., 2020). Prior work has also studied the use of neural networks to learn the heuristics and sampling stratergies in classical planners Ichter et al. (2018); Guez et al. (2018); Satorras & Welling (002)); Khan et al. (2020). Learning for planning is more common in Markov Decision Process (MDPs) for computing value function via dynamic programming based value iterations (Bellman, 1966; Bertsekas et al., 1995). Planning and learning in neural networks has been explored (Ilin et al., 2007) with a successful general formulation provided by value iteration networks (VIN) (Tamar et al., 2016) with follow-ups to improve scalability and efficiency (Lee et al., 2018; Karkus et al., 2017; Nardelli et al., 2018: Schleich et al., 2019; Khan et al., 2018: Chen al., 2020). However, these models only capture local value propagation using CNNs and are mostly applied in navigation setups. In contrast, proposed SPTs capture long-range spatial dependency and easily scale to both navigation and manipulation.
Differentiable planning structure has also been explored in reinforcement learning with model-free methods (Silver et al., 2017; Oh et al., 2017: ; Zhu et al., 2017; Farquhar et al., 2018) well as off-policy RL (Eysenbach et al., 2019; Laskin et al., 2020). Recent works also backpropagate through learned planners train the policy (Pathak al., 2018; Srinivas al., 2018; Amos et al., 2018) and use imagined rollouts of learned world model for long-term plans (Racanière et al., 2017; Hafner et al., 2019; Sekar et al., 2019). Unlike work, these works lack the structure of spatial planner.
8

---

Under review as a conference paper at ICLR 2021
Dense and Perfect supervision
Noisy supervision
Sparse supervision
Noisy and Sparse supervision
Map and Goal
of
Ingectores
Figure Sparse and Noisy Supervision. Figure showing examples of map and goal with different levels of supervision. Noisy supervision adds gaussian noise to ground truth distance values, and sparse supervision samples 5 trajectories for random starting locations to the goal location.
Dense and Perfect supervision
Noisy
Sparse
Noisy and Sparse supervision
supervision
supervision
Method
Map Acc
Plan Ace
Map Acc
Plan Acc
Map Acc
Plan Acc
Map Acc
Plan Acc
VIN
81.25
66.45
75.68
60.78
70.16
60.23
70.22
58.97
GPPN
85.57
82.13
80.13
76.11
72.73
75.13
70.08
72.85
SPT
98.96
98.42
96.35
95.83
80.15
97.18
77.17
94.34
Table 5: Sparse and Noisy Supervision Results. Table showing the average mapping and planning accuracy of the proposed model Spatial Planning Transformer (SPT) as compared to the baselines for end-to-end mapping and planning experiments under noisy and sparse supervision settings for the manipulation task.
Decomposing learning controller into mapping and planning is common in robot navigation (Khatib, 1986; Elfes, 1987). Some works have explored joint mapping and planning (Elfes, 1989; Fraundorfer et al., 2012). Maps also be built from vision (Konolige et al., 2010; Fuentes-Pacheco et al., 2015) with learned mapper (Parisotto & Salakhutdinov, 2017; Karkus et al., 2020). There has been some work learning maps without using map annotations well (Gregor al., 2019). For navigation specific applications, recent works proposed joint mapping and planning for navigation (Gupta et al., 2017; Zhang et al., 2017; Savinov et al., 2018; Chaplot al., 2020). However, most of these works either require access to ground truth map or assume interaction. Hence, they will first need to be trained in simulation. contrast, we show results when the map is not known to the agent by learning just from trajectories and can be directly learned from data collected in the real-world.
DISCUSSION
The SPT model designed to learn long-range spatial planning and outperforms baselines across multiple experimental settings both navigation and manipulation tasks. End-to-end learning experiments demonstrate that the SPT model can deal with unknown maps by learning mapping without any mup-supervisson However, there are some limitations that need to be addressed before learning-bass planning methods can be used for large-scale applications. We showed that the SPT model scales much better with increasing map sizes compared to the baselines, however larger map sizes lead to a high inference time. In the future, we plan to tackle larger map sizes by learning an encoding which reduces the size of the map before spatial planning. The action space was limited 4 actions in our experiments. Actions can be more fine-grained with smaller cells in the map, which can also be incorporated by tackling larger map sizes in the future.
REFERENCES
Brandon Amos, Ivan Jimenez, Jacob Sacks, Byron Boots, and Zico Kolter. Differentiable mpe for end-to-end planning and control. In NeurlPS, 2018.
Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey Hinton. Layer normalization. arXiv preprint arXiv: 160.:666070645000 2016.
Richard Bellman. Dynamic programming. Science, 1966.

---

Under review as a conference paper at ICLR 2021
Dimitri P Bertsekas, Dimitri P Bertsekas, Dimitri P Bertsekas, and Dimitri P Bertsekas. Dynamic programming and optimal control. Athena scientific Belmont, MA, 1995.
Mohak Bhardwaj, Byron Boots, and Mustafa Mukadam. Differentiable gaussian process motion planning. In International Conference on Robotics and Automation (ICRA). 2020.
Léon Bottou. Large-scale machine learning with stochastic gradient descent. In Proceedings of COMPSTAT'2010 Springer, 2010.
John Canny. The complexity of robot motion planning. MIT press, 1988.
Devendra Singh Chaplot, Dhiraj Gandhi, Saurabh Gupta, Abhinav Gupta, and Ruslan Salakhutdinov. Learning explore using active neural slam. arXiv preprint arXiv:2004.05/55, 2020.
Binghong Chen, Bo Dai, Qinjie Lin, Guo Ye, Han Liu, and Le Song. Learning to plan in high dimensions via neural exploration-explootation trees. In ICLR, 2020.
Edsger W Dijkstra et al. A note two problems in connexion with graphs. Numerische mathematik, 1959.
Hugh Durrant- Durrant-Whyte and Tim Bailey. Simultaneous localization and mapping: part i. IEEE robotics & automation magazine, 2006.
Alberto Elfes. Sonar-based real-world mapping and navigation. IEEE Journal on Robotics and Automation, 1987.
Alberto Elfes. Using occupancy grids for mobile robot perception and navigation. Computer, 1989.
Ben Eysenbach, Russ R Salakhutdinov, and Sergey Levine. Search on the replay buffer: Bridging planning and reinforcement learning. In NeurIPS, 2019.
Gregory Farquhar, Tim Rocktäschel, Maximilian Igl, and Shimon Whiteson. Treeqn and atreec: Differentiable tree-structured models for deep reinforcement learning. In ICLR, 2018.
Friedrich Fraundorfer, Lionel Heng, Dominik Honegger, Gim Hee Lee, Lorenz Meier, Petri Tanska- nen, and Mare Pollefeys. Vision- autonomous mapping and exploration using a quadrotor mav. In International Conference on Intelligent Robots and Systems, 2012.
Jorge Smentes-PPcheca José Ruiz-Ascencic and Juan Manuel Mandhn. Visual simultaneous localization and mapping: survey. Artificial intelligence review, 2015.
Tobias Glasmachers. Limits of end-to-end learning. arXiv preprint arXiv: 070.00000000.,.... 2017.
Reginald Golledge, Valerie Dougherty, and Scott Bell. Acquiring spatial knowledge: Survey versus route-based knowledge in unfamiliar environments. Annals of the association of American geographers, 1995.
Karol Gregor, Danilo Jimenez Rezende, Frederic Besse, Yan Wu, Hamza Merzic, and Aaron van den Oord. Shaping belief states with generative environment models for rl. Advances in Neural Information Processing Systems, 32: 124755-1134877 2019.
Arthur Guez, Theophane Weber, Ioannis Antonoglou, Karen Simonyan, Oriol Vinyals, Daan Wierstra, Remi Munos, and David Silver. Learning to search with metsnets. In International Conference on Machine Learning, pp. 1822-1831, 2018.
Saurabh Gupta, James Davidson, Sergey Levine, Rahul Sukthankar, and Jitendra Malik. Cognitive mapping and planning for visual navigation. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition, 2017.
Danijar Hafner, Timothy Lillicrap, Ian Fischer, Ruben Villegas, David Ha, Honglak Lee, and James Davidson. Learning latent dynamics for planning from pixels. In ICML. 2019.
Peter E Hart, Nils Nilsson, and Bertram Raphael. A formal basis for the heuristic determination of minimum paths. IEEE transactions on Systems Science and Cybernetics, 4(2):100-107, 1968.
10

---

Under review as a conference paper at ICLR 2021
Junjie Hu, Mete Ozay, Yan Zhang, and Takayuki Okatani. Revisiting single image depth estimation: Toward higher resolution maps with accurate object boundaries. 2019 IEEE Winter Conference Applications of Computer Vision (WACV), pp. 1043 1051. IEEE, 2019.
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
Auke Jan Ijspeert, Jun Nakanishi, Heiko Hoffmann, Peter Pastor, and Stefan Schaal. Dynamical movement primitives: learning attractor models for motor behaviors. Neural computation, 2013.
Roman Ilin, Robert Kozma, and Paul Werbos. Efficient learning in cellular simultaneous recurrent neural networks-the case of maze navigation problem. In 2007 IEEE International Symposium on Approximate Dynamic Programming and Reinforcement Learning, 2007.
Sertac Karaman and Emilio Frazzoli. Sampling-basee based algorithms for optimal motion planning. The international journal of robotics research, 2011.
Peter Karkus, David Hsu, and Wee Sun Lee. Qmdp-net: Deep learning for planning under partial observability. In Advances in Neural Information Processing Systems, 2017.
Peter Karkus, Anelia Angelova, Vincent Vanhoucke, and Rico Jonschkowski. Differentiable mapping networks: Learning structured map representations for sparse visual localization. arXiv preprint arXiv:2005.09530) 2020.
Lydia E Kavraki, Petr Svestka. J-C Latombe, and Mark H Overmars. Probabilistic roadmaps for path planning in high- nigh-dimensional configuration spaces. IEEE transactions on Robotics and Automation, 1996.
Arbaaz Khan, Clark Zhang, Nikolay Atanasov, Konstantinos Karydis, Vijay Kumar, and Daniel D Lee. Memory augmented control networks. In ICLR, 2018
Arbaaz Khan, Alejandro Ribeiro, Vijay Kumar, and Anthony G Francis. Graph neural networks for motion planning. arXiv preprint 7rXiv:0006.0624: 2020.
Oussama Khatib. Real-time obstacle avoidance for manipulators and mobile robots. In Autonomous robot vehicles. Springer, 1986.
Kurt Konolige, James Bowman, JD Chen, Patrick Mihelich, Michael Calonder, Vincent Lepetit, and Pascal Fua. View-based maps. The International Journal of Robotics Research, 2010.
Michael Laskin, Scott Emmons, Ajay Jain, Thanard Kurutach, Picter Abbeel, and Deepak Pathak. Sparse graphical memory for robust planning, arXiv preprint arXiv:2003.064 2020.
Steven M La Valle and James J Kuffner Jr. Randomized kinodynamic planning. The international journal of robotics research, 2001.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 1998.
Lisa Lee, Emilio Parisotto, Devendra Singh Chaplot, Eric Xing, and Ruslan Salakhutdinov. Gated path planning networks. In ICML, 2018.
Tomas Lozano-Perez. Spatial planning: configuration space approach. Autonomous robot vehicles. Springer, 1990.
Dmytro Mishkin, Alexey Dosovitskiy, and Vladlen Koltun. Benchmarking classic and learned navigation in complex 3d environments. arXiv preprint arXiv:1901.10915. 2019.
Nantas Nardelli, Gabriel Synnaeve, Zeming Lin, Pushmeet Kohli, Philip HS Torr, and Nicolas Usunier. Value propagation networks. arXiv preprint arXiv: 1999, 2018.
Junhyuk Oh, Satinder Singh, and Honglak Lee, Value prediction network. In Advances in Neural Information Processing Systems, 2017.
11

---

Under review as a conference paper at ICLR 2021
Emilio Parisotto and Ruslan Salakhutdinov. Neural map: Structured memory for deep reinforcement learning. arXiv preprint arXiv:1702.08360, 2017.
Deepak Pathak, Parsa Mahmoudich, Guanghao Luo, Pulkit Agrawal, Dian Chen, Yide Shentu, Evan Shelhamer, Jitendra Malik, Alexei A Efros, and Trevor Darrell. Zero-shot visual imitation. In ICLR, 2018.
Ahmed H Qureshi, Anthony Simeonov, Mayur J Bency, and Michael C Yip. Motion planning networks. In International Conference on Robotics and Automation (ICRA), 2019.
Ahmed H Qureshi, Jiangeng Dong, Austin Choe, and Michael Yip. Neural manipulation planning constraint manifolds. IEEE Robotics and Automation Letters, 5(4):6089-6066, 2020.
Sébastien Racanière, Théophane Weber, David Reichert, Lars Buesing, Arthur Guez, Danilo Jimenez Rezende, Adria Puigdomenech Badia, Oriol Vinyals. Nicolas Heess, Yujia Li, et al. Imagination- augmented agents for deep reinforcement learning. In NIPS, 2017.
Nathan D Ratliff, Jan Issac, Daniel Kappler, Stan Birchfield, and Dieter Fox. Riemannian motion policies. arXiv preprint arXiv: 1801.02844 2018
Victor Garcia Satorras and Max Welling. Neural enhanced belief propagation factor graphs. arXiv preprint arXiv:2003.0/998, 2020.
Nikolay Savinov, Alexey Dosovitskiy, and Vladlen Koltun, Semi-parametric topological memory for navigation. In ICLR, 2018.
Manolis Savva, Abhishek Kadian, Oleksandr Maksymets, Yili Zhao, Erik Wijmans, Bhavana Jain, Julian Straub, Jia Liu, Vladlen Koltun, Jitendra Malik, et al. Habitat: A platform for embodied ai research. ICCV, 2019.
Daniel Schleich, Tobias Klamt, and Sven Behnke, Value iteration networks on multiple levels of abstraction. arXiv preprint arXiv:/905, /068, 2019.
Ramanan Sekar, Oleh Rybkin, Kostas Daniilidis, Pieter Abbeel, Danijar Hafner, and Deepak Pathak. Planning to explore via self-supervised world models. In ICML, 2019.
David Silver, Hado Hasselt, Matteo Hessel, Tom Schaul, Arthur Guez, Tim Harley, Gabriel Dulac- Aroold, David Reichert, Neil Rabinowitz, Andre Barreto, al. The predictron: End-to-end learning and planning. In International Conference on Machine Learning. PMLR, 2017.
Aravind Srinivas, Allan Jabri, Pieter Abbeel, Sergey Levine, and Chelsea Finn. Universal planning networks. ICML, 2018.
Aviv Tamar, Yi Wu, Garrett Thomas, Sergey Levine, and Pieter Abbeel. Value iteration networks. In NIPS, 2016.
Edward Tolman. Cognitive maps in rats and men. Psychological review, 1948.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In NIPS, 2017.
Fei Xia, Amir R. Zamir, Zhi Yang He, Alexander Sax, Jitendra Malik, and Silvio Savarese. Gibson Env: real-world perception for embodied agents. In CVPR, 2018.
Jingwei Zhang, Lei Tai, Joschka Boedecker, Wolfram Burgard, and Ming Liu. Neural slam: Learning to explore with external memory. arXiv preprint a7Xiv 09520. 2017.
Yuke Zhu, Daniel Gordon, Eric Kolve, Dieter Fox, Li Fei-Fei, Abhinav Gupta, Roozbeh Mottaghi, and Ali Farhadi. Visual semantic planning using deep successor representations. In ICCV, 2017.
12

---

Under review as a conference paper at ICLR 2021
A BACKGROUND: TRANSFORMERS
The proposed spatial planning method is based on the Transformer model (Vaswani al., 2017). A Transformer layer, denoted by fIL. takes a tensor X E Rdx as input, where d is the embedding size and S is the size of the input. consists of two sublayers, multi-head self-attention layer (fSA) and position-wise fully connected layer (/FC). There is a residual connection around each sublayer, followed by layer normalization (Ba et al., 2016) (LN):
R LN (X) X), Y fx = (N( + R)
where R, Y Rdx are the intermediate and final representations, respectively.
The multi-head self-attention (fSA) layer has attention heads, each computes a scaled dot-product attention over queries Q, keys K and values V, which are all different projections of the input X:
Q: W K; W
V
QUKT VTn
Z. Attention Qi, K₁, V.) softmax
V
where Q, Rdx E Rd.xs, E . d2 and dy are parameters. The output of all attention heads, Z,s, are concatenated and projected the same dimension as the input. Finally, the position-wil -iite fully connected (frc) layer applies two linear transformations each position with ReLU activations to the output of the multi-head attention.
and all Ws
B DATASET DETAILS
We generate synthetic datasets for training the spatial planning models for both navigation and manipulation settings. For the navigation setting, we perform experiments with M x M maps with two different map sizes, M E {15, 30). We randomly generate Omin each map, where each obstacle is an rectangle at a random location with each side being a random length from to M/2. All the rectangular obstacles are rotated two random orientations.
Omez
obstacles in
For the manipulation setting, we consider a reacher task using planar arm with 2 degrees of freedom. use an operational space size P. Each link of the arm is of size P/4. The arm is centered at the center of the operational space. Let the orientation of two links be denoted by 0 and 02. We assume both the links can freely rotate plane, 01, 0g E [0, 2xr). For each environment, we generate Omin 0 to Omar 5circular obstacles centered distance away from the center, with a random radius between 0.05P and D 0.15P where D is the distance of the center of the obstacle from the center of the operational space. We convert each environment to a configuration space map of size M x M, where each cell (f, denotes whether the will collide with an obstacle when 0, 2 / M and map sizes, M E {18, 36), corresponding to 20 and 10 bins for each link. The choice of P does not affect the map as the collision check for each cell in the configuration space is performed in the continuous operational space where all distances are relative to P.
random location 0. 0.25PP to 0.75P
2 /M. We experiment with two
C NAVIGATION MAPPER ARCHITECTURE DETAILS
The Navigation Mapper module predicts single value between 0 and for each image in o indicating whether the cell the front of the image is an obstacle or not. The architecture of the Navigation mapper consists of ResNet18 convolutional layers followed by 3 fully-connected layers of size 256, 128 and as shown in Figure 7. Each cell can have upto 4 predictions (from images corresponding to the four neighboring cells facing the current cell), which are aggregated using max pooling to get single prediction.
D HIGHER DIMENSIONAL STATE AND ACTION SPACES
To test whether SPT maintains performance benefits higher dimensional state and action spaces, conducted some experiments for the navigation task. We relaxed the action space from 4 actions
13

---

Under review as a conference paper at ICLR 2021
3x128x128
512
256
ResNet18 Conv Layers
FC1
FC2
FC3
Flatten
ReLU
ReLU
Sigmoid
RGB Image
Navigation Mapper
Figure Navigation Mapper Architecture. Figure showing the architecture the Navigation Mapper.
to 100 actions by just allowing the agent to take any action in 10x10 grid around it (and using a low-level controller to go to any cell). The state space used for planning is discretized but the agent moves in a continuous state space in the Habitat simulator. We compute the continuous ground truth distance using Fast Marching Method (instead of Dijkstra) for training with a larger action space, which allows axis-aligned actions and distances.
accurately compute distance for all locations and not be constrained by
SPT and the baselines trained only on synthetic navigation mazes for this experiment. During evaluation, we assume perfect map based on part of the environment seen in the observations so far for planning. the overall map size at this level of discretization is higher than planning map size, we simply use greedy planning in window around the agent resulting in an "anytime" variant just like the classical RRT algorithms. This setup results much finer- seerggraiedd action space as shown in the demo example here SPT achieve navigation success rate of 78.0% as compared to 47.2% for GPPN and 43.5% for VIN basclines.
E ATTENTION VISUALIZATION
We show the visualization attention map corresponding to two different locations Figure Interestingly, noticed three consistent patterns: a) least of the attention head out of eight captures obstacles (left), b) one of the attention heads focuses on goal location (middle), and c) some attention maps focus nearby obstacles get accurate planning distance (right).
Attention weights three outbut (10,4) A-1 à
Input map goal [X] f
Attention heads (h) (6,10)
A 2
h -
Figure 8: Attention Visualization. Visualization of the attention heads Icarned by Spatial Planning Transform- SPTs learn an attention for each location the map with respect every other location.
F EXAMPLES
We show additional examples for navigation task for in-distribution test set (in Figure 9), out-of- distribution More Obstacles test set (in Figure 10) and Real-World test set (in Figure 11) each with map size 30. Additional examples for manipulation task are shown for in-distribution test set (in Figure 12) and for out-of-distributia More Obstacles test set (in Figure 13).
We also visualize examples for the end-to-ent mapping and planning experiments for the manipulation task. We show examples of map and action distance predictions using the SPT model trained with dense and perfect supervision Figure 14 and with noisy and sparse supervision in Figure 15.
'https://youta" be/ 2NHthb3t7AN
14

---

Under review as a conference paper at ICLR 2021
Input Map and Goal
VIN
GPPN
SPT
Ground Truth
Figure 9: Navigation in-distribution test set examples. Figure showing 3 examples of the input, the predic- tions using the proposed SPT model and the baselines, and the ground truth for the Navigation in-distribution set for map size M 30.
Input Map and Goal
VIN
GPPN
SPT
Ground Truth
Figure 10: Navigation out-of-distribution More Obstacles test set examples. Figure showing examples of the input, the predictions using the proposed SPT model and the baselines, and the ground truth for the Navigation out-of-distribution More Obstacles test set for map size M = 30.
15

---

Under review as a conference paper at ICLR 2021
Input Map and Goal
VIN
SPT
Ground Truth
Figure Navigation out-of-distribution Real-World set examples. Figure showing examples of the input, the predictions using the proposed SPT model and the baselines, and the ground truth for the Navigation out-of-distibbtiin test set for map size M 30.
Input Map and Goal
VIN
GPPN
SPT
Ground Truth
Figure 12: Manipulation in-distribution test set examples. Figure showing 3 examples of the input, the predictions using the proposed SPT model and the baselines, and the ground truth for the Manipulation in- distribution set for map size 36.
16

---

Under review as a conference paper at ICLR 2021
Input Map and Goal
VIN
GPPN
SPT
Ground Truth
MANZA
More Obstacles test set examples. Figure showing examples of the input, the predictions using the proposed SPT model and the baselines, and the ground truth for the Manipulation out-of-distribution More Obstacles test set for map size M 36.
Figure 13: Manipulation
Observation
Predicted Map
GT Map
Predicted Distance
GT Distance
Figure 14: Dense and Perfect Supervision. Figure showing examples of map and distance predictions using the SPT model trained with dense and perfect action-level supervision.
17

---

Under review as a conference paper at ICLR 2021
Observation
Predicted Map
GT Map
Predicted Distance
GT Distance
Figure 15: Sparse and Noisy Supervision. Figure showing examples of map and distance predictions using the SPT model trained with sparse and noisy action-level supervision.
18


Reviews:
[{"review_id": "_vKPJUUXHXs", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\nThis paper presents Spatial Planning Transformers (SPTs); neural network modules that perform spatial planning over grid-like state spaces. The paper also goes on to present the idea that differentiable mapping and differntiable planning modules could be trained end-to-end, for better performance. This is evaluated against two baselines (value iteration networks (VINs) and generative path planning networks (GPPNs)) on small-scale navigation and manipulation tasks.\n\n\n## Strengths\n\n**S1** The central idea presented in this paper is quite interesting. Re-formulating the planning problem as learning an attention operator over an input map is both interesting, and challenging. The approach does have a strong motivation, considering the impact transformers have had in language processing. SPTs seek to replace memory-based models, such as LSTMs with purely attention-based models such as transformers, to potentially capture long-range dependencies.\n\n**S2** The paper presents a promising idea in attempting to integrate differentiable mapping modules with differentiable planners. This could instigate further work on the lines of what kind of inductive biases are fruitful to have in neural planners.\n\n**S3** The paper was very-well written and easy to follow.\n\n\n## Weaknesses\n\nI do find several aspects of the paper can be improved, and I list my most important observations here. I look forward to the author response, and am open to changing my evaluation if the concerns are adequately addressed.\n\n**W1** Discrete action spaces: It seems like the proposed approach is tailored to discrete state-spaces or maps (and perhaps to discrete actions)? It could be interesting to know whether the approach scales to continuous state and/or action spaces. Upfront, it seems dubious, as it is unclear how the transformer blocks might apply to continuous maps.\n\n**W2** Scalability issues: The assumption of a grid-like partitioning indicates that SPTs may exhibit unfavourable scaling properties? For instance, if one were to move from a 2D (planar) space to 3D, this seems like it will dramatically increase planning complexity. (While this can also be argued for \"classical\" planners like RRT, they often are accompanied by an exploration-exploitation tradeoff that lends them an anytime flavour)\n\n**W3** Better placement wrt diff planning literature: I believe that SPTs can be better placed with respect to current literature on differentiable planning. For instance a few interesting approaches in this space include references [A-J]. Some of these [F, G, J] could be construed as concurrent work (but may be worth citing in a camera-ready version, for example). It would be a great addition to incorporate interesting new work in the robotics community on neural and/or differentiable planning [H, J]. It may also be worth using some of these approaches as baselines for evaluation.\n\n**W4** More baselines: The current draft seems to only use VINs and GPPNs as baseline planning approaches. The presented method will seem better-placed in the context of other recent contributions if more baselines were to be introduced. For instance, universal planning networks, motion planning networks, semi-parameteric topological memory are all relevant baselines for navigation and/or manipulation.\n\n**W5** In trying to present two important ideas (SPTs, diff mapping + planning), the current manuscript appears to lack a thorough study of neither. For instance, are there various combinations of differentiable mapping and planning strategies that can be evaluated? One would also have expected an evaluating against non-differentiable mapping + planning (i.e., \"classical\" robotics) strategies to strengthen this claim.\n\n\n## Summary\n\nIn summary, while the paper presents a very interesting idea, there are several questions to be asked of the experimental demonstrations of the idea. This could benifit from a revision, and I strongly encourage the authors to address some of the issues raised above.\n\n\n## References\n\n[A] Learning to Plan in High Dimensions via Neural Exploration-Exploitation Trees - arXiv 2019\n\n[B] Learning to search with MCTSnets - ICML 2018\n\n[C] TreeQN and ATreeC: Differentiable Tree-Structured Models for Deep Reinforcement Learning - ICLR 2018\n\n[D] Memory augmented control networks - ICLR 2018\n\n[E] Learning to Plan in High Dimensions via Neural Exploration-Exploitation Trees - arXiv 2019\n\n[F] Neural Enhanced Belief Propagation on Factor Graphs - arXiv 2020\n\n[G] Neural Manipulation Planning on Constraint Manifolds - arXiv 2020\n\n[H] Learning sampling distributions for robot motion planning - ICRA 2018\n\n[I] Semi-parametric topological memory for navigation - ICLR 2018\n\n[J] Graph neural networks for motion planning - arXiv 2020\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "J0wH2wfUnT2", "reviewer": "AnonReviewer3", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\nSummary:\n \nThe paper provides an interesting direction in the field of spatial path planning. The method is interesting as it is fully learnt in an end to end fashion. The key idea is to use a transformer like architecture to model long range dependencies. Also the paper extend its findings to out of distribution maps and  the cases where the ground truth map is not known to the agent. \n\n##########################################################################\n\nReasons for score: \n \nOverall, I think the paper is slightly below the acceptance threshold. The motivations and the architecture are clearly presented, but I think there is a lack of clarity in the way the methods and the results are presented, especially in the most interesting section, the one about the mapper. Also the analysis are limited to reconstructions of the map and some attention weights in the appendix. \n\n##########################################################################\n\nPros: \n \n1. Interesting new approach with potential applications in both navigations and manipulations task.\n2. The out of distribution results are convincing.\n\nCons:\n\n1.  Although the method is a clear advantage over previous ones it still requires to know the ground truth distance to get the map. \n\n2. Instead of using a paragraph to explain the transformer architecture, which is relatively well know, my suggestion would be clarifying the mapper section with more notation to clearly state the loss. This would already help to most likely increase my score.\n\n3. In section 3.2 the authors claim that “While it is possible to train a separate mapper model to predict maps from observations, this requires map annotations which are expensive to obtain and often inaccurate”. I don’t think this is true: e.g. Gregor K. et al., 2019 ->  https://arxiv.org/pdf/1906.09237.pdf present an example of how a map can be learnt.\n\n4. It is not clear how much the model relies on having perfect distances as supervision vs. noisy ones. An analysis on this topic I think would be important.\n\n5. No Analysis of computational complexity\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "6SgACq6B9np", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 4, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes a method to infer goal distance maps for use in path planning using transformer networks. These 2D distance maps are evaluated on both planning and combined mapping and planning experiments on synthetic data.\n\nWhile the proposed method seems technically sound and based on the experiments works as intended, it is not clear how the proposed system would be applicable in practice. Additionally, the motivations for the proposed approach over classical planning methods, such as run-time and incomplete environments, were not explored.\n\nFrom a machine learning point of view, there is nothing particularly novel about the proposed method which uses well known and existing methods to build the planning framework. This is not a negative point for methods which develop interesting algorithms for applications. However, in the case of this paper, there are many questions regarding the applicability of the resulting system.\nThe proposed method produces a distance to goal map based on an obstacle representation. While such a distance map can be used with search methods to find a path, it does not constitute a path planning method itself. Furthermore, the proposed method is by design limited to 2D spaces. While this to some extent might be justifiable for ground-based robots, it precludes the use of the approach in challenging outdoor environments or on flying robots. More importantly, this reduces the applicability this method has in manipulation severely as the vast majority of manipulators used these days have six or seven degrees of freedom. These limitations are furthermore exaggerated by the very coarse environment discretization used in the examples of 0.25 cm or 10 degrees. While 0.25 cm grid sizes for navigation can be acceptable in large outdoor environments, the 10 degree discretization used would be unsuitable for most manipulation tasks.\n\nOne of the motivations given by the paper for the development of an end to end learning framework is the computational efficiency of having to only perform a single forward pass over the input. This, in theory, enables fast recomputation of a solution should the environment change. Given the 2D grid structure of the input and outputs, one would expect a comparison to widely used search methods such as A* and R*. These methods would be very fast to compute on the problem setups used in the experiments while being provably optimal. Providing a run-time comparison against such methods would have been good to see. Similarly, comparisons to RRT based methods, which in the limit are also provably optimal, would be appreciated.\nWhile the combination of planning and mapping was interesting, it is not clear why this was needed, as methods capable of accurately mapping large scale environments exist without relying on learning systems. As the focus of the paper was on planning, this also caused some confusion on their relation.\n\nOverall, while the proposed method works, it is not clear what practical benefit it has. As a deep learning approach, it requires a significant amount of training and has no guarantees to provide predictable results at all times. This is in stark contrast with decade-old methods such as A*, RRT*, and trajectory optimization which have such guarantees. The major limitation of the proposed method to 2D spaces severely limits its applicability with questions regarding scalability given the sizes used in the experimental section.\n\n\n=== Post rebuttal ===\n\nThe inclusion of runtime comparisons with search based methods is a welcome addition, as it showcases that the method provides an interesting avenue to utilize GPUs for this kind of search task. Effectively trading up-front training time for deployment computational time. However, the question regarding the ability to handle larger state spaces is only touched on in the appendix and it is not clear from that description what the state space was. If the proposed approach works for planning in 6D environments or control of 7DoF manipulators then this is very interesting and should not be hidden away, so to speak, in the appendix but be highlighted in the main paper and showcased.\n\nIn light of the considerable amount of work that has been put into the revision I changed my score from 3 to 4. While I could see improvements and clarifications I could not see the main concern I had, handling of high dimensional problems, being addressed.", "extra_scores": {}, "extra_text": {}}, {"review_id": "-imnRSc--9x", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper correctly identifies some of the shortcomings of classical planning methods. The idea to use a transformer for planning seems promising and that is backed up by experimental results where the method outperforms previous work. I think the paper has some interesting ideas and the experimental section seems promising, but some assumptions are not stated clearly enough (I will discuss specific points under \"Cons\"). I recommend accepting the paper on the basis that the ideas presented are relevant to the community.\n\n### Pros\n\n* To the best of my knowledge, this is the first paper to propose combining transformers with neural planning in the style of value iteration networks.\n* The paper deals with both robotic manipulation and navigation in the same framework. It is nice to see these related problems being tackled jointly.\n* The method has an explicit component for creating maps, which is generally omitted in the framework of value iteration networks and their derivatives.\n* The experimental results clearly demonstrate an edge over other VIN-type approaches.\n\n### Cons\n\n* The section on the mapper makes it sound like it maps one observation to an entire map, though in almost all cases, one observation won't be enough to do so. No mechanism for aggregating observations over time is described. The only way I can see this working is if the method gets an exhaustive dictionary of images from many locations and orientations in the environment, such as the 3D experiments by [Lee et al.](https://arxiv.org/pdf/1806.06408.pdf) The experiments section also gives this impression. This does not invalidate the approach but I would like this to be stated more clearly and earlier on in the text.\n\n* The end-to-end module is trained using action-distance labels. This is basically assuming we have access to shortest-distance labels or a full value function. I don't understand how this is preferable to assuming we have full knowledge of the obstacles, which the paper seems to imply by saying:\n\n  > This essentially allows us to train a mapping module without any map-level supervision using a pretrained planner and action-level supervision.\n\n  My issue here is that I don't understand how we could get exhaustive shortest-distance labels without having access to an occupancy map or a list of obstacles. It's fine to assume we have access to such things during training, I just want this to be stated clearly.\n\n* Some metric that is a direct measure of navigation success would be beneficial (e.g. percentage of successful attempts or [success-path-length](https://arxiv.org/pdf/1807.06757.pdf)). The action-prediction-accuracy is a proxy to this but one can imagine situations where a model can still have high navigation success while taking sub-optimal actions some of the time.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes to jointly learn a mapper and planner for navigation or manipulation in a 2D space represented by an MxM grid, with the mapper taking raw observations as inputs and producing a 2D MxM occupancy and goal location map, and the planner -- pretrained on generic 2D maps of same size MxM -- produces an MxM action distance image (the plan). The whole system is trained end-to-end, with the mapper trained on the specific navigation or manipulation task, and the planner frozen. The Spatial Planning Transformer network can predict the MxM action plans faster than baselines (Value Iteration Networks and Gated Path Planning Networks) because of the attention mechanism in the transformer architecture, as opposed to the local information propagation through the convolutional encoding of the Bellman equation in VIN or GPPN. The differentiable approach is motivated by exploiting regularities in 2D maps and a faster inference time (as opposed to classical Dijkstra planners or VIN / GPPN), and is demonstrated on a simple room navigation task in the Gibson environment.

Reviewers have praised how a simple idea (transformer-based planning à la VIN) can be applied as a unifying approach to 2 DOF manipulation and 2D navigation, and the out-of-sample evaluation. The critique was about:
* the lacunary explanation of the mapper (corrected by the authors),
* the limits of non-recurrent mappers that cannot handle occlusions in the observations when building maps,
* confusion about where the full MxM image of action labels (necessary for supervision) can come from (the authors added experiments with sparse labels),
* claims about this approach being preferable to A* (countered by the authors, who conducted extensive experiments at the request of R4),
* focus on two problems at once (mapping and planning) rather than more ablation analysis of the planner, with a potential comparison to Active Neural SLAM,
* missing evaluation using navigation-specific metrics, such as SPL.

The authors have a point in their defense of differentiable / learning-based methods for planning (including VIN and GPPN) as opposed to classical planning such as A*, and there is value in investigating how an end-to-end differentiable method for mapping and planning could be designed. At the same time, several reviewers raised concerns about scalability and about the pertinence of combining two learnable modules (mapper and planner) rather than investigating and demonstrating the advantage of transformers for planning.

Given these reviews, rebuttal, and remaining concerns, I am sorry to reject this paper. I hope that with the proposed modifications it will be quickly accepted at another venue.
Decision: Reject