PaperlayerView exact revision on arXiv

Source-linked AI summary

Asymptotically near-optimal RRT for fast, high-quality, motion planning

Oren Salzman, Dan Halperin

arXiv:1308.0189v4cs.RO

TL;DR

Motion planning needs high-quality paths, while RRT may find solutions quickly without improving quality and RRG may fail within limited time. LBT-RRT uses bounded approximation and selective edge validation to interpolate between RRT and RRG, producing higher-quality paths than RRT while retaining fast solution finding.

  • Problem

    High-quality motion planning is difficult, while RRT may not improve path quality and RRG may fail to construct a solution within limited time.

  • Method

    LBT-RRT combines a tree subgraph of the RRG roadmap with a lower-bound graph, using an approximation factor and edge-quality estimates to avoid unnecessary local-planner calls.

  • Results

    LBT-RRT converges within a factor of (1+ε) of the optimum and interpolates between RRG at ε = 0 and RRT at ε = ∞; in alternating barriers, it matched RRT* path quality at 50 seconds while reaching 70% success.

  • Takeaways & Limitations

    LBT-RRT supports anytime planning by finding feasible paths quickly while continuing to search for higher-quality solutions, with the lazy goal-biased variant using dynamic shortest-path algorithms.

Abstract

from arXiv · show

We present Lower Bound Tree-RRT (LBT-RRT), a single-query sampling-based algorithm that is asymptotically near-optimal. Namely, the solution extracted from LBT-RRT converges to a solution that is within an approximation factor of 1+epsilon of the optimal solution. Our algorithm allows for a continuous interpolation between the fast RRT algorithm and the asymptotically optimal RRT* and RRG algorithms. When the approximation factor is 1 (i.e., no approximation is allowed), LBT-RRT behaves like RRG. When the approximation factor is unbounded, LBT-RRT behaves like RRT. In between, LBT-RRT is shown to produce paths that have higher quality than RRT would produce and run faster than RRT* would run. This is done by maintaining a tree which is a sub-graph of the RRG roadmap and a second, auxiliary graph, which we call the lower-bound graph. The combination of the two roadmaps, which is faster to maintain than the roadmap maintained by RRT*, efficiently guarantees asymptotic near-optimality. We suggest to use LBT-RRT for high-quality, anytime motion planning. We demonstrate the performance of the algorithm for scenarios ranging from 3 to 12 degrees of freedom and show that even for small approximation factors, the algorithm produces high-quality solutions (comparable to RRG and RRT*) with little running-time overhead when compared to RRT.

I. INTRODUCTION AND RELATED WORK

Sampling-based planners made previously infeasible motion-planning problems tractable, but producing high-quality paths remains difficult. Existing approaches trade off rapid feasibility, path refinement, and asymptotic optimality.

  • Motivation: Sampling-based planners such as PRM and RRT enabled solving motion-planning problems previously considered infeasible.Motion planning supports applications including surgical planning, computational biology, exploration, search-and-rescue, and warehouse management.
  • Motivation: RRT and PRM may produce solutions far from optimal, motivating variants and heuristics for higher-quality paths.Path quality can involve length, clearance, smoothness, energy, or combinations of these criteria.
  • High-quality planning: Post-processing methods improve paths locally through shortcutting, while path hybridization can combine multiple paths into a higher-quality path.Shortcutting often remains in the original path’s homotopy class, whereas hybridization may construct a higher-quality path from several lower-quality paths.
  • Anytime planning: Online optimization heuristics modify sampling or connection strategies, and other anytime approaches alternate exploration, refinement, shortcutting, or hybridization.Anytime motion planning seeks a solution quickly and refines it when additional time permits.
  • Asymptotic optimality: RRG and RRT* are asymptotically optimal, unlike RRT and PRM, whose solutions do not converge to the optimal path with probability one.RRG and RRT* modify how new samples connect to the existing data structure.
  • Asymptotic near-optimality: Asymptotic near-optimality relaxes optimality by requiring convergence within a factor of (1 + ε) of the optimum, supporting faster planning.This relaxation addresses the trade-off between solution quality and running time in anytime settings.

