Stanford team develops software to predict and prevent drone collisions

When Jeff Bezos unveiled his vision of drones delivering packages to Amazon customers during a 60 Minutes segment in late 2013, it caught many people as science fiction. Scarcely two years later, drones are poised to become a technology for not just delivering packages, but monitoring agriculture, gathering news in urban environments and even conducting search and rescue missions.

But before drone aviation can become pervasive, a new infrastructure must be developed to define low-altitude avenues of flight, regulate traffic in congested areas and prevent collisions.

On this front, the Stanford Intelligent Systems Laboratory (SISL) is part of a broad partnership led by NASA Ames to create an unmanned aerial system traffic management system, or UTM, to manage the expected surge in unmanned flights.

“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 envisions that the UTM system will be able to support the orchestration of a huge number of drone operations without air traffic control operators monitoring each and every vehicle in the air. A key attribute of this system will involve automated conflict avoidance – software that can alert multiple drones when a collision is possible, and calculate the maneuvers necessary to avoid it.

Kochenderfer recently coauthored a new paper with mechanical engineering graduate student Hao Yi Ong in which they detail a conflict-avoidance algorithm that, when implemented within the UTM system, will minimize the threat of low-altitude, unmanned collisions.

Ong says the sheer projected number of drones would make it impractical to replicate the human-operated air traffic control system to regulate drone flights.

Today the Federal Aviation Administration has 15,000 human controllers to manage roughly 87,000 pilot-driven flights per day.

Amazon’s drone projections alone could dwarf those numbers. Ong has conservatively estimated that Amazon Prime’s roughly 40 million subscribers could generate 130,000 drone deliveries per normal shopping day. And that’s before accounting for the dozens of other companies including Google and Matternet that are also developing commercial drone operations.

“You’re not going to hire another 30,000 people just to handle the traffic from drones,” Ong said. “It’s just not feasible.”

Avoiding conflict

NASA envisions that the cloud-based, largely autonomous UTM system will roll out in a series of four builds with increasing capabilities. The first build, which was released in August, largely focuses on geo-fencing – GPS-based corridors for drone flights – to maintain safety and efficiency.

“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.”

The Stanford team believes that automated conflict avoidance is the best way to enable a greater density of flights in crowded areas. But automating conflict avoidance to deal with the volume of drone traffic will require new algorithms to predict and avoid potential collisions.

Previously, when Kochenderfer worked at MIT’s Lincoln Laboratory, he developed a new approach to collision avoidance that is being incorporated into a next-generation system for manned aircraft, called ACAS X, that could serve as the building block for such a protocol. The system employs a process known as dynamic programming to figure out optimal collision avoidance strategies. In ACAS X, the software alerts human operators of potential risk and recommends a maneuver to avoid collision. The result has been a system that significantly enhances safety while decreasing the number of unnecessary alerts.

“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.

Beating ‘the curse of dimensionality’

Ong adapted some of the techniques from ACAS X and applied them toward developing an automated conflict avoidance system for unmanned aircraft. But the expected density of drone flights created an entirely new level of complexity for the SISL team.

“In traditional aviation, conflicts between more than two aircraft are pretty rare,” Ong said.

But in confined, urban airspaces, conflicts could easily involve three or more drones. For instance, consider several packages being delivered to the same address. Or imagine a blaze that draws multiple drones from the fire department, police and local media.

“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.”

To beat the curse, Ong’s cloud computing architecture separates multi-aircraft conflicts into paired problems. It quickly picks the best action for each pair of drones from a table predicting each drone’s flight path. The server then coordinates each of these pairwise solutions and issues a joint collision avoidance order to all of the affected drones.

In a matter of milliseconds, a dozen drones delivering Christmas Eve packages will know precisely what maneuvers to take to ensure each enjoys a safe flight path down a crowded cul-de-sac.

To test this approach, the researchers ran over 1 million simulations of encounters between two to 10 aircraft. They compared their pairwise solution to other solutions, such as a less-coordinated strategy in which each drone only reacts to its closest threat. Their pairwise solution showed significant safety improvements, faster decision times and decreased alert rates.

Ong and Kochenderfer said more work remains to be done, for instance, to account for communication breakdowns, sudden weather anomalies or deliberately disruptive drones. But they expect that an evolved version of their architecture will be implemented in one of the final builds of the UTM, which NASA estimates will be completed 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.