Year: 2020

Abstract:
We propose a meta path planning algorithm named 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 exploration and 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.

heading: 1 INTRODUCTION
text: 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-based approaches to avoid explicit discretization. Sampling-based planning algorithms, such as probabilistic roadmaps (PRM) (Kavraki et al., 1996), rapidly-exploring random trees (RRT) (LaValle, 1998), and their variants (Karaman & Frazzoli, 2011) incrementally build an implicit representation of the state space using probing samples. These generic algorithms typically employ a uniform sampler which does not make use of the structures of the problem. Therefore they may require lots of samples to obtain a 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., 2003) and reachability-guided 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.
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 a model for the planning environment incrementally and use the model for planning. Yee et al. (2016) 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, a planner based on such representation can then be transferred to new problems with improved sample efficiency.
∗indicates equal contribution.
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. (2018); Huh & Lee (2018) treat the sampler in the sampling-based planner as a stochastic policy to be learned and apply policy gradient or TD-algorithm to improve the policy. Finney et al. (2007); Bowen & Alterovitz (2014); Ye & Alterovitz (2017); Ichter et al. (2018); Kim et al. (2018); 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 handdesigned 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-shelf MLP architecture ignoring special structures in planning problems or can only deal with discrete state and action spaces in low-dimensional settings.
In this paper, we present Neural EXploration-EXploitation Tree (NEXT), a meta neural path planning 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 structures from previous experiences and produce promising search directions with automatic online exploration-exploitation balance adaption. Compared to existing learning-based 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, we 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-arts on several benchmark tasks.

heading: 1.1 RELATED WORKS
text: 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-based 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); Song 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 exploration-exploitation trade-off is also an important issue in planning. For instance, 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 exploration-exploitation in the fine action space. These existing works address the trade-off in an ad-hoc way, which may be inferior for the balance.
There have been sevearl non-learning-based planning methods that can also leverage experiences (Kavraki et al., 1996; Phillips et al., 2012) 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.

