Introduction: Drone Navigation - Rapidly-Exploring Random Tree

By

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

Supplies

Crazyflie 2.1 Drone

Jupyter Notebook

Step 1: Overview

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.

Step 2: RRT Algorithm Setup and Helper Functions

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

Step 3: Main RRT Algorithm

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

Step 4: Define Configuration Space

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.

Step 5: Plot the Trajectory

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.

Step 6: Implement Into the Hardware

A file for the entire code file is provided below

Attachments

Step 7: Results

The output should look similar to this:

Trajectory Setpoints

Trajectory Setpoints

The final result video is embedded above.