Team develops software to predict and prevent drone collisions

December 11, 2015 by Ian Chipman
Stanford engineers are developing software to predict and prevent collisions of unmanned aircraft, including delivery drones, in congested urban airspace. Credit: Chesky / Shutterstock

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

Explore further: Pioneering air traffic management system aims for safer drone air traffic

Related Stories

Wal-Mart eyes drone home deliveries

October 27, 2015

Wal-Mart is actively looking at the possibility of using drones to make deliveries to US customers, a spokesman said Monday, following the lead of Amazon and other retailers.

Government tests technology to find illegal drone operators

October 7, 2015

The Federal Aviation Administration has signed an agreement to test technology that could locate the operators of small drones that are flying illegally near airports, as the government tries to crack down on near-collisions ...

Recommended for you


Adjust slider to filter visible comments by rank

Display comments: newest first

5 / 5 (2) Dec 11, 2015
Watch for GPS spoofing, GPS jamming, injection of virtual drones into the network for a "DDOS" type attack (or stealthing of an individual drone from the network) and probably a dozen more shenannigans to create havok. If this isn't massively encrypted/secured and redundantly laid out then hackers are going to have a field day with this.
5 / 5 (2) Dec 11, 2015
Hackers, bad weather, target shooters, the guys who like to steal packages off porches (just follow the drone). The list goes on.
5 / 5 (3) Dec 11, 2015
the guys who like to steal packages off porches (just follow the drone).

At least that could be avoided. Over here, if you have no one to accept a package for you during the day, packages are delivered to automatic 'packing stations'. You are sent a key code with which you can retreive it from there.
Drones could deliver to such stations (where the packages are ssafely locked away) instead of directly to the front porch.
This would also make it possible for drones to navigate along a few, well established routes and fly by image recognition instead of solely by GPS (which would make spoofing a lot harder).

I don't see bad weather as much of a factor since that is quite predictable (and shooters are probably only an issue in the US).
5 / 5 (1) Dec 11, 2015
...(and shooters are probably only an issue in the US).
As fast as the drones can avoid collisions, they can identify and report the location of the active idiot with a gun. And the drones would also work wonders helping to catch the idiots who light up the cockpits of manned aircraft with lasers...
not rated yet Dec 11, 2015
I am dubious that drones are a good idea at all. Aircraft must navigate over people, property, etc. Any failure can be very bad.

o If one causes an accident where loss of life is concerned, how do we deal with this?
o If one loses power over your car, now what does your insurance do?
o If the drone you requested loses power over your friends car, he/his insurance, sues >>you<< for requesting an "accident prone automated delivery system" that failed, causing him damage.

More questions:
o How much cargo does a drone carry?
o How far can it go and still return to home base?
o Will these drones carry hazardous materials? (E.g., medicines, flammable liquids, etc.
o Are these commercial units powered with batteries, or fuel cells?
o Do they have RF locators in case they fail over a lake, park, or garbage dump?
o Is there a reward for returning a damaged drone?

So many questions, so few answers.
1 / 5 (1) Dec 12, 2015
So many questions, so few answers.
The answers are plentiful and you know so few of them that you're not asking good questions. For example, the proper question concerning accidents and liabilities is more along the lines of, "What are the ambulance chasers and disaster racketeers going to do for a living when drones and self-driving cars put an end to transportation mishaps?"
not rated yet Dec 13, 2015
Every complicated problem has numerous simple but useless answers. Drones may be good for some, and bad for others. The questions are: Good for who and bad for who? ambulance chasers will find a way to profit ...
not rated yet Dec 13, 2015
Every complicated problem has numerous simple but useless answers.
Yes, you've demonstrated that quite well.

Drones may be good for some, and bad for others. The questions are: Good for who and bad for who?
Good for all, even the lawbreakers and trouble makers they'll catch. Bad for a diminishing few who inject a healthy dose of human error into the particular circumstances.

ambulance chasers will find a way to profit ...
An economy predicated around greed and fear as motivation is a collective psychosis, a literal physical, neurological addiction to the fight-or-flight stimulus. Over the course of a few generations, it not only destroys all vibrance of the economy, but left unregulated it destroys the planet.
3 / 5 (2) Dec 13, 2015
OT Sorry for the delayed answer.
5 / 5 (1) Dec 13, 2015
Techno, thanks for following up, I'll check it out & respond as time permits, hopefully tomorrow.

Please sign in to add a comment. Registration is free, and takes less than a minute. Read more

Click here to reset your password.
Sign in to get notified via email when new comments are made.