PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning to Plan in High Dimensions via Neural Exploration-Exploitation Trees

Binghong Chen, Bo Dai, Qinjie Lin, Guo Ye, Han Liu, Le Song

arXiv:1903.00070v4cs.LGcs.ROstat.ML

TL;DR

High-dimensional continuous path planning needs methods that use prior experience without losing online adaptability. NEXT learns problem structure with a neural architecture, integrates that guidance into a UCB-style exploration–exploitation procedure, and outperforms prior planners across benchmark environments while improving from accumulated experience.

  • Problem

    Existing high-dimensional planners may require many samples, while prior experience is often discarded or difficult to generalize across related problems.

    Source: §1 · p. 1

  • Method

    NEXT learns promising search directions from prior planning problems and combines neural value and policy guidance with a UCB-style expansion algorithm.

    Source: §1 · p. 2, §4.2.2 · p. 6

  • Results

    NEXT achieves state-of-the-art performance across collision-check cost, success rate, and solution-path cost, outperforming competitors by a large margin across test environments.

    Source: §5.2 · pp. 8–9

  • Takeaways & Limitations

    NEXT can improve with accumulated experience, ultimately matching RRT*-10k performance on a 5d task using one-twentieth of its samples.

    Source: §5.2 · p. 9

    The learning-to-plan formulation assumes training problems are sampled from a problem distribution U.

    Source: §2 · p. 3

Abstract

from arXiv · show

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.

1 INTRODUCTION

High-dimensional path planning needs sample-efficient methods that can exploit shared structure across related problems rather than relying on uniform or manually designed sampling. NEXT learns generalizable search guidance and combines it with online exploration–exploitation balancing to improve planning efficiency.

1 INTRODUCTION

  • High-dimensional planning methods avoid explicit discretization, but generic uniform sampling can require many samples for feasible solutions, while hand-designed heuristics may not transfer reliably.Sampling-based methods such as PRM and RRT scale better than grid search, but their generic proposals ignore problem structure.Source: §1 · p. 1
  • Prior online and learning-based planners often discard experience across problems or depend on special features, parameters, or restricted discrete settings.These limitations hinder generalization to new continuous-state and continuous-action planning problems.Source: §1 · pp. 1–2
  • NEXT learns generalizable problem structures with an attention-based architecture, produces promising search directions, and integrates them into a UCB-style algorithm for online exploration–exploitation balance.The architecture embeds high-dimensional continuous spaces into low-dimensional discrete spaces and is learned end-to-end.Source: §1 · p. 2
  • NEXT uses prior experience to reduce required samples and significantly outperform previous state-of-the-art planners on several benchmark tasks.The paper presents this as an empirical result across high-dimensional planning problems.Source: §1 · p. 2

1.1 RELATED WORKS

  • Hand-coded heuristics incorporate human prior knowledge but remain fixed, while existing learned search heuristics are restricted to discrete domains or add unnecessary computation.This motivates a learned planner that can adapt its guidance across continuous planning problems.Source: §1.1 · p. 2
  • Experience-reusing non-learning planners can exploit prior search graphs, but they are designed for largely fixed obstacles and do not generalize to unseen tasks from the same distribution.Source: §1.1 · p. 2

2 SETTINGS FOR LEARNING TO PLAN

The paper formulates planning as finding a low-cost collision-free path and learning an algorithm that efficiently produces near-optimal paths across a distribution of problems. NEXT combines this learning objective with a tree-based planning framework and iterative experience-driven updates.

2 SETTINGS FOR LEARNING TO PLAN

  • The planning objective is to find a minimum-cost path from the initial state to the goal region while remaining in free space.Paths are represented nonparametrically as sequences of interconnected segments, with additive segment costs.Source: §2 · pp. 2–3
  • The learning-to-plan objective selects an algorithm that minimizes expected path-quality and planning-efficiency loss over sampled problems.Search-tree size is given as one example of an efficiency-related loss.Source: §2 · p. 3
  • NEXT is formed by composing a tree-based sampling template, an attention-based neural parametrization, an exploration–exploitation mechanism, and a meta-learning procedure.The components are introduced across the subsequent sections and combined into the final planner.Source: §2 · p. 3
  • Figure 1 depicts interactive planning and learning: a search tree grows under learned value and policy guidance, which are updated using the successful path.The process repeats across randomly generated planning problems.Source: Figure 1 · p. 3, §2 · p. 3

3 PRELIMINARIES

Tree-based sampling planners maintain a search tree rooted at the start state and expand it with collision-free samples until reaching the goal. NEXT extends this template with a learnable expansion operator that uses prior experience to bias exploration toward promising regions.

