DEVELOPMENT AND INTEGRATION OF HUMAN-CENTERED CONFLICT DETECTION AND
RESOLUTION TOOLS FOR AIRBORNE AUTONOMOUS OPERATIONS

Riva Canton Mohammad Refai Walter W. Johnson and Vernol Battiste

QSS Group Inc. UARC NASA Ames Research Center

Moffett Field, CA Moffett Field, CA Moffett Field, CA

Today's crowded airspace burdens both the pilot and controller with a
heavy workload pertaining to the maintenance of conflict-free flight.
Conflict detection and resolution (CD&R) tools have become a key element
in modern flight systems and future airspace concept simulations. In
this paper we describe an automated resolution tool that was developed
at NASA Ames Research Center as part of an experimental evaluation of
the Distributed Air-Ground concept. The tool is based on an analysis of
conflict geometry and was developed as an intent (i.e. flight plan)
resolution system. A key simplifying concept used in the development of
airborne automated resolutions is the notion of "Rules of the Road" - a
set of rules that uniquely assigns responsibility for the mitigation of
a conflict. This paper outlines the challenges in developing such an
automated resolution tool, as well as the lessons learned and the
limitations observed.

Introduction

Free flight allows aircraft greater flexibility in en route maneuvers
but shifts the responsibility for maintaining safe separation with other
aircraft onto the pilot. With the shift in responsibilities, a flight
deck tool is required in order to aid the flight crew with the tasks of
maintaining separation. This tool should detect conflicts far in advance
so that pilots can respond to conflict alerts in a strategic manner.
This approach is in contrast with the reactive, tactical response
elicited by the current Traffic Collision Avoidance System (TCAS), whose
alerts are short range and immediate. To study this concept, the Flight
Deck Display Research Laboratory at the NASA Ames Research Center has
developed a Cockpit Display of Traffic Information (CDTI) system that is
integrated with a Conflict Detection and Resolution (CD&R) tool. Based
on flight path "Intent", the CD&R tool detects conflicts up to 12
minutes in advance and automates conflict resolutions by presenting to
the pilot a list of pre-computed maneuvers that will result in a
"de-conflict" prior to the time of loss of separation (LOS). In June of
2004, as part of the Distributed Air-Ground Traffic Management (DAG-TM)
research program, research teams at the NASA Ames Research Center and
Langley Research Center conducted a joint experiment to investigate the
operational feasibility of the En Route Free Maneuvering concept, also
known as Concept Element 5 (CE 5). Central to the CE 5 study was the
idea of increasing airspace throughput by shifting more responsibilities
to the airborne systems for maintaining separation. In particular,
aircraft equipped with CD&R tools and flying autonomously are
responsible for maintaining separation from other autonomous aircraft
and from aircraft that are under Air Traffic Control (ATC) management
("managed" aircraft). The sections below discuss the implementation of
the CD&R tool, experimental trials, evaluation, and future research and
development in this area.

Implementation

Design Goals

The overall objective is to cultivate a flight deck system that will
promote the efficacy of free flight. The effectiveness of CD&R tool from
a human-factor perspective can be studied using a laboratory prototype
of the system. Long term issues involving CD&R tool-design for the next
generation flight decks can also be addressed. The primary design goal
is that it must be human-centered, and an extension of a pilot's
decision faculty. It should require no attention from the pilot in the
absence of a conflict alert and it should not inundate the pilot with
complex resolution activities when conflicts are detected. This system
will serve as a strategic planner that provides the pilot with greater
degree of freedom in terms of time and maneuver-options when confronted
with conflicts. A near instantaneous response to a user action is
crucial to the effectiveness of a CD&R tool. Therefore, system
performance is a major consideration.

Conflict Detection Algorithm

The conflict detection algorithm in the CD&R tool is an adaptation of
the methods described by Yang and Kuchar (1997, 1998). The algorithm
uses aircraft intent information to propagate current states forward in
time. These projected flight trajectories are then used to search for
conflicts with the ownship (the observer's aircraft hosting a CD&R
tool). A conflict is defined as an incident in which the ownship's
protected zone is penetrated by another aircraft (intruder). The
protected zone is a cylindrical volume of space 5 nm in radius and 2000
feet in height. With the ownship at the center, the protected zone is
projected out along its trajectory while searching for conflicts with
other aircraft.

