Learning to Plan in High Dimensions via Neural Exploration-Exploitation Trees
Authors: Binghong Chen
Bo Dai
Qinjie Lin
Guo Ye
Han Liu
Le Song
Venue:  (2020)
Keywords: learning to plan
representation learning
learning to design algorithm
reinforcement learning
meta learning

Abstract: We propose a meta path planning algorithm named \emph{Neural Exploration-Exploitation Trees~(NEXT)} for learning from prior experience for solving new path planning problems in high dimensional continuous state and action spaces. Compared to more classical sampling-based methods like RRT, our approach achieves much better sample efficiency in  high-dimensions and can benefit from prior experience of planning in similar environments. More specifically, NEXT exploits a novel neural architecture which can learn promising search directions from problem structures. The learned prior is then integrated into a UCB-type algorithm to achieve an online balance between \emph{exploration} and \emph{exploitation} when solving a new problem. We conduct thorough experiments to show that NEXT accomplishes new planning problems with more compact search trees and significantly outperforms state-of-the-art methods on several benchmarks.

Published as a conference paper at ICLR 2020
LEARNING TO PLAN IN HIGH DIMENSIONS VIA NEURAL SETLLORATIONEXPPOOTIE
TREES
"Binghong Chen', "Bo Dai Qinjie Lin?, Guo Ye①, Han Liu?, Le Song!
1 Georrga Institute of Technology Gooole Research, Brain Team
Northhweseern University Ant Financial
ABSTRACT
We propose a meta path planning algorithm named Neural Trees (NEXT) for learning from prior experience for solving new path planning problems in high dimensional continuous state and action spaces. Compared to more classical sampling- based methods like RRT. our approach achieves much better sample efficiency in high-dimensions and can benefit from prior experience of planning in similar envi- ronments. More specifically, NEXT exploits novel neural architecture which can learn promising search directions from problem structures. The learned prior is then integrated into a UCB-type algorithm to achieve an online balance between exploration and exploita- tion when solving a new problem. We conduct thorough experiments to show that NEXT accomplishes new planning problems with more compact search trees and significantly outperforms state-of the-art art methods several benchmarks.
INTRODUCTION
Path planning is a fundamental problem with many real-world applications, such as robot manipulation and autonomous driving. A simple planning problem within low-dimensional state space can be solved by first discretizing the continuous state space into a grid, and then searching for a path on top of it using graph search algorithms such as A (Hart et al. 1968). However, due to the curse of dimensionality, these approaches do not scale well with the number of dimensions of the state space. For high-dimensional planning problems, people often resort to sampling-bai based approaches avoid explicit discretization. Sampling-basee roadmaps (PRM) (Kavraki et al. 1996), rapidly-exppe rapidly-exploring random trees (RRT) Valle 1998). and their variants (Karaman & Frazzoli 2011) incrementally build an implicit representation of the state space using probing samples. These generic algorithms typically employ uniform sampler which does not make use of the structures of the problem. Therefore they may require lots of samples to obtain feasible solution for complicated problems. To improve the sample efficiency. heuristic biased samplers, such as Gaussian sampler (Boor et al., 1999). bridge test (Hsu et al. a (003) and reachability -uided sampler (Shkolnik et al. 2009) have been proposed. All these sampling heuristics are designed manually to address specific structural properties, which may or may not be valid for a new problem, and may lead to even worse performance compared to the uniform proposal.
planning algorithms, such probabilistic
Online adaptation in path planning has also been investigated for improving sample efficiency in current planning problem. Specifically,, Hsu et al. (2005) exploits online algorithms to dynamically adapts the mixture weights of several manually designed biased samplers. Burns& & Brock (2005a b) fit model for the planning environment incrementally and use the model for planning. Yee al. (0016) mimics the Monte-Carlos tree search (MCTS) for problems with continuous state and action spaces. These algorithms treat each planning problem independently, and the collected data from previous experiences and built model will be simply discarded when solving a new problem. However, in practice, similar planning problems may be solved again and again, where the problems are different but sharing common structures. For instance, grabbing a coffee cup on a table at different time are different problems, since the layout of paper and pens, the position and orientation of coffee cups may be different every time; however, all these problems show common structures of handling similar objects which are placed in similar fashions. Intuitively, if the common characteristics across problems can be learned via some shared latent representation, planner based on such representation can then be transferred to new problems with improved sample efficiency.
indicates equal contribution.

---

Published as a conference paper at ICLR 2020
Several methods have been proposed recently to learn from past planning experiences to conduct more efficient and generalizable planning for future problems. These works are limited in one way or the other. Zucker et al.] (2008); Zhang et al. (0118; Huh & Lee (2018) treat the sampler in the sampling-basee planner as a stochastic policy to be learned and apply policy gradient or TDDallorrihm to improve the policy. policy.FFinney Ichter et al. (2018); Kim et al.J (2018) 8): Kuo et al. (2018) apply imitation learning based on the collected demonstrations to bias for better sampler via variants of probabilistic models, e.g., (mixture of) Gaussians, conditional VAE, GAN, HMM and RNN. However, many of these approaches either rely on specially designed local features or assume the problems are indexed by special parameters, which limits the generalization ability. Deep representation learning provides a promising direction to extract the common structure among the planning problems, and thus mitigate such limitation on hand- designed features. However, existing work, e.g., motion planning networks (Qureshi et al., 2019). value iteration networks (VIN) (Tamar et al. 2016), and gated path planning networks (GPPN) (Lee et al., 2018), either apply off-the-sheli MLP architecture ignoring special structures in planning problems or can only deal with discrete state and action spaces in low-dimensional settings.
al. (2007); [Bowen& & Alterovitz (2014); Ye & Alterovitz (2017);
In this paper, we present Neural AnaloraatoonEEploittaainn Tree (NEXT), meta neural path plan- ning algorithm for high- dimensional continuous state space problems. The core contribution is a novel attention-based neural architecture that is capable of learning generalizable problem struc- tures from previous experiences and produce promising search directions with automatic online exploration-explotatoon balance adaption. Compared existing learning- planners,
NEXT is more generic. We propose an architecture that can embed high dimensional continuous state spaces into low dimensional discrete spaces, on which a neural planning module is used to extract planning representation. These module will be learned end-to-end.
NEXT balances exploration-exploitation trade-off. We integrate the learned neural prior into an upper confidence bound (UCB) style algorithm to achieve an online balance between exploration and exploitation when solving a new problem.
Empirically, show that NEXT can exploit past experiences to reduce the number of required samples drastically for solving new planning problems, and significantly outperforms previous state-of-the- thrtss several benchmark tasks.
1.1 RELATED WORKS
Designing non-uniform sampling strategies for random search to improve the planning efficiency has been considered as we discussed above. Besides the mentioned algorithms, there are other works along this line, including informed RRT* (Gammell et al. 2014) and batch informed Trees (BIT*) Gammell et al. 2015) as the representative work. Randomized A" (Diankov & Kuffner 2007) and sampling-bass baasee A (Persson & Sharf 2014) expand the search tree with hand-designed heuristics. These methods incorporate the human prior knowledge via hard-coded rules, which is fixed and unable to adapt to problems, and thus, may not universally applicable. Choudhury et al.] (2018) (ong et al. (2018) attempt to learn search heuristics. However, both methods are restricted to planning on discrete domains. Meanwhile, the latter one always employs an unnecessary hierarchical structure for path planning, which leads to inferior sample efficiency and extra computation.
The online iiploration-explottaaii Rickert et al.] (2009) constructs a potential field sampler and tuned the sampler variance based on collision rate for the trade-off heuristically. Paxton et al. (2017) separates the action space into high-level discrete options and low-level continuous actions, and only considered the trade-off at the discrete option level, ignoring the works address the trade-off in an ad-hoc way, which may be inferior for the balance.
trade-off is also an important issue in planning. For instance,
in the fine action space. These existing
There have been sevearl non lonn-eernning-bere based planning methods that can also leverage experi- ences (Kavraki et al.) 1996] Phillips et al.] (012) by utilizing search graphs created in previous problems. However, they are designed for largely fixed obstacles and cannot be generalized to unseen tasks from the same planning problems distribution.
2 SETTINGS FOR LEARNING TO PLAN
Let S C Rd be the state space of the problem, e.g., all the configurations of a robot and its base location in the workspace, Sabe C S be the obstacles set, Sfree S Sobs be the free space, Sinit. E Stree be the initial state and Syoat Ç (Strec be the goal region. Then the space of all collision- free paths can be defined as continuous function = = (c()) [0. 1] + Syree) Let e (-) E + IR.
2

---