3 PRELIMINARIES

  • Tree-based sampling algorithms incrementally connect sampled states into a tree rooted at the initial state and extract a feasible path when a leaf reaches the goal.Source: §3 · p. 3
  • The Expand operator generates a new state and parent, requiring the connecting edge to be collision-free so the tree remains feasible.Different Expand operators recover methods such as RRT and EST.Source: §3 · p. 4
  • Existing tree-based samplers solve problems independently from scratch and ignore useful experience from similar environments.NEXT introduces neural components that bias expansion toward more promising regions using past successful experiences.Source: §3 · p. 4

4 NEURAL EXPLORATION-EXPLOITATION TREES

NEXT combines a learnable neural Expand operator with UCB-style tree selection, embedding high-dimensional planning problems into a low-dimensional latent space for guided search. Its neural value and policy models are trained online from successful planning trajectories through meta self-improving learning.

4 NEURAL EXPLORATION-EXPLOITATION TREES

  • NEXT introduces a neural Expand operator that balances exploration and exploitation for high-dimensional continuous-state planning, with self-improving training integrated into the tree-search framework.The operator is learned from prior experience and instantiated within the TSA framework.Source: §4 · p. 4, §4.3 · p. 7

4.1 GUIDED PROGRESSIVE EXPANSION

  • The guided expansion first selects a tree state with a contextual UCB score, then generates reachable neighboring candidates using the learned policy and chooses among them by the same score.The average reward favors promising states, variance favors less-visited states, and λ controls their exploration-exploitation trade-off.Source: §4.1 · p. 4
  • Unlike MCTS, NEXT can expand from each visited tree state rather than only leaf states, avoiding hierarchical traversal constraints and extra UCB sampling for internal nodes.This design is presented as particularly suitable for path planning in high-dimensional continuous spaces.Source: §4.1 · p. 5

4.2.1 CONFIGURATION SPACE EMBEDDING

  • The neural architecture embeds high-dimensional configuration states into a discrete latent representation using separate spatial and remaining-configuration networks combined by attention.Spatial information is processed with convolutional layers, while the remaining state dimensions use fully connected layers; the method also applies to 3D workspaces.Source: §4.2.1 · pp. 5–6

4.2.2 NEURAL VALUE ITERATION

  • Neural value iteration operates in the learned embedding space, and its latent output supplies features for the state-value estimate and Gaussian expansion policy.The goal embedding is reused across states, which the authors report makes the algorithm run 10×-100× faster empirically.Source: Figure 2 · p. 5, §4.2.2 · p. 6

4.3 META SELF-IMPROVING LEARNING

  • Meta Self-Improving Learning updates the value and policy models from successful paths collected across prior planning problems, without an explicit train-test phase separation.Training begins with RRT* behavior when the neural models are untrained, then gradually reduces the RRT* mixture as the learned sampler improves.Source: §4.3 · p. 7

5 EXPERIMENTS

NEXT is evaluated on high-dimensional planning benchmarks, where it learns from prior problems and guides search toward promising regions. Across benchmark comparisons, ablations, and a robot-arm case study, it achieves strong solution quality and sample or time efficiency.

5.1 EXPERIMENT SETUP

  • The evaluation uses four randomly generated benchmark tasks spanning 2 DoF, 3 DoF, 5 DoF, and 7 DoF robots, with success, collision checks, and path cost as metrics.Learning-based methods are trained on 2,000 problems and tested on 1,000 held-out problems; NEXT updates its parameters every 200 training problems.Source: §5.1 · pp. 7–8, §5.2 · p. 8

5.2 RESULTS AND ANALYSIS

  • NEXT achieves state-of-the-art success rate, collision-check efficiency, and solution-path quality across all four test environments, outperforming learning-based and heuristic planners.Both NEXT-KS and NEXT-GP achieve these results with at most 500 samples; BIT* performs well on the 7 DoF task but remains behind NEXT.Source: §5.2 · pp. 8–9, Figure 7 · p. 9
  • NEXT-KS matches RRT∗-10k performance on the 5d task using one-twentieth as many samples after improving through prior planning experiences.The algorithms initially perform comparably to RRT∗, then NEXT improves as it observes more problems and better solutions, whereas competitors remain consistent.Source: §5.2 · p. 9

