NASA/TM–2012–216033

Efficient Computation of

Separation-Compliant Speed

Advisories for Air Traffic

Arriving in Terminal Airspace

A. V. Sadovsky

Ames Research Center, Moffett Field, California

D. Davis

UCLA, Department of Mathematics, Los Angeles, CA 90095-1555

D. R. Isaacson

Ames Research Center, Moffett Field, California

July 2012
NASA STI Program . . . in Profile

Since its founding, NASA has been

dedicated to the advancement of

aeronautics and space science. The

NASA scientific and technical

information (STI) program plays a key

part in helping NASA maintain this

important role.

The NASA STI Program operates

under the auspices of the Agency Chief

Information Officer. It collects,

organizes, provides for archiving, and

disseminates NASA’s STI. The NASA

STI Program provides access to the

NASA Aeronautics and Space

Database and its public interface, the

NASA Technical Report Server, thus

providing one of the largest collection

of aeronautical and space science STI

in the world. Results are published in

both non-NASA channels and by

NASA in the NASA STI Report Series,

which includes the following report

types:

• TECHNICAL PUBLICATION.

Reports of completed research or a

major significant phase of research

that present the results of NASA

programs and include extensive data

or theoretical analysis. Includes

compilations of significant scientific

and technical data and information

deemed to be of continuing reference

value. NASA counterpart of

peer-reviewed formal professional

papers, but having less stringent

limitations on manuscript length and

extent of graphic presentations.

• TECHNICAL MEMORANDUM.

Scientific and technical findings that

are preliminary or of specialized

interest, e.g., quick release reports,

working papers, and bibliographies

that contain minimal annotation.

Does not contain extensive analysis.

• CONTRACTOR REPORT.

Scientific and technical findings by

NASA-sponsored contractors and

grantees.

• CONFERENCE PUBLICATION.

Collected papers from scientific and

technical conferences, symposia,

seminars, or other meetings

sponsored or co-sponsored by NASA.

• SPECIAL PUBLICATION.

Scientific, technical, or historical

information from NASA programs,

projects, and missions, often

concerned with subjects having

substantial public interest.

• TECHNICAL TRANSLATION.

English- language translations of

foreign scientific and technical

material pertinent to NASA’s

mission.

Specialized services also include

creating custom thesauri, building

customized databases, and organizing

and publishing research results.

For more information about the NASA

STI Program, see the following:

• Access the NASA STI program home

page at http://www.sti.nasa.gov

• E-mail your question via the Internet

to help@sti.nasa.gov

• Fax your question to the NASA STI

Help Desk at 443-757-5803

• Phone the NASA STI Help Desk at

443-757-5802

• Write to:

NASA STI Help Desk

NASA Center for AeroSpace

Information

7115 Standard Drive

Hanover, MD 21076–1320
NASA/TM–2012–216033

Efficient Computation of

Separation-Compliant Speed

Advisories for Air Traffic

Arriving in Terminal Airspace

A. V. Sadovsky

Ames Research Center, Moffett Field, California

D. Davis

UCLA, Department of Mathematics, Los Angeles, CA 90095-1555

D. R. Isaacson

Ames Research Center, Moffett Field, California

National Aeronautics and

Space Administration

Ames Research Center

Moffett Field, California 94035-0001

July 2012
Acknowledgments

D. Davis’s research was supported by NSF Grant DGE-0707424.

The use of trademarks or names of manufacturers in this report is for accurate reporting and

does not constitute an offical endorsement, either expressed or implied, of such products or

manufacturers by the National Aeronautics and Space Administration.

Available from:

NASA Center for AeroSpace Information

7115 Standard Drive

Hanover, MD 21076-1320

443-757-5802
Abstract

A class of problems in air traffic management asks for a scheduling algorithm that supplies the air traffic services authority not only with a

schedule of arrivals and departures, but also with speed advisories. Since

advisories must be finite, a scheduling algorithm must ultimately produce

a finite data set, hence must either start with a purely discrete model

or involve a discretization of a continuous one. The former choice, often

preferred for intuitive clarity, naturally leads to mixed-integer programs,

hindering proofs of correctness and computational cost bounds (crucial

for real-time operations). In this paper, a hybrid control system is used

to model air traffic scheduling, capturing both the discrete and continuous aspects. This framework is applied to a class of problems, called the

Fully Routed Nominal Problem. We prove a number of geometric results

on feasible schedules and use these results to formulate an algorithm that

attempts to compute a collective speed advisory, effectively finite, and

has computational cost polynomial in the number of aircraft. This work

is a first step toward optimization and models refined with more realistic

detail.

1
Contents

1 Introduction 3

2 Background 4

3 An HCS Model of an Airspace 5

4 The Geometry of a Minimal Separation Requirement 9

5 An Alternative: Path-Based Transportation HCS 11

6 A Geometric Theory of the Fully Routed Nominal Arrival Problem 12

6.1 Problem Definition and Geometric Properties . . . . . . . 13

6.2 Simplifying Assumptions and Their Implications . . . . . 13

6.3 Geometry of the Global Continuous State Space . . . . . 14

6.3.1 The Global Coordinate System . . . . . . . . . . . 14

6.3.2 The Target Set and the Distal Boundary . . . . . . 14

6.3.3 Polygonally Approximated Pairwise Conflict Zones:

the Geometric Properties Used in the Algorithm . 15

6.3.4 Safe Wedges, Innermost Conflict Edges, and Distal

Innermost Conflict-Free Points (DICPs) . . . . . . 16

6.3.5 The Cone of Attainability, Feasible Trajectories,

and Feasible Solutions . . . . . . . . . . . . . . . . 17

6.3.6 The Geometry of FCFS: the Closest DICP to y

Corresponds to the Safe Wedge Containing y . . . 19

6.3.7 Existence and Nonexistence of Feasible Solutions . 20

7 A Polynomial-Time Speed Control Algorithm for Computing a Feasible Solution or Reporting That None Was

Found 21

8 Sample Numerical Solutions 22

9 Discussion 23

10 Acknowledgment 24

Acknowledgment 24

2
1 Introduction

Management of air traffic that is confined to a network of nominal routes

requires that each aircraft be scheduled to at least a few crucial waypoints and arrive at each waypoint as near as possible to the scheduled

time. This requirement gives rise to an entire class of scheduling problems, which vary by airspace configuration and various flight restrictions,

such as speed- or altitude ranges, aircraft type, and weather. Since the

airspace is often modeled as a directed graph, and a schedule as a chart

that estimates for each aircraft a time of arrival at each of the finitely

many waypoints, models of centralized scheduling of arrivals are frequently also sought in this, discrete, setting [?,?,?,?,?,?,?].

In such a model, aircraft are scheduled only at specific points (the

vertices of the graph), with no time stamps maintained or imputed of

the aircraft’s position or speed away from such a point. One weakness

of such inherently discrete models is their principal inability to assure,

without adding artificial constraints, pairwise separation between the

aircraft continuously in time, as is operationally required [?]. Another

weakness, specific to the models that lead to a mixed-integer program

(MIP) [?], is the difficulty of finding an algorithm that performs sufficiently better than the NP-hard worst case of a general mixed-integer

linear program (MILP) [?], although a number of the algorithms developed for solving a MILP modeling air traffic have been shown to perform

with a running time polynomial in the number of aircraft (see, for example, [?,?]). However, while sufficient constraints can be imposed in a

discrete model to assure separation at all times, the authors are unaware

of published discrete models that assure such separation and show computational performance suitable for aircraft traffic in a terminal airspace.

In this paper, we approach the scheduling of air traffic as a timecontinuous problem. The hybrid control system (HCS) framework proposed in [?] is used for modeling air traffic motion continuously in time

