Informed RRT*: Optimal sampling-based path planning focused via direct sampling of an admissible ellipsoidal heuristic

Jonathan D. Gammell, Siddhartha S. Srinivasa, Timothy D. BarfootIROS 2014 · DOI

TL;DR

This paper introduces Informed RRT*, an algorithm that significantly speeds up optimal path planning by intelligently focusing the search space. Instead of uniformly sampling the entire environment, it samples from an "informed subset" of states that are guaranteed to improve the current best solution, leading to faster convergence and better path quality.

What Problem Does This Paper Address?

Finding optimal paths in complex, high-dimensional environments is a fundamental challenge in robotics and artificial intelligence. Algorithms like Rapidly-exploring Random Trees (RRTs) are good at finding a path quickly, but they don't guarantee optimality. RRT improves upon RRT by asymptotically guaranteeing optimality, meaning it will eventually find the best path. However, RRT can be inefficient because it spends a lot of computational effort exploring areas of the state space that are unlikely to lead to a better solution, especially in large or high-dimensional problems. This paper addresses this inefficiency by proposing a method to focus the search on the most promising regions of the state space.

Methods

The core innovation is the concept of an "informed subset" of the state space. For path planning problems that aim to minimize path length, the set of states that can potentially improve the current best solution can be mathematically described as a prolate hyperspheroid (an elongated ellipsoid). The paper presents an exact method to directly sample from this ellipsoidal subset.

The Informed RRT* algorithm works as follows:

  1. Initialization: It starts like a standard RRT* algorithm, building a tree of possible paths.
  2. First Solution: Once an initial path (solution) is found, the algorithm identifies the current best solution cost ($C_{best}$).
  3. Informed Sampling: Instead of sampling randomly from the entire state space, Informed RRT* samples exclusively from the ellipsoidal subset defined by $C_{best}$ and the start/goal states. This subset is guaranteed to contain all states that could lead to a better solution.
  4. Rewiring: Like RRT*, it continues to rewire the tree to optimize paths.
  5. Iteration: As better solutions are found, the ellipsoidal sampling domain shrinks, further focusing the search.

The paper also details the mathematical derivation for transforming uniformly distributed samples from a unit n-ball into samples within this prolate hyperspheroid, including handling rotations and translations to align with the world frame.

Datasets

Not discussed in the paper. The authors use simulated environments and random worlds for evaluation.

Key Insights and Ideas

  • The "Informed Subset" is Key: The realization that states capable of improving a solution form a specific, geometrically defined subset (a prolate hyperspheroid) is crucial. This transforms the problem from a blind search to a targeted one.
  • Direct Sampling is More Efficient: Directly sampling from this informed subset is shown to be significantly more effective than indirect methods like heuristic-biased sampling or sample rejection, especially in high dimensions or when approaching the optimal solution.
  • Asymptotic Optimality Preserved, Convergence Accelerated: Informed RRT retains the theoretical guarantees of RRT (probabilistic completeness and asymptotic optimality) but achieves them much faster.
  • Reduced Dependence on Problem Size: By focusing the search, the algorithm becomes less sensitive to the overall size and dimensionality of the planning problem.

Key Results

  • Faster Convergence: Informed RRT consistently finds solutions of comparable or better quality in significantly less time than RRT. For example, in one test, it found a solution in 1 second compared to RRT*'s 8.26 seconds (Fig. 1).
  • Improved Solution Quality: The algorithm can find solutions with lower costs (better paths) within the same computational budget.
  • Effective in Difficult Passages: Informed RRT excels at navigating narrow passages and complex environments, finding solutions much faster than RRT (Fig. 7).
  • Near-Optimal Solutions: In obstacle-free scenarios, the algorithm can converge to machine precision of the optimal solution in finite time (Fig. 3).
  • Scalability: The performance benefits are observed across various state dimensions and problem complexities (Fig. 11).

Limitations and Future Work

  • Requires an Initial Solution: The current Informed RRT algorithm needs an initial solution to define the informed subset. The authors acknowledge this limitation and mention ongoing work on techniques like Batch Informed Trees (BIT) that can focus the search without an initial solution.
  • Heuristic Dependence: While the method is designed to work with admissible heuristics, its effectiveness is tied to the quality of the heuristic. If the heuristic provides no additional information (e.g., in obstacle-free cases), Informed RRT behaves like RRT.
  • Future Work: The authors suggest exploring techniques to focus the search without an initial solution and integrating Informed RRT* with other algorithms like path smoothing to further reduce search space. They also mention ongoing work on calculating an optimal rewiring radius for the informed subset.

Summary updated

BibTeX
@inproceedings{gammell2014informed,
  author = {Jonathan D. Gammell and Siddhartha S. Srinivasa and Timothy D. Barfoot},
  title = {{Informed RRT*: Optimal sampling-based path planning focused via direct sampling of an admissible ellipsoidal heuristic}},
  booktitle = {IEEE/RSJ International Conference on Intelligent Robots and Systems},
  year = {2014},
  doi = {10.1109/iros.2014.6942976},
}
Figure