B. Contribution

The paper introduces LBT-RRT, a single-query sampling-based planner designed to balance RRT’s speed with RRG’s asymptotic optimality. It maintains two roadmaps and targets high-quality solutions with limited running-time overhead.

  • Contribution: LBT-RRT is a single-query sampling-based algorithm whose solution converges within a factor of (1 + ε) of the optimal solution.The approximation factor controls the allowed suboptimality.
  • Contribution: LBT-RRT interpolates between RRG when ε = 0 and RRT when ε = ∞.At ε = 0, no approximation is allowed; with an unbounded approximation factor, the maintained tree matches RRT’s tree.
  • Contribution: The algorithm maintains an approximation tree and a lower-bound graph over the same vertices but with different edge sets.The lower-bound graph may contain infeasible paths, while the approximation tree provides feasible paths within the approximation factor.
  • Evaluation: Experiments across scenarios with 3 to 12 degrees of freedom produced solutions comparable to RRG and RRT* with little running-time overhead relative to RRT.The paper presents the method as suitable for high-quality, anytime motion planning.
  • Paper scope: This paper extends the 2014 conference version with additional experiments, framework extensions, and a fix for an oversight concerning the lower-bound roadmap.The paper describes the oversight and its correction in Section III.

B. Algorithmic background

RRT, RRG, and RRT* share a sampling-and-extension structure but differ in how they connect each new milestone to nearby vertices. RRT uses one edge, whereas RRG and RRT* consider logarithmically many neighbors.

  • Shared structure: RRT, RRG, and RRT* sample a free configuration, find its nearest roadmap vertex, steer toward it, and add the new configuration when the path is collision-free.A stopping criterion may be a sample count or a fixed time budget.
  • RRT: RRT adds only the directed edge from the nearest vertex to the new vertex.This connection scheme distinguishes RRT from the neighbor-based schemes of RRG and RRT*.
  • RRG and RRT*: RRG and RRT* consider k_RRG log(|V|) nearest neighbors of each new vertex, with RRG checking candidate connections for collision freedom.RRG adds both directions when a candidate connection is collision-free.

T .V, kRRG log(|T .V |))

LBT-RRT combines a feasible approximation tree with a lower-bound graph whose dynamic shortest paths guide selective edge validation. Its invariants bound the tree’s cost while avoiding unnecessary local-planner calls.

  • Background: RRT* maintains a sub-graph of the RRG roadmap through local rewiring, while RRG’s path cost is a lower bound on RRT*’s path cost for the same samples.RRG requires additional memory and local-planner calls, increasing running time.
  • Motivation: RRG and RRT* incur O(k_RRG log(|V|)) additional local-planner calls at each stage to support asymptotic optimality.LBT-RRT instead estimates edge quality before deciding whether validation is needed.
  • LBT-RRT: LBT-RRT maintains Glb and T_apx over the same vertices, with Glb as a graph and T_apx as a tree rooted at x_init.The subscripts denote lower bound and approximation.
  • Invariants: The bounded approximation invariant requires cost_Tapx(x) ≤ (1 + ε) · cost_Glb(x) for every node represented in both structures.This invariant limits the approximation tree’s cost relative to the lower-bound graph.
  • Invariants: The lower-bound invariant requires cost_Glb(x) ≤ cost_GRRG(x), maintained by ensuring GRRG’s edges are included in Glb.Glb may additionally contain edges that GRRG considered but found to be in collision.
  • Edge processing: When candidate edges are inserted into Glb, dynamic shortest-path updates identify affected vertices and queue nodes whose bounded approximation invariant may be violated.The queue is ordered by increasing cost_Glb, and processing can update T_apx or remove invalid Glb edges after collision checks.