in a broad class of airspace regions represented as directed multigraphs.

A schedule sought in this framework is, thus, a speed advisory, i.e. a

continuous time parameterization of each aircraft’s motion along a predetermined path. The pairwise separation requirements are imposed in

continuous time.

This framework has two main merits. First, it is capable of capturing realistically the following aspects of the research field of Air Traffic

Management (ATM): separation requirements for every pair of aircraft at

every instant in time, speed restrictions, off-nominal routes, and uncertainty in the actual times of an aircraft’s arrival at a waypoint. Second,

it rests on the apparatus of HCS, which is relatively well-understood theoretically [?,?,?,?,?,?,?] and furnished with general numerical methods

(see, e.g., [?]). While no optimization is pursued in this paper, and only

feasible trajectories are sought for a given HCS, the framework can serve

as a setting for problems in optimal control [?].

3
The contribution of this paper is an algorithm for the class of Fully

Routed Nominal Problems (section ??) in ATM, where the goal is to

guide a given finite set of aircraft, each along its pre-determined path,

out of the route network in a separation-compliant way. The algorithm,

formulated in section ??, constructs, or reports failure to construct, a

feasible (i.e., compliant with the separation and speed range constraints)

speed advisory that guides all the aircraft as required. The computational cost is shown to be bounded by a low-degree polynomial in the

number of aircraft.

2 Background

The inherently discrete models mentioned in section ?? have historic origins. Planning of air transportation, from the time it came into mass

use and to the time of this writing, has in practice been based on two

doctrines, i), that scheduling and separation assurance are two separate

tasks and, ii), that a schedule need not synthesize for each aircraft a 4-D

aircraft trajectory (i.e., a time-parameterized curve in 3-D space), but

only specify an appropriate set of waypoints and the times at which they

should be reached by the aircraft. (Current air transportation operations

rely on Air Traffic Control (ATC) [?] to devise and issue clearance instructions to each aircraft and to modify the schedule when necessary in

order to maintain aircraft separation.) While automated trajectory synthesis has received some attention from researchers (see [?] and references

within) and is finding its way into air traffic operations (see, e.g., [?,?]),

doctrine i) remains a dominant practice: currently such synthesis does

not meet, simultaneously, a given schedule and the time-continuous pairwise separation requirement.

As these conservative tendencies have persisted, increases in traffic demand have hampered ATC’s mission–to promote “safe, orderly,

and expeditious flow of traffic” [?]–in all aspects except safety. To address these newly arising difficulties of ATC, researchers have sought

to minimize various performance indices. Examples of such indices are

makespan [?, ?], fuel burn [?, ?], average or total delay [?, ?], excess

separation [?], and deviation from preferred time of arrivals and departures [?]. With this broadened focus, researchers have approached various types of air traffic scheduling problems in terminal airspace using

such frameworks as dynamic network flows, constraint-based scheduling,

and scheduling combined with separation considerations; a detailed survey, references, and discussion of this past research can be found in [?].

Further work on, and wider use of, automated generation of 4-D trajectories, as envisioned in the future [?], will raise the question of how

the responsibility for scheduling and for separation should be divided

between the automation system and the human controller. Having 4-D

trajectory generation handled by the automation, and separation assur4
ance by the controller, would leave the controller with the full weight

of separation responsibility while considerably restricting their freedom

in the choice of aircraft maneuvers. Such a practice is likely to limit

the benefits associated with the use of 4-D trajectories and likely to

be unacceptable to air traffic controllers. This consideration has led us

to consider an investigation, undertaken herein, of algorithms for 4-D

trajectory generation that aim, as a controller does today, to maintain

separation along the entire continuous trajectory for each aircraft.

3 An HCS Model of an Airspace

100 150 200 250 300 350 400 450 500 550 600

240

260

280

300

320

340

360

380

400

420

 nmi

 nmi

A portion of the LAX Terminal Airspace 

for arriving traffic 

arrival runway 

Figure 1. A portion of the LAX terminal airspace for arriving traffic.

The thin arrows indicate the traffic directions.

For the operational purposes of ATM, an airspace is regarded as a region

with a set of marked points, called waypoints. Some pairs of waypoints

are connected by route segments. (For example, a portion of the airspace

surrounding the Los Angeles International Airport is shown in Fig. ??.)

The same pair of points may be connected by more than one segment.

In practice, a route segment directly connecting a pair of waypoints is

rectilinear, but this assumption is made here only in section ??. This

setting is naturally modeled by a directed multigraph [?]: the waypoints

are the vertices, while the route segments are the edges. A sequence of

route segments with every consecutive pair adjacent is called a route and

is none other than the graph-theoretic path [?].

Although the application central to this paper is in ATM, the following construct is, in principle, suitable for any finite set of moving agents

whose movement is confined to a route network. Assume one is given

5
the following data:

1. A directed multigraph G = (V, E), each vertex v ∈ V being a point

in a Euclidean space E of dimension 2 or 3. If e ∈ E is an edge from

v1 ∈ V to v2 ∈ V , then the nominal route segment from waypoint

v1 to waypoint v2 is a curve in E, connecting v1 to v2. All such

curves will henceforth be assumed rectifiable [?, section 4.6-9] and

capable of a parameterization which is continuous and piecewise

continuously differentiable. A cusp in the curve can be traversed

with the assumption (made throughout this paper) that inertia is

neglected, and approximately smoothed if inertia is included. The

outdegree and indegree of a vertex are allowed arbitrary values. To

emphasize the aerospace context, the multigraph G = (V, E) will

be called a route network.

2. A finite set A = {1, . . . , A}. of moving agents α ∈ A in G. If agent

α is moving along edge e, the agent’s position is specified by the

arc length coordinate y

α

e along a path containing e; the choice of

arc length coordinates will be clarified as the model is developed

and will always have the coordinate increase along the direction of

the edge.

3. For each agent α ∈ A, a specification of the agent’s initial position,

which is a point in G specified, for example, by an edge in G and

a fractional distance along that edge.

4. The inertia-free dynamical law [?] (henceforth the dot denotes differentiation with respect to physical time t)  ̇x

α

e = s

α

e

, where the

s

α

e

’s are the corresponding speeds, describing the motion of those

agents α that have not yet exited the system. In what follows, and

with the details provided in the following paragraph, the coordinates x

α

e will play the role of state variables; the speeds s

α

e

, of the

control variables.

5. State constraints: the separation requirement for each pair of agents.

This requirement is described mathematically, in terms of the coordinates x

α, in section ??. A state in which at least one pair of

agents violates the separation requirement will be called a conflicting state.

6. Control constraints: bounds on the speeds s

α

e

.

6
(A)

e2

e1 e3

e4

e5 

e6

1

2

3

(B)

e2

e1

e4

e5 

e6

1

2

3

e3

(C)

e2

e1

e4

e5 

e6

1

2

3

e3

Figure 2. Examples of three discrete modes with edge set E =

{e1, e2, . . . , e6} and moving agent set A = {1, 2, 3} (A = 3). The agents

are shown as numbered gray squares. The discrete modes shown are: (A)

μ1 : μ1(1) = e1, μ1(2) = e1, μ1(3) = e4; (B) μ2 : μ2(1) = e1, μ2(2) =

e2, μ2(3) = e4; (C) μ3 : μ3(1) = e1, μ3(2) = e3, μ3(3) = e4.

One choice of a hybrid control system (HCS) [?] fit for modeling

coordinated multi-agent motion in a route network G was introduced

in [?]. In this HCS, one defines each discrete mode (in [?], location) as

a mapping μ : A → E, which specifies for each agent α the edge μ(α)

