Notebook 7.2 - Rapidly Exploring Random Trees

This notebook contains a simple implementation of the RRT algorithm that we covered in Part 4 of our session.

RRTs are algorithms that allow the exploration of a search space. They are space-filling algorithm that randomly grow towards unexplored areas of the problem and are widely used in autonomous motion planning.

RRTs have 3 main processes:

  1. Random node generation - where an area is selected at random to be explored.
  2. Closest node finding - assign the newly generated random node to the closest node in the existing tree.
  3. Step node generation - the newly generated node is then moved so that the distance to the closest node in the tree equals a specified step distance.

Our implementation is purely numerical, and we do not rely on external packages. We only need matplotlib, for visualisation - so we check that it has been installed correctly.

Algorithm Implementation