|
It is the central tenet of the Free Flight concept
that the proper distribution of real-time decision-making
between users and air traffic service providers
will improve system safety and efficiency. Consequently,
it is important to thoroughly understand the
trade-off between centralized and decentralized
information flow and control for such large systems.
Technically such systems are difficult to analyze
because they are composed of many objects that
interact in a complex and hybrid environment. At
present there are no effective analytical tools for use
in the design and analysis of such systems. The
objective of the present task is to contribute, through
university research grants and internal research, to
the development of such tools, and to then apply
them to the specific case of air traffic management.
The participating universities are the University of
California at Berkeley, University of Utah, University
of Illinois at Chicago, Wayne State University, Case
Western Reserve University, and State University of
New York at Stony Brook.
One approach that is followed is to try to understand
in detail simpler problems and to then generalize
the results to the real problem. An example is
shown in the figure. The system evolves on a rectangular
grid, and only two-dimensional motion along
the grid is permitted. There are sources injecting
objects representing individual flights into the grid
and sinks absorbing the objects. Sources and sinks
may represent departure and arrival airports or entry
and exit cells at a given flight level. In the figure, the
cell at (1,1) is both a sink for gray objects and a
source of black objects. Conversely, the cell at (12,14)
the example there are only two colors; in the general
case there may be many more. Each object attempts
to minimize the total number of steps that it takes to
move from source to sink. There are many solutions
for each object. Safety dictates that occupation of the
same cell or the interchange of cells is forbidden.
System cost is the conflict-free total deviation from
the sum of individual minima. The following questions
are addressed: Does a given departure sched-ule
have a zero-cost solution? Does a given pattern
on the grid have a zero-cost solution? In either case if
there is a solution, can the solution be constructed
with only local information and local rules and
decisions, or are global information and central
control necessary? If there is no zero-cost solution,
then what are the minimum-cost solutions? What is
the most efficient modification of the schedule or
pattern? The key objective of the research is to obtain
answers to these questions analytically and only from
the properties of schedules and patterns. Progress has
been made in this direction, and theorems have been
developed that guarantee local cost-free solutions.
For example, according to one theorem, if (1) the
source/sink pair is not inline, (2) the pair is separated
by a distance that is a multiple of four, (3) the time of
departure for one color is a multiple of four, (0, 4,
8,...), and (4) that of the other color is the same but
staggered by two, (2, 6, 10,...), then all conflicts are
resolvable by local one-one negotiation. Consequently,
the pattern in the figure is solvable without
central control. On the other hand, several resolvable
configurations that require central control have also
been found. The objective of the work on this cellular
model of air traffic management is to complete the
theory for the two-color case, and then extend the
results to more colors.
Point of Contact: G. Meyer
(650) 604-5750
gmeyer@mail.arc.nasa.gov
Back To Top
Previous Paper
Return to Global Civil Aviation
Next Paper |
|
Fig. 1. An example configuration.
|
|