currently occupied by that agent. Examples of three discrete modes on

a 6-edge route network with 3 moving agents are shown in Fig. ??.

(A)

l(e4)

l(e1)

(0,0,0)

2

μ1

1

l(e1)

3

X

(B)

l(e4)

l(e1)

(0,0,0)

2

1

l(e2)

3

μ2

X

(C)

l(e4)

l(e1)

(0,0,0)

2

1

l(e3)

3

μ3

X

(D)

2

1

3

2

2

μ1

X

μ2

X μ3

X

Figure 3. (A-C) The continuous state spaces Xμ1, Xμ2, Xμ3corresponding to discrete modes μ1, μ2, μ3 from Fig. ??. Among the discrete modes

the system may enter from μ1 are μ2 and μ3, accordingly as agent 2 enters e2 or e3. Conflicting states not shown. (D) A gluing of Xμ1

to Xμ2

and to Xμ3. Glued, all three state spaces share a face, but no two have

any other points in common. Conflicting states not shown.

Denoting the arc length parameterization of edge μ(α) by x

α

μ

, the

dynamical law corresponding to discrete mode μ is given by the system

x ̇

α

μ = s

α

μ

, α ∈ A, of differential control equations. Suppose each x

α

μ

ranges from 0 to the length l(μ(α)) of edge μ(α). The set Xμ of all

continuous states xμ = (x

α

μ

)α∈A =



x

1

μ

, x2

μ

, . . . , xA

μ



in discrete mode

μ is then obtained by taking the A-dimensional parallelotope given by

7
the Cartesian product Q

α

[0, l(μ(α))] and removing from it all states

that violate the separation constraint for at least one pair of agents

(conflicting states). (The set Xμ is an example of a roadmap coordination

space, defined in [?, section 1.2].) For example, Fig. ??A shows the Xμ1

for discrete mode μ1 from Fig. ??A; the conflicting states are not shown

in Fig. ??.

One must then specify, for each pair of states xμ ∈ Xμ, xμ′ ∈ Xμ′ ,

whether it is possible for the system to go from one to the other, thus

switching from one discrete mode to another, instantly. The set, denoted

Sμ,μ′, of all such state pairs (xμ, xμ′) for a given pair of discrete modes

μ, μ′is called a switching set [?]. For this HCS, the switching sets are

completely determined by the following condition: (xμ, xμ′) ∈ Sμ,μ′ if

and only if there is at least one agent, α, that in discrete mode μ occupies

a vertex v ∈ V with coordinate x

α

μ = l(μ(α)), and in discrete mode μ

′

occupies that same vertex with coordinate x

α

μ′ = 0. Thus, as the system

switches from μ to μ

′

, agent α exits edge μ(α) and enters edge μ

′

(α).

Geometrically, the switching sets are described by a topological gluing

[?] (similar to that used in [?, section 3]) between the corresponding

continuous state spaces Xμ and Xμ′: the right endpoint of [0, l(μ(α))]

is identified with the left endpoint of [0, l(μ

′

(α))]. If the transition from

μ to μ

′

involves a change of edge for more than one agent, then each of

these agents effects a gluing. Thus, the face x

α

μ(α) = l(μ(α)) of Xμ is

to be glued to the face x

α

μ′(α) = 0 of Xμ′ for each discrete mode μ

′

that

allows a direct transition from μ. (For example, in Fig. ??(A-C), the

“top” (in the sense of the Figure) face of Xμ1is glued to the bottom face

of Xμ2and of Xμ3; see Fig. ??D.) The state space obtained by carrying

out all such gluings, and denoted X, is called the global continuous state

space. Denoting the gluing operation by the non-standard symbol

glue

∪ ,

one has X =

glue

∪ μ Xμ. Since the set of the conflicting states in each

Xμ is closed [?], as it will be defined below using sharp inequalities,

two states xμ, xμ′ identified as a result of the above gluing are either

both conflicting or both separation-compliant. It follows from the above

that every global continuous state space is a chain of dimension A on

RA [?, section 35E] with the conflicting states removed, but generally

fails to be a differentiable manifold [?].

The only discrete control variable appearing in this HCS would thus

be the one indicating, for an agent reaching a vertex of outdegree ≥ 2,

which edge the agent is to take (or whether the agent should exit the

system) when leaving that vertex.

8
4 The Geometry of a Minimal Separation Requirement

(A)

2

1

e1

e2

a1

a2

0

θ

(B)

2

1

e1

e2

c1a1

c2a2

0

θ

Figure 4. Agents 1, 2 on their respective rectilinear edges e1, e2, which

share a common vertex, taken as the origin 0 in R2. The orientation

of the edges is not specified. (A) The unit vectors a1, a2 are collinear

with the respective edges, but their directions do not necessarily agree

with the edges’ orientations. (B) With suitably chosen scalar coefficients

c1, c2, the vectors c1a1 and c2a2 are the respective position vectors of the

two agents.

In some types of transportation, including aircraft and trains, every pair

of moving agents must be separated by a distance no smaller than a predetermined minimal separation. Such requirements can be asymmetric

and anisotropic; for a detailed discussion, see [?, section II]. Here we

will characterize states that violate the separation requirement using

conservative approximations, addressing only the following asymmetry:

if two moving agents are in-trail (i.e., one is directly following the other

along a route segment which is not necessarily in a horizontal plane) and

have different weight classes, then the minimal separation can depend on

the weight class of the agent in front. (For example, if an aircraft of type

Heavy is directly following one of type Small, the required separation is

smaller than if the aircraft were interchanged.) To capture this potential

asymmetry, for each pair α1, α2 of agents with the first one leading, we

introduce the minimal separation rα1,α2. If the asymmetry takes place,

it can be written

rα1,α26= rα2,α1(1)

We now calculate the set of all conflicting states in a discrete mode μ of an

HCS described above; recall that these are the states where at least two

agents violate the separation requirement. The scenario shown in Fig.

??A has two agents on two different rectilinear edges, which need not lie

in a horizontal plane, with a common vertex and no specified orientation.

(If the edges are curvilinear with low curvature near a common vertex

or intersection, these portions can be approximated by linear segments;

otherwise, the analysis becomes considerably more complicated.)

9
Remark 4.1. Since edge orientation is not specified, Fig. ?? describes

four cases: both agents are moving toward the common vertex, both moving away from the common vertex, and two more cases in which one agent

moves toward, and the other away from, the common vertex.

(A)

c2

c1

(B)

c2

c1

Figure 5. (A) An example of two elliptical sectors in the c1c2-plane

corresponding to conflicting states. (B) An example of two stripes in the

c1c2-plane corresponding to conflicting states of two agents on the same

edge.

We will use the Euclidean inner product [?] h·, ·i and the corresponding norm [?] || · || in the 2-D space containing the two edges. Pick the

common vertex as the origin and the unit vectors a1, a2 as the basis

vectors that, regardless of the edge orientations, point from the origin

toward the respective agents. With suitable scalars c1, c2, the vectors

c1a1 and c2a2 are the agents’ respective position vectors. The squared

distance between the two agents, denoted by D2, is

D2 = ||c1a1 − c2a2||2 = (c1)

2 + (c2)2 − 2c1c2ha1, a2i

Equating D2to the squared minimal separation, say, r

2

1,2

, we obtain the

equation

D

2 = r2

1,2

of an ellipse in the c1c2-plane. The corresponding set of conflicting sets

is described by the elliptical sector obtained by intersecting the open

octant c2 > c1 > 0 with the ellipse-bound region D2 < r2

1,2

(respectively,

D < r2

2,1

) when agent 1 (respectively, agent 2) is the one closer to the

