Informed RRT*

Once an initial path is found, the algorithm defines a hyperellipsoid with the start and goal states as focal points. The transverse diameter equals the current best solution cost c_best, and the conjugate diameter equals the straight-line heuristic. Sampling is restricted to this subset, rejecting any state outside the ellipsoid. This transforms the problem from exploring the entire C-Space to a focused region that shrinks as the solution improves.

Informed RRT* inherits the probabilistic completeness and asymptotic optimality of RRT*. As the number of iterations approaches infinity, the probability of finding the optimal path converges to one. The informed sampling strategy does not compromise this guarantee—it only accelerates convergence by rejecting states that cannot possibly improve the current solution, making it suitable for high-dimensional planning problems.

The algorithm samples uniformly within the informed subset using a transformation method:

• Sample a unit n-ball uniformly
• Transform the ball into an ellipsoid aligned with the start-goal axis
• Rotate and scale the sample to match the current ellipsoid geometry This procedure maintains uniform distribution within the ellipsoid, ensuring the RGG (Random Geometric Graph) properties required for optimal convergence are preserved.

Like standard RRT*, Informed RRT* performs rewiring—reconnecting nearby nodes if a lower-cost path is found through the new sample. The algorithm also uses admissible cost-to-go heuristics (typically Euclidean distance) to prune edges. A potential parent or child connection is only considered if the sum of the cost-to-come, edge cost, and heuristic cost-to-go is less than c_best, further reducing computational overhead.

Practical implementations often process samples in batches to amortize the cost of ellipsoid recomputation. After adding a batch of nodes, the algorithm updates c_best and recalculates the ellipsoid parameters. This approach is critical for kinodynamic planning and manipulator motion planning where collision checking dominates runtime, allowing the planner to maintain consistent frame rates in dynamic environments.

Informed RRT* converges to the optimal solution an order of magnitude faster than standard RRT* in practice. Unlike PRM* which requires a preprocessing phase, Informed RRT* is a single-query algorithm that improves incrementally. The convergence rate depends on the state space dimension and obstacle geometry—the ellipsoid volume shrinks as c_best approaches the true optimal cost, creating a positive feedback loop that accelerates refinement.

A formal property guaranteeing that the cost of the returned path converges to the global optimum as the number of samples approaches infinity. Both RRT* and Informed RRT* possess this property. The key distinction is convergence rate:

• Standard RRT* converges slowly because samples are distributed uniformly across the entire C-space
• Informed RRT* achieves exponential convergence by focusing samples into an ever-shrinking ellipsoid In practice, this means Informed RRT* finds near-optimal paths with orders of magnitude fewer samples, making it viable for real-time industrial robotics applications.