Amazon introduced their drone delivery program in 2013. Some didn’t believe the program would surface, but a few years after, the possibility of drone delivery is far greater than ever. Drones would be useful for a lot of things like media, agriculture, and crowd control.
Scroll down for video
But drones could become too many in the sky and our airspace would become congested. There would be the need to develop a means of avoiding collisions between drones in the air.
A partnership by NASA Ames with the Stanford Intelligent Systems Laboratory (SISL) is making efforts to create an unmanned aerial system traffic management system (UTM) to manage the expected increase in drones.
“UTM is meant to fulfill a lot of the functions of air traffic control, but it will be in the cloud and largely automated,” said SISL Director Mykel Kochenderfer, an assistant professor of aeronautics and astronautics.
NASA predicts that the UTM would be able to manage a congested air traffic without the need of human controllers. A key part of UTM is its ability to alert several drones when a collision is imminent and calculate maneuvers necessary to avoid the collision.
Kochenderfer coauthored a paper with mechanical engineering graduate student Hao Yi Ong. The paper details an algorithm that would reduce the future possibilities of drone collisions when the algorithm is implemented within the UTM system.
The FAA has 15,000 human controllers handling 87,000 flights per day. Imagine a future where there are about 130,000 drones in the sky. Do you hire twice the number of human controllers available currently to cater to this new traffic? No need. The software would handle the task more efficiently.
Avoiding Drone Conflicts
The UTM system would be released in four builds. The first build would focus on geo-fencing. This involves GPS-based corridors for drone flights.
“That works for farming applications,” Ong said. “But once you want to start moving transport drones around urban areas, you can’t really do that, because you’re not going to block out the airspace over entire residential areas just for when your aircraft is flying through.”
It is believed by the team that conflict avoidance is the best way to deal with flights in crowded areas, but this would involve new algorithms.
ACAS X was developed by Kochenderfer as a new approach to conflict avoidance. The system uses a dynamic programming process to reason out optimal collision avoidance strategies. The software alerts human operators of possible risks and recommends maneuvers to prevent collisions.
“The FAA was very happy with the outcome and supported further development,” Kochenderfer said. Indeed, the ACAS X system is currently being standardized by the FAA and the international safety community.
The Dimensionality Course
The techniques from ACAS X were applied to drones, but the number of drones were too much for the system.
“In traditional aviation, conflicts between more than two aircraft are pretty rare,” Ong shared.
Imagine a fire accident. There would be multiple drones from firefighters, police, and the media. The drones might keep on clashing with each other, thereby undermining the emergency efforts.
“As the number of aircraft grows, the avoidance problem becomes exponentially more complicated—a challenge that mathematicians call the curse of dimensionality,” Ong said. “So we have to come up with better ways than just brute-force searching and iterating through all possible solutions.”
A pairwise solution was developed to overcome these problems, and it worked as collisions were avoided and faster safer flight plans were devised for each drone in the system.
More work would still be done to improve the system a lot. It is estimated that one of the final builds of the architecture would be available by 2019.
“It’s gratifying to work on a problem that people are coming together and knocking heads and figuring out the best solution, even though there actually isn’t a single profitable flight yet,” said Ong, whose work was recognized in September as the Best Graduate Student Paper at the Digital Avionics Systems Conference held in Prague.