origin. The role of the angle θ between the edges e1, e2 in both sectors is

the equality ha1, a2i = cos(θ). An example of two such sectors is shown

in Fig. ??A. The asymmetry of the gray-shaded region about the dashed

diagonal is the asymmetry (??).

In each of the four cases listed in Remark ??, the respective continuous state coordinates x

1

μ

, x2

μ of agents 1, 2 in discrete mode μ map to

the coefficients c1, c2, as follows:

1. If both agents are moving toward the common vertex, then x

α

μ =

l(eα) − cα for α = 1, 2.

2. If both agents are moving away from the common vertex, then

x

α

μ = cα for α = 1, 2.

10
3. If agent 1 is approaching, and agent 2 going away from, the common

vertex, then x

1

μ = l(e1) − c1, x2μ = c2.

4. If agent 2 is approaching, and agent 1 going away from, the common

vertex, then x

1

μ = c1, x2μ = l(e2) − c2.

If θ ≥ 90◦, then in the last two cases μ allows only one in-trail sequence,

so the minimal separations used for the two sectors in Fig. ??A are

equal. If the two agents 1, 2 are on the same edge, then the set in

the c1c2-plane of the conflicting states appears as in Fig. ??B and is,

in accordance with (??), asymmetric about the dashed diagonal. The

mapping from the continuous state coordinates x

1

μ

, x2

μ

to the coefficients

c1, c2 is constructed analogously to the above four cases.

(A)

1

2

(B)

2

1

(C)

Figure 6. An example of two agents whose paths overlap. The black

star shows the beginning of the overlap in (A) and the corresponding

state (both agents being at that point) in (B); the white star, the end

of the overlap in (A) and the corresponding state (both agents being at

that point) in (B). The system, shown in (A), has seven discrete modes

with both agents in the transportation network. Each mode’s set of

separation-violating states, shown in (B) as a connected [?] gray region,

is “glued” to some of the others. The result of the gluing is the connected

region shown in (C).

The above calculation is illustrated, for an example of two moving

agents, in Fig. ??. Each discrete mode’s set of conflicting states is

shown as a connected [?] gray region. For dimension A above 2, one must

compute for each pair of agents the set of states violating the separation

requirements. Each such set is a cylinder, or union of cylinders, with the

base shaped as shown in Fig. ??C, in the total state space ∪μXμ. We

note that the set of all separation-violating states in ∪μXμ is cylindrical

in the sense of [?, Definition 2.2], the latter definition a key requirement

for the applicability of a number of theoretical results of [?].

5 An Alternative: Path-Based Transportation

HCS

The HCS defined in this section will be instrumental in a precise formulation of the Fully Routed Nominal Arrival problem, defined in section

??. Assume the data ??)-??), listed in section ??, are given.

11
1. For each agent α ∈ A, let e

INIT;α denote the edge occupied initially

by agent α. (Two or more agents can occupy the same edge.)

2. Let P



e

INIT;α



be the set of all paths in the multigraph that

begin with the edge e

INIT;α and end with an edge that contains

an acceptable destination for α. Denote the length of a path p ∈

P



e

INIT;α



by l(p).

3. Define each discrete mode as a mapping that assigns each agent

α to a path in P



e

INIT;α



. In more detail, ν is a mapping from

the set A of moving agents to the union ∪αP



e

INIT;α



such that

ν(α) ∈ P e

INIT;α



for each α ∈ A.

4. In each ν, have the arc length coordinate y

α

ν

evolve according to

the dynamical law

y ̇

α

ν = s

α

ν

, α ∈ A, (2)

where s

α

ν

is the control variable corresponding to the agent’s speed

of motion along the path.

5. For each agent α and each discrete mode μ, specify the speed constraint

S

α;min

μ ≤ s

α ≤ Sα;max

μ

, (3)

where [S

α;min

μ

, Sα;max

μ

] is the speed range allowed for agent α in

discrete mode μ.

Definition 5.1. The HCS defined in this section will be called a pathbased transportation HCS.

In a path-based transportation HCS, every discrete mode ν corresponds to a possible routing of the agents in A, and every execution

occurs in only one discrete mode. It follows that the discrete controls

in a path-based transportation HCS are, effectively, identified with the

discrete modes, and play but a trivial role.

6 A Geometric Theory of the Fully Routed Nominal Arrival Problem

The geometric results obtained in this section will be used in the formulation of the algorithm in section ?? to prove correctness and bounds on

computational costs for some of the steps.

12
6.1 Problem Definition and Geometric Properties

In this section, we describe and analyze theoretically a subclass of the

HCS defined above, the analysis being a foundation for the algorithm in

section ??. This subclass represents a most commonly modeled scenario

of air traffic, which is arriving in merging and, possibly, diverging flows,

with no multiple routing options: each arriving aircraft follows without

deviation a prescribed path in the route network. Consequently, the

resulting path-based transportation HCS (definition ??) has only one

discrete mode. Henceforth, the moving agents are aircraft. The subscript

ν will be dropped for brevity.

Remark 6.1. The assumption that each aircraft is assigned a route may

not always hold. In cases when such assignment (known in Air Traffic

Operations as routing) is not given, but is sought as part of the problem,

the corresponding HCS has multiple discrete modes. The theory and

algorithm developed in this section can then be used for each of those

discrete modes, and the result computed in one of the modes selected

later as final. See [?] for an analysis of computational costs and the

possibility of parallel computation of routing.

The problem consists in computing a control strategy (s

α(t))α∈A that

will, in accordance with dynamical law (??), take each aircraft to the end

of its prescribed path. To ATM operations, such a control strategy would

serve as a speed advisory. This problem will be called the Fully Routed

Nominal Arrival problem. It consists in finding feasible trajectories. No

optimization is pursued.

Section ?? gives a list of assumptions made to simplify the computations. As is shown below, these assumptions allow a solution by an

algorithm that is noniterative and proven to halt in polynomial time (in

the number of aircraft). Because of the urgency that can accompany

ATM decisions, this bound on computation time is a highly desired feature of every solution candidate to be deployed as an operational tool in

the field, especially for automated tools responsible for both separation

assurance and scheduling.

6.2 Simplifying Assumptions and Their Implications

Assumption 6.1. All control strategies considered before section ?? will

be assumed executable with certainty, i.e. without execution error that

may be caused by wind, transportation performance, or human factors.

In particular, under this assumption, the aircraft is able to follow its

prescribed route exactly, without deviation.

An approach to including execution uncertainty in the model is discussed in section ??.

13
Assumption 6.2. All aircraft have the same cruising speed range,

[S

min, Smax]

Assumption 6.3. All aircraft pairs have the same required minimal

separation distance, henceforth denoted r.

Assumption 6.4. During the execution of the algorithm described in

section ??, below, no new aircraft enter the system.

6.3 Geometry of the Global Continuous State Space

6.3.1 The Global Coordinate System

Since the system is fully routed, each aircraft α is assigned a uniquely

determined path, whose length will henceforth be denoted Mα, α =

1, . . . , A. Accordingly, the global state space Y for the problem can

be obtained by removing from the parallelotope Q

α∈A[0, Mα] all the

conflicting states. We choose the coordinate system, for the whole of

Y , so that the state variable y

α indicates the arc length coordinate of

aircraft α on its path and ranges from 0 to Mα. Unless said otherwise,

all state variables are regarded as coordinates referred to the standard

basis e1 = (1, 0, . . . , 0, 0), . . . , eA = (0, 0, . . . , 0, 1).

6.3.2 The Target Set and the Distal Boundary

(A)

distal edges

0

(B)

M

0

Figure 7. The case of A = 3 aircraft: (A) The distal edges and the target

