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.

Chad Jenkins named Editor-in-Chief of the ACM Transactions on Human-Robot Interaction (THRI)

We are thrilled to become part of the ACM family of journals,” explained THRI Co-Editor-in-Chief Odest Chadwicke Jenkins of the University of Michigan. “ACM’s reputation as a publisher of computing research is unparalleled. At the same time, the broad representation of computing disciplines in the ACM, the organization’s global reach, and platforms such as the Digital Library, are a perfect complement to our own goals for THRI.

Jenkins, along with Co-Editor-in-Chief Selma Šabanović of Indiana University, have set three primary goals for the journal in the coming years, including: 1) Sustaining the intellectual growth of HRI as a field of study (both quantitatively and qualitatively), 2) Enabling timely and productive feedback from readers, and 3) Cultivating new and leading-edge ideas in both robotics and the human-centered sciences

The inaugural issue of the rebranded ACM Transactions on Human-Robot Interaction (THRI) is planned for March 2018. Those seeking to submit for the publication, or who have questions for the editors, are encouraged to visit the current HRI Journal website.

The full article.

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.

U-M CSE Graduate Students present papers at ICAPS 2017

CSE graduate students Qi Zhang and Shun Zhang will present exciting research papers at ICAPS 2017, the 27th International Conference on Automated Planning and Scheduling, taking place this June at Carnegie Mellon University in Pittsburgh PA.

Here are the papers:

Minimizing Maximum Regret in Commitment Constrained Sequential Decision Making

Approximately-Optimal Queries for Planning in Reward-Uncertain Markov Decision Processes


A Shoutout to Two Michigan PhDs in Robotics

Science RoboticsThe research of Mechanical Engineering and Robotics alum Dr. Alireza Ramezani is featured on the February cover of Science Robotics. Dr. Ramezani defended his dissertation, “Feedback Control Design for MARLO, a 3D-Bipedal Robot,” in 2013. 

The U-M Mathematics Department has awarded Hamed Razavi with the 2016 Sumner B. Myers Prize, which honors the best PhD thesis in mathematics.  No award is made unless a thesis is judged to be truly distinguished:
Hamed Razavi, “Symmetry Method for Limit Cycle Walking of Legged Robots”, co-advised by Tony Bloch (Math) and Jessy Grizzle (EECS).
Michigan Daily 2/5/17 article