RRT Path Finding

Project

This project implements a 3D Rapidly-Exploring Random Tree (RRT) pathfinding algorithm in Python. A RRT is a way to fully explore a random space with obstacles and passages in a uniform fashion. The tree starts from a random position in yellow and trys to randomly find a path to a point in green. The solved examples here are interactive.

Method

The tree is built by first selecting a random point as the root of the tree. It then selects a random point in the space and finds the closest part of the tree to this new point. From here it attempts to build the tree in the direction of the new point so long as there is not an obstacle in the way. At every iteration the tree checks if the goal is now visible from the new branch and if so computes the path from the root to the goal. If it is not visible, the cycle repeats.

As this algorithm proceeds infinitely it will build a tree that fully and uniformly explores the space it can reach and will provide a way to get from the root to any point. There are some drawbacks to this however. As the space expands, the rate at which the tree grows into new areas slows down dramatically. The computed path is also often far from optimal. FInding a path in any non-trivial environment is also computationally intensive and extremely variable.