C. Analysis

LBT-RRT maintains a lower-bound graph and approximation tree whose invariants support asymptotic near-optimality. Its analysis establishes termination and a runtime bound parameterized by dynamic shortest-path updates.

  • Every RRG edge is added to the lower-bound graph, while approximation-tree edges remain collision free.
  • The consider_edge procedure preserves the bounded approximation invariant after each call by updating the approximation tree or deleting invalid lower-bound edges.
  • O(n log n) iterations suffice for the queue-processing loop to terminate because each node has degree O(log n).
  • LBT-RRT is asymptotically near-optimal, with path cost converging almost surely to at most (1 + ε) times the optimal cost.
  • The total runtime is O(δ̂ · n log^2 n), while non-SSSP operations have the same O(n log n) order as RRG; practical runtime is often dominated by local planning.

D. Implementation details

Two implementation optimizations reduce unnecessary work by prioritizing promising neighbors and avoiding edge insertions that would immediately be removed.

  • Ordering X_near by lower-bound cost lets the algorithm test the most promising neighbor first and stop after finding an edge that satisfies the invariant.
  • Before invoking dynamic shortest-path insertion, the algorithm checks whether the bounded approximation invariant would be violated and validates collision freedom first.

E. Discussion

LBT-RRT targets the trade-off between RRT’s fast feasibility and RRG’s or RRT*’s higher path quality. The paper also documents and fixes an earlier implementation oversight that invalidated near-optimality.

  • RRG may fail to find a solution within limited time, whereas RRT finds one quickly but does not improve its quality for a single-configuration goal.
  • LBT-RRT seeks a feasible path quickly while continuing to search for higher-quality paths.
  • The conference version stored a locally rewired tree instead of the lower-bound graph, so its local invariant test missed descendant cost changes and lacked asymptotic near-optimality.
  • The revised LBT-RRT is reported to be asymptotically near-optimal and to converge to high-quality solutions faster than the original algorithm.

IV. EVALUATION

Experiments evaluate LBT-RRT against RRT, RRG, RRT*, and RRT+RRT* under fixed time budgets across motion-planning scenarios. Results show a speed–quality trade-off in which LBT-RRT approaches RRT* quality with moderate overhead.

  • Experimental setup: The evaluation covers scenarios with 3, 6, and 12 degrees of freedom and averages each result over 100 runs.
  • Scenarios: The Alternating barriers scenario uses a free-flying robot with three perpendicular rods navigating barriers containing large and small holes.
  • Results: Success rates increase monotonically with the time budget, while average path lengths generally decrease except for RRT.
  • Results: For Alternating barriers, RRT reaches 70% success after 30 seconds, RRT* after 70 seconds, and LBT-RRT after 50 seconds across tested ε values.
  • Results: At 50 seconds in Alternating barriers, LBT-RRT typically matches RRT* path quality while retaining a high success rate.
  • Results: Similar behavior appears in the Maze and Cubicles scenarios: LBT-RRT finds high-quality paths within time frames that RRT requires to find any solution.

V. LAZY, GOAL-BIASED LBT-RRT

Lazy, goal-biased LBT-RRT relaxes the bounded approximation invariant to goal nodes and uses lazy edge validation with LPA* to reduce local-planner calls. Experiments compare this variant with LBT-RRT, RRT*, and RRG across benchmark scenarios.

  • Goal-biased invariant: The variant maintains the bounded approximation invariant only for goal nodes, avoiding updates of approximate shortest paths to every graph node.It replaces dynamic SSSP with LPA*, which repeatedly finds shortest paths from the start to a specified goal under edge updates.
  • Lazy validation: Edges are initially added lazily without local-planner calls or collision checks, and validation is triggered only when a goal path is found.The algorithm then follows candidate goal-path edges backward, checking whether they are collision-free.
  • Computational behavior: Before a path is found, the lazy, goal-biased variant performs no more local-planner calls than RRT.This preserves RRT-like early solution-finding behavior while postponing validation work.

