Drone Navigation - Rapidly-Exploring Random Tree

This project implements a navigation algorithm known as a Rapidly-Exploring Random Tree (RRT) to navigate through an obstacle course

Crazyflie 2.1 Drone

Jupyter Notebook

This project takes the theory of the RRT algorithm and implements it into a crazyflie drone to navigate a known obstacle course. While researching, I stumbled upon this paper by Steven M. Lavelle. He outlines the benefit of an RRT to be robust across many scenarios - holonomic & non-holonomic constraints and higher DoF systems. This allowed me to use the RRT to path-plan for a 6 DoF non-holonomic drone.

This story outlines the code for RRT creation, configuration space planning, and hardware implementation. A video at the end displays the drone's performance.

These blocks are for the setup and helper functions of the main RRT algorithm. The blocks follow the photo sequence:

1. Setup
2. Configuration checking
3. Edge checking
4. Random configuration sampling
5. Path creation

The algorithm follows the sudo-code developed by Steven LaVelle in his paper.

The blocks follow the photo sequence:

1. Main RRT algorithm
2. Path creation through back tracking

This creates a configuration space for the RRT navigation. The algorithm "knows" how the course will look by receiving measurements of the location and size of each obstacle in advance. The drone has a set boundary that determines the universal location. Although the RRT depicts the drone as a point, the obstacles are "inflated" to compensate for the drones volume.

After plotting the trajectory, the path should look something like the above. Sometimes a path isn't found due to the RRT's random nature. Just retry the block until a path is found.

A file for the entire code file is provided below

The output should look similar to this:

Trajectory Setpoints

The final result video is embedded above.