When Jeff Bezos unveiled his vision of drones delivering packages to Amazon customers in late 2013, it struck many people as science fiction. But now, scarcely two years later, drones are poised to become a technology for not just delivering packages, but also monitoring agriculture, gathering news in urban environments, and even conducting search and rescue missions.
But before drone aviation can become pervasive, there needs to be a new infrastructure 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 unpiloted aerial system traffic management system, or UTM, to manage the expected surge in these kind of 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,” says SISL Director Mykel Kochenderfer, assistant professor of aeronautics and astronautics at Stanford University.
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, unpiloted collisions.
The sheer projected number of drones would make it impractical to replicate the human-operated air traffic control system to regulate drone flights, Ong says.
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 says. “It’s just not feasible.”
Avoiding Collisions
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 says. “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.”
Researchers believe 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.
Kochenderfer previously developed a new approach to collision avoidance that is being incorporated into a next-generation system for piloted 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 says. Indeed, the ACAS X system is currently being standardized by the FAA and the international safety community.
Ong adapted some of the techniques from ACAS X and applied them toward developing an automated conflict avoidance system for unpiloted aircraft. But the expected density of drone flights create an entirely new level of complexity for the SISL team.
“In traditional aviation, conflicts between more than two aircraft are pretty rare,” Ong says.
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 says. “So we have to come up with better ways than just brute-force searching and iterating through all possible solutions.”
Crowded Cul-de-sacs
To beat the curse, the 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.
More work remains to be done, for instance, to account for communication breakdowns, sudden weather anomalies, or deliberately disruptive drones. But researchers 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,” Ong says.
This article was originally published by Ian Chipman for Stanford University. Republished via Futurity.org under Creative Commons License 4.0.