VI. CONCLUSION AND FUTURE WORK

The paper concludes that LBT-RRT provides asymptotically near-optimal planning through approximation-controlled lower-bound reasoning and dynamic shortest-path methods. It identifies stopping criteria and broader quality measures as directions for extending the framework.

  • Conclusion: LBT-RRT uses an approximation factor to avoid expensive local-planner calls when no substantially better solution may be obtained.The lazy, goal-biased variant also uses dynamic shortest-path algorithms.
  • Future work: The framework may benefit from advances in dynamic shortest-path algorithms, including methods that maintain shortest-path trees under batches of updates.Such methods could replace the SSSP algorithm used by LBT-RRT.
  • Future work: Future work seeks natural stopping criteria tied to how rapidly solution quality improves as additional samples are introduced.Such criteria could support progressively reducing ε during an anytime run.
  • Future work: Applicability to other quality measures remains an open question: energy consumption appears promising, whereas bottleneck clearance is unlikely to fit the framework.For bottleneck clearance, bounding edge quality already identifies collision freedom.

APPENDIX

The appendix discusses replacing RRT or RRT* in dynamic, manifold, parallel, and other planning settings, and extends the lower-bound framework to FMT*. These applications emphasize retaining efficiency while weakening optimality to near-optimality.

  • Implementation and parallelization: The same primitive-operation optimizations and heuristics used by RRT and RRT* can generally be applied to LBT-RRT.The appendix discusses collision checking, sampling, nearest-neighbor computation, CPU parallelism, and GPU collision checking.
  • Re-planning using RRTs: LBT-RRT can replace RRT in replanning schemes for changing configuration spaces, potentially producing higher-quality paths when its overhead is acceptable.The existing tree can be trimmed after environmental changes and grown until a new solution is generated.
  • High-quality planning: For fast convergence to a high-quality solution, LBT-RRT trades an optimality guarantee for a weaker near-optimality guarantee.This makes it a candidate replacement for either RRT or RRT* depending on the desired balance.
  • Framework extensions: The lower-bound framework is also applied to FMT*, producing LBT-aFMT* with two trees, maintained invariants, and cached collision information.The anytime baseline aFMT* repeatedly doubles its sample count and can reuse prior samples and connections.
  • Framework extensions: In the Corridors scenario, LBT-aFMT* with ε = 0.5 reaches a 60% narrow-corridor success rate in half the time required by aFMT*.The scenario contrasts a wide corridor, easy to sample, with a narrow corridor requiring more samples for a low-cost path.

Algorithm 9 LBT-aFMT∗(Cache)

Algorithm 9 constructs LBT-aFMT* using shared samples, two trees, cached local-planner results, and a bounded-approximation test. It selects approximate edges when their cost is within (1 + ε) of the lower-bound estimate and validates lower-bound edges otherwise.

  • Initialization: The algorithm initializes a shared vertex set containing xinit and n collision-free samples, then creates lower-bound and approximate trees over that set.Both trees initially contain the same vertices and no edges.
  • Candidate selection: For each expansion, it identifies neighboring candidates and computes lower-bound and cached approximate predecessors using their respective tree costs.The approximate predecessor is chosen only from edges present in Cache.
  • Approximation test: If capx ≤ (1 + ε) · clb, the algorithm assigns the approximate predecessor without checking the edge locally.This is the lazy branch of the bounded-approximation decision.
  • Edge validation: Otherwise, it calls collision_free(ylb, x) and assigns the lower-bound predecessor to both trees only when the edge is collision-free.Validated nodes are added to the expansion frontier.
  • Termination: The algorithm removes the expanded node from the frontier, returns FAILURE when the frontier is empty, and otherwise expands the frontier node with minimum cost until reaching XGoal.On reaching the goal, it returns PATH.
Loading 1308.0189v4…