MIT researchers create algorithm to stop drones from colliding midair

Listen to this article

The MIT team tested its collision avoidance system in a flight environment with six drones and in simulation. | Source: MIT

A research team from MIT created a trajectory-planning system called Robust MADER that can allow drones working together in the same airspace to pick safe paths forward without crashing into each other. The algorithm is an updated version of MADER, a 2020 project that worked well in simulation but didn’t hold up in real-world testing. 

The original MADER system involved each agent broadcasting its trajectory so fellow drones know where it’s planning to go. In simulation, this worked without problems, with all drones considering each other’s trajectories when planning their own. When put to the test, the team found that it didn’t take into account delays in communication between drones, resulting in unexpected collisions. 

“MADER worked great in simulations, but it hadn’t been tested in hardware. So, we built a bunch of drones and started flying them. The drones need to talk to each other to share trajectories, but once you start flying, you realize pretty quickly that there are always communication delays that introduce some failures,” Kota Kondo, an aeronautics and astronautics graduate student, said.

Robust MADER is able to generate collision-free trajectories for drones even when there is a delay in communications between agents. The system is an asynchronous, decentralized, multiagent trajectory planner, meaning each drone formulates its own trajectory and then checks with drones nearby to ensure it won’t run into any of them. 

The drones optimize their new trajectories using an algorithm that incorporates the trajectories they received from nearby drones, and agents constantly optimize and broadcast new trajectories to avoid collisions. 

To get around any delays in sharing trajectories, every drone has a delay-check period, where it spends a fixed amount of time repeatedly checking for communications from other agents to see if its new trajectory is safe. If it finds a possible collision, it abandons the new trajectory and keeps going on its current one. The length of this delay-check period depends on the distance between agents and other environmental factors that could hamper communications. 

While the system does require all drones to agree on each new trajectory, they don’t all have to agree at the same time, making it a scalable system. It could be used in any situation where multiple drones are working together in the same airspace like spraying pesticides over crops. 

The MIT team ran hundreds of simulations in which they artificially introduced communication delays, and found that MADER was 100% successful at avoiding collisions. When tested with six drones and two aerial obstacles in a flight environment, Robust MADER was able to avoid all collisions, while the old algorithm would have caused seven collisions. 

Moving forward, the research team hopes to put Robust MADER to the test outdoors, where obstacles can affect communications. They also hope to outfit drones with visual sensors so they can detect other agents or obstacles, predict their movements and include that information in trajectory optimizations. 

Kota Konda wrote the paper with Jesus Tordesillas, a postdoc; Parker C. Lusk, a graduate student; Reinaldo Figueroa, Juan Rached, and Joseph Merkel, MIT undergraduates; and senior author Jonathan P. How, the Richard C. Maclaurin Professor of Aeronautics and Astronautics, a principal investigator in the Laboratory for Information and Decision Systems (LIDS), and a member of the MIT-IBM Watson AI Lab. This work was supported by Boeing Research and Technology.