|
The
first part of the project is described in [1] and summarized on this
page. The animations can be played in Quicktime 7 or Windows Media
Player 9 and above.
Abstract. A new Eulerian model of airspace is derived and applied to high
altitude traffic for a full Air Traffic Control Center of the National
Airspace System. The Eulerian model is reduced to a linear time
invariant dynamical system, in which the state is a vector of
aggregate aircraft counts. The model is validated against ASDI data
and applied to the Oakland airspace. The problem of controlling sector
aircraft count is posed as an Integer Program, in which the dynamical
system appears in the contraints. To improve the computational time of
calculating the solution, the Integer Program is relaxed to a Linear Program, solved
for instances with more than one million variables. The computational
results show that a high proportion of solutions of the LP are
integers. The computational time is satisfactory for two hour Traffic
Flow Management problems.
 
FACET (courtesy of NASA Ames). Click on image to start movie.
|
Eulerian models.
The almost uninterrupted growth of US air traffic over the last few decades has motivated the design of a semi-automated Air
Traffic Control (ATC) system to help Air Traffic Controllers manage
the increasing complexity of traffic flow in the en route
airspace. ATC is operated at the sector level, where a sector is a small
portion of the airspace controlled by a single human Air Traffic
Controller. Traffic Flow Management (TFM) typically deals
with traffic at the Center level, i.e. 10 to 20 sectors. TFM
problems include maintaining the aircraft count in each
sector below a legal threshold in order to ease the human ATC
workload, as well as to ensure the safety of the flights [2]. This task is quite cumbersome; furthermore, extensive
traffic forecast simulations (including all airborne aircraft) are
computationally too expensive to include systematic investigations of
traffic patterns that lead to sector overload. As a result, a new class
of traffic flow models has emerged from recent studies: Eulerian
models, which are control volume based [3]. This is in
contrast to Lagrangian models, which are trajectory-based and
take into account all aircraft trajectories.
Eulerian models have two main advantages over Lagrangian models:
(i)
They are computationally tractable, and their computational complexity
does not depend on the number of aircraft, but only on the size of the
physical problem of interest.
(ii) Their control-theoretic structure
enables the use of standard methodologies to analyze them.
 
Click on image to start movie.
|
Automated model building, and model validation.
Aircraft Situation Display to Industry (ASDI) data provides
flight information for all airborne aircraft at a given time, updated
every minute. It includes a time stamp and flight
data (latitude, longitude, heading, altitude, etc.).
The objective of automated model building is to
construct a graph-theoretic model of air traffic flow directly from the
ASDI
files. Several pattern recognition methods have been implemented
to automatically build a graph model of the observed
flows. The suite of algorithms investigated includes a variety of
techniques,
some of them relying purely on flight tracks, others using additional
information that can be extracted from ASDI data (e.g. flight plan
data). None of these algorithms have provided satisfactory results
for practical purposes, thus leading to a graph-theoretic approach
outlined in [1]. We developed an algorithm that takes the geographic
structure of the airspace as a starting point for building the desired
air traffic flow graph. Air traffic flow on this graph is modeled as a
discrete time linear dynamical system.
This model is validated using ASDI data and Future ATM Concepts Evaluation
Tool (FACET) [4]. In particular, we show that
the metric of interest for TFM (aircraft count) is reproduced
adequately by the model.
The animation shows the comparison of the actual ASDI data and the
simulation based on the model, for parts of Oakland, Salt Lake, Los
Angeles and Seattle ARTCCs (ZOA, ZLC, ZLA, and ZSE). In particular,
sector aircraft counts are displayed on the top graphs. Click on the
left-hand side of the image for the movie in WMV Windows Media Player
format, and on the right-hand side of the image for the movie in MOV
Quicktime format.
 
Click on image to start movie.
|
MILP formulation of two-hour Traffic Flow Management.
The problem of controlling aircraft counts in the airspace is posed as a Mixed Integer Linear Program
(MILP), where the dynamical
system appears in the constraints, as is
traditionally done in optimal control [5]. The mathematical formulation
of the MILP is provided in [1]. Numerical experiments are run to
demonstrate the tractability of these methods for problems involving
more than one million integer variables. The running time is improved
by relaxing the MILP to a Linear Program
(LP) to provide
guaranteed polynomial running time. The computational results show a
high proportion of integer solutions to the LP, appropriate for the
application of interest. The resulting computational time is
satisfactory for two hour Traffic Flow Management problems (a few
minutes for a two hour window).
The animation shows the results of the MILP, as well as the
corresponding sector count in the controlled sector (ZOA33, colored on
the animation). As a comparison, the situation in absence of control is
also displayed: the capacity of ZOA33 (chosen arbitrarily as 10
aircraft in this study) is violated without actuation.
References.
[1] C.-A. Robelin, D. Sun, G.
Wu, and A. M. Bayen, "MILP control of aggregate Eulerian network
airspace models," accepted in February 2006 for publication in the Proceedings of the 2006 American Control Conference.
[2] S. Devasia, M. Heymann, abd G. Meyer, "Automation procedures for air traffic management: a token-based approach," in Proceedings of the American Control Conference, Anchorage, AK, May 2002, pp. 736-741.
[3] P. K. Menon, G. D. Sweriduk, and K. Bilimoria, "New approach for modeling, analysis and control of air traffic flow," AIAA Journal of Guidance, Control and Dynamics, vol. 27, no. 5, pp. 737-744, 2004.
[4] K. Bilimoria, B. Sridhar, G. Chatterji, K. Sheth, and S. Grabbe, "FACET: Future ATM concepts evaluation tool," in Proceedings of the 3rd USA/Europe ATM 2001 R&D Seminar, Naples, Italy, June 2001.
[5] F. Borreli, Ed., Constrained Optimal Control of Linear and Hybrid Systems, ser. Lecture Notes in Control and Information Sciences. New York, NY: Springer Verlag, 2003, vol. 290.
|
People 