Published as a conference paper at ICLR 2020
be the cost functional over path. The optimal path planning problem is to find the optimal path in terms of cost c(-) from start Synit to goal Soaat in free space Stree i.e.,
argmingez C (E) : s.t. {(0) = Sinit: {(1) E SSoall
(I)
Traditionally (Karaman & Frazzoli
2011), the planner has direct access to (Sinét; Soont C c()) and the
workspace map (Ichter et al. 2018 Tamar al. 2016 Lee al. 2018), map(.) IR or E {0, 1}.
(0: free spaces and I: obstacles). Since Free often has a very irregular geometry (illustrated in Figure i0 in Appendix A is usually represented via collision detection module which is able to detect the obstacles in path segment. For the same reason, the feasible paths in E are hard to be described in parametric forms, and thus, the nonparametrie ç, such as sequence of intereonnected
path segments (so, $1), (81, 82), (sT-1, ST] C S with {(0) 80
Sinit and {(1) = 8T, is used
with an additive cost Σ c ([)=
Assuming given the planning problems {U; := (Ssmit: Sgaat, S, free, map, c (-)) 1=1 sampled from some distribution U, we are interested in learning algorithm alg (-), which can produce the (nearly)-opp -optimll path efficiently from the observed planning problems. Formally, the learning to plan defined as
alg" (-) argminaige. Eveu [e (alg(U)),,
(2)
where A denotes the planning algorithm family, and e (-) denotes some loss function which evaluates the quality of the generated path and the efficiency of the alg (-), e.g., size of the search tree. We elab- orate each component in Eq (2) in the following sections. We first introduce the tree-based sampling algorithm template in Section 3 upon which we instantiate the alg (-) via novel attention- balance mechanism in Section [ We design the ê-loss function and the meta learning algorithm in Section 4.3 Composing every
neural parametrization in Section 4.2 with ppploration-xploiitaee
component together, we obtain the neural exploration-exploiaaioo trees (NEXT) which achieves
outstanding performances in Section
5
Repeat
New Task
Select
Expand
d Upciate
Goal
Goal
max V+U
m
Start
sell-improe
max V+U
Start
Start
Start
Start
Start
Start
Start
max V+U
Goal
Goal
Goal
Goal
seff-mprove
Tt (s)
Figure I: Illustration of NEXT. In each epoch, NEXT executed on randomly generated planning problem.
The search tree grows with V and #* guidanee. (V', #²) will be updated according to the successful path. Such planning and learning iteration is continued interactively.
Algorithm 1: bree-based Sampling Algorithm
3 PRELIMINARIES
Problem:
The sampling-basee based planners are more practi-
U = (Simit, Syout: S, Stree, map, e(-)); Initialize T (V,E) with V x- {sinst).
cal and become dominant for high-dimensional path planning problems (Elbanhawi & Simie 2014). We describe unifying view for many existing tree- based sampling algorithms (TSA),
E 0:
for 1 +- 0 to do
Sparent, Snew +- Expand (T, U) Obstacleeee (8 (Sparent: Snew) then V VU (Snew) and E + E+EU Spprent: Snewl] 1): T Postprocess (T, U)
which we will also base our algorithm upon. More specifically, this family of algorithms maintain a search tree T rooted at the initial point Sinit and connecting all sampled points V in the configuration space with edge set The tree will be expanded by incorporating more sampled states until some leaf reaches Syoat- Then, feasible solution for the path planning
D Optional
Snew Sgeal then return T;
3

---

Published as a conference paper at ICLR 2020
problem will be extracted based on the tree T. The template of tree-based sampling algorithms is summarized in Algorithm [ and illustrated in Fig. [c.. A key component of the algorithm is the Expand operator, which generates the next exploration point 8aew and its parent Sporent V. To ensure the feasibility of the solution, the Snew must be reachable from T, i.e., [Sparent, 8new is collision-free, which is checked by collision detection function. As we will discuss in Appendix B by instantiating different Expand operators, we will arrive at many existing algorithms, such as RRT (La Valle 1998) and EST (Hsu al. 1997 Phillips et al. 2004).
One major limitation of existing TSAs is that they solve each problem independently from scratch and ignore past planning experiences in similar environments. We introduce the neural components into TSA template to form the learnable planning algorithm family A. which can explicitly take advantages of the past successful experiences to bias the Expand towards more promising regions.
NEURAL EXPLORATION EENORRATTON-EXPLOTAATTOOO TREES
Based on the TSA framework, we introduce a learnable neural based Expand operator, which can balance between exploration and exploitation, to instantiate A in Eq 2 With the self-improving
training, we obtain the meta NEXT algorithm illustrated in Figure 1
4.1 GUIDED PROGRESSIVE EXPANSION
We start with our design of the Expand. We assume having an estimated value
Algorithm 2: NEXT :: Expand = (V)
function (s(UU,, which stands for the 1 -pprent <- argmax,gv ((s):
> Selection
optimal cost from s to target in plan- 2 {s1,...,,8h) 8 ~ (s'( [ss'|sparentt U)
rtd.
D Candidates
ning problem U, and a policy #* (s' [s. U), 3 Snew f- arggax./E(ss...... ((s'); Expansion
which generates the promising action 4 return Sparent; Snews
from state s. The concrete parametriza-
tion of V and #* will be explained in Section 4.2 and learned in Section 4.3 We will these
functions to construct the learnable Expand with explicit exploration-exploiaaiio balancing.
The Expand operator will expand the current search tree T by new neighboring state Snew around T. We design the expansion as a two-step procedure: (i) select a state Sparent from existing tree T;
(ii) expand a state Snew in the neighborhood of Sporent. More specifically,
Selecting Sparent from T in step (i). Consider the negative value function - V (s(U) as the rewards r (s), step (i) shares some similarity with the multi-armed bandit problem by viewing existing nodes 8 E as arms. However, the vanilla UCB algorithm is not directly applicable, since the number of states is increasing the algorithm proceeds and the value of these adjacent states are naturally correlated. We address this challenge by modeling the correlation explicitly as in contextual bandits. Specifically, parametrize the UCB of the reward function as & (s), and select node from T according to ((s)
(3) where F. and or denote the average reward and variance estimator after t-calls to Expand. Denote the sequence of t selected tree nodes so far as St = {8) pprrene:.... o s. then we can use kernel
Sparent = argmax,ev d(s) : Fr (s) + Ao, (s).
smoothing estimator for Fr(s) = Eves, ((d')))(())) and (r(s)) log Eves, w(s') where k(s', s) Eveo, M(s',a) is kernel function and w(ss) = =EvES, s(5 Other parametrizations of Fz and o, are also possible, such as Gaussian Process parametrization in Appendix C The average reward exploits more promising states, while the variance promotes exploration towards less frequently visited states; and the exploration versus exploitation is balanced by a tunable weight À > 0.
w(s)
Expanding a reachable Snew in step (ii). Given the selected Sporent. we consider expanding a reachable state the neighborhood Syarent as an infinite-armed bandit problem. Although one can first samples i arms uniformly from a neighborhood around Sparent and runs a UCB algorithm on the randomly generated finite arms (Wang et al., 22009), such uniform sampler ignores problem structures, and will lead to unnecessary samples. Instead we will employ a policy #* (s'|s, U for guidance when generating the candidates. The final choice for next move will be selected from these candidates with max ò (s) defined in As explained in more details in Section 4.2 n² will be
In the path planning setting, we use #* (s' (s, U) and #* (als, U) interchangeably the action is state.
4

---

Published as a conference paper at ICLR 2020
Figure 2: Our neural network model maps a N N-link robot from the original planning space (a (N + 2)-d configuration space) to a 3d discrete latent planning space in which we plan path using value iteration. The result of value iteration then used as features for defining V (s(U)
n(3) R
(x,y,,, 0art,, (0,) gM+2
(( e
(d|ssU),
Otiginal Planning Space
Latant Planning Space
trained to mimic previous successful planning experiences across different problems, that is, biasing the sampling towards the states with higher successful probability.
With these detailed step (i) and (ii), we obtain NEXT :: Expand in Algorithm 2 (illustrated in Fig- ure lb) and (c)). Plugging it into the TSA in 1 construct alg (-) A which will be learned.
The guided progressive expansion bears similarity to MCTS but deals with high dimensional continu- ous spaces. Moreover, the essential difference lies in the way to select state in T for expansion: the MCTS only expands the leaf states in due to the hierarchical assumption, limiting the exploration ability and incurring extra unnecessary UCB sampling for internal traversal in T; while the proposed operation enables expansion from each visited state, particularly suitable for path planning problems.
4.2 NEURAL ARCHITECTURE FOR VALUE FUNCTION AND EXPANSION POLICY
In this section, we will introduce our neural architectures for V Us) and म* (s'|s, ([s.U) U) used in NEXT :: Expand. The proposed neural architectures can be understood as first embedding the state and problem into discrete latent representation via an attention- -based module in Section 4.2. upon which the neuralized value iteration, introduced in Section 4.2.2 is performed extract features for defining V (s(U) and #* (s'[s, U), as illustrated in Figure
4.2.1 CONFIGURATION SPACE EMBEDDING
Our network for embedding high- high-dimension configuration space into a latent representation is designed based
attention mechanism. More specifically, let 8 denote the workspace in state and S denote the remaining dimensions the state, i.e. 8 = (8" sh). s" and s will be embedded by different sub-neural networks and combined for the final representation, as illustrated in Figure For simplicity of exposition, we will focus on the 2d workspace, i.e., s E IR2. However, our method applies 3d workspace well.
Spatial Attention: (d, d.
Stack
(I.coovv relu)<k.,
0
0.1
D
9
2
Coordinate
Cocrdirate
0.]
0.9
(dense, relu) kp
state
Element-wise Product
Config Attention: (,,)
Full Attention: (d.d. d.
Figure 3: Attention-bass based state embedding module. s" = (xx, y) and i = S. The upper part is spatial attention, with the first two channels being and and the last two channels being constant templates with the row and column coordinates, shown with set to 3. The bottom module leams the representation for The final embedding is obtained by outcr-product of these attention parts.
The workspace information " will be embedded as ps"(s") gexd i hyperparameter related to map (see remark below). The spatial embedding module (upper part in Figure 3) composed k. convolution layers, i.e., fw (s") = relu(0,) ① (s")))
Spatial attention.
f (s") = sof softmaxd (fF, (s))),
(4)
where 0 denotes the convolution kernels, @ denotes the convolution operator and f("(")) E ddx with d, channels. The first layer fi" is designed to represent s" into d x x 4 tensor as fod (s""); s 88 "2,jj, i,j 1,...,dl without any loss of information.
5

---

Published as a conference paper at ICLR 2020
Repeat Ttimes
Map: (d.d) Goal state:
Goad Attention
Cone (0)
Attention Module
Planning Module
it
State st (s)
(*(s)) # (s'1(()(s)))
Atlention
(sss)
Module
Sum over dins dimensions
Figure 4: Overall model architecture. Current and goal states are embedded through attention module. Then the embedding of the goal state concatenated with the map produce =²(0) and R the input to the planning module. The output the planning module is aggregated with the embedding the current state to produce feature (s) for defining V and R"
Configuration attention.
The remaining configuration state information will be embedded as (s")) through kn fully-connected layers (bottom-left part in Figure 3) i.e.
1t (s") = softmax (Ah, (s))), where yh (sh)) Rdda and (s*) =
f (1 = relu (0) (. bz).
The final representation (s(() will be obtained by multiplying n² (s") with (s"))) element-wisely, ( = (s")) (*"")), which is d x d x da tensor attention map with pa(s) > O, and Enji Me (s) (bottom-right part in Figure 3). Intuitively, one can think dg as the level of the learned discretization of the configuration space s and the entries in μ softly assign the actual state to these discretized locations. 0 :- (10.") Ji 100h be b.) are the parameters to be learned.
k.. -1
Remark (different map size): To process map using convolution neural networks, we resize it to x d image, with the same size as the spatial attention in Eq (4, where is a hyperparameter.
4.2.2 NEURAL VALUE ITERATION
We then apply neuralized value iteration on top of the configuration space embedding to extract further planning features (Tammr et al. (016)] Lee et al., (018)). Specifically, we first produce the embedding (4(00) of the center of the goal region &yoot. We execute steps of neuralized Bellman updates (planning module in Figure 4 in the embedding space,
(() min ( + (t-(-1) R RR). with (v^(0) R) (Wo + [uo ( mapl),
and obtain (T) E dxdxxxd xp, Both Wo and W1 are 3d convolution kernels, min implements the pooling across channels. Accordingly, (T) now be understood as latent representation of the value function (-) in learned embedding space for the problem U with goont in map.
To define the value function for partieular state 8, i.e., 5= (s]U', from the latent representation =*() we first construct another attention model between the embedding of state s using pa(s) and y/ (T))
i... vi (8) Eeir Vejik (s) for k = 1,....24 Pp. Finally we define
*(2")
(5) where fw, and lw,, are fully connected dense layers with parameters W22 and W3 respectively, and N(hw, (15(s)) o²) is Gaussian distribution with variance o². Note that we also parametrize the policy # (s'(s, U' using the embedding (T), since the policy is connected to the value function argmin,'es e ([s, s')) + V* (s' It should also be emphasized that our parametrization, the calculation of (T) only relies on the μi (Syoat), which can be reused for evaluating 5. (s(U) and 7" (s'|s, U) over different 8, saving computational resources. Using this trick the algorithm runs 10x-100x faster empirically.
Vx (s(U)) hw, (15(5)), and #* (s' (hw,,
via (s'[s,U)
The overall model architecture in alg(.) is illustrated in Figure The parameters W (Wo, Wi, W2, Wa, 0) will be learned together by our meta self-improving learning. For the de- tails of the parameterization and the size of convolution kernels in our implementation, please refer Figure in Appendix D

---

Published as a conference paper at ICLR 2020
4.3 META SELF-IMPROVING LEARNING
The learning of the planner alg (-) reduces to learning the parameters in V (s|U) and म* (5'18, U) and is carried out while planning experiences accumulate. We do not have an explicit training and testing phase separation. Particularly, we use mixture of RRT Expand and NEXT Expand with probability e and e, respectively, inside the TSA framework in Algorithm [ The RRT postprocessing step is used in the template. The c is set to be 1 initially since {V", are not well-trained, and thus, the algorithm behaves like RRT". As the training proceeds, anneal gradually as the sampler becomes more efficient.
The dataset D,,- = U;))= for the n-th training epoch is collected from the previous successful planning experiences across multiple random problems. We fix the size of dataset and update 'D in the same way as experience reply buffer (Lin 1992, (cchaul et al. 2013). For experience (T, U) E Dr. we can reconstruct the successful path {s Ji=1 from the search tree T (m is the number of segments), and the value of each state sf in the path will be the sum of cost to the goal
region, i.e., y¹ = Emee c([s', "I+ We learn {V* == by optimizing objective
min
((V " (T,U)ED,
Σ
ΣΣ D.
log #t (s*+
(s)) + (6)
The loss c pushes the V' and x* to chase the successful trajectories, providing effective guidance in alg (-) for searching, and therefore leading to efficient searching procedure with less sample complexity and better solution. On one hand, the value function and policy esti-
Algorithm 3: Meta Self-Improving Learning
Initialize dataset Do: for epoch t- to N do
Sample a planning problem U:
T < TSA(U) with ~ Uni [0, 1], and
E-RTT :: Expand+ (1-c) :: Expand:
mation {V*, """ } is improved based upon the successful outcomes from NEXT itself on pre-
Postprocessing with
RRT Postprocess:
vious problems. On the other hand, the updated " will be applied in the next epoch to improve the performance. Therefore, the train- ing is named as Meta relf-Improiing Learn- ing (MSIL). Since all the trajectories we col-
Dn, + --Dn-1 U {(T,U)) if successful
else Dn-
for j 0 L do
Sample (Tz.U) from D.:
Reconstruct sub-optimal path {s j== and the cost of paths based on T5; Update parameters
lected for learning are feasible, the reachability of the proposed samples enforced implicitly via imitating these successful paths.
W + W - Vwl(V , TT,
By putting every components together into the learning to plan framework in Eq ( the over- 10
Anneal c = ac, a E (0,1);
all procedure is summarized in Algorithm 3 and illustrated in Figure] [
5 EXPERIMENTS
In this section, we evaluate the proposed NEXT empirically on different planning tasks in a variety of environments. Comparing to the existing planning algorithms, NEXT achieves the state-of -f-the--rt performances, terms of both success rate and the quality of the found solutions. We further demonstrate the power of the proposed two components by the corresponding ablation study. We also include a case study on a real-world robot arm control problem at the end of the section.
5.1 EXPERIMENT SETUP
Benchmark environments. We designed four benchmark tasks to demonstrate the effectiveness of our algorithm for high-dimensional planning. The first three involve planning in a 2d workspace with 2 DoF (degrees of freedom) point robot, 3 DoF stick robot and 5 DoF snake robot, respectively. The last one involves planning a DoF spacecraft in a 3d workspace. For all problems in each benchmark task, the workspace maps were randomly generated from fixed distribution; the initial and goal states were sampled uniformly randomly in the free space; the cost function c-)) was set as the sum of the Euclidean path length and the control effort penalty of rotating the robot joints.
Baselines. We compared NEXT with RRT (Karaman & Frazzoli, 201T), BIT (Gammell et al. 2015), CVAE-plan (Ichter et al. 2018), Reinforce-plan (Zhang et al. 2018), and an improved
7

---

Published as a conference paper at ICLR 2020
H
(a) RRT* (w/o rewiring)
(h) NEXT-KS search tree (c) NEXT-GP search tree (d) learned V and
Figure 5: Search trees and the learned V and #² produced by NEXT. Obstacles are colored in blue. The start and goal locations denoted by orange and brown dots. In (a) (c), samples represented with yellow circles. In (d), the level of redness denotes the value of the cost-to-go estimate V*, The cyan arrows point from a given state to the mean of the learned policy H' (s'1s. U).
(a) NEXT-KS solution path
(b) NEXT- KS search tree
(c) RRT search tree (w/o rewiring)
Figure 6: Search trees and solution path produced in an instance of spacecraft planning. The 7 DOF spacecraft has yellow body and two 2 DOF red arms. NEXT-KS produced nearly minimum viable search tree while RRT failed find path within limited trials.
version of GPPN (Lee et al., 2018) in terms of both planning time and solution quality. RRT and BIT are two widely used effective instances of TSA in Algorithm I In our experiments, equipped RRT with the goal biasing heuristic to improve its performance. BIT adopts the informed search strategy (Gammell et al. 2015) to accelerate planning. CVAE-plan and Reinforce- plan two learning-enhanced TSA planners proposed recently. CVAE-plan learns a conditional VAE as the sampler (Sohn et al.) 2015), which will be trained by near-optimal paths produced by RRT Reinforce-plan learns to do rejection sampling with policy gradient methods. For the improved GPPN, we combined its architecture for map with fully-connected MLP for the rest state, such that it can be applied to high-dimenn nigh-dimensional continuous spaces. Please refer to Appendix E for more details.
Settings. For each task, we randomly generated 3000 differrnt problems from the same distribution without duplicated maps. We trained all learning- based baselines using the first 2000 problems, and reserved the rest for testing. The parameters for RRT* and BIT* are also tuned using the first 2000 problems. For NEXT, we let it improve itself using MSIL over the first 2000 problems. In this period, for every 200 problems, we updated its parameters and annealed e once.
5.2 RESULTS AND ANALYSIS
Comparison results. Examples of all four environments are illustrated in Appendix F.1 and Figure 6 where NEXT finds high-quality solutions as shown. We also illustrated the comparison of the search trees on two 2d and 7d planning tasks between NEXT and RRT* in Figure (a)-(c) and Figure (b) and (c). Obviously, the proposed NEXT algorithm explores with guidance and achieves better quality solutions with fewer samples, while the RRT* expands randomly which may fail to find solution. The learned V and # in the 2d task are also shown in Figure 5 d). As we can see, they are consistent with our expectation, towards the ultimate target in the map. For more search tree comparisons for all four experiments, please check Figure T8
and Appendix F
To systematically evaluate the algorithms, we recorded the cost of time (measured by the number of collision checks used) to find a collision-free path, the success rate within time limits, and the cost of the solution path for each run. The results of the reserved 1000 test problems of each environment are shown in the top row of Figure 7 We set the maximal number of samples as 500 for all algorithms. Both the kernel smoothing (NEXT-KS) and the Gaussian process (NEXT-GPP) version of NEXT achieves the state-of-te oh-the performances, under all three criteria in all test environments. Although the BIT* utilizes the heuristic particularly suitable for 3d maze in 7d task and performs quite well,
8

---

Published as a conference paper at ICLR 2020
NEXT-KS
Dijkstra
GPAN-GP
BIT
CYAE
1.0
2.00
0.8
1.75
Average path cost
Success rete
0.6
3.25
0.4
Avenage
0.75
0.25
20
30
50
70
20
30
5D
70
20
3D
50
70
Experiments
Experiments
Experiments
RRT*-10k
NEXT-GP
0.9
0.8
Average path cast
Success rafe
Average callsion
6-
3.0
2.5
Training phose
Training phase
Training phase
Figure 7: First row: histograms of results, in terms of success rate, average collision checks, and average cost of the solution paths; Second row: NEXT improvement curves in experiments. All algorithms are set to use up to 500 samples, except RRT--10K, which uses 10,000 samples. The value of collision checks and path costs are normalized w.r.t. the performance of RRT
the NEXT algorithm still outperform every competitor by large margin, matter learning- -ased prefixed hcuristic planner, demonstrating the advantages of the proposed NEXT algorithm.
Self-improving. We plot the performance improvement curves of our algorithms the 5d planning task in the bottom row of Figure 7 For comparison, we also plot the performance of RRT". At the beginning phase of self- aiff-imrovinng from previous experiences and improve themselves as they see more problems and better solutions. In the end, NEXT-KS is able match the performance of RRT using only meetteetteth of its samples, while the competitors perform consistently without any improvements.
algorithms are comparable to RRT". They then gradually learn
Due the space limits, we put improvement curves other environments in Figure 17 and the quantitative evaluation in Table 2 and 3 in Appendix Please refer to the details there.
5.3 ABLATION STUDIES
Ablation study guided progressive expansion. To demonstrate the power of NEXT :: Expand, we replace it with breadth-firs search (BFS) (Kim et al. 2018). another expanding strategy, while keeping other components the same. Specifically, BFS uses a search queue in planning. It repeatedly pops a state out from the search queue, samples i states from (-Is), and pushes all generated samples and state s back to the queue, until the goal reached. For fairness, we use the learned sampling policy (s'ls, U) by NEXT-KS in BFS. As shown Figure 7 BFS obtained worse paths with much larger number of collision checks and far lower success rate, which justifies the importance of the balance between exploration versus exploitation achieved by the proposed NEXT :: Expand.
Ablation study I: neural architecture. To further demonstrate the benefits of the proposed neural architecture for learning generalizable representations in high-dimension planning problems, We replaced our attention- based neural architecture with an improved GPPN, as explained in Appendix for ablation study. We extended the GPPN for continuous space by adding an extra reactive policy network to its final layers. We emphasize the original GPPN is not applicable to the tasks in our experiments. Intuitively, the improved GPPN first produces a 'rough plan' by processing the robot's discretized workspace positions. Then the reactive policy network predicts a continuous action from both the workspace feature and the full configuration state the robot. We provide more preference to the improved GPPN by training in the training problems. During test time it is also combined with both versions of the guided progressive expansion operators. As can see, both GPPN-KS and GPPN-GP clearly much
imitate the near-optimal paths produced by RRT*

---

Published as a conference paper at ICLR 2020
MEXT
CWAE
Reinforce
ART
Average path cost
Success rate
05050.401
Time Limit (seconds)
Time Limit (saconds)
Figure 8: The success rate and average path cost of different planners under varying time limits, Running NEXT second achieves the same success rate as running BIT for 50 seconds.
worse than NEXT-KS and NEXT-GP, demonstrating the advantage of our proposed attention-base neural architecture high-dimensional planning tasks.
Ablation study III: learning versus heuristic. The NEXT algorithm in Figure 5 shows similar behavior the Dijkstra heuristic, i.e. sampling on the shortest path connecting the start and the goal in workspace. However, in higher dimensional space, the Dijkstra heuristic will fail. To demonstrate that, we replace the policy and value network with Dijkstra heuristic, using the best direction in workspace to guide sampling. NEXT performs much better than Dijkstra in all but the 2d case, in which the workspace happens to the state space.
5.4 CASE STUDY: ROBOT ARM CONTROL
We conduct real-world case study controlling robot arms move objects shelf. On this representative real-time task, we demonstrate the advantages of the NEXT in terms of the wall-clock.
In each planning task, there is shelf of multiple levels, with each level horizontally divided into multiple bins. The task is to plan a path from a location in one bin to another, i.e., the end effectors of the start and goal configurations are in different bins. The heights of levels, widths of bins, and the start and goal are randomly drawn from some fixed distribution. Different from previous experiments, the base of the robot is fixed. We consider the BIT instead R as the imperfect expert in 3000 training problems. We then evaluate the algorithm separated 1000 testing problems. We compare NEXT(- KS) with the highly tuned BIT* and RRT* in OMPL, and also CVAE-plan and Reinforce- paaafrree-plan in Figure [8] As seen from the visualization of the found paths in Figure this is a very difficult task. Our NEXT outperforms the baselines by a large margin, requiring only second reach the same success rate as running 50 seconds of BIT*
Figure 9: The collision-fee free path produced by NEXT for robot arm planning. The start and goal configurations have and-effectors in different bins of the shelf.
Due to space limits, we put details of the experiment setups, more results and analysis in Appendix F.4
6 CONCLUSION
In this paper, we propose a self-improving planner, Neural Intoraatoon-Eploittatii Trees (NEXT), which can generalize and achieve better performance with experiences accumulated. The algorithm achieves a delicate balance between expansion operation. To obtain the generalizable ability across different problems, we proposed new parametrization for the value function and policy, which captures the Bellman recursive structure in the digh-dime continuous state and action space. We demonstrate the power of the proposed algorithm by outperforming previous state-of-the-an planners with significant margins on planning problems in variety of different environments.
via our carefully designed UCB-type
10

---

Published as a conference paper at ICLR 2020
ACKNOWLEDGEMENT
We thank the Google Research Brain team members for helpful thoughts and discussions as well as the anonymous reviewers for their insightful comments and suggestions. This work is supported in part by NSF grants CDS&E- 1900017 D3SC, CCF-1836936 FMitF. IIS-1841351, CAREER IIS- 1350983 to L.S, and by NSF grants BIGDATA 1840866, CAREER 1841569, TRIPODS 1740735, DARPA-PAR P-----AP--------1-111 18-02-09--0---- WED-RML--FP-00S an Alfred P Sloan Fellowship, a PECASE award to H.L.
REFERENCES
Auer, P., Cesa- Cesa-Bianchi, N., and Fischer, P. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2-3))235-2555 2002.
Mohak Bhardwaj, Sanjiban Choudhury, and Sebastian Scherer. Learning heuristic search via imitation. 2017.
arXiv preprint arXiv:
Boor, V., Overmars, M. H., and Van Der Stappen, A. F. The gaussian sampling strategy for probabilistic roadmap planners. In Robotics and automation, 1999. proceedings. 1999 ieee international conference on, volume 2, pp. 1018-1023. IEEE, 1999.
Burns, B. and Brock, O. Sampling-based motion planning using predictive models. In Robotics and Automation, 2005. ICRA 2005. Proceedings of the 2005 IEEE International Conference on, pp- 3120-3125. IEEE, 2005a.
Burns, and Brock, O. Toward optimal configuration space sampling. In Robotics: Science and Systems, pp. 105 195-112 112. Citeseer, 2005b.
Bowen, Chris, and Ron Alterovitz. Closed-loop global motion planning for reactive execution of learned tasks. In JEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 1754-1760, 2014.
Cadena Cesar, Luca Carlone, Henry Carrillo, Yasir Latif, Davide Scaramuzza, José Neira, Ian Reid, and John J. Leonard. Past, present, and future of simultaneous localization and mapping: Toward the perrettperception age. IEEE Transactions on Robotics, 32(6), 2016.
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):
2018
Chu, W., Li, L.,, Reyzin, L., and Schapire, R. Contextual bandits with linear payoff functions. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pp. 208-214, 2011.
Coučtoux, A., Hoock, J.-B., Sokolovska, N., Teytaud, O., and Bonnard, N. Continuous upper confidence trees. In International Conference Learning and Intelligent Optimization, pp- 433 445. Springer, 2011.
Rosen Diankov. Automated Construction of Robotic Manipulation Programs. PhD thesis, Carnegie Mellon University, Robotics Institute, August 2010.
Rosen Diankov and James Kuffner. Randomized statistical path planning. In 2007 JEEE/RSI International Conference on Intelligent Robots and Systems, pp. 1-6. IEEE, 2007.
Elhanhawi, M. and Simic, M. Sampling-based robot motion planning: review. leee access, 56-77, 2014.
Finney, S., Kaclbling, L. P., and Lozano-Perez, T. Predicting partial paths from planning problem parameters. In Robotics Science and Systems, 2007.
Fulgenzi. Chiara and Tay, Christopher and Spalanzani, Anne and Laugier, Christian Probabilistic random trees and gaussian processes
navigation in dynamic environment using In JEEF/RSJ International Conference Intelligent Robots and Systems, pp. 1056-1062, 2008.

---

Published as a conference paper at ICLR 2020
Gammell, J. D., Srinivasa, S. S., and Barfoot, T. D. Informed nt:: Optimal sampling basedd path planning focused via direct sampling of an admissible ellipsoidal heuristic. arXiv preprint arXiv:1404.2334 2014.
Gammell, J. D., Srinivasa, S. S., and Barfoot, T. D. Batch informed trees (bit*): Sampling-basee based optimal planning via the heuristically guided search of implicit random geometric graphs. In Robotics and Automation (ICRA), 2015 IEEE International Conference on, pp. 3067-3074. IEEE, 2015.
Guez, Arthur and Weber, Théophane and Antonoglou, Ioannis and Simonyan, Karen and Vinyals, Oriol and Wierstra, Daan and Munos, Rémi and Silver, David Learning to search with metsnets arXiv preprint arXiv: 18Xiv: we....002...4 04097, 2018.
Peter E. Hart, Nils Nilsson, and Bertram Raphael. A formal basis for the heuristic determination of minimum cost paths. IEEE transactions on Systems Science and Cybernetics, 4(2):100-107, 1968.
Hsu, D., Latombe, J.-C., and Motwani, R. Path planning in expansive configuration spaces. In Robotics and Automation, 1997. Proceedings. 1997 IEFE International Conference on, volume 3, pp. 2719-2726. IERE, 1997.
Hsu, D., Jiang, T., Reif, J., and Sun, Z. The bridge test for sampling narrow passages with probabilistic roadmap planners. In Robotics and Automation, 2003. Proceedings. ICRA (CRA'03. IEEE International Conference on, volume pp. 4420-4426. IEEE, 2003.
Hsu, D., Sánchez-Ante, G., and Sun, Z. Hybrid prm sampling with cost-sensitive adaptive strategy. In Robotics and Automation, 2005. ICRA 2005. Proceedings of the 2005 IEEE International Conference on, pp. 3874-3880. IEEE, 2005.
Huh, Jinwook and Lee, Daniel Efficient Sampling With Q-Learning to Guide Rapidly Exploring Random Trees. IEEE Robotics and Automation Letters, 3:3868-3875, 2018.
Ichter, B., Harrison, J., and Pavone, M. Learning sampling distributions for robot motion planning. In 2018 IEEE International Conference on Robotics and Automation (ICRA), pp. 7087-7094. IEEE, 2018.
Karaman, S. and Frazzoli, E. Sampling-based algorithms for optimal motion planning. The interna- tional journal of robotics research, 30(7):846-894, 2011.
Karkus, Hsu, D., and Lee, W. S. Qmdp-net: Deep learning for planning under partial observability. In Advances in Neural Information Processing Systems, pp. 4694-4704, 2017.
Kavraki, L. E., Svestka, P., Latombe, J.-C., and Overmars, M. H. Probabilistic roadmaps for path planning in high-dimensional configuration spaces. IEEE Transactions on Roboties and Automation, 12(4). 1996.
Kim, B., Kaelbling, L. P., and Lozano-Pérez, T. learning an action sampler from tfr-target search experience. 2018.
Guiding search in continuous state-action spaces by
Kocsis, L. and Szepesvári, C. Bandit based monte-carlo planning. In European conference on machine learning, pp. 282-293. Springer, 2006.
Krause, A. and Ong, C. S. Contextual gaussian process bandit optimization. In Advances in Neural Information Processing Systems, pp. 2447-2455, 2011.
Kuo, Yen-Ling and Barbu, Andrei and Katz, Boris Deep sequential models for sampling-based planning In JEFE/RSJ International Conference on Intelligent Robots and Systems, pp. 6490-6497, 2018.
Langford, and Zhang, T. The epoch-greedy algorithm for multi-armed bandits with side information. In Advances in neural information processing systems, pp. 817-824, 2008
LaValle, S. M. Rapidly-exploring random trees: A new tool for path planning. 1998.
Lee, L., Parisotto, E., Chaplot. D. S., Xing, E., and Salakhutdinov, R. Gated path planning networks. arXiv preprint arXiv: 11880000408 2018.
12

---

Published as a conference paper at ICLR 2020
Long-Ji Lin. Self-improving reactive agents based on reinforcement learning, planning and teaching. Machine learning, 8(3-4):293-33) 321, 1992.
Paxton, Chris and Raman, Vasumathi and Hager. Gregory D and Kobilarov, Marin Combining neural
networks and tree search for task and motion planning challenging environments In IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 6059-6066, 2017.
Sven Mikael Persson and Inna Sharf. Sampling- based a* algorithm for robot path-planning The International Journal of Robotics Research, 33(13); 1708, 2014.
Phillips,1 J. M., Bedrossian, N., and Kavraki, L. E. Guided expansive spaces trees: A search strategy for motion-and cost-constrained state spaces. In IEEE International Conference on Robotics and Automation, pp. 3968-3973, 2004.
Mike Phillips, Benjamin J Cohen, Sachin Chitta, and Maxim Likhachev. E-graphs: Bootstrapping planning with experience graphs. In Robotics: Science and Systems, volume 5, pp. 110, 2012.
Qureshi, Ahmed H and Simeonov, Anthony and Bency, Mayur J and Yip, Michael C. Motion planning networks. In IEEE International Conference Robotics and Automation, 2019.
Reif, J. H. Complexity of the mover's problem and generalizations. In Foundations of Computer Science, 1979., 20th Annual Symposium on, pp. 421-427. IEEE, 1979.
Rickert, Markus and Brock, Oliver and Knoll, Alois. Balancing exploration and exploitation in motion planning In IEEE International Conference on Robotics and Automation, pp. 2812-2817. IEEE, 2008.
Tom Schaul, John Quan, Ioannis Antonoglou, and David Silver. Prioritized experience replay. arXiv preprint 1rXi::1511.009555 2015.
Shkolnik, A., Walter, M., and Tedrake, R. Reachability-gudde sampling for planning under differen- tial constraints. In Robotics and Automation, 2009. ICRA '09. IEEE International Conference on, pp. 2859-2865. IEEE, 2009.
Silver, David and Hubert, Thomas and Schrittwieser, Julian and Antonoglou, Ioannis and Lai, Matthew and Guez, Arthur and Lanctot, Marc and Sifre, Laurent and Kumaran, Dharshan and Graepel, Thore and others Mastering chess and shogi by self-play with general reinforcement learning algorithm. arXiv preprint
2017.
Sohn, K., Lee, H., and Yan, X. generative models. In Advances in Neural Information Processing Systems, pp. 3483-3491, 2015.
Learning structured output representation using deep conditional
Jialin Song, Ravi Lanka, Albert Zhao, Yisong Yue, and Masahiro Ono. Learning to search via retrospective imitation. arXiv preprint arXiv:1804.0 00846. 2018.
Srinivas, N., Krause, A., Kakade, S. M., and Seeger, M. Gaussian process optimization in the bandit setting: No regret and experimental design. arXiv preprint arXiv:0912.3995, 2009.
Ioan A. Şucan, Mark Moll, and Lydia E. Kavraki. The Open Motion Planning Library. IEEE Robotics & Automation Magazine, 19(4):72-82, December 2012. doi: 10.1109//MAA22012.200000
http://ommp..aarrkilabbogg
Tamar, A., Wu, Y., Thomas, G., Levine, S., and Abbeel, P. Value iteration networks. In Advances in
Neural Information Processing Systems, pp. 2154-2162, 2016.
Wang, Y., Audibert, J.-Y., and Munos, R. Algorithms for infinitely many-armed bandits. In Advances in Neural Information Processing Systems, pp. 1729-1736, 2009.
Ye, Gu and Alterovitz, Ron Guided motion planning. In Robotics research, pp. 291-6307. Springer, 2017.
Yee, T., Lisy, V., and Bowling, M. Monte carlo tree search in continuous action spaces with execution uncertainty. In Proceedings of the Crenty-Fiftth International Joint Conference on Artificial Intelligence, pp. 690-696. AAAI Press, 2016.
13

---

Published as a conference paper at ICLR 2020
Zhang, C., Huh, J., and Lee, D. D. Learning implicit sampling distributions for motion planning. arXiv preprint
2018.
Zucker, M., Kuffner, J., and Bagnell, J. A. Adaptive workspace biasing for sampling-based planners. In Robotics and Automation, 2008. ICRA 2008, IEEE International Conference on, pp. 3757-3762. IEEE, 2008.
14

---

Published as a conference paper at ICLR 2020
Appendix
A ILLUSSRAAIINN OF THE DIFFICULTY IN PLANNING PROBLEMS
The Figure 10 a) illustrates a concrete planning problem for a stick robot in 2d workspace. With one extra continuous action for rotation, the configuration state visualized in Figure [0 which is highly irregular and unknown to the planner.
(a) Workspace
(b) Configuration space
Figure 10: Different views of the same planning problem. In (a) we color the obstacles, the starting and the goal position of the robot in deep blue, orange and brown, respectively. The stick robot can move and rotate. The corresponding configuration space is 3d, as visualized (b), with the extra dimension being the rotation angle w.r.t. the x-axis. The blue region indicates the feasible state space, i... the set collision-free states. The starting and goal position are denoted with an orange and brown dot, respectively. Although the workspace looks trivial, the configuration space is irregular, which makes the planning difficult.
B MORE PRELIMINARIES
Tree-based sampling planner The tree-based sampling planner algorithm illustrated in Fig- II The Expand in Algorithm| I operatorr returns existing node the tree Sparent V and new state Snew E S sampled from the neighborhood of Sparent- Then the line segment [Sparent, Snew] passed function ObstacleFree for collision checking. If the line segment [Sparents Snew is collision-free (no obstacle in the middle, or called reachable from T), then Snew is added to the tree vertex set V/ and the line segment is added the edge set If the newly added node Snew has reached the target Syout. the algorithm will return. Optionally, some concrete algorithms can define Postprocess operator refine the search tree. For an example of the Expand operator, as shown in Figure (c), since there is no obstacle on the dotted edge [sporent: Snew], i.e., Snew is reachable, the new state and edge will be added to the search tree (connected by the solid edges).
Goal
New
Start
Start
Parent
Parent
Figure 11: Illustration for one iteration of Algorithm I The left and right figures illustrate two different cases where the sample returned by the Expand operator is unreachable and reachable from the search tree.
Now we will provide two concrete algorithm examples. For instance,
If we instantiate the Expand operator as Algorithm then we obtain the expidly-exploingg random trees (RRT) algorithm Valle 1998), which first samples state from the configuration space
15

---

Published as a conference paper at ICLR 2020
Algorithm 4: RRT Expand(T,U) (T,
Data: T = -V.8) U = (Sinit; Syout, S, S Sree; map, c(.))
Brand < Unif(S)
P Sample configuration space
Sparent argmingey ||5rand s||;
Pull to a tree node
3 Snew f argmin,ggge....... B (epppannt:))) ||s Srand|l;
return 8 pparent, Snewr
Algorithm 5: EST :: Expand(T,U)
Data: T (V,)), (Sinit, Syoat, S S Steee map, c(-))
Sparent ~ ((8), V:
> Sample a tree node Sample neighborhood
Snew (Spparee)))
return Spearest; Snews
S and then pulls toward the neighborhood of current tree measured by ball of radius y ((s, 1) = (s' E S ||s' - =|l < v7)
Moreover, if the Postprocess operator is introduced to modify the maintained search tree as in RRT (Karaman & Frazzoli 2011), the algorithm is provable to obtain the optimal path asymptotically.
If we instantiate the Expand operator as Algorithm 5 then we obtain the expansive-spa trees (EST) algorithm (Hsu et al. 1997; Phillips al. 2004). which samples state from the nodes of the existing tree, and then draw sample from the neighborhood of s.
UCB-based algorithms Specifically, in a K-armed bandit problem, the UCB algorithm will first play each of the arms once, and then keep track of the average reward F, and the visitation count n, for each arm. After T rounds of trials, the UCB algorithm will maintain a set of information {(F,, n K with Σ;= n, = T. Then, for the next round, the UCB algorithm will select the next arm based the one-sided confidence interval estimation provided by the Chernoff-Hoefddigg bound,
0 agg.a.,ee1.....f. F2
where A controls the exploration-expllration trade-off. It has been shown that the UCB algorithm achieves O (logT) regret. However, the MCTS not directly applicable continuous state-action spaces.
There have been many attempts to generalize the UCB and UCT algorithms continuous state-action spaces (Chu et al. 2011 Krause & Ong 2011; Couêtoux et al., 2011 Yee et al. 2016). For instance, contextual bandit algorithms allow continuous arms but involve non-trivial high dimensional non-convex optimization to select the next arm. In UCT, the progressive widening technique has been designed to deal with continuous actions (Wang al., (009). Even with these extensions, the MCTS restricts the exploration only from leaves states, implicitly adding an unnecessary hierarchical structure for path planning, resulting inferior exploration efficiency and extra computation path planning tasks.
Although these off-the-shelf algorithms are not directly applicable to our path planning setting, their successes show the importance of apploration-cxploittaii trade-off and will provide the principles for our algorithm for continuous state-action planning problems.
Planning networks Value iteration networks (Tamar al. 2016) employ neural networks to embed the value iteration algorithm from planning and then use this embedded algorithm to extract input features and define downstream models such as value functions and policies.
Specifically, VIN mimics the following recursive application of Bellman update operator G to value function V*
V (s|U) (gV") (s) min Σ
+V* (s(1U)).
where P(s"|s, ss, a) is the state transition model. When the state space for s and action space for a are low dimensional, these spaces can be discretized into grids. Then, the local cost function c[[s, s')) and the
16

---

Published as a conference paper at ICLR 2020
value function (s) can be represented matrices (2d) or tensors (3d) with each entry indexed by grid locations. Furthermore, if the transition model P(s'|s, a) is local, that is P(s'|s, a) = for s' & Bss), it resembles set of convolution kernels, each indexed by discrete action And the Bellman update operator essentially convolves P(s'|s, a) with o[[s, s')) and V* (s))'U)) and then performs min-pooling operation across the convolution channels.
Inspired by the above computation pattern of the Bellman operator, value iteration networks design the neural architecture follows, V- min
[W map, R)
Fet min
[W +
+t- R
(10)
where + is the convolution operation, both map, Vn and R are d x d matrices, and the parameter W1 are h convolution kernels of size k k. The min implements the pooling across he convolution channels.
The gated path planning networks (GPPN) (Lee et cell (9) with the well-established LSTM update, i.e.,
2018) improves the VIN by replacing the VIN
V dt LSTM Σ (Wi [ [V.))).))) .
(11)
where the summation is taking over all the kg convolution channels.
After constructing the VIN and GPPN, the parameters of the model, i.e., { R. Wi] can be learned by imitation learning or reinforcement learning.
The application of planning networks are restricted in low-dimension tasks. However, their success enlightens our neural architecture for generalizable representation for high- high-dimension planning tasks.
C PARAMETRIZED UCB ALGORITHMS
We list two examples of parametrized UCB as the instantiation used in GPE:
GP-UCB: The GP-UCB Chu et al. (0ITT) is derived by parameterizing via Gaussian Processes (GP) with kernel (s, s' ie.. Er (s) IT, U] GGP (0, GP-UCB maintains an UCB of the reward after t-step Φ (s) Fr (s) + )o (s),
(12)
where
Fr (s) = by (8) (Ke + al) at) nt.
(s) (s, ke (s) (K++al) ki (8),
with K2 (s) = [k (8s; ..s. K, [ (8,, and S. = (81, .2,..... 81) denotes the sequence of selected nodes in current trees. The variance estimation of (s) takes the number of visits into account in an implicit way: the variance will reduce, as the neighborhood of is visited more frequently (Srinivas et al. 2009).
KS-UCB: We can also use kernel regression as an alternative parametrization for et 2016), which leads an UCB of the reward after t-step as & (s) = Fr (s) + do (s),
Yee
(13)
where
Fe [s] = Eves, is &
Eves, t (5',8)
log Eves, (s')
tt (s)
w (s)
with w (s) = Eves, lo (s', s). Clearly, the variance estimation is to promote exploration towards less frequently visited states.
As we can see, in both two examples of the parametrized UCB, we parametrize the observed rewards, leading to generalizable UCB for increased states by considering the correlations.
17

---

Published as a conference paper at ICLR 2020
D POLICY AND VALUE NETWORK ARCHITECTURE
We explain the implementation details of the proposed parametrization for poliey and value function. Figure T2 and Figure 13 are neural architectures for the attention module, the policy/value network, and the planning module, respectively.
Ingue stt0
Eiputt mine nap geree
Japut: pasl state Syoes
Ingut: stato F Bt
Alttion mudule
Goal embeiding (gua) ggddddd
State (a(a) tsese
Pepand and Stack
Stack
("""" e geoee
Task embedding g)
Cony 1, rolz
Comy 1, 16, rots
Con: 3 3,
Comn 3
Come 1,322 neu
Cony 1, 32, rots
Parning modile
Loop I' tims
64, reuu
Dense,
é getis reshape it to g gestndapp
Cony x 1,
Dense, dl,
Elenent wise product sum ower first dimmisions
Spotal ambtdding (r*) E gess
Condig embedding AGGG") BP
Detse, 32, mřu
Eleneni-wii wise product
Attection module
Therse, 37, rioo
Denue,
Dense,
Ourput: Pull Bulleebbeddegggeee c ge
Output R UV("
Oztput P"(s()
Figure 12: Left: attention module, instantiating the Figure 3 ing the Figure 4
Right: policy/value network, instantiat-
In the figures, we use rectangle blocks to denote inputs, intermediate results and outputs, stadium shape blocks to denote operations, and rounded rectangle blocks to denote modules. We use different layers, green for
colors for different operations. In particular, we use blue for convolutional/LSST dense layers, and orange for anything else. For convolutional layers, "Conv 1 x 1, 32, relu" denotes a layer with 1 1 kernels, 32 channels, followed by rectified linear unit; for dense layers, "Dense, 64, relu" denotes a layer of size 64, followed by a rectified linear unit.
The attention module (Figure 121feft) embeds state to d x d x da tensor. The planning module (Figure [3) a one-step LSTM update which takes the result of a convolutional layer as input. Both the input and hidden size of the LSTM cell are de. All d locations share one set of parameters and are processed by the LSTM one batch.
The main architecture is illustrated in Figure 12 right. It takes maze map, state and goal as input, and outputs the action and the value. Refer to Section 4.2 for details for computing (s)). In our experiments, set the values of the hyper-parameters to be (d, dey da.p) (15, 64,8,
18

---

Published as a conference paper at ICLR 2020
Irpab A, c grlntin,
Jnpori a sethers,
Planning module
Dons 1 1,
ISTM iepub getrada
ISTM hidden
Cutprrt gandtd
ourgut ganddd
Figure 13: planning module
E EXPERIMENT DETAILS
E. BENCHMARK ENVIRONMENTS
We used four benchmark environments in our experiment. For the first three, the workspace dimension is 2d. We generated the maps with the recursive backtracker algorithm using the following imple- mentation: https://github.co htt.a//co///llc///eeeeeeeeeeeeee satee--pah-planning bettwrks/bloobmaster imsterr/eenerate _ataseet.ppyy Examples of the workspace are shown Figure Three environments differ in the choice of robots:
Workspace planning (2d). The robot is abstracted with a point mass moving in the plane. Without higher dimensions, this problem reduces to planning in the workspace.
Rigid body navigation (3d). A rigid body robot, abstracted as thin rectangle, is used here. The extra rotation dimension is added the planning problem. This robot can rotate and move freely without any constraints in the free space.
3-link snake (5d). The robot a DoF snake with two joints. Two more angle dimensions are added to the planning task. To prevent links from folding, restrict the angles the range of [- / /r, n /4].
The fourth environment has 3d workspace. Cuboid obstacles were generated uniformly randomly in space with density == 20%. Example of the workspace is shown in Figure and 16 where the blue cuboids are obstacles. The environment described below:
Spacecraft planning (7d). The robot a spacecraft with a cuboid body and two DoF arms connecting two opposite sides of the body. There is joint in the middle of each arm. The outer arm can rotate around this joint. Each arm can also rotate as a whole around its connection point with the body. All rotation angles are restricted in the range of [0, x/2]. The spacecraft itself cannot rotate.
E.2 HYPERPARAMETER FOR MSIL
During self iallovippoviig over the first 2000 problems, NEXT updated its parameters and annealed once for every 200 problems. The value of the annealing was set as the following:
1,
if < 1000,
0.5 - 0.1 -i- 1000)/200,
if 1000 <i< 2000,
0.1.
otherwise.
with denoting the problem number.
E.3 BASELINE: THE IMPROVED GPPN
The original GPPN is not directly applicable we add a fully-com collycconeeeted MLP to its final layers, so that the improved architecture can be applied to high-dimensional continuous domain. As shown in Figure 14, the GPPN first processes the discretized
experiments. Inspired by Tamar et al. (2016).
19

---

Published as a conference paper at ICLR 2020
Workspace
Map
Initial Position
GPPN
Full
V*(5)
Value
Position
Goal
State
Initial
MLP
# (s'(((s))
Action
Goal
State
Figure 14:
Improved GPPN architecture
workspace locations. Its output and the full robot configurations are processed together by the MLP, which then produces the current value and action estimates. The improved GPPN is trained using supervisions from the near-optimal paths produced by RRT*
F
EXPERIMENT RESULTS
F.I SOLUTION PATH ILLUSTRATION
 C of
Figure 15: The solution path produced by NEXT in workspace planning task (2d), rigid body navigation task (3d), 3-link snake task (5d) from left to right. The orange dot and the brown dot are starting and goal locations, respectively.
Figure 16: The solution paths produced by NEXT in spacecraft planning task (7d). Spacecraft has yellow body and two 2 DoF (red) arms. Blue cuboids are obstacles.
F.2 DETAILS OF QUANTITATIVE EVALUATION
More detailed results shown in Table 2 including learning- based and non-learnin- based ones, on the last 1000 problems in each experiment. We normalized the number collision checks and the cost of paths based the solution of RRT* The success rate result is not normalized. The
20

---

Published as a conference paper at ICLR 2020
best planners in each experiment in bold. NEXT-KS and NEXT-GP outperform the current state-of-the-ar planning algorithm with large margins.
Table Success rate results. The higher the better. NEXT-KS performs the best.
NEXT-KS
NEXT-GP
GPPN-KS
GPPN-GP
RRT
BIT*
BFS
CVAE
Reject
2d 0.988
0,981
0.718
0.632
0.735
0.710
0.185
0,535
0.720
3d
0.943
0.841
0.689
0,554
0.490
0,514
0.121
0.114
0.498
5d
0.883
0.768
0.633
0.515
0.455
0.497
0.030
0.476
0.444
7d
0.931
0.906
0.634
0.369
0.361
0.814
0.288
0.272
0.370
Table 2: Average number collision checks results. The lower the better. The score is normalized based on the solution of RRT". NEXT-KS performs the best in 3 benchmarks.
NEXT-KS
NEXT-GP
GPPN-KS
GPPN-GP
RRT
BIT
CVAF
Reject
2d 0.177
0.243
2.342
3,484
1.000
5.945
9.247
1.983
1.011
3d
0.694
1,334
2.214
3.125
1.000
7.924
7.292
2.162
0.988
5d
0.888
1.520
1.800
2.706
1.000
7.483
5.758
1.188
0.997
7d
0.653
0.502
1.877
1,313
1.000
4.683
3.856
1.591
0.987
Table 3: Average cost of paths. The lower the better. The score normalized based on the solution of RRT The NEXT-KS achieves the best solutions.
NEXT-KS
NEXT-GP
GPPN-KS
GPPN-GP
RRT
BIT
BFS
CVAE
Reject
2d
0.172
0.193
1.049
1.333
1.000
1.140
2.811
1.649
1.050
3d
0.116
0.315
0.612
0.875
1.000
0.955
1.720
1.734
0.984
5d
0.215
0.426
0.673
0.890
1.000
0.923
1.780
0.961
1.020
0.108
0.147
0.573
0.987
1.000
0.291
1.114
1.139
0.986
We demonstrated the performance improvement curves for 2d workspace planning, 3d rigid body navigation in Figure 17 As we can see, similar to the performances on 5d 3-link snake planning task Figure 7 in these tasks, the NEXT-KS and NEXT-GP improve the performances along with more and more experiences collected, justified the self-improvement ability by learning 7' and #*
F.3 SEARCH TREES COMPARISON
We illustrate the search trees generated by RRT and the proposed NEXT algorithms with 500 samples Figure T8] Figure 19 Figure 20 and Fi several 2d, 3d, 5d and 7d planning tasks, respectively. To help readers better understand how the trees were expanded, we actually visualize the RRT* search trees without edge rewiring, which is equivalent to the RRT search trees, however the vertex set is the same. Comparing the search trees generated by RRT* side by side, we can clearly see the advantages and the efficiency of the proposed NEXT algorithmss. In all the tasks, even 2d workspace planning task, the RRT* indeed randomly searches without realizing the goals, and thus cannot complete the missions, while the NEXT algorithms search towards the goals with the guidance from V and =*, therefore, successfully provides high-quality solutions.
21

---

Published as a conference paper at ICLR 2020
MOTSPP
100
135
Figure 17: The first and second rows display the improvement curves of our algorithms on 3000 problems of the 2d workspace planning and 3d rigid body navigation problems. We compare our algorithms with RRT*, Three columns correspond to the success rate, the average collision checks, and the average cost of the solution paths for each algorithm.
5
E
(a) R (w/o rewiring) (b) NEXT-KS search tree (c) NEXT-GP search tree (d) learned 5 and #*
Figure 18: Column (a) to (c) are the search trees produced by the RRT*, NEXT-KS, and NEXT-GP on the same workspace planning task (2d). The learned V and म from NEXT-KS are plotted in column (d). In the figures, obstacles denoted by orange and brown dots, respectively. In column (a) to (c), samples are represented with hollow yellow circles, and edges colored in green. In column (d), the level of redness denotes the value of the cost-to-go estimate V* and the cyan arrows point from given state to the center of the proposal distribution 7" (s'1s, U). We set the maximum number of samples to be 500.
colored in deep blue, the starting and goal locations
22

---

Published as a conference paper at ICLR 2020
E
ERE
RRT search tree (w/o rewiring)
E
ZAF
NEXT-KS search trees
Figure 19: Each column corresponds to example from the rigid body navigation problem (3d). The top and the bottom rows are the search trees produced by the RRT* and NEXT-KS, respectively. In the figures, obstacles The samples, starting states, and goal states are denoted by yellow, orange, and brown matchsticks, respectively. Edges are colored green. We the maximum number of samples to be 500.
colored in deep blue, and the rigid bodies are represented with matchsticks.
RRT search tree (w/o rewiring)
NEXT-KS search trees
Each column corresponds one example from the 3-link snake problem (5d). The top and the bottom rows are the search trees produced by the RRT* and NEXT-KS, respectively. In the figures, obstacles are colored in deep blue, and the rigid bodies are represented with matchsticks. The samples, starting states, and goal states are denoted by yellow, orange, and brown matchsticks, respectively. Edges are colored in green. We the maximum number of samples to be 500.
Figure 20:
23

---

Published as a conference paper at ICLR 2020
RRT search tree (w/o rewiring)
NEXT-KS search trees
Each column corresponds to one example from the spacecraft planning problem (7d). The top and the bottom rows are the search trees produced by the RRT* and NEXT-KS, respectively. In the figures, obstacles are colored in blue, and each spacecraft has yellow body and two 2 DoF red arms We set the maximum number samples to 500.
Figure 21:
24

---

Published as a conference paper at ICLR 2020
F.4 CASE STUDY DETAILS
We conduct a real-world case study on controlling robot arms to move objects on a shelf. This is representative of common scenarios in practice where the robot needs plan its motion in real-time to reach the inside of some narrow space. For this case study, we focus more on the practical aspect evaluate how much can we improve on the wall-clock time by learning from similar planning problems.
F.4.1 TASK DESCRIPTION
We generate planning problems randomly to form the training set and test set. In each planning task, there shelf of multiple levels, with each level horizontally divided into multiple bins. The heights of levels and widths of bins are randomly drawn from some fixed distribution. Samples of shelves are shown Figure 22 Both the start and goal configurations are randomly sampled from distribution within the reachable region of the robot arm. The planning environment is created with the OpenRave simulator Diankov 2010).
The task is to find path for the 7 DoF robot arm to move from a location in one bin to another, iee. the end effectors of the start and goal configurations are in different bins, as illustrated in Figure 23 In this case, the base of the robot is fixed and we are planning the movement of arm. We generated 3000 problems for training and 1000 problems for testing.
F.4.2 BASELINES AND TRAINING
For traditional planners, we include OMPL (Suaan al. 2012) implementation of BIT (Gam mell et al. 2015) and RRT (Karaman & Frazzoli 2011) as baselines. The hyperparameters of RRT and BIT are specially tuned for this experiment. We also compare with learning- based planners CVAE-plan (Ichter et al.) 2018) and Reinforce-plan (Zhang et al. 2018). The supervisions for CVAE-plan are produced by the well-tuned BIT on the training set. To train NEXT, we consider the BIT* instead of RRT* as the imperfect expert in training problems.
F.4.3 RESULTS
We evaluate the algorithms on the separated testing problems, and record the success rate using 10 different time limits. The success rate and average path quality are plot Figure and recorded in Table and Table The solution paths found by NEXT and BIT* are illustrated in Figure 23 In terms both success rate and solution path quality, NEXT dominates all the planners under all time limits.
Figure 22: Examples of different shelves sampled from the distribution.
25

---

Published as a conference paper at ICLR 2020
Figure 23: First robot arm solution trajectories produced by NEXT(-KS) in four planning problems; Second row: BIT solutions on the same planning problems. NEXT only takes 5 seconds complete each problem while BIT* needs 250 seconds to find solution for the hardest problems (last two columns).
Table 4: Success rates of different planners under varying time limits, the higher the better.
5s
10s
15s
20s
25s
30s
35s
40s
45s
50s
NEXT
0.579
0.657
0.703
0.709
0.745
0.743
0.746
0.752
0.772
0.763
CVAE
0.354
0.437
0.482
0.509
0.507
0.539
0.553
0.551
0.579
0.580
Reinforce
0.160
0.170
0.200
0.150
0.180
0.190
0.175
0.180
0.225
0.175
BIT*
0.226
0.288
0.320
0.365
0.364
0.429
0.425
0.422
0.443
0.475
RRT
0.135
0.148
0.144
0.136
0.147
0.159
0.152
0.158
0.157
0.165
Table 5: Average path costs of different planners under varying time limits, the lower the better.
5s
10s
15s
20s
25s
30s
35s
40s
45s
50s
NEXT
25.143
21.873
20.052
19.773
18.318
18.381
18.274
18.047
17.224
17.587
CVAE
34.414
30.815
28.909
27.717
27.784
26.408
25.776
25.883
24.665
24.659
Reinforce
42.781
42.471
41.142
43.295
42.129
41.657
42.235
42.093
40.269
42.282
BIT*
39.543
37.086
35.744
34.002
34.007
31.414
31.587
31.651
30.841
29.601
RRT*
43.368
42.855
42.981
43.355
42.919
42,410
42.680
42.441
42.504
42,165
26


Reviews:
[{"review_id": "SkewetU15S", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "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": "Summary:\n\nMotion-planning in high dimensional spaces is challenging due to the curse of dimensionality. Sampling-based motion planners like PRM, PRM*, RRT, RRT*, BIT* etc have been the go-to solution family. But often these algorithms solve every planning problem tabula rasa. This work combines learning with sampling-based planning such that the parent-sampling and expansion steps instead of being done by common heuristics are learnt in an online manner. Also the resulting exploration-exploitation problem is naturally dealt via using a UCB-style contextual bandit algorithm. Since the number of parents are always varying the common trick of 'describe the action choices with respect to the environment' is adopted so that varying number of actions (states to be sampled from) can be naturally incorporated. \n\nThe other significant aspect of this paper is that there is a self-improving component (Algorithm 3) where a dataset is built up every time step, of environments where either an expansion with RRT or the learnt expansion policy is attempted with the policy being invoked more as time goes on and it trains more. If the process succeeds in finding a path to the goal then this example is added to a dataset and the dataset used to update the policy and associated value function to guide it towards the feasible paths found in the tree. \n\nComments:\n\n\n- Algorithm 3: \"Reconstruct optimal path\". These paths are not really optimal for the problem. They are optimal in the tree T that is built so far for example U. But for the problem they are feasible and if RRT* were to be run asymptotically then perhaps near-optimal. The accompanying text should be updated accordingly so that there isn't confusion.\n\n- Here is my main concern with Algorithm 3: For equation 6  where the policy and value functions are updated, the policy is inevitably going to suffer from covariate shift. This is because the algorithm is essentially doing behavior cloning (BC) with respect to the feasible paths found on the planning examples. Since we are inherently in a sequential setting (non-iid) where the states visited by the policy are a direct result of its own decisions the error bound will be quadratic in the horizon (path-length) for equation 6. This phenomenon has been well-understood in imitation learning literature and algorithms like DAgger, AggreVate or online versions like AggreVateD, LOLS already address these problems in a principled manner. Equation 6 should ideally be replaced with an inner DAgger/AggreVateD like loop (with an RRT* dynamic oracle) for stable learning of policy and value function. I am happy to be convinced that covariate shift and resulting quadratic mistake-bound problems are not present here.\n\n- Application of imitation learning to both self-improvement style path planning and leveraging experience in planning has been done before: See \"Learning to Search via Retrospective Imitation\nJialin Song, Ravi Lanka, Albert Zhao, Aadyot Bhatnagar, Yisong Yue, Masahiro Ono, 2018\" (this is unpublished it seems so it is unfair of me to mention this perhaps but I wanted to give an example of how to use dynamic oracles for stable imitation in planning.) and \"Data-driven Planning via Imitation Learning\nSanjiban Choudhury, Mohak Bhardwaj, Sankalp Arora, Ashish Kapoor†, Gireeja Ranade, Sebastian Scherer and Debadeepta Dey\", IJRR 2018. At least the last paper should be cited and discussed in related work.\n\n- Also would be curious how the authors would situate methods which are non-learning based but leverage experience in planning (example E-Graphs: Bootstrapping Planning with Experience Graphs, Phillips et al, RSS 2012) via graphs discovered in other problems directly. Perhaps a discussion in related work is warranted?\n\nUpdate: After rebuttal updating to Accept.\n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A"}, "extra_text": {}}, {"review_id": "Hylq3SQaYr", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "This paper proposes an approach to learn how to plan in continuous spaces using neural\nnets to learn a value function and a policy for scoring and sampling next-step candidates\nin a stochastic tree search.  The networks are updated as more planning tasks\nare executed, producing more data for the policy and value function, leading to gradually\nbetter plans compared to a number of baselines on benchmarks introduced by the authors.\n\nThis is a very interesting paper, although I did not always found it easy to read,\nmaybe too densely packed for comfort. My main concerns are clarity of the exposition (especially\nof the neural net architecture (sec 4.2) and that the comparisons are exclusively done\non benchmarks introduced by the authors rather than on benchmarks on which the baseline\nmethods had been previously been optimized, which may introduce a bias in favour of the\nproposed approach.\n\nClarifications\n\nBefore eqn 2, I don't understand why U includes both S_free and map, although the map specifies the free space and thus S_free seems redundant.\n\nIn sec 3 (page 3), the authors introduce a new notation s_init which seems to be the same as s_0 in the previous sections (or is it?).\n\nSection 4.2 was really difficult for me to parse and is too compressed (so is the rest of the paper but this one was worse).\n\nFigures were too small (esp. fig 4 and fig 7) for me to read from the printed paper.\n\nThe term 'meta self-improving learning' seems inappropriate. I did not see  how this was a form of meta-learning. Unless I missed something I suggest to change the terminology.\n\nOther Concerns\n\nI have a concern regarding the way r_t(s) is estimated (page 4) by kernel interpolation of the rewards. I fear that it will not generalize properly when trying to extrapolate, especially in high dimensions (since the claim of the paper is that the proposed algorithms is meant for 'high dimensional' states).\n\nIn addition, the experiments are actually performed in  rather low-dimensional settings (compared to working on problems with perceptual inputs, for example).\n\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A"}, "extra_text": {}}, {"review_id": "Bkey_3u7qS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "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 introduces a novel  meta path planning algorithm  that utilizes neural network module that improves the data-efficiency for iterated path planning problems.\n\nThe authors address a relevant issue and the experiments make sense given the research question.  I particular like the 3 ablation studies that the authors include, which makes the empirical analysis very thorough.\n\nWriting and Clarity:\nThe introduction is written quite well. Section II&III is written quite technical and dense. This can be very hard to understand for non-experts. However these section are  important to understand the  rest paper. Finally, these two sections should be integrated (preliminaries, quite literally, should be at the beginning). Section 5 \n\n\nAdditional Questions:\n1. Philosophically, how does the self-improvement for iterative planning problems not contradict the no-free lunch theorem? What kind of repeated structure do we assume here (because it seems as in Fig. 1 both the obstacles as well as the goal state change randomly)\n2. As you employ a neural network to do value iteration how does the wall-clock time compare to the baselines?  I do not mean the environment time-ticks (that you checked for using the number of collision checks), but actual compute time. \n3. How sensitive is the proposed solution to parameter initialization?  Did you find much variation in changing hyper-parameters, such as network topology, learning rate et cetera?\n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: All reviewers unanimously accept the paper.
Decision: Accept (Spotlight)