set, and (B) an illustration of the distal boundary.

14
The vertex M = (M1, . . . , MA) of Y will be called the distal vertex of

Y . The faces of Y containing the distal vertex will be called distal faces.

Distal faces of dimension 1 will be called distal edges. Since the distal

edges correspond, one-to-one, to states in which all but one aircraft have

exited the airspace, we define the target set of the Fully Routed Nominal

Arrival problem as the union of all distal edges. Fig. ??A illustrates the

distal edges for 3 aircraft.

The union of all the (A − 1)-dimensional faces adjacent to the distal

vertex will be called the distal boundary. An illustration of the distal

boundary for the case of 3 aircraft is given in Fig. ??B.

6.3.3 Polygonally Approximated Pairwise Conflict Zones: the

Geometric Properties Used in the Algorithm

Each pairwise conflict zone will be approximated here by a polygon that

is the intersection of three half-planes. This approximation achieves

considerable computational advantage, but likely incurs a cost if an optimization were pursued: by enlarging the conflict zone, one restricts the

class of considered candidate solutions. This loss would be most severe

if at least two of the paths of the agents were to cross (the relevant

operational concepts are same courses, crossing courses, and opposite

courses; see [?, section 1-2-2].) In the framework of the above model,

such a crossing can be viewed as a short overlap (compare to Fig. ??).

To analyze the geometry of the conflicting state sets that result from this

approximation in the global state space X, it will be convenient to introduce the technical terms of protrusion, safe wedge, innermost conflict

edge, and distal innermost conflict-free point.

In the A-dimensional Euclidean space RA, define the unit vector

d = √

1

A

(1, 1, . . . , 1).

Let Hα1,α2;−1 and Hα1,α2;+1 denote, respectively, the half-spaces consisting of all states y = (y

1

, . . . , yA) satisfying y

α1 − yα2 > −rα1,α2 and

y

α1 − yα2 < rα1,α2

, where r

α1,α2

is the sum of the required minimal separation distance between aircraft α1 and α2 and a “buffer,” which is a

value sufficiently large to make sure that the obtained polygonal approximation contains all of the exact pairwise conflict zone depicted in Fig.

??C.

15
(A)

M

d

(B)

M

d

(C)

M

d

(D) (E)

innermost

conflict−

free

edges

M

d

DICPs

Figure 8. The shaded regions are the orthogonal projections of the halfspaces (A) Hα1,α2;−1

, (B) Hα1,α2;+1, and (C) F

α1,α2 onto the yα1 yα2

-

plane. Their intersection is the polygonal approximation, shown in Fig.

??D, of the conflict zone for α1, α2. (D) An approximation of a pairwise

conflict zone (Fig. ??C) by a polygonal region equal to the intersection

of three half-planes. (E) The geometry of the safe wedges (shaded) and

DICPs.

Define the half-space F

α1,α2 to consist of all states y satisfying hy −

M, −di < fα1,α2, where f

α1,α2

is the orthogonal distance from M to the

bounding hyperplane of F

α1,α2 (Fig. ??).

The pairwise conflict zone for the aircraft pair α1, α2 is, then, approximated by the open [?] polyhedral region

Z

α1,α2 = Hα1,α2;−1 ∩ Hα1,α2;+1 ∩ Fα1,α2

, (4)

depicted in Fig. ??D. The distance f

α1,α2 will be called the protrusion

of the conflict zone (??).

6.3.4 Safe Wedges, Innermost Conflict Edges, and Distal Innermost Conflict-Free Points (DICPs)

The intersection Hα1,α2;−1 ∩ Hα1,α2;+1 is a conflicting slab of the form

|y

α1 −y

α2

| < r. By “removing” from the A-dimensional Euclidean space

16
RA all the conflicting slabs (i.e., the slabs corresponding to all pairs of

aircraft), one obtains a pairwise disjoint collection of A! polyhedral regions, called safe wedges. The intersection of a safe wedge with the global

continuous state space is a conflict-free region and has a 1-dimensional

face (a line) parallel to d. This line will be called an innermost conflictfree edge. The intersection of this edge with a distal face of dimension

(A − 1) is a point called a distal innermost conflict-free point (DICP).

Safety wedges and DICPs for the case of A = 2 aircraft are illustrated

in Fig. ??E.

Consider “the positive A-dimensional quadrant”

RA

≥0 = {(y

1

, y2, . . . , yA) : y

α ≥ 0 for all α}

of the A-dimensional Euclidean space RA. For each permutation σ of

the indices 1, . . . , A, the set of all y = (y

1

, y2, . . . , yA) such that

0 ≤ y

σ(1) < yσ(2) < . . . < yσ(A)

(5)

determines a subset Yσ of the “quadrant” RA

≥0

.

Definition 6.1. The subset Yσ (in fact, the interior of a polyhedral

angle) will henceforth be called the basic polyhedral angle corresponding

to the permutation σ.

Note: Henceforth, the end of a mathematical proof is marked by an

open square.

Lemma 6.1. If the permutation σ is such that the safe wedge W consists

of all y = (y

1

, y2, . . . , yA) with

y

σ(α) ≤ r + yσ(α+1) for α = 1, 2, . . . , A − 1, (6)

then W is contained in Yσ.

Proof. Condition (??) follows from (??).

Theorem 6.1. If all the required minimal distances for in-trail separation have the same value, r, then the coordinate A-tuple of every DICP

is the sum of M and a permutation of 0, −r, −2r, . . . , −(A − 1)r, and,

conversely, every such permutation gives a DICP.

Proof. These A-tuples are exactly those at which all constraints (??) are

active.

6.3.5 The Cone of Attainability, Feasible Trajectories, and

Feasible Solutions

The flow of the traffic consisting of A aircraft α = 1, . . . , A can be seen

as a trajectory (y

1

(t), y2(t), . . . , yA(t)) of the inertia-free dynamical law

(??).

17
Remark 6.2. Throughout this paper, the term collective trajectory (or,

simply, trajectory) will mean a time-parameterized curve

(y

1

(t), y2(t), . . . , yA(t))

in the global continuous state space X that satisfies (??) for some choice

of a control strategy s(t) = (s

1

(t), . . . , sA(t)). This usage of the term

trajectory differs from that commonly seen in Air Traffic Management.

(A)

y(t)

y0

= (y , y ) 1 2

0 0

(B)

(C)

Figure 9. An example with two aircraft. The conflict zone is as in Fig.

??D. (A) A collective state trajectory y(t), with initial state y(0) = y0.

(B) The cone of attainability C(y0) (shown in the lighter shade) at y0.

(C) The cone is positioned so that there are no feasible solutions.

Recall assumption ??. A segment y0 y in X is said to be attainable

if all aircraft pairs (α1, α2) satisfy

S

min

Smax

(y

α2 − y

α2

0

) ≤ y

α1 − y

α1

0 ≤

S

max

Smin (y

α2 − y

α2

0

) (7)

A ray emanating from y0 is said to be attainable if for every point y on

the ray the segment y0y is attainable. The union of all attainable rays

emanating from y0 is a polyhedral cone, called the cone of attainability at

y0 and denoted C(y0). This cone is a pointed cone with vertex y0. A collective trajectory y(t) with initial state y(0) = y0 is said to be attainable

if it is piecewise differentiable and, at every point y of differentiability,

the corresponding tangent vector lies in the cone of attainability at y.

18
A conflict-free attainable trajectory is said to be feasible. A 2-aircraft

example is shown notionally in Fig. ??.

Definition 6.2. A feasible trajectory whose final state is in the target

set is called a feasible solution.

The following lemma characterizes all the collective states from which

it is safe to have all aircraft fly at the same speed.

