Ph.D. Dissertation

Defense: Oct. 1, 2003, AA297 Seminar in Guidance, Navigation and Control, Stanford University
Submission: Dec. 2, 2003
Degree conferral: Jan. 8, 2004

Academic Advisor: Professor Claire J. Tomlin, Aeronautics and Astronautics, Stanford

Committee chair: Professor Yinyu Ye, Management Sciences and Engineering, Stanford
Committee member: Professor Stephen P. Boyd, Electrical Engineering, Stanford
Committee member: Professor Antony Jameson, Aeronautics and Astronautics, Stanford
Committee member: Professor Sanjay Lall, Aeronautics and Astronautics, Stanford
Committee member: Dr. George Meyer, Automation Concepts Branch, NASA Ames

Abstract:

The research presented in this thesis is motivated by the need for efficient analysis, automation, and optimization tools for the National Airspace System (NAS) and more generally for large scale networks of dynamical systems.

A new modeling framework based on hybrid system theory is developed, which captures congestion propagation into the Air Traffic Control (ATC) system. This model is validated against Enhanced Traffic Management System (ETMS) data and used for analyzing low level actuation of the human Air Traffic Controller. This model enables us to quantify the capacity limit of the airspace in terms of geometry and traffic patterns, as well as the speed of propagation of congestion in the system. Once this setting is in place, maneuver assignment problems are posed as optimization programs, some of which can be reduced to Mixed Integer Linear Programs (MILPs). Problem specific algorithms are designed to show that certain MILPs can be solved exactly in polynomial time. These algorithms are shown to run faster than CPLEX (the leading commercial software to solve MILPs) when implemented on the same platforms. For other problems, approximation algorithms are designed, with guaranteed bounds on running time and performance. An architecture is proposed for the implementation of this method using a live ETMS data feed.

Flow control problems in the NAS are modeled using an Eulerian framework. A partial differential equation (PDE) model of high altitude traffic is derived, using a modified Lighthill-Whitham-Richards (LWR) PDE. High altitude traffic is modeled as a network of LWR PDEs linked through their boundary conditions. The model is validated against ETMS data. A new adjoint-based method is developed for controlling ATC network flow management problems and successfully applied to realistic scenarios for the airspace between Chicago and the east coast. Accurate numerical analysis schemes are used and run very fast on this set of coupled one dimensional problems. The resulting simulations provide high level ATC control strategy (i.e. NAS-wide) in the form of flow patterns and routing policies to apply to streams of aircraft going through the system.

Finally, tactical control problems at the level of the dynamics of individual aircraft are studied in order to meet safety specifications. The problem of proving safety of conflict avoidance protocols is posed in the Hamilton-Jacobi framework, and linked to existing mathematical results. A proof of safety is derived for conflict avoidance. It is tested on real ATC scenarios for En Route traffic and shows an excellent match with recorded Air Traffic Controller's actions. 

[Download as PDF file: 6.3 Mb]

[Download as gzipped PS file: 4.2 Mb]