The core of the algorithm is built based on a probabilistic model, but
it can be configured to become a deterministic model at run-time by
reducing the sampling rate to N=1.

![](media/image1.jpeg){width="3.0034722222222223in" height="1.79375in"}

Figure 1. A conflict occurs when intruder aircraft penetrates the
ownship's protected zone.

In the probabilistic approach, Gaussian and non-Gaussian distribution
errors are introduced into the position, speed, and heading components
of the aircraft states to model trajectory uncertainties. A Monte Carlo
method is used to simulate the perturbed trajectories over N iterations.
The probability of a conflict is the number of detected intrusions (or
"hits") divided by N.

With upwards of 300 aircraft to process in the simulated airspace,
performance is a primary consideration. Performance issues are mitigated
in various ways. A number of filters are applied in order to screen out
unlikely conflict candidates early in the process. Load management is
accomplished through configurable sampling rate. A sampling rate of one
second with 500 Monte Carlo iterations has been found to provide
satisfactory results when combined with sample filtering. Using a 3.2
GHz dual processor and high speed graphic card at each simulation
station, the system CPU budget is 25% for CD&R while graphical
computation and other processes take up another 40%. Finally, the CD&R
system is a standalone multi-threaded component; it can be deployed
independently on a separate computer system to increase processing
speed.

It should be noted that the solutions (computed conflicts) must be
invariant. Specifically, a conflicting aircraft pair should see the same
alert attributes (situational Awareness (SA) level, time to loss of
separation (LOS), etc) from both sides.

Alert System and Symbology

Alerts are presented to the pilot through an escalating progression of
alert conditions instead of an all-or-nothing approach, as would be the
case for a TCAS resolution advisory. Alerts are categorized into three
SA levels, with SA3 being the highest urgency and loss of separation
imminence, and SA1 the lowest. In the probabilistic approach, an SA
level is assigned by weighting the probability of a conflict with the
corresponding Time Remained Prior to Loss of Separation (TLOS). The
result is a mapping table shown in Figure 2.

![](media/image2.jpeg){width="2.9923611111111112in" height="2.76875in"}

Figure 2. Assigning SA levels in a probabilistic model - Mapping of
probability against TLOS.

Since uncertainty increases with time and distance in a predictor
system, the probability of a conflict is therefore inversely related to
the distance and time to the point of LOS. It is precisely this
characteristic that facilitates a multi-leveled alert system. The
probability of conflict becomes higher as aircraft approach LOS.
Inspection of Figure 2 shows that an SA1 alert indicates medium
probability with long TLOS to low probability with short TLOS; an SA2
alert indicates moderately high probability with long TLOS to medium
probability with short TLOS; SA3 alert indicates high probability in
general.

In the deterministic approach (N=1), no uncertainties are introduced.
The multi-leveled transition depends on TLOS alone; staged at twelve
minutes, eight minutes, and four minutes for levels SA1, SA2, and SA3
respectively.

Alert presentation to the crew employs various visual and auditory cues.
At SA1, the ownship's symbol (default color is magenta) and the
intruder's symbol (default color can be blue, green, or white) both turn
to amber on the CDTI. If the intruder aircraft is out of display range,
the "Alert" button "lights up" in yellow to alert the pilot that the
intruder aircraft is not in view. By clicking on the "Alert" button,
CDTI automatically zooms out to a larger range that brings the intruder
aircraft into view. When the alert level escalates to SA2, an amber halo
is superimposed on the conflicting-aircraft symbols. At SA3, an amber
predictor pulse is projected along the flight paths, and an amber
protected-zone-ring is projected out to the LOS position. Also at SA3,
an audible chime is sounded. This transition from a subtle visual
stimulus to a more salient one coupled with an audible sound is designed
to cue the pilot as to the degree of urgency, thereby prompting the
pilot to prioritize tasks.

