Path planning using RRT

RRT expands to Rapidly-Exploring Random Trees and is used widely in the field of robotics for path planning.

Algorithm

1. Insert start point in the tree
2. 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
3. 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.