Lemma 6.2. If y0 is a DICP, then there exists a feasible solution with

initial state y0. Consequently, a feasible trajectory with the final state a

DICP can be extended to a feasible solution.

Let |·|∞ denote the max norm, defined for a vector ξ = (ξ1, ξ2, . . . , ξA)

in RA by |ξ|∞ = maxα |ξα|.

Proof. The collective trajectory y(t) = y0 + tSmax 1

|d|∞

d, with the α-th

component excluded once aircraft α exits the global continuous state

space, is conflict-free since y0 lies in a safe wedge and since y ̇ is codirectional with d.

6.3.6 The Geometry of FCFS: the Closest DICP to y Corresponds to the Safe Wedge Containing y

The key result of this section, theorem ??, tells how to find (in time

O(A2)) a DICP that requires “minimal position shifting” to be performed

on the current collective state.

Lemma 6.3. If a = (a1, a2) and b = (b1, b2) are vectors in the first octant of the 2-dimensional Euclidean space R2 with Cartesian coordinates

y1, y2, i.e. satisfy 0 < a1 < a2 and 0 < b1 < b2, then

a1b1 + a2b2 > a1b2 + a2b1 (8)

Proof. Both a and b lie in the positive quadrant of the plane and below

the diagonal y1 = y2. Therefore, the angle between a and b is smaller

than that between a and b

′ = (b2, b1) (the latter point being above the

diagonal). Since all angles are between 0 and π/2, one has ha, bi >

ha, b

′

i, which is inequality (??).

Lemma 6.4. Suppose a = (a1, . . . , aA) and b = (b1, . . . , bA) are vectors, with all standard components distinct, in the A-dimensional Euclidean space RA such that 0 < a1 < a2 < . . . < aA and 0 <

bα for α = 1, . . . , A. For each permutation σ of {1, 2, . . . , A}, let σb =

(bσ(1), bσ(2), . . . , bσ(A)). Then, of the products ha, σbi corresponding to all

the different permutations σ, a largest one is delivered by that permutation σ∗ for which bσ∗(1) < bσ∗(2) < . . . < bσ∗(A)

.

19
Proof. Applying BubbleSort [?] to the numerical sequence

b1, . . . , bA, (9)

one obtains a sequence σ1, σ2, . . . , σJ−1, σJ = σ∗ of permutations of

{1, 2, . . . , A}, every two consecutive ones differing by a transposition

that puts two elements of (??) in increasing order. By lemma ??,

ha, σj−1bi < ha, σjbi for j = 2, 3, . . . , J. Thus, the largest of the products ha, σjbi is given by σJ = σ∗.

The following helps locate a DICP closest to a given y.

Theorem 6.2. If y and a DICP p lie in the same basic polyhedral angle,

then p is a closest DICP to y.

Proof. For this proof, change coordinates so that M is now the origin,

and d points along the positive diagonal. If q were a DICP closer to

y than p is, then the permutation σ such that q = σp would satisfy

hσp, yi > hp, yi, contradicting lemma ??.

6.3.7 Existence and Nonexistence of Feasible Solutions

Lemma 6.5. (A sufficient condition for the existence of a feasible solution.) If y0 is in a safe wedge, then there exists a feasible solution with

initial state y0.

Proof. Consider the trajectory y(t) = y0+ts

1

|d|∞

d, with t increasing to

the value T for which y(T) lies on the distal boundary. By construction,

the trajectory is feasible, and y(T) lies in a safe wedge. The state yT ,

taken to be the initial state for a new, (A−1)-dimensional, problem, lies

in a safe wedge of the new ambient (A − 1)-dimensional space. (For, in

the state yT , at least one aircraft, say α-th, has exited the airspace, so

all the pairwise conflict zones involving α are removed.) Consequently,

the lemma holds by induction on A.

Theorem 6.3. (A sufficient condition for the absence of feasible solutions.) If a pairwise conflict zone (??) (not necessarily with a largest

protrusion) is such that C(y0)∩∂F α1,α2is contained entirely in the conflicting slab Hα1,α2;−1 ∩ Hα1,α2;+1 (Fig. ??C), then there is no feasible

solution with initial state y0.

Proof. In a cone C(y0) so positioned, every attainable collective trajectory reaches a conflicting state before reaching the target set.

20
7 A Polynomial-Time Speed Control Algorithm

for Computing a Feasible Solution or Reporting That None Was Found

Keep the notation introduced above. In the following algorithm, the

computational cost (abbreviated C.c.) of each step is given in square

brackets.

Given: An initial state y0, global continuous state space (completely

determined by (M − y0)), and the pairwise conflict zones (??).

1. Find all conflicting slabs that contain y0. [C.c.: (A

2

) = O(A2).]

2. If y0 lies in no conflicting slab, i.e., lies in a safe wedge, exit the

algorithm, returning the speed advisory constructed in lemma ??.

[C.c.: O(A).]

3. Test whether the collective state y0 is in any of the pairwise conflict

zones (??). [C.c.: O(A2).] If it is, go to step ??.

4. Find a DICP p closest to y0. [By theorem ??, the computational

cost of this step is O(A log2 A).]

5. Compute the state y1 = p + αd that lies on the boundary of

C(y0). [C.c.: O(A).]

Remark 7.1. By construction, the state y1 lies in a safe wedge,

hence the segment y1p is a feasible trajectory (lemma ??). If segment y0y1 is feasible, then the trajectory y0y1p is feasible and, by

lemma ??, extends to a feasible solution.

6. If segment y0y1 is feasible, exit the algorithm, returning the speed

advisory for the trajectory described in remark ??. [C.c.: O(A2).

Computations are required to check the feasibility of y0 y1.]

7. (In this step, let Γ denote the hyperplane orthogonal to d and

passing through the origin. Orthogonal projection onto Γ will also

be denoted by Γ.) Segment y0 y1 has been found infeasible. Use a

fixed number of iterations of the Bisection Method to look for the

parameter β that determines the point q = β Γp such that the

point y1;∗, defined as the intersection between the line through q

parallel to d and the boundary of C(y0), yields a feasible segment

y0 y1;∗. If this segment is found, return a speed advisory for the

trajectory y0 y1;∗p (analogously to step ??). Otherwise, go to step

??.

8. Exit the algorithm with the message, “Cannot produce a conflictfree speed advisory by speed control only.”

21
Table 1. The output format of an advisory segment.

a/c 1 speed a/c 2 speed . . . a/c A speed TTF

8 Sample Numerical Solutions

If a feasible speed advisory is found by the algorithm of section ?? successfully, it is output as one or more rectilinear segments, each called an

advisory segment and conforming to the format shown in Table ??. Here

TTF stands for the time to fly (with that speed) and indicates the time

duration in which the advisory segment is to be traversed. However, in

the numerical results presented below (Table ??), instead of showing all

the individual speeds, the following abbreviated format will be used:

min. of the A speeds max. of the A speeds TTF (10)

100 150 200 250 300 350 400 450 500 550 600

240

260

280

300

320

340

360

380

400

420

 nmi

 nmi

Elapsed time (hrs): 0

# aircraft: 23; actual speed min & max: [211.84, 250]

arrival runway 

Figure 10. The initial state of a traffic scenario for 23 aircraft. To capture

airspace adequately, an aspect ratio different from 1 is used. The thin

arrows indicate the directions of the traffic.

The above algorithm was applied to a number of arriving traffic scenarios in the portion of the LAX airspace shown in Fig. ??. Although all

the paths in this airspace portions converge to one runway, such convergence is not a requirement: the algorithm is applicable to all situations

where the aircraft follow pre-determined paths. The solutions found for

