PaperlayerView exact revision on arXiv

Source-linked AI summary

Informed Sampling for Asymptotically Optimal Path Planning (Consolidated Version)

Jonathan D Gammell, Timothy D Barfoot, Siddhartha S Srinivasa

arXiv:1706.06454v5cs.RO

TL;DR

RRT* wastes effort exploring states that cannot improve an existing solution, motivating informed search. The paper formalizes omniscient and informed sets, analyzes the L2 informed set, and directly samples its prolate hyperspheroid. Informed RRT* avoids the dimensionality dependence of prior focusing methods, with linear convergence on some problems and performance that remains effective across state dimensions and informed-set sizes.

  • Problem

    RRT* continues exploring the planning domain after an initial solution, although only states that can improve that solution need consideration; exact identification requires solving the problem.

  • Method

    The paper formalizes omniscient and informed sets, analyzes the Euclidean L2 informed set, and directly samples its prolate hyperspheroid using Informed RRT*.

  • Results

    Informed RRT* has better theoretical convergence and experimental performance than existing focused planners, and can achieve linear convergence on some minimum-path-length problems.

  • Takeaways & Limitations

    Direct informed sampling provides 100% recall and high precision regardless of informed-set size or state dimension, while matching RRT* when the heuristic provides no information.

  • Takeaways & Limitations

    Existing techniques exploiting the L2 heuristic can lose recall, lose precision as solutions improve, or fail to account for the factorial decrease in informed-set measure with state dimension.

Abstract

from arXiv · show

Anytime almost-surely asymptotically optimal planners, such as RRT*, incrementally find paths to every state in the search domain. This is inefficient once an initial solution is found as then only states that can provide a better solution need to be considered. Exact knowledge of these states requires solving the problem but can be approximated with heuristics. This paper formally defines these sets of states and demonstrates how they can be used to analyze arbitrary planning problems. It uses the well-known $L^2$ norm (i.e., Euclidean distance) to analyze minimum-path-length problems and shows that existing approaches decrease in effectiveness factorially (i.e., faster than exponentially) with state dimension. It presents a method to address this curse of dimensionality by directly sampling the prolate hyperspheroids (i.e., symmetric $n$-dimensional ellipses) that define the $L^2$ informed set. The importance of this direct informed sampling technique is demonstrated with Informed RRT*. This extension of RRT* has less theoretical dependence on state dimension and problem size than existing techniques and allows for linear convergence on some problems. It is shown experimentally to find better solutions faster than existing techniques on both abstract planning problems and HERB, a two-arm manipulation robot.

I. INTRODUCTION

RRT* can waste effort exploring the entire domain after finding an initial solution, although only states capable of improving that solution need consideration. The paper formalizes these states and develops direct sampling of admissible L2 informed sets to address the factorial loss in existing methods as dimension increases.

  • Motivation: RRT* incrementally rewires a tree through free space and is inefficient for finding the optimum in a single-query planning problem.Its asymptotic convergence results from improving paths to every state in the domain.
  • Motivation: Only states capable of providing a better solution need consideration, but identifying them exactly requires solving the planning problem.Heuristics can approximate these states and focus asymptotically optimal search.
  • Omniscient and informed sets: The paper defines omniscient and informed sets and uses precision and recall to quantify how well informed sets estimate the states that can improve a solution.For holonomic planning, improvement probability can be bounded by the probability of sampling an admissible informed set.
  • L2 informed set: The L2 informed set is universally admissible, exactly matches the omniscient set without obstacles or constraints, and supports analysis of minimum-path-length planning.The L2 norm is Euclidean distance and provides 100% recall; its bound is sharp in the obstacle-free, unconstrained case.
  • Curse of dimensionality: Existing rejection-sampling and focusing techniques have an improvement probability that decreases factorially with state dimension.The paper identifies this faster-than-exponential decline as the minimum-path-length curse of dimensionality.
  • Direct informed sampling: Directly sampling the prolate hyperspheroid defining the L2 informed set reduces this curse and outperforms existing focusing techniques by orders of magnitude as dimension increases.The method directly samples the symmetric n-dimensional ellipse rather than relying on rejection sampling.
  • Informed RRT*: Informed RRT* combines direct informed sampling with admissible graph pruning and has better theoretical convergence and experimental performance than existing focused planners.It remains probabilistically complete and almost-surely asymptotically optimal, with linear convergence on some problems.

III. PRIOR WORK ACCELERATING RRT* CONVERGENCE