5.3 ABLATION STUDIES

  • Replacing guided progressive expansion with BFS produces worse paths, more collision checks, and lower success, supporting the importance of NEXT's exploration-exploitation balance.The ablation retains NEXT-KS's learned sampling policy while changing the expansion strategy.Source: §5.3 · p. 9
  • Replacing NEXT's attention-based architecture with improved GPPN yields substantially worse performance, demonstrating the architecture's advantage for high-dimensional planning.The improved GPPN receives additional continuous-action modeling and imitation training from near-optimal RRT∗ paths.Source: §5.3 · pp. 9–10

5.4 CASE STUDY: ROBOT ARM CONTROL

  • In robot-arm shelf planning with a fixed robot base, NEXT reaches the same success rate as BIT* in 1 second that BIT* reaches in 50 seconds, outperforming the baselines by a large margin.The case study uses 3,000 training problems and 1,000 separate testing problems, comparing NEXT(-KS) with BIT*, RRT*, CVAE-plan, and Reinforce-plan.Source: §5.4 · p. 10, Figure 8 · p. 10

6 CONCLUSION

NEXT is presented as a self-improving planner that learns generalizable value and policy representations from accumulated experience while balancing exploration and exploitation. The paper motivates this design through high-dimensional planning challenges, tree-based sampling, parametrized UCB methods, and neural planning architectures.

6 CONCLUSION

  • NEXT combines a UCB-type expansion rule with learned value and policy representations to generalize across planning problems and improve with accumulated experience.Its parametrization captures Bellman recursive structure in high-dimensional continuous state and action spaces.Source: §6 · p. 10

A ILLUSTRATION OF THE DIFFICULTY IN PLANNING PROBLEMS

  • High-dimensional planning is difficult because grid-based graph search does not scale with state-space dimension, motivating sampling-based methods.A stick robot example shows that adding rotation creates an irregular three-dimensional configuration space even when the workspace appears simple.Source: A ILLUSTRATION OF THE DIFFICULTY IN… · p. 15

B MORE PRELIMINARIES

  • Tree-based sampling planners expand a tree by sampling a nearby state, collision-checking the connecting segment, and adding reachable states until the goal is reached.RRT and EST arise from different choices of the Expand operator, while postprocessing can yield asymptotic optimality for RRT*.Source: B MORE PRELIMINARIES · pp. 15–16
  • Classical UCB methods select actions using reward estimates and confidence bonuses, but their direct use is difficult in continuous state-action spaces.Continuous extensions and MCTS techniques can impose extra optimization or hierarchical structure that reduces exploration efficiency for path planning.Source: B MORE PRELIMINARIES · p. 16
  • Planning networks embed Bellman-style value iteration into neural architectures, but their direct applications are restricted to low-dimensional tasks.Their success motivates neural representations for high-dimensional planning.Source: B MORE PRELIMINARIES · pp. 16–17

C PARAMETRIZED UCB ALGORITHMS

  • Parametrized UCB methods use correlations among observed states to form generalizable confidence estimates that promote exploration of less-visited regions.GP-UCB uses Gaussian-process uncertainty, while KS-UCB uses kernel regression.Source: C PARAMETRIZED UCB ALGORITHMS · p. 17

D POLICY AND VALUE NETWORK ARCHITECTURE

NEXT uses an attention-based neural architecture to process planning inputs and produce policy and value outputs. Its planning module applies a shared one-step LSTM update across spatial locations.

D POLICY AND VALUE NETWORK ARCHITECTURE

E.1 BENCHMARK ENVIRONMENTS

The experiments evaluate NEXT across four planning environments spanning 2d to 7d configuration spaces and multiple robot morphologies. They also specify self-improving training, an improved GPPN baseline, and qualitative solution-path examples.

E.1 BENCHMARK ENVIRONMENTS

  • The benchmark suite covers workspace planning, rigid-body navigation, 3-link snake planning, and 7d spacecraft planning.The first three use 2d workspaces with 2, 3, and 5 DoF robots, while the spacecraft task uses a 3d workspace and 7 DoF.Source: §E.1 · p. 19
  • The rigid-body and snake tasks add rotation or joint-angle dimensions, while the spacecraft includes a cuboid body and two 2 DoF arms with restricted rotations.Snake joint angles are restricted to [−π/4, π/4], and spacecraft rotation angles are restricted to [0, π/2].Source: §E.1 · p. 19

E.2 HYPERPARAMETER FOR MSIL

  • During self-improvement on the first 2000 problems, NEXT updates its parameters and anneals epsilon every 200 problems.The schedule sets epsilon to 1 before problem 1000, decreases it from 0.5 after problem 1000, and reaches 0.1 thereafter.Source: §E.2 · p. 19

E.3 BASELINE: THE IMPROVED GPPN

  • The improved GPPN processes discretized workspace locations and combines them with full robot configurations through an MLP to estimate actions and values.It is trained using near-optimal paths produced by RRT*.Source: §E.3 · pp. 19–20, Figure 14 · p. 20

