ENRI International Workshop on ATM/CNS. Tokyo, Japan. (EIWAC 2009).

Separation Assurance in the Future Air Traffic System
H. Erzberger
Adjunct Professor of Electrical Engineering
University of California, Santa Cruz
Consulting Professor of Aeronautics and Astronautics
Stanford University
California, USA
Heinz.Erzberger@nasa.gov
Abstract: This paper addresses concepts and algorithms for automated separation assurance intended for use in the
future air traffic system. In order to achieve a high level of safety and protection against failures in an automated system,a proposed design includes two independent methods for detecting and resolving conflicts. One system detects andresolves strategic conflicts while a second independent system detects and resolves conflicts at short range. Furthermore,
the paper describes a significant extension of a previously developed strategic resolution algorithm referred to as the
Arrival Manager. This new function automatically sequences, merges and deconflicts arrival traffic converging totransition points that feed major airports. The paper concludes with proposals for a series of evolutionary steps leading
eventually toward a future air traffic system that incorporates a high degree of automated separation assurance.

assurance. Such automation will constitute a change
from the current method of separation assurance, which
is primarily the responsibility of the controller. A
consequence of this change is that responsibility forensuring separation will shift from the controller to an
automated system. The major challenge presented bysuch a shift is the requirement to demonstrate that asystem with this level of automation is safer than thecurrent system over a wide range of operating
conditions
andtraffic
densities.

1. ARCHITECTURE FOR SEPARATIONASSURANCEThe design of the future U.S. air traffic system, referred
to as NextGen, is the subject of current research atuniversities and research centers around the country.
Although the design concepts continue to evolve as
research progresses, the final design is expected toinclude a high level of automation in separation

Figure 1 Major Elements of a Concept for Automated Separation Assurance
1

H. Erzberger

Fig. 1 shows the key elements of a proposed groundcentered system for automated separation assurance. In
order to provide increased protection against loss of
separation during failures, the proposed system
incorporates two independent conflict detection andresolution algorithms, each of which is designed todetect and resolve conflicts over different time ranges.
The first algorithm, referred to as the Autoresolver,
handles conflicts with times to loss of separation in therange of 2 to 20 minutes. This algorithm is intended for
resolution of non-urgent conflicts and is the mainstay ofseparation assurance. Its design and performance inenroute airspace are described in several papers [1-3].
Recently a function for sequencing, spacing anddeconflicting arrival traffic, referred to as the Arrival
Manager, was developed and integrated into theAutoresolver. The design of the Arrival Manager is themain subject of this paper.

conventional voice link to maintain separation ofunequipped aircraft.
All changes to aircraft trajectories initiated by the
conflict resolution algorithms or made by controllers or
pilots are immediately entered in real time into a
repository of currently assigned trajectories maintainedby the ground system.
2. DESIGN OF ARRIVAL MANAGER
The Arrival Manager performs arrival scheduling,
sequencing, spacing and conflict resolution. It
generates a 4-dimensional descent trajectory for eacharrival aircraft and has been integrated with apreviously developed algorithm for resolving en-route
conflicts [1-2].
In order to accommodate in-trail time constraints
between consecutive arrivals crossing an arrival fix, a
new type of conflict, referred to as a sequencing
conflict, is introduced. A sequencing conflict is defined
as a violation of a specified value of minimum time
separation, Tmin, between two consecutive arrivals
crossing an arrival fix. The minimum time separations
are assumed to be provided by an arrival meteringsystem such as the Traffic Management Advisor [5],which is used to manage arrival traffic at large airports
in the U.S. A consequence of introducing thisadditional type of conflict is that arrival aircraft may
simultaneously be involved in either or bothconventional loss of separation conflicts andsequencing conflicts. The Arrival Manager must be
designed to resolve both types of conflicts while
maintaining the arrival sequence order specified by the
Traffic Management Advisor whenever possible.