The paper organizes prior RRT* convergence-acceleration methods around how they exploit additional information to focus search. These methods primarily use sample biasing, sample rejection, and graph pruning.

  • Prior techniques aim to increase the real-time rate of searching the omniscient set by exploiting additional information.
  • Most prior approaches can be viewed as sample biasing, sample rejection, or graph pruning.
  • The paper reviews these techniques in Sections III-A–III-D.

A. Sample Biasing

Prior methods focus RRT* using biased sampling, rejection, or pruning, but their effectiveness involves trade-offs in recall, precision, computational cost, or state dimension. Direct informed sampling is presented as avoiding known-unhelpful states while preserving uniformity over the searched informed set.

  • Sample Biasing: Path biasing increases precision by decreasing recall, because it reduces exploration of other homotopy classes and requires a user-chosen tuning ratio.
  • Sample Rejection: Global or bounded sampling generally preserves recall but has low precision, especially in large planning problems or high state dimensions.
  • Direct Informed Sampling: Direct informed sampling avoids states known to be unable to improve a solution while remaining almost-surely asymptotically optimal through uniform sampling within the searched informed set.
  • Sample Rejection: Rectangular rejection sampling improves precision in large planning problems, but its effectiveness still decreases factorially with state dimension.
  • Direct Informed Sampling: Direct informed sampling maintains high precision and 100% recall regardless of informed-set and problem-domain relative sizes, scaling more effectively to high-dimensional problems.
  • Graph Pruning: Admissible graph pruning removes unnecessary states without negatively affecting the search, while direct sampling avoids computational effort on states known unable to improve the solution.

E. Direct Informed Sampling for Path Length

For minimum-path-length planning, the L2 informed set is a prolate hyperspheroid that contains states capable of improving the current solution. Directly sampling this set addresses the factorial loss of rectangular rejection sampling as dimension increases.

  • Informed RRT* combines direct informed sampling with admissible graph pruning to focus search for improvements while retaining probabilistic completeness and almost-sure asymptotic optimality.
  • The L2 informed set is the intersection of the free space and a prolate hyperspheroid whose focal points are xstart and xgoal and whose size shrinks as solutions improve.
  • The L2 heuristic is universally admissible and exactly describes the omniscient set when obstacles and constraints are absent.
  • The probability of improving a solution becomes arbitrarily small near cmin, for large sampling domains, or in high state dimensions.
  • RRT* improvement probability under rectangular sampling decreases factorially with state dimension for holonomic minimum-path-length problems.
  • Rectangular rejection sampling succeeds in 79% of R2, 2% of R8, and 4 × 10^-4% of R16 best-case settings.
  • Direct informed sampling generates uniform samples by transforming unit n-ball samples through scaling, rotation, and translation into the prolate hyperspheroid.
  • The informed-set intersection with the planning domain can be sampled efficiently by repeatedly sampling the smaller set until a sample lies in both sets.

1) Algorithm:

The implementation uses singular value decomposition and uniform unit-ball sampling to support direct informed sampling. Problem-domain sampling supplies uniform samples over the full planning domain.

  • SVD computes the matrix decomposition used by the direct sampling implementation.
  • SampleUnitBall(n) returns uniformly distributed samples from the interior of an n-dimensional unit ball.
  • SampleProblem returns samples uniformly distributed over the entire planning domain.

2) Practical Performance:

Direct informed sampling becomes dramatically more efficient than rectangular rejection sampling as dimension increases, while multigoal informed sets require overlap-aware sampling to remain uniform.

  • Sampling efficiency: Direct informed sampling is slower in R2 than rectangular rejection sampling, requiring 3.5×10^-7 versus 7.3 × 10^-8 seconds per sample.
  • Sampling efficiency: Rectangular rejection results are optimistic because constant domains are loose and adaptive rectangles incur alignment or rotation costs.These factors can increase rejection rates or computational cost beyond the reported experiment.
  • Multigoal informed sets: The multigoal set is formed from the union of individual informed sets, with subset selection weighted by relative measure when the sets do not intersect.
  • Multigoal informed sets: For overlapping multigoal informed sets, proportional rejection corrects the oversampling caused by combining uniformly sampled individual subsets.The method produces a uniform distribution over arbitrarily overlapping individual informed sets.

1) Algorithm:

Informed RRT* focuses post-solution search on a shrinking L2 informed set through direct sampling, graph pruning, and adjusted rewiring while preserving RRT* guarantees.

  • Algorithm: After finding a solution, Informed RRT* directly samples the informed set and prunes unnecessary graph states to focus subsequent improvement.It uses the current best solution to redefine the search domain and repeats this process as the solution improves.
  • Algorithm: Informed RRT* combines direct informed sampling, admissible graph pruning, and an updated rewiring-neighbourhood calculation.The approach can also be integrated into RRTX and Batch Informed Trees.
  • Algorithm: For multiple goals, the informed-set sampler handles arbitrarily overlapping individual L2 sets by probabilistic rejection to maintain uniform density.
  • Algorithm: The graph is searched within a shrinking subset defined by the current solution, with samples generated directly from that subset.
  • Guarantees: Informed RRT* remains probabilistically complete and almost-surely asymptotically optimal because initial-solution search is unchanged and the focused search preserves the required sampling and rewiring conditions.

B. Graph Pruning (Alg. 7)

The paper analyzes convergence and graph pruning for L2-informed planning, showing that naive focusing degrades factorially with dimension while Informed RRT* retains stronger convergence properties.

  • B. Graph Pruning (Alg. 7): Vertices outside the informed set cannot be pruned solely from their own heuristic values because descendants may still belong to the informed set.Removing such vertices can reduce vertex density and harm search performance.
  • B. Graph Pruning (Alg. 7): Admissible pruning removes a vertex only when it and all descendants cannot improve the current solution, preserving every potentially beneficial vertex.
  • Convergence analysis: Smaller informed-set rewiring neighbourhoods reduce per-iteration rewiring cost while maintaining almost-sure asymptotic optimality.
  • Convergence analysis: Adaptive rectangular rejection sampling can converge linearly at best, but its convergence approaches sublinear factorially as state dimension increases.
  • Convergence analysis: Informed RRT* uses direct informed sampling to avoid this limitation, with linear convergence in obstacle- and constraint-free problems and weaker dependence on state dimension.
  • Convergence analysis: The best-case convergence rate of Informed RRT* is always better than that of RRT*, with or without rejection sampling.

A. Experimental Validation and Extension

Experiments validate the predicted linear convergence of Informed RRT* under infinite rewiring, while finite or shrinking neighbourhoods slow convergence and expose tuning trade-offs.

  • A. Experimental Validation and Extension: Finite constant rewiring produces slower convergence that appears initially nonlinear before becoming linear.The authors hypothesize that sample density relative to maximum edge length contributes to this pattern.
  • A. Experimental Validation and Extension: A decreasing finite rewiring neighbourhood produces apparently sublinear convergence, hypothesized to result from shrinking too quickly relative to sample density.
  • A. Experimental Validation and Extension: The results motivate further study of the trade-off between per-iteration rewiring cost and convergence rate.
  • A. Experimental Validation and Extension: The experiments compare Informed RRT* with RRT* and variants using graph pruning, heuristic rejection, or all three focusing techniques together.

A. Toy Problems

Toy-problem experiments show that Informed RRT* increasingly outperforms nondirect methods as state dimension and problem size grow, while retaining comparable performance in small problems. Its direct sampling focuses search on the L2 informed set without sacrificing recall.

  • A. Toy Problems: Informed RRT* performs equivalently to rejection sampling in low dimensions but outperforms existing techniques in higher dimensions.The first experiment used randomized obstacle variants in R2, R4, and R8 over 100 trials.
  • A. Toy Problems: Increasing problem size and state dimension decreases nondirect methods’ ability to find near-optimal solutions, while Informed RRT* limits these effects.The second experiment varied map width and targeted solutions better than 1.01c*, 1.05c*, and 1.15c* in R2, R4, and R8, respectively.
  • A. Toy Problems: Informed RRT* has better real-time convergence toward the optimum than existing techniques, especially in higher state dimensions.This result was observed on problems with many homotopy classes in R2, R4, and R8.
  • A. Toy Problems: 3.9%, 7.9%, and 28.2% path-length improvements were achieved by Informed RRT* across the three HERB transitions, respectively.RRT* with and without pruning and rejection sampling failed to improve the initial solutions; the first improvement was not statistically significant.
  • A. Toy Problems: Directly sampling the L2 informed set provides 100% recall and high precision regardless of its relative size or state dimension.The method generates uniformly distributed samples in the informed set and considers all homotopy classes that could provide better solutions.
  • A. Toy Problems: The improvement from informed sampling can be limited in small domains or when optimal solutions are long and circuitous.In those situations, Informed RRT* is designed to perform no worse than other methods exploiting the L2 heuristic.