two of the scenarios, each with two advisory segments, are summarized

22
Table 2. Each of the Tables gives a 2-segment speed advisory and TTF

for an arriving traffic scenarios. In columns 4-6 of each Table, each line

fits format (??).

#

a/c

y0 advis.

seg.

min.

speed

(kts)

max.

speed

(kts)

seg.

TTF

(hr)

23 Fig. ?? 1

2

211.84

250.00

250.00

250.00

0.56

0.41

#

a/c

y0 advis.

seg.

min.

speed

(kts)

max.

speed

(kts)

seg.

TTF

(hr)

24 not

shown

1

2

199.11

250.00

250.00

250.00

0.59

0.44

in Table ??. The initial states are conflict-free. One of the two scenarios

is depicted in Fig. ??, with circles of radius r centered at the aircraft.

9 Discussion

The above HCS framework addresses simultaneously the following issues

in Air Traffic Management and adjacent fields: scheduling, speed advisory generation, conflicts (avoidance, detection, and recovery), computational efficiency, and algorithm correctness. The theory and algorithm

given above are mainly a proof of concept, intended to demonstrate how

HCS can be used to obtain provably correct solutions efficiently. The

following are some directions for further research.

Control equations with inertia: A model more realistic than the dynamical law (??) should include inertia, thus making the agents’s acceleration (and not speed) the quantity directly controllable.

Allowing new aircraft to enter the airspace during the computation: A

reasonable direction is a search for geometric insight into those entrances

for which the original, A-dimensional, problem has a feasible solution

but the newly obtained one does not. The problem above, together

with the Scheduled Routing Problem formulated in [?], suggest that

such insight would be valuable not only in air traffic management and in

airspace design, but also in the general field of multi-agent coordination.

In published literature, entrance of new aircraft into the system has been

considered in the context of the dynamic Aircraft Scheduling (Landing)

Problem (see [?]), which, however, does not consider separation except

at the runway.

Conflict recovery: Recovering from a conflicting state yc in the above

model is equivalent to finding–or establishing the absence of–a shortest

23
(or otherwise optimal) attainable trajectory from yc to a nearest safe

wedge. Theorem ?? is instrumental here, as a nearest safe wedge is with

a nearest DICP, and the latter is computable in time polynomial in A.

Path control (in ATM operational terminology, Vectors): In operational ATM practice, an aircraft is often allowed, and even instructed,

to deviate from a given route. Such deviations are known in Air Traffic

Operations as path control. This deformation of the given route results

in a deformation of the global continuous state space and of the pairwise

conflict zones. Insight into the relation between the two deformations

can be instrumental in extending the model to include path control.

Modeling uncertainty of control execution: Control of aircraft is affected by such sources of uncertainty as human factors, aircraft performance, and weather. In the context of the above HCS, such uncertainty

generally leads to stochastic dynamical law [?, chapter 14]. Among the

most common sources of random perturbation to an aircraft’s execution of control is wind. In the special case when each aircraft is cleared

for a procedure that prescribes a specific route consisting of rectilinear

segments, connected by fixed-radius turns (e.g., RF-leg types [?]), the

aircraft’s navigation system will keep the aircraft on the route even in

the presence of wind. Therefore, the wind affects only those components

of the aircraft’s speed and acceleration tangential to the route. This

suggests a stochastic dynamical law, for the Fully Routed Problem, that

includes inertia (i.e., the control variable is the acceleration), governs

the arc length coordinate y

α and the arc length speed sα as stochastic

processes serving as the state variables, and has the form

dyα = s

α

dt, dsα = a

α

dt + aw dt + dWα, α ∈ A

where aw is the (possibly time-dependent) mean of the tangential component of the acceleration due to wind, and W is a Wiener process that

characterizes the fluctuations of the acceleration due to wind about the

mean.

10 Acknowledgment

D. Davis’s research was supported by NSF Grant DGE-0707424. The

authors thank D. Denery (NASA ARC) for suggesting the use of hybrid

systems for ATM, W. Haskell (USC) for editing early drafts of the paper,

H. Swenson (NASA ARC) and J. Mitchell (SUNY Stony Brook) for

helpful suggestions.

References

1. Carr, G. C.; Erzberger, H.; and Neuman, F.: Delay Exchanges in Arrival Sequencing and Scheduling. Journal of Aircraft, vol. 36, 1999,

pp. 785–791.

24
2. Bayen, A.; Tomlin, C.; Ye, Y.; and Zhang, J.: An Approximation

Algorithm for Scheduling Aircraft with Holding Time. IEEE Conference on Decision and Control (CDC), 2003.

3. Roy, K.; Bayen, A.; and Tomlin, C.: Polynomial Time Algorithms

for Scheduling of Arrival Aircraft. AIAA Guidance, Navigation, and

Control Conference and Exhibit, 2005.

4. Bianco, L.; Dell’Olmo, P.; and Giordani, S.: Scheduling models for

air traffic control in terminal areas. J. Scheduling, vol. 9, no. 3, 2006,

pp. 223–253.

5. Balakrishnan, H.; and Chandran, B.: Scheduling Aircraft Landings

under Constrained Position Shifting. AIAA Guidance, Navigation,

and Control Conference and Exhibit, Keystone, CO, 2006.

6. Lee, H.; and Balakrishnan, H.: A Study of Tradeoffs in Scheduling

Terminal-Area Operations. Proceedings of the IEEE, vol. 96, no. 12,

dec. 2008, pp. 2081 –2095.

7. Chipalkatty, R.; Twu, P.; Rahmani, A.; and Egerstedt, M.: Distributed scheduling for air traffic throughput maximization during

the terminal phase of flight. Decision and Control (CDC), 2010 49th

IEEE Conference on, dec. 2010, pp. 1195 –1200.

8. U.S.A.: Order JO 7110.65T, Air Traffic Control. U.S. Dept.

of Transportation, Federal Aviation Administration, Washington,

D.C., 2010.

9. Bradley, S.; Hax, A.; and Magnanti, T.: Applied Mathematical Programming. Addison Wesley, 1977.

10. Vazirani, V. V.: Approximation Algorithms. Springer, Mar. 2004.

11. Bayen, A. M.; Zhang, J.; Tomlin, C. J.; and Ye, Y.: MILP formulation and polynomial time algorithm for an aircraft scheduling

problem. 2003.

12. Sadovsky, A.; Davis, D.; and Isaacson, D.: Optimal routing and

control of multiple agents moving in a transportation network and

subject to an arrival schedule and separation constraints. In review,

2012.

13. Sussmann, H. J.: A maximum principle for hybrid optimal control

problems. The 38th IEEE Conference on Decision and Control, 1999,

pp. 425–430.

14. Sussmann, H. J.: A nonsmooth hybrid maximum principle. The First

European Community Nonlinear Control Network Workshop on ‘Stability and Stabilization’, 1999, pp. 325–354.

25
15. Tomlin, C.; Mitchell, I.; Bayen, A. M.; and Oishi, M.: Computational techniques for the verification of hybrid systems. Proceedings

of the IEEE, vol. 91, no. 7, 2003, pp. 986–1001.

16. Branicky, M.: Introduction to hybrid systems. Birkhauser, 2005.

17. Simic, S.; Johansson, H.; Sastry, S.; and Lygeros, J.: Towards a geometric theory of hybrid systems. Dynamics of Continuous, Discrete,

and Impulsive Systems, Series A, 2005.

18. Dmitruk, A.; and Kaganovich, A.: The Hybrid Maximum Principle

is a consequence of Pontryagin Maximum Principle. Systems and

Control Letters, vol. 57, no. 11, 2008, pp. 964 – 970.