The second algorithm is designed to handle urgent
conflicts, which are those with times to loss of
separation of less than 2 minutes. Its main purpose is toprovide a safety net for those infrequently occurring
situations when conflicts are not resolved in a timely
manner by the first algorithm. This algorithm is an
integral part of the Tactical Separation Assured Flight
Environment (TSAFE) in the system shown in Fig. 1.
Its analytical formulation is given in Ref. 4. Although
the two algorithms perform similar functions they differ
substantially in their analytical formulation as well as
their software implementation.
As shown in Fig. 1, operational implementation of asystem for automated separation assurance requires an
air-ground data link that allows ground-based systems
to uplink resolution trajectories to systems onboard
aircraft. The controller will continue to use a

Figure 2 Illustrating the Arrival Sequencing Process

2

ENRI International Workshop on ATM/CNS. Tokyo, Japan. (EIWAC 2009).

Similar to the Traffic Management Advisor, the Arrival
Manager uses a Freeze Horizon to determine when an
aircraft first becomes eligible for arrival sequencing
and deconfliction. The Freeze Horizon is a userspecified time interval, which is typically set to 20
minutes. For all aircraft heading toward a particulararrival fix, the Arrival Manager periodically (typicallyonce per minute) computes updated values of theestimated times of arrival (ETA) to the arrival fix.
When the difference between the ETA for an aircraft
and current time becomes less than the Freeze Horizon
for the first time, the aircraft is said to have crossed theFreeze Horizon and becomes eligible for arrival
sequencing and deconfliction. Fig. 2 shows a Freeze
Horizon line, several aircraft heading toward an arrival
fix and the minimum time separation, Tmin, between
in-trail arrivals at the arrival fix.

identifier: loss of separation conflict, sequencing
conflict or a combination conflict. Previously
scheduled aircraft that have crossed the arrival fix since
the last scheduling epoch are deleted from the list.
The Arrival Manager now proceeds to resolve theconflicts one at a time starting with the conflict aircraftthat has the smallest ETA (is closest in time to thearrival fix) and continuing until the last of the newconflict aircraft has been processed. If the Arrival
Manager succeeds in finding a trajectory that resolves
all the conflicts for an aircraft, it changes the status ofthat aircraft to frozen and scheduled. Thus, after all
new aircraft have been processed the list will contain
only frozen and conflict-free aircraft. The Arrival
Manager then waits for real time to advance to thebeginning of the next scheduling update cycle. Whenthat time is reached the Arrival Manager repeats theprocess for all new aircraft that have crossed the Freeze
Horizon.

The Arrival Manager differentiates between aircraftthat were sequenced and deconflicted at an earlier time,such as aircraft A, B, and C in Fig. 2, and those, suchas aircraft D, that have crossed the Freeze Horizon at
the current scheduling time and are now eligible to besequenced. Those that were previously sequenced anddeconflicted are treated as having frozen arrival
trajectories, which will not be changed to accommodate
new aircraft whose ETA’s have crossed the freeze
horizon for the first time. The strategy of sequencing
and deconflicting arrival aircraft only once after they
have crossed the freeze horizon ensures stability of
trajectories and fairness in the sequencing process.
Thus, aircraft D must now be scheduled anddeconflicted without changing the trajectories of thefrozen aircraft.

