When multiple drones are working in the same airspace, perhaps spraying pesticides on a cornfield, they run the risk of colliding with each other. To help avoid these costly collisions, researchers at MIT proposed a system called MADER in 2020. This multi-agent trajectory planner enables a group of drones to develop an optimal, collision-free trajectory.
Each agent broadcasts its trajectory so that the other drones know where it intends to go. The agents then consider each other’s trajectories as they optimize their own to ensure they do not collide.
But when the team tested the system on real drones, they found that if the drone didn’t have up-to-date information about its partner’s trajectory, it could inadvertently choose a path that led to a collision. The researchers modified their system and are now rolling out Robust MADER, a multi-agent trajectory planner that generates collision-free trajectories even when communication between agents is delayed.
“MADER works well in simulations, but it has not been tested in hardware. Therefore, we built a batch of drones and started flying them. The drones need to talk to each other to share trajectories, but once you start flying, you quickly realize that there are always communication delays that introduce some glitches,” said Kota Kondo, a graduate student in aeronautics and astronautics.
Making multiple drones work together
When multiple drones are working together in the same airspace, they run the risk of colliding. But now researchers at AeroAstro have created a trajectory planning system that allows drones in the same airspace to always choose a safe path forward. Credit: Courtesy of the researchers
The algorithm includes a delay-checking step, during which the drone waits a certain amount of time before committing to a new, optimized trajectory. If it receives additional trajectory information from other drones during the delay, it may abandon its new trajectory and restart the optimization process.
When Kondo and his collaborators tested Robust MADER in flight experiments with simulated and real drones, it achieved a 100 percent success rate in generating collision-free trajectories. While the drones’ flight times were somewhat slower than some other methods, no other baseline could guarantee safety.
“If you want to fly safer, you have to be careful, so it makes sense that if you don’t want to collide with an obstacle, it will take longer to get to your destination.” Kondo said, “If you collide with something, it doesn’t really matter how fast you go, because you won’t get to your destination.”
Kondo, along with postdoctoral fellow Jesus Tordesillas, graduate student Parker C. Lusk, MIT undergraduates Reinaldo Figueroa, Juan Rached and Joseph Merkel, and senior author Richard C. Maclaurin Professor of Aeronautics and Astronautics and Information and Decision Systems Laboratory (LIDS) principal investigator and member of the MIT-IBM Watson AI Lab, Jonathan P. How, co-authored the paper. The research will be presented at the International Conference on Robotics and Automation.
Planning trajectories
MADER is an asynchronous, decentralized, multi-agent trajectory planner. This means that each UAV develops its own trajectory, and while all agents must agree on each new trajectory, they do not need to agree at the same time. This makes MADER more scalable than other approaches, since it is difficult for thousands of UAVs to agree on a trajectory at the same time. Because of its decentralized nature, the system will also work better in realistic 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 receives from other agents. By constantly optimizing and broadcasting their new trajectories, drones can avoid collisions.
However, perhaps an agent shared its new trajectory a few seconds ago, but its companion did not receive it immediately due to communication delays. In real-world environments, signals are often delayed by environmental factors such as interference from other devices or stormy weather. Due to this inevitable delay, a drone may inadvertently submit a new trajectory that puts it on a collision course.
Robust MADER completely prevents such collisions because each agent has two available trajectories. It keeps one trajectory that it knows is safe and that it has checked for potential collisions. While flying along the original trajectory, the drone optimizes a new trajectory, but it will not commit to the new trajectory until it has completed the delayed check step.
During the delayed check, the drone spends a fixed amount of time double-checking 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 again. The length of the delayed checking period depends on the distance between agents and environmental factors that may impede communication. For example, if the agents are miles apart, then the delayed check period needs to be longer.
Eliminating collisions completely
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% successful in generating collision-free trajectories, while all baselines caused collisions.
The researchers also built six drones and two aerial obstacles and tested Robust MADER in a multi-agent flight environment. they found that while using the original version of MADER in this environment 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 problems. Because we know there’s a difference between simulation and hardware, we made the algorithm robust so it works in real drones, and it’s very rewarding to see that in practice,” Kondo said.
Using Robust MADER, the drones were able to fly 3.4 meters per second, although their average travel time was slightly longer than some baselines. But no method has been completely collision-free in every experiment.
In the future, Kondo and his collaborators hope to put Robust MADER to the test outdoors, where there are many obstacles and types of noise that can interfere with communication. They also want to equip the drones with vision sensors so that they can detect other agents or obstacles, predict their movements, and incorporate that information into trajectory optimization.
