New Algorithm Keeps Drones from Colliding in Midair

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.

Adam Zewe is a writer at Massachusetts Institute of Technology. This strory is reprinted with permission of MIT News.