![](media/image3.png){width="2.9944444444444445in"
height="3.076388888888889in"}

Figure 3. CDTI showing an SA3 alert level. Alert button lights up in
yellow (bottom, second from left).

When SA1 first appears at roughly twelve minutes prior to LOS, alert
presentation cues the pilot that there is ample time to act and more
options are available if action is taken immediately. When the alert
level escalates to SA2 at roughly eight minutes to LOS, the pilot is
reminded that there is a moderately high probability that a loss of
separation is going to occur, and that the situation should be resolved
within four minutes. When the alert level escalates to SA3 at roughly
four minutes to LOS, a loss of separation is imminent - something has to
be done immediately. Figure 3 depicts an SA3 alert level in the CDTI.

Concept of Conflict Probes

A probe is defined as a deliberate search for conflicts along an
"Intent" trajectory. The primary "Current Probe" probes the current
intended route and is active at all times. However, the CD&R tool has
two additional probes: the "RAT (Route Analysis Tool) Probe" and the
"Vector Probe". A dedicated Monte Carlo simulation powers each probe.
The RAT is an independent component of the CDTI that provides a
graphical user interface for modifying a flight path by inserting,
deleting, and moving waypoints and leg segments of the existing flight
plan. A detailed presentation of the RAT is beyond the scope of this
paper. It will suffice here to characterize the RAT as a strategic
planner for route modifications. When a modified route is proposed using
the RAT (RAT route), a new probe is set off to search for conflicts
along the proposed flight plan, thereby providing a level of confidence
that the route is conflict free before committing to it.

![](media/image4.jpeg){width="3.0in" height="2.85in"}

Figure 4. Current, RAT, and Vector Probes along their respective routes
on the CDTI display.

The Vector Probe allows a pilot to probe for conflicts along an
arbitrary heading. Dialing the heading on the Mode Control Panel
activates the Vector Probe. A probe is set off to search for conflicts
along the heading line as the pilot sweeps it across the display. This
probe boosts the effectiveness of the CD&R tool, allowing it to support
a free-flight environment in the truest sense. Figure 4 depicts the
three conflict probes on the display.

Resolution Algorithm and Automation Display

The conflict resolution algorithm is an adaptation of the geometric
optimization method presented by Bilimoria (2000). Efficient conflict
resolution commands are computed for four different types of maneuvers:
altitude change, speed change, heading change, and a combination of
heading and speed change; these resolutions are presented to the pilot
as proposed flight plans. For each maneuver type, two solutions with the
least deviations from the nominal trajectory are selected. A maximum of
eight solutions are provided when available. The computed resolutions
are prioritized by their efficiency. As shown in Figure 5, a list of
computed resolutions pops up when the "Res" button is clicked. The most
efficient maneuver (least perturbation to the current trajectory)
appears at the top of the list. The appropriate proposed flight plan is
loaded into the RAT when the pilot clicks on one of the resolution
options; this affords the pilot the opportunity to inspect and revise
the selected resolution at will.

![](media/image5.jpeg){width="2.9965277777777777in"
height="2.752083333333333in"}

Figure 5. Display of automated conflict resolutions (enlargement shows 3
maneuver options).

In some cases, not all eight resolutions are available due to
constraints such as TLOS, altitude restrictions, proximity of other
aircraft, and FMS equipage (an FMS may not be able to implement a
combined speed-heading maneuver, for example). The list of automated
resolutions is dynamic. If no action is taken while the LOS point is
approaching, these resolution options will expire one by one as they
become invalid. The pilots can choose to ignore the automated
resolutions and manually devise their own avoidance maneuvers.

The Rules-Of-The-Road Component (ROR)

The outcome of conflict detection is expected to be invariant and
symmetrical between aircraft. Specifically, conflicting aircraft pairs
should receive identical alerts if they have deployed the same CD&R
tool. This can potentially lead to a race condition when both aircraft
execute avoidance maneuvers concurrently, which if uncoordinated, may
result in further conflicts that could become un-resolvable. To mitigate
such situation, the CD&R tool incorporated "rules of the road" - a set
of rules designed for coordinating collision avoidance in VFR flight.