The Arrival Manager generates separate lists ofscheduled aircraft for all arrival fixes at an airport.
Moreover, if separate crossing altitudes are assigned tojet, turboprop and piston aircraft at an arrival fix, as isoften the case, the Arrival Manager generates andmaintains separate lists for the streams of aircraft
assigned to each crossing altitude.
The process that generates conflict-free trajectories foreach new aircraft comprises rules and procedures thatwill be described in a future technical report in moredetail. In summary, for either sequencing or combined
sequencing and loss-of-separation conflicts, the Arrival
Manager first computes the earliest time slot (STAmin)for the aircraft to be scheduled that meets the required
separation time constraint relative to the STA’s offrozen aircraft. The STAmin can be earlier or later than
the aircraft’s OETA, although more often it will belater if frozen aircraft are close by and immediately
ahead of an unscheduled aircraft. This is the typicalsituation during an arrival traffic rush. Then the Arrival
Manager instructs the trial trajectory generator tocompute a meet-time trajectory that achieves the
STAmin within specified error tolerances. If this trial
trajectory is found to be conflict-free relative to
trajectories of all frozen aircraft, the trial trajectory isfrozen and becomes the trajectory that is uplinked tothe aircraft. At the same time, the status of the aircraft
is changed to frozen, and the Arrival Manager proceeds
to process the next-in-line new aircraft. On the other
hand, if the trial plan trajectory that achieves STAmin isstill projected to lose separation with a frozen aircraft,then the resolution logic generates a sequence of trial
trajectories, each with incrementally greater delay
relative to STAmin. Each of these is again checked forloss of separation and sequencing conflicts with frozen
aircraft. The first trajectory found that is free of bothtypes of conflicts terminates the trial-planning process
and results in acceptance and implementation of the

In order to keep track of the scheduling status ofaircraft, the Arrival Manager maintains a list of frozen
aircraft that were previously scheduled. This list isarranged in the order the frozen aircraft have beenscheduled to cross the arrival fix. The list also contains
two other time parameters for each aircraft. These are
the original estimated time of arrival (OETA), which is
the ETA that was computed at the time the aircraft
initially crossed the Freeze Horizon and the scheduled(frozen) time of arrival (STA), which is the time theaircraft is scheduled to cross the arrival fix.
An essential operation performed by the Arrival
Manager is to merge the set of new aircraft that havecrossed the Freeze Horizon at the current schedulingepoch into the set of frozen aircraft without causing
either separation or sequencing conflicts. The first stepin this process is to merge the new aircraft into the listof frozen aircraft in first-come-first-served order. The
OETA’s of the new aircraft determine where they will
be inserted into the STA-ordered list of frozen aircraft.
Next, the combined list is examined to identify
sequencing conflicts between frozen and new aircraft
and between pairs of new aircraft. Each new aircraft istagged, if it is not conflict-free, with a conflict type3

H. Erzberger

Figure 3 Merging and Scheduling New Arrival Into An Arrival Stream

trajectory. Here it is important to note that because of
the sequential procedure for processing new aircraft,conflicts between the aircraft currently being processedand new aircraft not yet processed are ignored.

Current time is 20 minutes to the left of the Freeze
Horizon line and is off the plot to allow a better view ofthe scheduling events of interest. This example waschosen from thousands of such plots generated for a
24-hour run, because it illustrates how the Arrival
Manager handles both normal and exceptionalscheduling situations. The three time lines in the figure
show OETA’s and two STA’s for each aircraft
converging to this arrival fix. The STAprev line shows
the frozen arrival schedules for traffic scheduled at theprevious and at earlier scheduling event times. It shows
how the four new arrivals (red lines) that crossed thefreeze horizon since the previous scheduling event
would fit into the arrival sequence if their trajectories
were left unchanged. The three new arrivals near thefreeze horizon represent the normal situation. Since
they are in violation of the one-minute sequencing
constraint, they must be rescheduled and deconflicted.
The effect of this process is shown in the STAnow timeline. It can be seen that the process has preserved thefirst-come-first-to-land sequence order based on their
OETA order and has resulted in time separations close
to the required one-minute minimum time interval.

New arrivals with only loss-of-separation conflicts arehandled slightly differently. If such a conflict occurs
between aircraft in the same stream class (i.e., aircraft
for the same arrival fix with the same crossing altitude),
the resolution process uses the same rules forgenerating trial resolutions as previously developed forarrivals, except that an additional constraint must be
satisfied by the trial resolution trajectory. Namely, eachtrial trajectory is also checked for violation ofsequencing constraints with any frozen aircraft in thesame stream class. While a conflict may initiallypresent purely as a loss-of-separation conflict, the trial
resolutions generated to resolve it often create
violations of sequencing constraints with frozen aircraft,which then require additional trial-plan trajectory
iterations to resolve.
A time-line plot, an example of which is shown in Fig.
3, provides an insightful graphical illustration of the
dynamics of the sequencing process. This plot was
generated from the results of a fast-time simulation of
the Arrival Manager for traffic into the Detroit airport.
The input to the simulation was based on a 24-hourtraffic recording from a particular day. Plots such asthese are generated automatically by a simulation data
analysis system and are posted on a website [6]. In theplot, time at arrival fix crossing is shown in units ofhours and minutes and increases from left to right.