F.1 SOLUTION PATH ILLUSTRATION

  • NEXT produces solution paths for workspace, rigid-body, snake, and spacecraft planning tasks, with start and goal locations shown in the visualizations.The examples span 2d, 3d, 5d, and 7d planning settings.Source: Figure 15 · p. 20, Figure 16 · p. 20

F.2 DETAILS OF QUANTITATIVE EVALUATION

NEXT-KS and NEXT-GP outperform current state-of-the-art planners across the reported quantitative evaluations, while performance improves with additional experience. Search-tree visualizations and a real-world robot-arm case study further emphasize efficiency and wall-clock advantages.

F.2 DETAILS OF QUANTITATIVE EVALUATION

  • NEXT-KS and NEXT-GP outperform the current state-of-the-art planning algorithm with large margins across the experiments.The evaluation reports success rate, normalized collision checks, and normalized path cost on the final 1000 problems.Source: §F.2 · pp. 20–21
  • NEXT-KS achieves the best success rate, the best collision-check performance in three benchmarks, and the best path solutions in the reported tables.Higher success rate is better, whereas collision checks and normalized path cost are lower-is-better metrics.Source: Table 1 · p. 21, Table 2 · p. 21, Table 3 · p. 21
  • NEXT-KS and NEXT-GP improve as more experiences are collected, supporting the reported self-improvement ability through learned value and policy functions.The improvement curves cover 2d workspace planning and 3d rigid-body navigation, with similar behavior reported for the 5d snake task.Source: §F.2 · p. 21, Figure 17 · p. 22

F.3 SEARCH TREES COMPARISON

  • With 500 samples, NEXT search trees move toward goals and produce high-quality solutions, whereas RRT* trees search randomly and can fail to complete the missions.The comparison spans 2d workspace, 3d rigid-body, 5d snake, and 7d spacecraft tasks.Source: §F.3 · p. 21, Figure 18 · p. 22, Figure 19 · p. 23

F.4 CASE STUDY DETAILS

  • The robot-arm shelf case study evaluates how learning from similar problems improves real-time wall-clock performance.The task involves moving objects between bins on a multi-level shelf.Source: §F.4 · p. 25

F.4.1 TASK DESCRIPTION

The evaluation uses randomly generated 7-DoF robot-arm shelf-planning problems in OpenRave, with separate training and testing sets. NEXT is compared against tuned traditional and learning-based planners, using BIT* as its imperfect training expert.

F.4.1 TASK DESCRIPTION

  • Shelf environments vary through randomly drawn level heights and bin widths, while start and goal configurations are sampled from the reachable region.The planning environment is created with the OpenRave simulator.Source: §F.4.1 · p. 25
  • The task is to plan a 7-DoF arm path between different shelf bins with a fixed robot base, using 3000 training and 1000 testing problems.Shelf levels, bin widths, and start and goal configurations are randomly sampled within the robot's reachable region.Source: §F.4.1 · p. 25

F.4.2 BASELINES AND TRAINING

  • NEXT is evaluated against tuned OMPL implementations of BIT* and RRT*, plus the learning-based planners CVAE-plan and Reinforce-plan.CVAE-plan uses supervision generated by the tuned BIT* planner, which also serves as NEXT's imperfect expert during training.Source: §F.4.2 · p. 25

F.4.3 RESULTS

Across ten time limits, NEXT dominates all evaluated planners in both success rate and solution path quality. Visual comparisons show NEXT solutions alongside BIT* solutions, including substantially shorter completion time on the hardest problems.

F.4.3 RESULTS

  • NEXT dominates all planners in both success rate and solution path quality under every evaluated time limit.Success rates and average path costs are reported in the supplied tables and figures.Source: §F.4.3 · p. 25, Table 4 · p. 26, Table 5 · p. 26
  • Figure 22 shows examples of different shelves sampled from the environment distribution.These examples illustrate the variability of the evaluated shelf configurations.Source: Figure 22 · p. 25
  • NEXT completes each robot-arm problem in 5 seconds, whereas BIT* requires 250 seconds to find a solution on the hardest problems.The comparison concerns the last two planning-problem columns shown in the solution-trajectory figure.Source: Figure 23 · p. 26
  • Figure 23 contrasts NEXT(-KS) solution trajectories in the first row with BIT* trajectories for the same four planning problems in the second row.The figure presents matched solution-path examples rather than aggregate metrics.Source: Figure 23 · p. 26

Related papers

Loading 1903.00070v4…