ROR is a component of the CD&R system that automates the application of
rules to a conflict situation. ROR relieves the flight crew from the
distraction of having to mentally analyze the situation and apply the
proper rule to arrive at a right-of-way conclusion. The right-of-way
issue is settled by means of *burdening settlement*. In other words, ROR
analysis identifies which aircraft has the burden of resolving a
particular conflict.

When a conflict is detected, ROR analyzes the flight plans and the
flight states of the conflicting aircraft at the point of LOS. A set of
hierarchically ordered rules is then applied sequentially. A rule is
found applicable only if the following complemental condition is
satisfied: one aircraft must be non-compliant while the other is
compliant with respect to that rule. If a rule is found to be
inapplicable, then the next rule is applied and so on until the
complemental condition is satisfied. The non-compliant aircraft is said
to be the burdened aircraft and will be responsible for making
trajectory modifications in order to resolve the conflict. The outcome
of ROR analysis is a *burdening settlement* advisory that is issued to
the two aircraft. Each settlement is accompanied by a short phrase
(reason) that cites the particular rule leading to the settlement. By
this automation process, only one aircraft is required to take action to
resolve a conflict, thereby mitigating the potential danger of a race
condition early on. Figure 6 shows multiple *burdening settlements*
issued by ROR during multiple conflicts.

To avoid ambiguities induced by highly articulated flight paths, the ROR
rules are applied at the point of LOS. The following is the list of
hierarchical rules implemented in the ROR (definitions of these rules as
well as an in-depth treatment on ROR are presented by Johnson, Canton,
Battiste, and Johnson. 2005):

\- IFR/AFR rule

\- Altitude Rule

\- Vectored Rule

\- Left/Right Rule

\- Level Flight Rule

\- Descend/Climb Rule

\- Overtake Rule

![](media/image6.jpeg){width="2.998611111111111in"
height="3.6847222222222222in"}

Figure 6. Display of burdening settlements during multiple conflicts
(enlargement shows reasons).

Flight Deck Integration

To emulate full flight deck functionality on different platforms for the
CE5 study, the conflict detection-capable CDTI was integrated into the
Advanced Concepts Flight Simulator (ACFS) as well as the Multi-Aircraft
Control System (MACS). The ACFS is a 6-degree-of-freedom full mission
B737 flight simulator in the Crew Vehicle Systems Research Facility
(CVSRF) at the NASA Ames Research Center. The MACS is a desktop computer
flight simulation program that emulates the B777 flight deck controls.
It was developed by the Airspace Operation Laboratory (AOL) at Ames
(Prevot, 2002).

Experimental Trials and Evaluation

Conflict Detection and Alerting

The probabilistic conflict detection algorithm was evaluated during a
pre-CE5 "shakedown" period. Conflicts were detected and pilots alerted
through the aforementioned multi-leveled system. The escalation of alert
levels from SA1 to SA3 followed a main evolutionary trend in the
Probability-TLOS domain. This evolutionary trend is labeled as the "Main
Sequence" in Figure 7. A very small number of alerts entered the main
sequence midway from outside the shaded region. Those alerts manifested
themselves as "pop-ups". Pop-ups were problematic in that they were
likely already in alert level SA3 when they first appeared. This left
the flight crew very little time to respond strategically.

![](media/image7.jpeg){width="2.9923611111111112in" height="2.75625in"}

Figure 7. Evolution of alert levels along the Main Sequence.

Another artifact observed was alert dithering (i.e. a fluctuating alert
level). This proved distracting to the pilots. Both pop-ups and
dithering artifacts can be attributed to incompatible simulator behavior
from different simulation platforms, the absence of a network wide
time-synchronization system in the distributed simulation, and to a
lesser extent the low density sampling of Monte Carlo space (500
iterations per cycle). Further study is needed in these areas.

A third artifact of the probabilistic algorithm was the violation of the
aforementioned invariance. There were a very small number of cases in
which the conflicting aircraft pair did not receive the same alert at
precisely the same moment. This inconsistency was due to two
probabilistic systems taking random samples independently (therefore,
non-identical variance), as well as system messaging delays and the
absence of a time-synchronization system. Further study is warranted in
this area.

