RRT* 3D

Problem Statement

RRT* incrementally builds a tree in continuous space and asymptotically improves path cost through rewiring.

Model and Formulation

At each iteration:

1. Sample random state x_rand
2. Extend nearest node toward sample
3. Choose parent minimizing local cost
4. Rewire neighbors if new path improves their cost

As iterations grow, solution cost converges toward optimal.

Practical Notes

• Goal bias improves convergence speed.
• Step size controls exploration granularity.
• Collision checks dominate runtime.

Implementation and Execution

python -m flybots.simulations.path_planning.rrt_star_3d

Evidence

References

• Karaman and Frazzoli, Sampling-based Algorithms for Optimal Motion Planning (2011)
• Lavalle and Kuffner, Rapidly-exploring Random Trees

Related Algorithms

• PRM 3D
• A* 3D