APPENDIX A PROOFS OF LEMMAS 4 AND 5

The proofs establish that RRT* can improve a solution only by adding states from the omniscient set, and, in holonomic planning, this requires sampling that set. The appendix also proves uniform sampling through an invertible transformation from a unit n-ball to a hyperellipsoid.

  • Lemma 4: Adding a state from the omniscient set is necessary for RRT* to improve the current solution, but it is not sufficient because improvement also depends on tree structure.The omniscient set contains states that can provide better solutions; whether they do so depends on the tree’s optimality.
  • Lemma 5: In holonomic planning after an initial κ iterations, sampling the omniscient set is necessary for RRT* to improve the current solution.The proof uses the fact that, in holonomic planning, the newly added state equals the random sample under the relevant expansion relationship.
  • Lemma 5: The necessity result is stated for holonomic planning and can extend to specific constraints under appropriate assumptions.The sampling distribution must maintain nonzero probability over the entire omniscient set.
  • Lemma 15: Uniform samples from a unit n-ball remain uniformly distributed after an invertible linear transformation into a hyperellipsoid.The transformed density is constant over the hyperellipsoid, and the construction applies to orthogonal-axis hyperellipsoids such as prolate hyperspheroids.

APPENDIX C PROOF OF LEMMA 17

The proof derives a sharp bound on the expected next-iteration cost for minimum-path-length planning from the probability of sampling the omniscient set. The bound is exact for an obstacle-free, unconstrained best-case RRT* configuration with infinite rewiring radius.

  • Lemma 17: The expected next solution cost is bounded using the current cost, theoretical minimum cost, state dimension, and probability of adding a state from the omniscient set.The probability term is generally a function of the current solution cost.
  • Expected-cost decomposition: Adding a state from the omniscient set is necessary for improvement, while sampling outside it leaves the solution cost unchanged.This reduces the expected-cost expression to the probability-weighted cost of adding a state from the omniscient set.
  • Sharpness: The lower bound is sharp over all possible planning problems and algorithm configurations.It becomes exact for infinite-rewiring RRT* in an obstacle-free environment without constraints.
  • Prolate hyperspheroid: In obstacle-free, unconstrained minimum-path-length planning, the omniscient set is the prolate hyperspheroid.Its measure supplies the sampling probability used in the expected-cost analysis.
  • Derivation: The proof evaluates the prolate hyperspheroid integral using its differential volume, trigonometric integrals, beta-function identities, and the recursive structure of the n-dimensional unit ball.Substitution and simplification yield the exact best-case expected solution cost used in the sharp bound.

APPENDIX D PROOFS OF THEOREMS 18–20

The theorems characterize convergence rates for RRT* in holonomic minimum-path-length planning. Standard RRT* converges sublinearly, while its best-case rate is tied to how the probability of sampling the informed set decreases near the optimum.

  • Theorem 18: RRT* converges sublinearly toward the optimum for holonomic minimum-path-length planning problems.The theorem is supported by the asymptotic decrease of the probability of adding a state from the informed set.
  • Theorem 18: The convergence-rate bound uses the sharp expected-cost lower bound from Lemma 17 and the informed-set sampling probability.The lower bound corresponds to obstacle-free, constraint-free planning in the best-case configuration.
  • Theorem 18: As RRT* approaches the optimum, the probability of adding a state from the informed set tends to zero.In the asymptotic limit, the probability of adding a state becomes the probability of sampling the informed set.

B. Proof of Theorem 19

Theorem 19 bounds adaptive rectangular rejection sampling by a rate that is linear at best but approaches sublinear convergence factorially as state dimension increases. Informed RRT* instead has a linear best-case convergence rate under the stated holonomic assumptions.

  • Theorem 19: Adaptive rectangular rejection sampling gives RRT* at-best linear convergence, approaching sublinear convergence factorially as state dimension increases.The theorem provides sharp bounds over all holonomic minimum-path-length planning problems and algorithm configurations.
  • Theorem 20: Informed RRT* converges at best linearly toward the optimum for holonomic minimum-path-length planning problems.The lower bound occurs exactly with an infinite rewiring neighbourhood in the absence of obstacles and constraints.
  • Theorem 20: The proof of Theorem 20 uses a unity probability of adding a new state from the informed set.This replaces the informed-set sampling probability in the general convergence-rate argument.
Loading 1706.06454v5…