New algorithm keeps drones from colliding in midair

When multiple drones are working together in the same airspace, perhaps spraying pesticide over a field of corn, there’s a risk they might crash into each other.

To help avoid these costly crashes, MIT researchers presented a system called MADER in 2020. This multiagent trajectory-planner enables a group of drones to formulate optimal, collision-free trajectories. Each agent broadcasts its trajectory so fellow drones know where it is planning to go. Agents then consider each other’s trajectories when optimizing their own to ensure they don’t collide.

But when the team tested the system on real drones, they found that if a drone doesn’t have up-to-date information on the trajectories of its partners, it might inadvertently select a path that results in a collision. The researchers revamped their system and are now rolling out Robust MADER, a multiagent trajectory planner that generates collision-free trajectories even when communications between agents are delayed.

“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,” says Kota Kondo, an aeronautics and astronautics graduate student.

The algorithm incorporates a delay-check step during which a drone waits a specific amount of time before it commits to a new, optimized trajectory. If it receives additional trajectory information from fellow drones during the delay period, it might abandon its new trajectory and start the optimization process over again.

When Kondo and his collaborators tested Robust MADER, both in simulations and flight experiments with real drones, it achieved a 100 percent success rate at generating collision-free trajectories. While the drones’ travel time was a bit slower than it would be with some other approaches, no other baselines could guarantee safety.

“If you want to fly safer, you have to be careful, so it is reasonable that if you don’t want to collide with an obstacle, it will take you more time to get to your destination. If you collide with something, no matter how fast you go, it doesn’t really matter because you won’t reach your destination,” Kondo says.

Kondo 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. The research will be presented at the International Conference on Robots and Automation.

Planning trajectories

MADER is an asynchronous, decentralized, multiagent trajectory-planner. This means that each drone formulates its own trajectory and that, while all agents must agree on each new trajectory, they don’t need to agree at the same time. This makes MADER more scalable than other approaches, since it would be very difficult for thousands of drones to agree on a trajectory simultaneously. Due to its decentralized nature, the system would also work better in real-world environments where drones may fly far from a central computer.

With MADER, each drone optimizes a new trajectory using an algorithm that incorporates the trajectories it has received from other agents. By continually optimizing and broadcasting their new trajectories, the drones avoid collisions.

But perhaps one agent shared its new trajectory several seconds ago, but a fellow agent didn’t receive it right away because the communication was delayed. In real-world environments, signals are often delayed by interference from other devices or environmental factors like stormy weather. Due to this unavoidable delay, a drone might inadvertently commit to a new trajectory that sets it on a collision course.

Robust MADER prevents such collisions because each agent has two trajectories available. It keeps one trajectory that it knows is safe, which it has already checked for potential collisions. While following that original trajectory, the drone optimizes a new trajectory but does not commit to the new trajectory until it completes a delay-check step.

During the delay-check period, the drone spends a fixed amount of time repeatedly checking for communications from other agents to see if its new trajectory is safe. If it detects a potential collision, it abandons the new trajectory and starts the optimization process over again.

The length of the delay-check period depends on the distance between agents and environmental factors that could hamper communications, Kondo says. If the agents are many miles apart, for instance, then the delay-check period would need to be longer.

Completely collision-free

The researchers tested their new approach by running hundreds of simulations in which they artificially introduced communication delays. In each simulation, Robust MADER was 100 percent successful at generating collision-free trajectories, while all the baselines caused crashes.

The researchers also built six drones and two aerial obstacles and tested Robust MADER in a multiagent flight environment. They found that, while using the original version of MADER in this environment would have resulted in seven collisions, Robust MADER did not cause a single crash in any of the hardware experiments.

“Until you actually fly the hardware, you don’t know what might cause a problem. Because we know that there is a difference between simulations and hardware, we made the algorithm robust, so it worked in the actual drones, and seeing that in practice was very rewarding,” Kondo says.

Drones were able to fly 3.4 meters per second with Robust MADER, although they had a slightly longer average travel time than some baselines. But no other method was perfectly collision-free in every experiment.

In the future, Kondo and his collaborators want to put Robust MADER to the test outdoors, where many obstacles and types of noise can affect communications. They also want to outfit drones with visual sensors so they can detect other agents or obstacles, predict their movements, and include that information in trajectory optimizations.

This work was supported by Boeing Research and Technology.