As an immediate remedy to these artifacts (and to further improve system
performance), the conflict detection algorithm was re-configured to
probe deterministically (by sampling the Monte Carlo space once per
cycle). This was the version of the CD&R that went into the actual CE5
experiment.

Automated Conflict Resolution

The automated conflict resolution was implemented incrementally leading
up to the pre-CE5 shakedown. While it worked well in simpler forms, its
performance was less than ideal when more complex maneuver types were
added to the solutions. The increase in complexity was compounded by the
generation of new flight plans that were incompatible with other CDTI
components. The result was less than ideal solutions and poor system
performance. A decision was made to disable the automated conflict
resolution feature for the actual CE5 experiment, and continue to
resolve conflicts manually.

Rules of the Road Automation

ROR performed flawlessly during the shakedown and the actual CE5
experiment. It accurately applied rules and issued burdening settlements
that could be consistently verified by the conflict aircraft pair. As a
result, resolution maneuvers were made only by the burdened aircraft
during autonomous-autonomous encounters, eliminating right-of-way
ambiguities. Together with the deterministic conflict detection and
alert, ROR fulfilled the role of the airborne self-separation tool for
the autonomous flights during the CE5 experiment.

Conclusion and Future Work

Although the automated conflict resolution tool was not yet matured at
the time of the CE5 experiment and had to be disabled, the overall
CD&R-capable CDTI proved very successful. The Current Probe, the RAT
Probe, the Vector Probe, and the ROR all contributed to enhancing the
pilot's ability to resolve conflicts manually, a result consistent with
previous work. It has been shown that pilot-generated resolutions are
more effective when aided by decision support tools (Johnson, Bilimoria,
Thomas, Lee, and Battiste, 2003).

While the concept and the design of the automated conflict resolution is
sound, more work will be done to handle the complexity of multiple
maneuver types and seamless interface with other CDTI components.

The dithering and the pop-up alert artifacts of the probabilistic
conflict detection algorithm could be addressed with enhancements to the
algorithm, the overall messaging system, and possibly with a denser
Monte Carlo sampling. A new alert level mapping scheme should also be
explored.

Finally, although the ROR performed flawlessly during the CE5 and
handled all right-of-way issues, there was no provision in place to
handle the case in which no rule applied. This case currently always
defaults to burdening the ownship. So far, it has not occurred in
experiments, but if it does, it will lead to the race condition because
both aircraft will be burdened. A new ruling scheme is being developed
for this special case.

References

Bilimoria, K.D. (2000). A Geometric Optimization Approach to Aircraft
Conflict Resolution. *Paper No. 2000-4265,* *AIAA Guidance, Navigation,
and Control Conference*, August 2000.

Johnson N.H., Canton R., Battiste V., Johnson W.W. (2005). Rules of the
Road: Requirements and Implementation for a Simulation of En-route
Self-Separation. Submission to the *2005 International Symposium on
Aviation Psychology,* Oklahoma City, OK.

Johnson, W.W., Bilimoria, K.D., Thomas, L.C., Lee, H.Q., Battiste, V.
(2003). Comparison of Pilot and Automation Generated Conflict
Resolutions, *Paper No. 2003-5400*, *AIAA Guidance, Navigation, and
Control Conference and Exhibit*, August 2003.

Prevot, T. (2002). Exploring the Many Perspectives of Distributed Air
Traffic Management: The Multi Aircraft Control System MACS",
*International Conference on Human-Computer Interaction in Aeronautics*,
HCI-Aero 2002, Cambridge, MA, October, 2002.

Yang, L.C., Kuchar, J.K. (1997). Prototype Conflict Alerting Logic for
Free Flight. *AIAA Journal of Guidance, Control, and Dynamics*, Vol. 20,
No. 4, July-August, 1997.

Yang, L.C., Kuchar, J.K. (1998). Using Intent Information In
Probabilistic Conflict Analysis. *AIAA-98-4237, AIAA Guidance,
Navigation, and Control Conference*, Boston, MA, August 10-12, 1998.