RRT expands to Rapidly-Exploring Random Trees and is used widely in the field of robotics for path planning.
- Insert start point in the tree
- While tree cannot connect to goal
- Sample random point r in the image space
- Find point p in the tree that is closest to r
- Add branch of defined length from p to r
- If new branch intersects with obstacle then either discard or trim it
- Find the path from start to end through the tree
|Output of RRT algorithm|
The above figure shows the output path produced by using RRT. Complete python implementation can be found on GitHub. In the future I will be making the path smoother by using splines and make it less convoluted.