Source-linked AI summary
Informed RRT*: Optimal Sampling-based Path Planning Focused via Direct Sampling of an Admissible Ellipsoidal Heuristic
Jonathan D. Gammell, Siddhartha S. Srinivasa, Timothy D. Barfoot
TL;DR
RRT* can spend substantial effort pursuing optimal paths throughout the planning domain, despite serving a single query. The paper directly samples an admissible prolate-hyperspheroid subset containing states that may improve the current solution, producing Informed RRT*. This retains RRT*'s probabilistic guarantees while improving convergence, solution quality, and performance across difficult, high-dimensional, and large-range problems.
Problem
RRT*'s uniform global sampling makes it asymptotically optimize paths to every state, an inefficient behavior for single-query planning that becomes expensive in high dimensions.
Method
The paper directly samples an admissible prolate-hyperspheroid subset containing states that can improve the current path-length solution, using it in Informed RRT*.
Results
Informed RRT* improves convergence, final solution quality, difficult-passage performance, and dependence on planning dimension and range while retaining RRT*'s probabilistic guarantees.
Takeaways & Limitations
Focused sampling provides a simple RRT* modification that concentrates computation on potentially improving states without additional tuning.
Takeaways & Limitations
The informed search depends on the current solution cost, cannot focus when its hyperspheroid exceeds the planning domain, and requires an initial solution before focusing.
Abstract
from arXiv · showhide
Rapidly-exploring random trees (RRTs) are popular in motion planning because they find solutions efficiently to single-query problems. Optimal RRTs (RRT*s) extend RRTs to the problem of finding the optimal solution, but in doing so asymptotically find the optimal path from the initial state to every state in the planning domain. This behaviour is not only inefficient but also inconsistent with their single-query nature. For problems seeking to minimize path length, the subset of states that can improve a solution can be described by a prolate hyperspheroid. We show that unless this subset is sampled directly, the probability of improving a solution becomes arbitrarily small in large worlds or high state dimensions. In this paper, we present an exact method to focus the search by directly sampling this subset. The advantages of the presented sampling technique are demonstrated with a new algorithm, Informed RRT*. This method retains the same probabilistic guarantees on completeness and optimality as RRT* while improving the convergence rate and final solution quality. We present the algorithm as a simple modification to RRT* that could be further extended by more advanced path-planning algorithms. We show experimentally that it outperforms RRT* in rate of convergence, final solution cost, and ability to find difficult passages while demonstrating less dependence on the state dimension and range of the planning problem.
I. INTRODUCTION
RRT* achieves asymptotic optimality but spends effort optimizing paths to every state, conflicting with its single-query use. The paper focuses sampling on an admissible ellipsoidal subset that can improve the current path, yielding Informed RRT* and faster convergence without extra tuning.
- I. INTRODUCTION: RRT* uses incremental rewiring to achieve asymptotic optimality, but its global sampling optimizes paths to every state and becomes expensive in high dimensions.This behavior is inconsistent with the single-query nature of the planning problem.
- I. INTRODUCTION: For path-length minimization in Rn, states that can improve the current solution lie within an ellipsoidal subset of the planning domain.The subset is estimated using an admissible heuristic that never overestimates the true constrained path cost.
- I. INTRODUCTION: Uniform sampling adds potentially improving states with probability that becomes arbitrarily small as problem size increases or the solution approaches the theoretical minimum.Directly sampling the ellipsoidal subset addresses this vanishing probability; under strict no-obstacle assumptions, convergence is linear.
- I. INTRODUCTION: Informed RRT* behaves like RRT* until finding an initial solution, then samples only from the admissible informed subset without additional parameters or assumptions.When the subset equals the full planning domain, Informed RRT* is equivalent to RRT*.
- I. INTRODUCTION: In simulation, Informed RRT* performs comparably on simple configurations and achieves order-of-magnitude improvements as configurations become more difficult.It also shows less dependence on planning dimension and domain, finds better topologically distinct paths sooner, and can reach machine-zero optimality without obstacles.
- A. Problem Definition: The paper formally defines optimal planning as finding a minimum-cost path from xstart to xgoal through free space.The state space excludes obstacle-collision states, and the path belongs to a set of nontrivial paths.
B. Prior Work
Prior approaches focus sampling or pruning toward potentially useful states, but often retain invalid samples, require global exploration, or compromise RRT* assumptions.
- Prior methods include sample biasing, path biasing, heuristic-based rejection, graph pruning, and iterative searches.
- Sample Biasing: Heuristic-biased sampling increases selection probability using heuristic costs but can still produce suboptimal RRT solutions.
- Sample Biasing: Path biasing samples around the current solution but assumes proximity to an optimal homotopy class and requires user-tuned global-to-local sampling.
- Sample Biasing: Dualtree RRT* refines the current solution using a user-specified iteration percentage, increasing path improvement at the expense of exploring other homotopy classes.
- Sample Biasing: RRT*-Smart combines path biasing with smoothing, but smoothing can reduce exploration of alternative homotopy classes and violate uniform-density assumptions.
- Sample Biasing: Cloud RRT* uses visibility analysis to initialize and update sampling concentration near the current path.
2) Heuristic-based Sample Rejection:
Heuristic-based rejection samples from a larger domain and keeps states passing a heuristic test, but its efficiency declines as the useful subset shrinks or dimension increases.
- Heuristic-based sample rejection draws from the planning domain and retains samples according to their heuristic value.
- The iterations needed to find a state in the informed subset scale with that subset’s relative size and become nontrivial near the theoretical minimum or in larger domains.
- C-FOREST samples from a bounding hyperrectangle around the informed subset, improving rejection performance but losing utility as problem dimension increases.
3) Graph Pruning:
Graph-pruning methods remove states that cannot improve the current solution, but incur computational or probabilistic limitations and may rely on inadmissible heuristics.
- Graph pruning periodically removes graph states whose heuristic cost exceeds the current solution while continuing global sampling.
- Because adding each RRT state requires nearest-neighbour computation, graph pruning is more expensive than rejection while retaining similar probabilistic limitations.
- Anytime RRT* prunes vertices using current vertex cost plus a vertex-to-goal heuristic, but the heuristic is inadmissible and can remove useful states prematurely.
- RRT# updates LPA*-style keys after each new state and connects newly sampled states only to vertices with up-to-date keys below the current best solution.
4) Anytime RRTs:
Anytime RRTs restrict successive planning problems using the previous solution, while this paper instead explicitly computes and directly samples the admissible informed subset.
- Anytime RRTs: Anytime RRTs use the previous solution to define a smaller planning domain for a sequence of independent planning problems.
- Anytime RRTs: The earlier method represented these domains as ellipses but did not explain how to generate samples within them.
- Direct Informed Sampling: The paper’s algorithm explicitly calculates X b f and samples from it directly.
- Direct Informed Sampling: For planar path-length minimization, X b f is an ellipse with the start and goal as focal points, shaped by cmin and cbest.
- Direct Informed Sampling: Direct sampling avoids assumptions about the optimal homotopy class, excludes states unable to improve the solution, and retains informed states throughout the search.
- Direct Informed Sampling: When the heuristic provides no additional information, the proposed method performs identically to RRT*.
III. ANALYSIS OF THE ELLIPSOIDAL INFORMED SUBSET
For path-length minimization, admissible heuristics define an informed prolate-hyperspheroid subset containing states that may improve the current solution. Uniform sampling makes improvements increasingly unlikely in large domains or high dimensions, while direct sampling yields linear convergence without obstacles.
- An admissible heuristic bounds the cost of paths constrained through a state by combining admissible estimates from start to state and state to goal.
- For path-length problems, Euclidean distance defines a closed-form informed subset: an n-dimensional prolate hyperspheroid with start and goal as focal points and current solution cost as transverse diameter.
- Uniform sampling improves a solution with probability at most λ(X_b_f)/λ(X_s), so improvement probability becomes arbitrarily small as the domain grows or the solution approaches the theoretical minimum.
- 8% is the maximum improvement probability for rejection sampling from a tightly bounding hyperrectangle when n = 6, regardless of the specific solution or problem parameters.
- With uniform sampling from the informed subset, the best-solution cost converges linearly to the theoretical minimum in obstacle-free problems.The convergence rate depends only on the state dimension; the obstacle-free assumption is impractical but illustrates direct sampling’s effectiveness.
IV. DIRECT SAMPLING OF AN ELLIPSOIDAL SUBSET
The direct sampler generates uniform samples in the informed hyperellipsoid by transforming samples from a unit n-ball, then applying scaling, rotation, and translation. Its rotation aligns the ellipsoid frame with the world frame.
- Uniform hyperellipsoid samples are produced by transforming uniformly distributed samples from a unit n-ball.
- The transformation preserves uniformity and can be computed using a Cholesky decomposition of the hyperellipsoid matrix.
- For prolate hyperspheroids, the transformation can be calculated from the transverse axis and radii using an axis-aligned diagonal matrix and its decomposition.
- A rotation matrix maps the hyperellipsoid-aligned frame to the world frame and is obtained directly through a general Wahba problem solution.
- The final state is obtained through sampling, transformation, rotation, and translation, as specified algorithmically in Algorithm 2.
V. INFORMED RRT*
Informed RRT* modifies RRT* by focusing sampling after the first solution is found on states that may improve the current best solution. It retains the incremental tree-building and rewiring structure of RRT*.
- Informed RRT* incrementally builds and rewires a tree in free state space while searching for an optimal path.
- Once a solution is found, the algorithm focuses sampling on the part of the planning problem that can improve the solution.
- The planner stores candidate solutions, uses their minimum cost to define the informed subset, and samples that subset directly.
- The Sample function returns i.i.d. states whose constrained optimal path cost between two poses is below the specified maximum heuristic value.
- Informed RRT* uses goal-region membership tests, world-frame rotation, and uniform unit-n-ball sampling as supporting subfunctions.
A. Calculating the Rewiring Radius
The rewiring radius must balance asymptotic convergence against computational tractability. Its lower bound is expressed using the planning-space measure and graph size, under the uniform-unit-square assumption from RRT* analysis.
- The rewiring radius must be large enough for almost-sure asymptotic convergence but small enough to keep the number of rewiring candidates tractable.
VI. SIMULATIONS
Experiments show that Informed RRT* focuses sampling on states capable of improving solutions, reducing dependence on planning range and improving convergence, near-optimal planning, and difficult-passage discovery across planning problems and dimensions.
- Problem range: Informed RRT* finds suitable solutions in approximately the same time as planning range increases, while RRT* takes longer because it searches states that cannot improve the solution.The informed search space is independent of planning range once an initial solution is found.
- Target solution cost: Informed RRT* finds near-optimal solutions in significantly fewer iterations than RRT* by directly increasing sampling density around the optimal solution.Improving the solution further focuses the informed search, whereas global sampling spreads RRT*'s density across the planning domain.
- Difficult passages: Informed RRT* finds difficult passages that improve the current solution quicker than RRT*, regardless of their homotopy class.Focusing on the informed subset increases the probability of sampling regions containing narrow gaps between obstacles.
- Difficult passages: For a 3% off-centre gap, Informed RRT* finds a path through the narrow opening in 4.00 seconds, compared with 12.32 seconds for RRT*.The focused search begins from an initial solution flanking the obstacle.
- Random worlds: Experiments in random worlds show that Informed RRT*'s improvements apply across a wide range of planning problems and state dimensions.The experiments used 100 runs for each variation with matched pseudo-random seeds and maps.
VII. DISCUSSION & CONCLUSION
The paper characterizes the states that can improve path-length solutions and introduces direct sampling of that subset. Informed RRT* outperforms RRT* on near-optimal planning across state dimensions, while remaining dependent on the current solution cost and the ellipsoidal subset's size.
- Conclusion: For path-length minimization in Rn, a prolate hyperspheroid with the initial and goal states as focal points estimates the subset of states that can improve a solution.The probability of reaching this subset through rejection sampling becomes arbitrarily small as dimension, sampled-set size, or solution quality increases.
- Conclusion: Informed RRT* directly samples the estimated improving subset and outperforms RRT* in finding near-optimal solutions in finite time regardless of state dimension.The result does not require assumptions about the optimal homotopy class.
- Evaluation: Fig. 8 reports median computational time to reach within 2% of optimal cost across map widths, with nonparametric 95% confidence intervals based on 100 independent runs.The comparison is between RRT* and Informed RRT* on the Fig. 5(a) problem in R2.
- Limitations: Informed RRT* cannot focus the search when its prolate hyperspheroid is larger than the planning problem, and it cannot shrink the subset below the optimal-solution lower bound.The method is therefore inherently dependent on the current solution cost.