The fourth new arrival (numbered 170) is designated a
pop-up arrival, so named because it entered thesequencing process far below the freeze horizon. Popups are undesirable because they are often difficult tomerge into the frozen aircraft stream, but they cannot
always be prevented from occurring. This particular
popup departed from a nearby airport with a shortflying time to the arrival fix. Other reasons for theoccurrence of pop-ups are onboard emergencies and4

ENRI International Workshop on ATM/CNS. Tokyo, Japan. (EIWAC 2009).

aircraft that have diverted to an alternate airport due toweather. In this case, the slot finder function of the
Arrival Manager scans the scheduled times of frozen
aircraft to locate the nearest available time slot. An
acceptable time slot must have at least a two-minutegap between adjacent frozen aircraft. The aircraft has
been scheduled for the earliest available slot, which islocated after the scheduled time of aircraft 169. A trial
trajectory was computed that delayed the aircraft by theamount of time required to meet the specified slot time.
The trial trajectory was then checked for loss-ofseparation conflicts and was found to be conflict-free inthis case, thereby completing the scheduling process forthe current time.

that had been created in the process of sequencing anddeconfliction of the arrival traffic.
The Arrival Manager has been implemented in softwareand integrated into the Autoresolver software suite. A
fast-time simulation has been used to validate thealgorithm and evaluate its performance. A web-based
data analysis capability is available for evaluating theresults of the simulation. It includes displays ofscheduling lists and time line plots of traffic crossing
arrival fixes [6]. This capability is a convenient
analysis tool for evaluating scheduling decisions andresolution procedures.
3. EVOLUTIONARY PATH TO
DEVELOPMENT

It is noted that the sequencing process in the previous
scheduling time (STAprev) produced a time separation
between aircraft 165 and 166 that is in excess of therequired one-minute interval. Such excess time can be a
byproduct of the simultaneous resolution of asequencing and loss of separation conflict.

Since changes in air traffic control operations havehistorically evolved gradually, often over long periodsof time, it is important to consider if separation
assurance can evolve toward higher levels of
automation in a series of steps. The system architecture
and the algorithms outlined in this paper can be viewed
as the final step in the long road toward a future air
traffic system that will include a high level ofautomation. Both the system architecture and thealgorithms for conflict detection and resolution outlinedin this paper lend themselves to operational
implementation in evolutionary steps. The two main
options for stepwise implementation are short-range
conflict resolution and strategic conflict resolution.

Whenever the Autoresolver is called upon to resolve alist of conflicts, the order in which the conflicts areresolved follows specific rules. The highest-level rule
requires that arrival vs. arrival conflicts have priority
over all other conflict types in the resolution process.
This rule helps to reduce delays in the arrival queues
and ensures an orderly arrival flow. Furthermore, theresolution process starts by resolving conflicts at the fix
with the highest arrival traffic count at the airport withthe most traffic in the Center. For example, at the
Cleveland Center, the Southeast arrival fix for jets at
Detroit (DTW) often experiences the highest traffic
demand and therefore is selected as the starting point
for the resolution process.

As described in Ref. 4, the first option, which isreferred to as TSAFE, would be a paradigm-shifting
step in that it would largely remove the controller from
responsibility for detecting and resolving short-range
conflicts. The two supporting technologies required for
implementing this option are the data link built into
Mode S and the onboard systems required for TCAS
level 2. These technologies are already in operationaluse and could be adapted for this application withrelatively minor modifications to systems onboard
aircraft. In addition, the short-range detection andresolution algorithm would also have to be
implemented in the ground system. Alternatively, it
may also be possible to implement TSAFE or similar
technologies as an airborne separation assurance
system that is independent of systems on the ground.
Airborne separation assurance is the subject of researchat institutes throughout the world.