heading: 2 SETTINGS FOR LEARNING TO PLAN
text: Let S ⊆ Rq be the state space of the problem, e.g., all the configurations of a robot and its base location in the workspace, Sobs ( S be the obstacles set, Sfree := S \ Sobs be the free space, sinit ∈ Sfree be the initial state and Sgoal ( Sfree be the goal region. Then the space of all collisionfree paths can be defined as a continuous function Ξ := {ξ (·) : [0, 1]→ Sfree} . Let c (·) : Ξ 7→ R
be the cost functional over a path. The optimal path planning problem is to find the optimal path in terms of cost c(·) from start sinit to goal Sgoal in free space Sfree, i.e., ξ∗ = argminξ∈Ξ c (ξ) , s.t. ξ(0) = sinit, ξ(1) ∈ Sgoal. (1) Traditionally (Karaman & Frazzoli, 2011), the planner has direct access to (sinit,Sgoal, c (·)) and the workspace map (Ichter et al., 2018; Tamar et al., 2016; Lee et al., 2018), map(·) : R2 or R3 7→ {0, 1}, (0: free spaces and 1: obstacles). Since Sfree often has a very irregular geometry (illustrated in Figure 10 in Appendix A), it is usually represented via a collision detection module which is able to detect the obstacles in a path segment. For the same reason, the feasible paths in Ξ are hard to be described in parametric forms, and thus, the nonparametric ξ, such as a sequence of interconnected path segments [s0, s1], [s1, s2], . . . , [sT−1, sT ] ⊂ S with ξ(0) = s0 = sinit and ξ(1) = sT , is used with an additive cost ∑T i=1 c ([si−1, si]).
Assuming given the planning problems {Ui := (sinit,Sgoal,S,Sfree, map, c (·))}Ni=1 sampled from some distribution U , we are interested in learning an algorithm alg (·), which can produce the (nearly)-optimal path efficiently from the observed planning problems. Formally, the learning to plan is defined as alg∗ (·) = argminalg∈A EU∈U [` (alg(U))] , (2) where A denotes the planning algorithm family, and ` (·) 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 elaborate 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 a novel attention-based neural parametrization in Section 4.2 with exploration-exploitation balance mechanism in Section 4.1. We design the `-loss function and the meta learning algorithm in Section 4.3. Composing every component together, we obtain the neural exploration-exploitation trees (NEXT) which achieves outstanding performances in Section 5.
Goal
Start
Goal Goal
Start
Start
l l l l L max V+U
max V+U
Goal
Start
Goal
Start
max V+U
π( |s)
b. Selecta. New Task c. Expand d. Update
Repeat
l L
Goal
Start
Goal
Start
Goal
Startse lf-
im pr
ov e
se lf-
im pr
ov e
max V+U
π( |s)
... ... ... ...
problem will be extracted based on the tree T . The template of tree-based sampling algorithms is summarized in Algorithm 1 and illustrated in Fig. 1(c). A key component of the algorithm is the Expand operator, which generates the next exploration point snew and its parent sparent ∈ V . To ensure the feasibility of the solution, the snew must be reachable from T , i.e., [sparent, snew] is collision-free, which is checked by a 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 (LaValle, 1998) and EST (Hsu et 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.

heading: 4 NEURAL EXPLORATION-EXPLOITATION TREES
text: 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.

heading: 4.1 GUIDED PROGRESSIVE EXPANSION
text: Algorithm 2: NEXT :: Expand(T = (V, E), U) 1 sparent ← argmaxs∈V φ(s) ; . Selection 2 {s1, . . . , sk}
iid.∼ π̃∗(s′|sparent, U) ; . Candidates 3 snew ← argmaxs′∈{s1,...,sk} φ(s
′); . Expansion 4 return sparent, snew; We start with our design of the Expand. We assume having an estimated value function Ṽ ∗(s|U), which stands for the optimal cost from s to target in planning problem U , and a policy π̃∗ (s′|s, U), which generates the promising action s′ from state s. The concrete parametrization of Ṽ ∗ and π̃∗ will be explained in Section 4.2 and learned in Section 4.3. We will use these functions to construct the learnable Expand with explicit exploration-exploitation balancing.
The Expand operator will expand the current search tree T by a 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 sparent. 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 s ∈ V as arms. However, the vanilla UCB algorithm is not directly applicable, since the number of states is increasing as 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, we parametrize the UCB of the reward function as φ (s), and select a node from T according to φ(s)
sparent = argmaxs∈V φ(s) := r̄t (s) + λσt (s) , (3) where r̄t and σt denote the average reward and variance estimator after t-calls to Expand. Denote the sequence of t selected tree nodes so far as St = {s1parent, . . . , stparent}, then we can use kernel
smoothing estimator for r̄t(s) = ∑ s′∈St k(s′,s)r(s′)∑
s′∈St k(s′,s) and σt(s) =
√ log ∑ s′∈St w(s′)
w(s) where k(s ′, s) is a kernel function and w(s) = ∑ s′∈St k(s
′, s). Other parametrizations of r̄t and σt 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.
Expanding a reachable snew in step (ii). Given the selected sparent, we consider expanding a reachable state in the neighborhood sparent as an infinite-armed bandit problem. Although one can first samples k arms uniformly from a neighborhood around sparent and runs a UCB algorithm on the randomly generated finite arms (Wang et al., 2009), such uniform sampler ignores problem structures, and will lead to unnecessary samples. Instead we will employ a policy π̃∗ (s′|s, U)1 for guidance when generating the candidates. The final choice for next move will be selected from these candidates with maxφ (s) defined in (3). As explained in more details in Section 4.2, π̃∗ will be
1In the path planning setting, we use π̃∗ (s′|s, U) and π̃∗ (a|s, U) interchangeably as the action is next state.
𝑠 = 𝑥, 𝑦, 𝜃1, ⋯ , 𝜃𝑁 ∈ ℝ 𝑁+2
𝜇(𝑠) ∈ ℝ3
𝜇(𝑠𝑔𝑜𝑎𝑙) ∈ ℝ 3
Original Planning Space Latent Planning Space
Figure 2: Our neural network model maps a 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 a path using value iteration. The result of value iteration is then used as features for defining Ṽ ∗ (s|U) and π̃∗ (s′|s, U).
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 Figure 1(b) and (c)). Plugging it into the TSA in 1, we construct alg (·) ∈ A which will be learned. The guided progressive expansion bears similarity to MCTS but deals with high dimensional continuous spaces. Moreover, the essential difference lies in the way to select state in T for expansion: the MCTS only expands the leaf states in T 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.

heading: 4.2 NEURAL ARCHITECTURE FOR VALUE FUNCTION AND EXPANSION POLICY
text: In this section, we will introduce our neural architectures for Ṽ ∗ (s|U) and π̃∗ (s′|s, U) used in NEXT :: Expand. The proposed neural architectures can be understood as first embedding the state and problem into a discrete latent representation via an attention-based module in Section 4.2.1, upon which the neuralized value iteration, introduced in Section 4.2.2, is performed to extract features for defining Ṽ ∗ (s|U) and π̃∗ (s′|s, U), as illustrated in Figure 2.

heading: 4.2.1 CONFIGURATION SPACE EMBEDDING
text: Our network for embedding high-dimension configuration space into a latent representation is designed based on an attention mechanism. More specifically, let sw denote the workspace in state and sh denote the remaining dimensions of the state, i.e. s = (sw, sh). sw and sh will be embedded by different sub-neural networks and combined for the final representation, as illustrated in Figure 3. For simplicity of exposition, we will focus on the 2d workspace, i.e., sw ∈ R2. However, our method applies to 3d workspace as well.
• Spatial attention. The workspace information sw will be embedded as µw(sw) ∈ Rd×d, d is a hyperparameter related to map (see remark below). The spatial embedding module (upper part in Figure 3) is composed of kw convolution layers, i.e.,
µw(sw) = softmax2d(fwkw(s w)), fwi+1(s w) = relu(θwi ⊕ fwi (sw)), (4) where θwi denotes the convolution kernels, ⊕ denotes the convolution operator and fwi (sw) ∈ Rd×d×di with di channels. The first layer fw0 is designed to represent sw into a d× d× 4 tensor as fw0 (s w)ij = [s w 1 , s w 2 , i, j], i, j = 1, . . . , d, without any loss of information.
• Configuration attention. The remaining configuration state information will be embedded as µh(sh) through kh fully-connected layers (bottom-left part in Figure 3), i.e.
µh(sh) = softmax(fhkh(s h)), fhi+1(s h) = relu(θhi f h i (s h) + bi),
where µh(sh) ∈ Rda and fh0 (sh) = sh.
The final representation µθ(s) will be obtained by multiplying µw(sw) with µh(sh) element-wisely, µθ(s)ijl = µ
w(sw)ij · µh(sh)l, which is a d × d × da tensor attention map with µθ(s)ijl > 0, and ∑ ijl µθ(s)ijl = 1 (bottom-right part in Figure 3). Intuitively, one can think of da as the level of the learned discretization of the configuration space sh, and the entries in µ softly assign the actual state s to these discretized locations. θ := ({θwi } kw−1 i=0 , {θhi , bi} kh−1 i=0 ) are the parameters to be learned.
Remark (different map size): To process map using convolution neural networks, we resize it to a d× d image, with the same size as the spatial attention in Eq (4), where d is a hyperparameter.

heading: 4.2.2 NEURAL VALUE ITERATION
text: We then apply neuralized value iteration on top of the configuration space embedding to extract further planning features (Tamar et al., 2016; Lee et al., 2018). Specifically, we first produce the embedding µθ(sgoal) of the center of the goal region sgoal. We execute T steps of neuralized Bellman updates (planning module in Figure 4) in the embedding space,
ν∗(t) = min ( W1 ⊕ [ ν∗(t−1), R̃ ]) , with (ν∗(0), R̃) = σ (W0 ⊕ [µθ(sgoal), map]) ,
and obtain ν∗(T ) ∈ Rd×d×da×p. Both W0 and W1 are 3d convolution kernels, min implements the pooling across channels. Accordingly, ν∗(T ) now can be understood as a latent representation of the value function Ṽ ∗(·) in learned embedding space for the problem U with sgoal in map.
To define the value function for particular state s, i.e., Ṽ ∗ (s|U), from the latent representation ν∗(T ), we first construct another attention model between the embedding of state s using µθ(s) and ν∗(T ), i.e., ψ (s)k = ∑ ijl ν ∗(T ) ijlk · µθ (s)ijl, for k = 1, . . . , p. Finally we define Ṽ ∗ (s|U) = hW2 (ψ(s)) , and π̃∗ (s′|s, U) = N (hW3 (ψ(s)) , σ2) (5) where hW2 and hW3 are fully connected dense layers with parameters W2 and W3 respectively, and N (hW3 (ψ(s)) , σ2) is a Gaussian distribution with variance σ2. Note that we also parametrize the policy π̃∗ (s′|s, U) using the embedding ν∗(T ), since the policy is connected to the value function via π∗ (s′|s, U) = argmins′∈S c ([s, s′]) + V ∗ (s′|U). It should also be emphasized that in our parametrization, the calculation of ν∗(T ) only relies on the µθ (sgoal), which can be reused for evaluating Ṽ ∗ (s|U) and π̃∗ (s′|s, U) over different s, saving computational resources. Using this trick the algorithm runs 10×-100× faster empirically. The overall model architecture in alg (·) is illustrated in Figure 4. The parameters W = (W0,W1,W2,W3, θ) will be learned together by our meta self-improving learning. For the details of the parameterization and the size of convolution kernels in our implementation, please refer to Figure 12 in Appendix D.

heading: 4.3 META SELF-IMPROVING LEARNING
text: The learning of the planner alg (·) reduces to learning the parameters in Ṽ ∗ (s|U) and π̃∗ (s′|s, U) and is carried out while planning experiences accumulate. We do not have an explicit training and testing phase separation. Particularly, we use a mixture of RRT :: Expand and NEXT :: Expand with probability and 1 − , respectively, inside the TSA framework in Algorithm 1. The RRT∗ postprocessing step is used in the template. The is set to be 1 initially since {Ṽ ∗, π̃∗} are not well-trained, and thus, the algorithm behaves like RRT∗. As the training proceeds, we anneal gradually as the sampler becomes more efficient.
The dataset Dn = {(Tj , Uj)}nj=1 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; Schaul et al., 2015). For an experience (T , U) ∈ Dn, we can reconstruct the successful path {si}mi=1 from the search tree T (m is the number of segments), and the value of each state si in the path will be the sum of cost to the goal region, i.e., yi := ∑m−1 l=i c([s l, sl+1]). We learn {Ṽ ∗, π̃∗} by optimizing objective
min W ∑ (T ,U)∈Dn `(Ṽ ∗, π̃∗; T , U):=− ∑ Dn m−1∑ i=1 log π̃∗ ( si+1|si ) + m∑ i=1 (Ṽ ∗ ( si ) −yi)22 +λ ‖W‖ 2 . (6)
Algorithm 3: Meta Self-Improving Learning 1 Initialize dataset D0; 2 for epoch n← 1 to N do 3 Sample a planning problem U ; 4 T ← TSA(U) with ∼ Unif [0, 1], and
·RRT :: Expand+(1− )·NEXT :: Expand; Postprocessing with RRT∗ :: Postprocess;
5 Dn ←Dn−1 ∪ {(T , U)} if successful else Dn−1; 6 for j ← 0 to L do 7 Sample (Tj , Uj) from Dn; 8 Reconstruct sub-optimal path {si}mi=1 and the cost of paths based on Tj ; 9 Update parameters
W ←W − η∇W `(Ṽ ∗, π̃∗; Tj , Uj); 10 Anneal = α , α ∈ (0, 1);
The loss (6) pushes the Ṽ ∗ and π̃∗ 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 estimation {Ṽ ∗, π̃∗} is improved based upon the successful outcomes from NEXT itself on previous problems. On the other hand, the updated {Ṽ ∗, π̃∗} will be applied in the next epoch to improve the performance. Therefore, the training is named as Meta Self-Improving Learning (MSIL). Since all the trajectories we collected for learning are feasible, the reachability of the proposed samples is enforced implicitly via imitating these successful paths.
By putting every components together into the learning to plan framework in Eq (2), the overall procedure is summarized in Algorithm 3 and illustrated in Figure 1.

heading: 5 EXPERIMENTS
text: 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-the-art performances, in 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.

heading: 5.1 EXPERIMENT SETUP
text: 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 a 2 DoF (degrees of freedom) point robot, a 3 DoF stick robot and a 5 DoF snake robot, respectively. The last one involves planning a 7 DoF spacecraft in a 3d workspace. For all problems in each benchmark task, the workspace maps were randomly generated from a 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, 2011), BIT∗ (Gammell et al., 2015), CVAE-plan (Ichter et al., 2018), Reinforce-plan (Zhang et al., 2018), and an improved
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 1. In our experiments, we 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 are 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 a fully-connected MLP for the rest state, such that it can be applied to high-dimensional continuous spaces. Please refer to Appendix E for more details.
Settings. For each task, we randomly generated 3000 different 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 once.

heading: 5.2 RESULTS AND ANALYSIS
text: 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 5 (a)-(c) and Figure 6 (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 a 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 18, 19, 20 and 21 in 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-GP) version of NEXT achieves the state-of-the-art 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,
the NEXT algorithm still outperform every competitor by a large margin, no matter learning-based or prefixed heuristic planner, demonstrating the advantages of the proposed NEXT algorithm.
Self-improving. We plot the performance improvement curves of our algorithms on 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-improving, our algorithms are comparable to RRT∗. They then gradually learn from previous experiences and improve themselves as they see more problems and better solutions. In the end, NEXT-KS is able to match the performance of RRT∗-10k using only one-twentieth of its samples, while the competitors perform consistently without any improvements.
Due to the space limits, we put improvement curves on other environments in Figure 17 and the quantitative evaluation in Table 1, 2, and 3 in Appendix F. Please refer to the details there.

heading: 5.3 ABLATION STUDIES
text: Ablation study I: guided progressive expansion. To demonstrate the power of NEXT :: Expand, we replace it with breadth-first 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 s out from the search queue, samples k states from π (·|s), and pushes all generated samples and state s back to the queue, until the goal is reached. For fairness, we use the learned sampling policy π (s′|s, U) by NEXT-KS in BFS. As shown in Figure 7, BFS obtained worse paths with a 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 II: 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 E, 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 of the robot. We provide more preference to the improved GPPN by training it to imitate the near-optimal paths produced by RRT* in the training problems. During test time it is also combined with both versions of the guided progressive expansion operators. As we can see, both GPPN-KS and GPPN-GP are clearly much
worse than NEXT-KS and NEXT-GP, demonstrating the advantage of our proposed attention-based neural architecture in high-dimensional planning tasks.
Ablation study III: learning versus heuristic. The NEXT algorithm in Figure 5 shows similar behavior as 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 be the state space.

heading: 5.4 CASE STUDY: ROBOT ARM CONTROL
text: We conduct a real-world case study on controlling robot arms to move objects on a 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 a 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 of RRT* as the imperfect expert in 3000 training problems. We then evaluate the algorithm on a separated 1000 testing problems. We compare NEXT(KS) with the highly tuned BIT* and RRT* in OMPL, and also CVAE-plan and Reinforce-plan in Figure 8. As seen from the visualization of the found paths in Figure 9, this is a very difficult task. Our NEXT outperforms the baselines by a large margin, requiring only 1 second to reach the same success rate as running 50 seconds of BIT*.
Due to space limits, we put details of the experiment setups, more results and analysis in Appendix F.4.

heading: 6 CONCLUSION
text: In this paper, we propose a self-improving planner, Neural EXploration-EXploitation Trees (NEXT), which can generalize and achieve better performance with experiences accumulated. The algorithm achieves a delicate balance between exploration-exploitation via our carefully designed UCB-type expansion operation. To obtain the generalizable ability across different problems, we proposed a new parametrization for the value function and policy, which captures the Bellman recursive structure in the high-dimensional continuous state and action space. We demonstrate the power of the proposed algorithm by outperforming previous state-of-the-art planners with significant margins on planning problems in a variety of different environments.

heading: ACKNOWLEDGEMENT
text: 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 IIS1350983 to L.S, and by NSF grants BIGDATA 1840866, CAREER 1841569, TRIPODS 1740735, DARPA-PA-18-02-09-QED-RML-FP-003, an Alfred P Sloan Fellowship, a PECASE award to H.L.

heading: B MORE PRELIMINARIES
text: Tree-based sampling planner The tree-based sampling planner algorithm is illustrated in Figure 11. The Expand in Algorithm 1 operator returns an existing node in the tree sparent ∈ V and a new state snew ∈ S sampled from the neighborhood of sparent. Then the line segment [sparent, snew] is passed to function ObstacleFree for collision checking. If the line segment [sparent, 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 to the tree edge set E . If the newly added node snew has reached the target Sgoal, the algorithm will return. Optionally, some concrete algorithms can define a Postprocess operator to refine the search tree. For an example of the Expand operator, as shown in Figure 1 (c), since there is no obstacle on the dotted edge [sparent, snew], i.e., snew is reachable, the new state and edge will be added to the search tree (connected by the solid edges).
Now we will provide two concrete algorithm examples. For instance,
• If we instantiate the Expand operator as Algorithm 4, then we obtain the rapidly-exploring random trees (RRT) algorithm (LaValle, 1998), which first samples a state s from the configuration space
Algorithm 4: RRT :: Expand(T , U) Data: T = (V, E), U = (sinit,Sgoal,S,Sfree, map, c(·))
1 srand ← Unif(S); . Sample configuration space 2 sparent ← argmins∈V ‖srand − s‖; . Pull to a tree node 3 snew ← argmins∈B(sparent,η) ‖s− srand‖; 4 return sparent, snew;
Algorithm 5: EST :: Expand(T , U) Data: T = (V, E), U = (sinit,Sgoal,S,Sfree, map, c(·))
1 sparent ∼ φ(s), s ∈ V; . Sample a tree node 2 snew ← Unif(B(sparent)); . Sample neighborhood 3 return snearest, snew;
S and then pulls it toward the neighborhood of current tree T measured by a ball of radius η: B(s, η) = {s′ ∈ S | ‖s′ − s‖ 6 η}.
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-space trees (EST) algorithm (Hsu et al., 1997; Phillips et al., 2004), which samples a state s from the nodes of the existing tree, and then draw a 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 r̄i and the visitation count ni for each arm. After T rounds of trials, the UCB algorithm will maintain a set of information {(r̄i, ni)}Ki=1 with ∑K i=1 ni = T . Then, for the next round, the UCB algorithm will select the next arm based on the one-sided confidence interval estimation provided by the Chernoff-Hoeffding bound,
a∗T+1 = argmaxi∈{1,...,K} r̄i + λ √ log T ni , (7)
where λ controls the exploration-exploration trade-off. It has been shown that the UCB algorithm achieves O (log T ) regret. However, the MCTS is not directly applicable to continuous state-action spaces.
There have been many attempts to generalize the UCB and UCT algorithms to 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 a 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 et al., 2009). 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 in path planning tasks.
Although these off-the-shelf algorithms are not directly applicable to our path planning setting, their successes show the importance of exploration-exploitation trade-off and will provide the principles for our algorithm for continuous state-action planning problems.
Planning networks Value iteration networks (Tamar et 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 a ∑ s′ P (s′|s, a)(c ([s, s′]) + V ∗ (s′|U)). (8)
where P (s′|s, 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
value function V ∗(s′|U) can be represented as 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) = 0 for s′ /∈ B(s), it resembles a set of convolution kernels, each indexed by a discrete action a. And the Bellman update operator essentially convolves P (s′|s, a) with c([s, s′]) and V ∗(s′|U), and then performs a min-pooling operation across the convolution channels.
Inspired by the above computation pattern of the Bellman operator, value iteration networks design the neural architecture as follows, Ṽ ∗0 = min ( W1 ⊕ [ map, R̃ ]) (9)
Ṽ ∗t = min ( W1 ⊕ [ Ṽ ∗t−1, R̃ ]) (10)
where ⊕ is the convolution operation, both map, Ṽ ∗t and R̃ are d× d matrices, and the parameter W1 are kc convolution kernels of size k × k. The min implements the pooling across kc convolution channels.
The gated path planning networks (GPPN) (Lee et al., 2018) improves the VIN by replacing the VIN cell (9) with the well-established LSTM update, i.e.,
Ṽ t, c̃t = LSTM (∑( W1 ⊕ [ Ṽ t, R̃ ]) , c̃t ) , (11)
where the summation is taking over all the kc convolution channels. After constructing the VIN and GPPN, the parameters of the model, i.e., { R̃,W1 } 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-dimension planning tasks.

heading: C PARAMETRIZED UCB ALGORITHMS
text: We list two examples of parametrized UCB as the instantiation of (3) used in GPE:
• GP-UCB: The GP-UCB Chu et al. (2011) is derived by parameterizing via Gaussian Processes (GP) with kernel k (s, s′), i.e., E [r (s) |T , U ] ∼ GP (0, k), GP-UCB maintains an UCB of the reward after t-step as
φ (s) := r̄t (s) + λσt (s) , (12) where
r̄t (s) = kt (s) (Kt + αI) −1 rt,
σ2t (s) = k (s, s)− kt (s) > (Kt + αI) −1 kt (s) ,
with kt (s) = [k (si, s)]si∈St ,Kt = [k (s, s ′)]s,s′∈St , and St = {s1, s2, . . . , st} denotes the sequence of selected nodes in current trees. The variance estimation σ2t (s) takes the number of visits into account in an implicit way: the variance will reduce, as the neighborhood of s is visited more frequently (Srinivas et al., 2009).
• KS-UCB: We can also use kernel regression as an alternative parametrization for (7) (Yee et al., 2016), which leads to an UCB of the reward after t-step as
φ (s) := r̄t (s) + λσt (s) , (13) where
r̄t [s] =
∑ s′∈St k (s
′, s) r (s′)∑ s′∈St k (s ′, s) ,
σt (s) =
√ log ∑ s′∈St w (s ′)
w (s) , with w (s) = ∑ s′∈St k (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.

heading: D POLICY AND VALUE NETWORK ARCHITECTURE
text: We explain the implementation details of the proposed parametrization for policy and value function. Figure 12 and Figure 13 are neural architectures for the attention module, the policy/value network, and the planning module, respectively.

heading: Loop 𝑇 times
text: 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 colors for different operations. In particular, we use blue for convolutional/LSTM layers, green for dense layers, and orange for anything else. For convolutional layers, "Conv 1× 1, 32, relu" denotes a layer with 1× 1 kernels, 32 channels, followed by a 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 12-left) embeds a state to a d× d× da tensor. The planning module (Figure 13) is 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× d locations share one set of parameters and are processed by the LSTM in 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, we set the values of the hyper-parameters to be (d, de, da, p) = (15, 64, 8, 8).

heading: E EXPERIMENT DETAILS

heading: E.1 BENCHMARK ENVIRONMENTS
text: We used four benchmark environments in our experiment. For the first three, the workspace dimension is 2d. We generated the maze maps with the recursive backtracker algorithm using the following implementation: https://github.com/lileee/gated-path-planning-networks/blob/master/generate_dataset.py. Examples of the workspace are shown in Figure 15. 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 a thin rectangle, is used here. The extra rotation dimension is added to the planning problem. This robot can rotate and move freely without any constraints in the free space. • 3-link snake (5d). The robot is a 5 DoF snake with two joints. Two more angle dimensions are
added to the planning task. To prevent links from folding, we restrict the angles to the range of [−π/4, π/4].
The fourth environment has a 3d workspace. Cuboid obstacles were generated uniformly randomly in space with density ≈ 20%. Example of the workspace is shown in Figure 6 and 16, where the blue cuboids are obstacles. The environment is described below:
• Spacecraft planning (7d). The robot is a spacecraft with a cuboid body and two 2 DoF arms connecting to two opposite sides of the body. There is a 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, π/2]. The spacecraft itself cannot rotate.

heading: E.2 HYPERPARAMETER FOR MSIL
text: During self-improving 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 i < 1000, 0.5− 0.1 · b(i− 1000)/200c, if 1000 6 i < 2000, 0.1, otherwise,
with i denoting the problem number.

heading: E.3 BASELINE: THE IMPROVED GPPN
text: The original GPPN is not directly applicable to our experiments. Inspired by Tamar et al. (2016), we add a fully-connected 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
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*.

heading: F EXPERIMENT RESULTS

heading: F.1 SOLUTION PATH ILLUSTRATION

heading: F.2 DETAILS OF QUANTITATIVE EVALUATION
text: More detailed results are shown in Table 1, 2, 3, including learning-based and non-learning-based ones, on the last 1000 problems in each experiment. We normalized the number of collision checks and the cost of paths based on the solution of RRT∗. The success rate result is not normalized. The
best planners in each experiment are in bold. NEXT-KS and NEXT-GP outperform the current state-of-the-art planning algorithm with large margins.
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 in 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 Ṽ ∗ and π̃∗.

heading: F.3 SEARCH TREES COMPARISON
text: We illustrate the search trees generated by RRT* and the proposed NEXT algorithms with 500 samples in Figure 18, Figure 19, Figure 20 and Figure 21 on 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 to the search trees generated by RRT∗ side by side, we can clearly see the advantages and the efficiency of the proposed NEXT algorithms. In all the tasks, even in 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.

heading: F.4 CASE STUDY DETAILS
text: We conduct a real-world case study on controlling robot arms to move objects on a shelf. This is a representative of common scenarios in practice where the robot needs to 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 to evaluate how much can we improve on the wall-clock time by learning from similar planning problems.

heading: F.4.1 TASK DESCRIPTION
text: We generate planning problems randomly to form the training set and test set. In each planning task, there is a 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 in Figure 22. Both the start and goal configurations are randomly sampled from a 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 a path for the 7 DoF robot arm to move from a location in one bin to another, i.e., 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.

heading: F.4.2 BASELINES AND TRAINING
text: For traditional planners, we include C++ OMPL (Şucan et al., 2012) implementation of BIT* (Gammell 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.

heading: F.4.3 RESULTS
text: 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 in Figure 8 and recorded in Table 4 and Table 5. The solution paths found by NEXT and BIT* are illustrated in Figure 23. In terms of both success rate and solution path quality, NEXT dominates all the planners under all time limits.

Review summaries:
Motion-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.