Computational control of networks of dynamical systems: Application to the National Airspace System

The research presented in this thesis is motivated by the need for efficient analysis, automation, and optimization tools for the National Airspace System (NAS).; A 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 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). For other problems, approximation algorithms are designed, with guaranteed bounds on running time and performance.; 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. An adjoint-based method is developed for controlling network flow problems and applied to 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 NAS-wide ATC control strategies in the form of flow patterns to apply to streams of aircraft.; Finally, tactical control problems at the level of the dynamics of individual aircraft are studied. The problem of proving safety of conflict avoidance protocols is posed in the Hamilton-Jacobi framework. 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.