While resolving the arrival conflicts in this stream class,secondary conflicts may be created with out-of-streamclass traffic and with non-arrivals. These secondaries
are treated as new conflicts and added to the list ofunresolved conflicts. They will be resolved insubsequent steps as shall be explained. Next, conflicts
in the turboprop stream class at the same arrival fix are
resolved, followed by conflicts in the prop stream classat this fix. The same procedure is repeated for all
remaining arrival fixes at this airport, where the orderin which the fixes are selected is determined by theirtraffic demand ranking. At each stage in this process,secondary conflicts with aircraft sequenced anddeconflicted in previous steps are not permitted, whilesecondaries generated with traffic in stream classes not
yet processed, and with overflights, are permitted tooccur. This process is repeated for all other airports in
the Center, where the order of airports is determined bytheir rank based on traffic demand. At each schedulingepoch, the last step is to resolve the non-arrival
conflicts. The conflicts resolved in the last step include
the original set of non-arrival conflicts as well as new
secondary conflicts between arrivals and non-arrivals

The second option would be to implement strategic
conflict resolution using an algorithm such as theAutoresolver described in this paper and in references[2-4]. The Autoresolver would have to be integrated
into the ground system where it would be used bycontrollers initially as a decision support tool.
Controllers would issue the automatically generated
resolution trajectories to equipped aircraft primarily via
5H. Erzberger[3] Farley, Todd; Erzberger, Heinz; “Fast Time Airdata link. However, in the absence of TSAFE, theywould retain responsibility for short-range conflicts.
This option is critically dependent on the installation ofa ground-air data link in a large proportion of aircraft.
Such a data link is under development but is still years
away from deployment in the U.S. airspace. Once adata link becomes widely operational in aircraft andground systems, this option could be implemented firstin high-altitude enroute airspace and then extended into
lower altitude transition airspace at a later time. The
Arrival Manager described in this paper would have tobe deployed to handle arrival flows conflict-free into
terminal area airspace.

Traffic Simulation of a Conflict Resolution
Algorithm under High Air Traffic Demand.” USA
Europe ATM Seminar, paper # 173, July 2-5, 2007,
Barcelona, Spain.
[4] Erzberger, Heinz; “Algorithm and Operational

Concept for Resolving Short Range Conflicts.”
26th International Congress of the Aeronautical
Sciences, September 2008, Anchorage, Alaska.
[5] Swenson, H. N.; Hoang, T.; Engelland, S.; “Design

and Operational Evaluation of the Traffic
Management Advisor at the Fort Worth Air RouteTraffic Control Center.” 1st USA/Europe Air
Traffic Management Research & Development
Seminar, Saclay, France, June 17-19, 1997

After both the short-range and strategic resolutionfunctions have been in operation for a period of time,
the final evolutionary step would consist of integratingthese functions, thereby achieving the level ofautomated separation assurance envisioned for
NextGen.

[6] Website for performance statistics and analysis ofresolution trajectories for algorithm described inthis paper and in references 2 and 3. Availablefrom:
http://airtrafficconflictresolutions.arc.nasa.gov/aacwebapp/conflicts?action=dblist

REFERENCES[1] Erzberger, Heinz; Transforming the NAS: The

Next Generation Air Traffic Control System; 24th
International Congress of the Aeronautical
Sciences (ICAS), August 30, 2004, Yokohama,Japan.

COPYRIGHT STATEMENT
The author confirms that the University of California
holds copyright of the material included in this paper.
The author and the University of California grant full
permission for the publication and distribution of thispaper as part of the EIWAC 2009 proceedings or as
individual off-prints from the proceedings.

[2] Erzberger, H.; “Automated Conflict Resolution for

Air Traffic Control,” 25th International Congressof the Aeronautical Sciences, September 2006,
Hamburg, Germany.

6