As drones become more prevalent, programming challenges for creating algorithms for real-time flight become all the more pressing.

In an effort to solve this, researchers at the MIT Computer Science and Artificial Intelligence Laboratory (CSAIL) have developed algorithms to improve drone maneuverability in cluttered environments such as a forest.

Check out the video below to see a drone navigating an obstacle course of strings and PVC pipes:

Drones can use IRIS and MISDP to navigate cluttered environments like this simulated forest. (Video courtesy of MIT.)

Improving Quadrotor Navigation

The flight mechanism for a quadrotor drone is complex and requires intricate algorithms for control and proper performance.

A drone’s software requires 12 numbers to determine its position:

Forward/Backward (Surge)
Up/Down (Heave)
Left/Right (Sway)
Front-to-Back Rotation (Pitch)
Side-to-Side Rotation (Roll)
Horizontal Rotation (Yaw)

In addition to this information, the software needs to account simultaneously for obstacles. This is an especially challenging feat if done in real time.

The CSAIL researchers addressed this issue by creating new algorithms that identify free space through which a drone can move.

This is a departure from previous drone algorithms which focus on obstacles in the drone’s path.

The technique is called iterative regional inflation by semidefinite programming (IRIS). Combined with a mixed-integer semidefinite program (MISDP), the algorithm enables drones to navigate cluttered environments. The former identifies free spaces while the latter navigates them.

The software identifies free-space regions using a library of 40 to 50 trajectories with outer boundaries to contain the drone. These boundaries form “funnels” chosen by the algorithm to create a sequence of steps to guide the drone around obstacles.

“As the drone flies, it continuously searches through the library to stitch together a series of paths that are computationally guaranteed to avoid obstacles,” said Anirudha Majumdar, PhD student and lead author of a related technical report.

“Many of the individual funnels will not be collision-free, but with a large enough library you can be certain that your route will be clear,” he concluded.

Sacrificing Drone Speed for Complexity

MISDP cannot currently plan in real time; it takes ten minutes on average to create a route for the obstacle course. However, routes could be calculated more quickly at the cost of precision by defining free-space regions more broadly, for example.

This is not the first time CSAIL researchers have debuted a method for faster drone movement. Although the drones using this new algorithm aren’t the fastest, they are generally more complex—meaning they can navigate in smaller, denser environments.

The researchers are hoping that others will build on and refine their work, which is why they’ve made it open-source and available on GitHub.