Decentralized air traffic control for drone-laden skies

Anticipating skies crowded with crisscrossing autonomous vehicles, University of Michigan researchers have developed a future air traffic control system that allows any number of autonomous planes to safely route around each other to their final destinations.

Kunal Garg, a University of Michigan graduate student, designed the system to be utilized by autonomous fixed-wing aircraft, which require more time and space to turn than rotorcraft such as quadcopters. The work could be extended to autonomous vehicles, which follow similar turning dynamics.

autonomous air traffic simulation
In this simulation, autonomous fixed-wing aircraft change goal points and flight modes to avoid collisions based on control laws developed by Kunal Garg.

“It doesn’t seem that complicated: given two points, design a safe trajectory,” Garg said. “But, adding the dynamics and constraints of fixed-wing aircraft, decentralizing the system to allow for unlimited scalability, and doing all this with a limited communication radius makes it complicated.”

In the paper, “Hybrid Planning and Control for Multiple Fixed-Wing Aircraft under Input Constraints,” Garg and his advisor Dimitra Panagou, Core Faculty in Robotics and Assistant Professor of Aerospace Engineering, show that for an arbitrarily large number of planes, the planes will always be able to resolve their conflicts, reach their goal location, and maintain safety.  The paper is a finalist in the 2019 American Institute of Aeronautics and Astronautics Scitech Conference Graduate Student Paper Competition.

In approaching the problem, Garg first simplified it with a realistic constraint. While planes can ascend or descend to avoid one another, there are likely to be altitude restrictions on autonomous aircraft, especially in urban areas. Given this, he removed altitude from the equation, and focused on creating safe flight paths in two dimensions.

With the simpler problem, Garg created the control laws.

“We wanted to exploit hybrid systems because designing a single controller for this complicated system would have been very difficult,” Garg said. “We divided the system into five modes and, depending on what the aircraft are doing, they will decide which mode to choose. Each mode which has its own controller that will make sure it is always safe.”

“If the aircraft is alone, the controller will take it to its goal location. If it has one aircraft coming head on, it will do a roundabout maneuver. If there are more than two aircraft, depending on their location, the algorithm will decide the safe mode for all of those aircraft.”

Allowing for safe paths in this system is also possible because aircraft can be assigned temporary goals in place of their final destination in order to avoid collisions. And, because the aircraft are not solving any optimization problems, the algorithms can be implemented on low-cost microcontroller boards that are often already onboard flying autonomous vehicles.

“Instead of trying to solve a complete problem in one go, hybrid system theory allows us to solve individual parts, where the analysis becomes simpler, and then we can stitch them together into a complete solution,” said Garg.

While the modes were hand-designed by the researchers, they hope in the future to automate the design of such a system, or as Garg said, “How can we design an algorithm that will find an algorithm for safe trajectories?”

In addition, the team is working on adding other types of aircraft, such as quadcopters, to their system. They are also testing cases where there might be disturbances, such as malfunctioning sensors or wind.

The research is supported by NASA Grant NNX16AH81A and the Air Force Office of Scientific Research award number FA9550-17-1-0284.

Yuxiao Chen’s Formal Design Process: Achieving Ever-Greater Balance Between Safety and Performance

The concept of “formal methods”, also know as “correct by construction” is applied to the trajectory planning for mobile robots/small autonomous vehicles. The main challenges are (i) the presence of multiple moving objects (pedestrians, other robots/vehicles), and (ii) plant uncertainties. We aim to address both in our research.

The example publications show a formal design process to deal with multiple moving objects (without considering plant uncertainties). Our method achieves better balance between safety (zero collision!) and performance (the robot does not keep stopping to avoid collisions) compared with other methods from the literature.

Mr. Yuxiao Chen is a U-M graduate student co-advised by Professors Huei Peng and Jessy Grizzle.

Necmiye Ozay Wins Hybrid Systems Prize

For her outstanding work in hybrid systems, a theoretical area very important to robotics, Professor Necmiye Ozay has received a major best paper award. The details of her award are here. Necmiye’s work on Correct-by-Design Control Software Synthesis is aimed at breaking down the barriers that have prevented this field from tackling important industrial problems. In the paper, she and her co-author develop finite abstractions that are equipped with robustness margins, allowing sensing and model imperfections to be addressed in a formally correct manner. They apply the results to Adaptive Cruise Control, an important Automated Drive Assist System, and point out other important applications in robotics and autonomous vehicles.

A new robotic navigation method: Multi-Policy Decision Making (MPDM)

In dynamic environments crowded with people, robot motion planning becomes difficult due to the complex and tightly-coupled interactions between agents. Trajectory planning methods, supported by models of typical human behavior and personal space, often produce reasonable behavior. However, they do not account for the future closed loop interactions of other agents with the trajectory being constructed. As a consequence, the trajectories are unable to anticipate cooperative interactions (such as a human yielding), or adverse interactions (such as the robot blocking the way). We propose a new method – Multi-Policy Decision Making (MPDM) for navigation amongst pedestrians in which the trajectory of the robot is not explicitly planned, but instead, a planning process selects one of a set of closed-loop behaviors whose utility can be predicted through forward simulation.

Read more.

Here is the MPDM presentation by Dhanvin Mehta, Gonzalo Ferrer and Edwin Olson, U-M, Ann Arbor.