19. Passenberg, B.; Caines, P. E.; Sobotka, M.; Stursberg, O.; and Buss,

M.: The minimum principle for hybrid systems with partitioned

state space and unspecified discrete state sequence. in Proc. of the

49th IEEE Conf. on Decision and Control, 2010.

20. Sethian, J.; and Vladimirsky, A.: Ordered Upwinds Methods for Hybrid Control. Proceedings Fifth International Conference on Hybrid

Systems and Control, LCNS 2289, 2002.

21. D. R. Isaacson and J. E. Robinson III and H. Swenson and D. Denery: A Concept for Robust, High Density Terminal Air Traffic Operations. 10th AIAA Aviation Technology, Integration, and Operations

(ATIO) Conference, Fort Worth, TX , 2010.

22. Swenson, H. N.; Hoang, T.; Engelland, S.; Vincent, D.; Sanders, T.;

Sanford, B.; and Heere, K.: Design and Operational Evaluation of

the Traffic Management Advisor at the Fort Worth. 1st USA/Europe

Air Traffic Management R&D Seminar, Saclay, France, 1997, pp.

17 – 19.

23. Love, D.; Horn, W.; and Fellman, L.: An evaluation of the use of the

URET prototype tool at Indianapolis and Memphis air route traffic control centers, using benefit metrics. Digital Avionics Systems

Conference, 2002. Proceedings. The 21st, vol. 1, 2002, pp. 1A1–1 –

1A1–12 vol.1.

24. Neuman, F.; and Erzberger, H.: Analysis of Delay Reducing and

Fuel Saving: Sequencing and Spacing Algorithms for Arrival Traffic.

NASA TM-103880, 1991.

25. Sadovsky, A.; Swenson, H.; Haskell, W.; and Rakas, J.: Optimal

Time Advance in Terminal Area Arrivals: Throughput vs. Fuel Savings. 30th Digital Avionics Systems Conference (DASC), Seattle,

WA, 2011.

26
26. Isaacson, D.; Sadovsky, A.; and Davis, D.: Scheduling for Future

Terminal Air Traffic Operations: Problem Statement and Review of

Prior Research. To be submitted, 2012.

27. U.S.A.: Concept of Operations for the Next Generation Air Transportation System, Version 2.0. 2007.

28. Papadimitriou, C. H.; and Steiglitz, K.: Combinatorial Optimization; Algorithms and Complexity. Dover Publications, 1998.

29. Korn, G.; and Korn, T.: Mathematical Handbook for Scientists and

Engineers: Definitions, Theorems, and Formulas for Reference and

Review. McGraw-Hill, New York, 1961.

30. Ghrist, R.; O’Kane, J. M.; and LaValle, S. M.: Computing Pareto

Optimal Coordinations on Roadmaps. The International Journal

of Robotics Research, vol. 24, no. 11, 2005, pp. 997–1010. URL

http://ijr.sagepub.com/content/24/11/997.abstract.

31. Adams, C.; and Franzosa, R.: Introduction to topology: pure and

applied. Pearson Prentice Hall, 2008.

32. Arnol’d, V.: Mathematical Methods of Classical Mechanics.

Springer, 2nd ed., 1997.

33. Jung, J. B.; and Ghrist, R.: Pareto optimal multi-robot coordination

with acceleration constraints. Robotics and Automation, 2008. ICRA

2008. IEEE International Conference on, may 2008, pp. 1942 –1947.

34. Cormen, T.; Leiserson, C.; and Rivest, R.: Introduction to Algorithms. The MIT Press, Cambridge, MA, 1990.

35. Bryson, A. E.; and Ho, Y. C.: Applied optimal control. New York:

Blaisdell, 1969.

36. ARINC, T. C. G.: 424-20 Navigation System Database. 2011. URL

https://www.arinc.com/cf/store/catalog detail.cfm?item id=1714.

27
REPORT DOCUMENTATION PAGE Form Approved

OMB No. 0704–0188

The public reporting burden for this collection of information is estimated to average 1 hour per response, including the time for reviewing instructions, searching existing data sources,

gathering and maintaining the data needed, and completing and reviewing the collection of information. Send comments regarding this burden estimate or any other aspect of this collection

of information, including suggestions for reducing this burden, to Department of Defense, Washington Headquarters Services, Directorate for Information Operations and Reports

(0704-0188), 1215 Jefferson Davis Highway, Suite 1204, Arlington, VA 22202-4302. Respondents should be aware that notwithstanding any other provision of law, no person shall be

subject to any penalty for failing to comply with a collection of information if it does not display a currently valid OMB control number.

PLEASE DO NOT RETURN YOUR FORM TO THE ABOVE ADDRESS.

Standard Form 298 (Rev. 8/98)

Prescribed by ANSI Std. Z39.18

1. REPORT DATE (DD-MM-YYYY)

01-07-2012

2. REPORT TYPE

Technical Memorandum

3. DATES COVERED (From - To)

4. TITLE AND SUBTITLE

Efficient Computation of Separation-Compliant Speed Advisories for Air

Traffic Arriving in Terminal Airspace

5a. CONTRACT NUMBER

5b. GRANT NUMBER

5c. PROGRAM ELEMENT NUMBER

5d. PROJECT NUMBER

5e. TASK NUMBER

5f. WORK UNIT NUMBER

6. AUTHOR(S)

A. V. Sadovsky and D. Davis and D. R. Isaacson

7. PERFORMING ORGANIZATION NAME(S) AND ADDRESS(ES)

NASA Ames Research Center

Moffett Field, California 94035-0001

8. PERFORMING ORGANIZATION

REPORT NUMBER

L–¡ARC L-number¿

9. SPONSORING/MONITORING AGENCY NAME(S) AND ADDRESS(ES)

National Aeronautics and Space Administration

Washington, DC 20546-0001

10. SPONSOR/MONITOR’S ACRONYM(S)

NASA

11. SPONSOR/MONITOR’S REPORT

NUMBER(S)

NASA/TM–2012–216033

12. DISTRIBUTION/AVAILABILITY STATEMENT

Unclassified-Unlimited

Subject Category 03

Availability: NASA CASI (443) 757-5802

13. SUPPLEMENTARY NOTES

An electronic version can be found at http://ntrs.nasa.gov.

14. ABSTRACT

A class of problems in air traffic management asks for a scheduling algorithm that supplies the air traffic services authority

not only with a schedule of arrivals and departures, but also with speed advisories. Since advisories must be finite, a

scheduling algorithm must ultimately produce a finite data set, hence must either start with a purely discrete model or

involve a discretization of a continuous one. The former choice, often preferred for intuitive clarity, naturally leads to

mixed-integer programs, hindering proofs of correctness and computational cost bounds (crucial for real-time operations). In

this paper, a hybrid control system is used to model air traffic scheduling, capturing both the discrete and continuous aspects.

This framework is applied to a class of problems, called the Fully Routed Nominal Problem. We prove a number of geometric

results on feasible schedules and use these results to formulate an algorithm that attempts to compute a collective speed

advisory, effectively finite, and has computational cost polynomial in the number of aircraft. This work is a first step toward

optimization and models refined with more realistic detail.

15. SUBJECT TERMS

air transportation, arrival scheduling, separation assurance, continuous dynamics, control strategy, feasible trajectory

16. SECURITY CLASSIFICATION OF:

a. REPORT

U

b. ABSTRACT

U

c. THIS PAGE

U

17. LIMITATION OF

ABSTRACT

UU

18. NUMBER

OF

PAGES

34

19a. NAME OF RESPONSIBLE PERSON

STI Help Desk (email: help@sti.nasa.gov)

19b. TELEPHONE NUMBER (Include area code)

(443) 757-5802