Evaluation of conflict-resolution policies on controller taskload

Adan Ernesto VELA, William SINGHOSE, Karen FEIGH,John-Paul CLARKE, Eri FERON

a Department of Industrial Engineering and Management System, University of Central Florida, Orlando, FL 32816, USA

b George W. Woodruff School of Mechanical Engineering, Georgia Institute of Technology, Atlanta, GA 30332, USA

c Daniel Guggenheim School of Aerospace Engineering, Georgia Institute of Technology, Atlanta, GA 30332, USA

KEYWORDS Air traffic control;Air traffic management;Conflict detection and resolution;Decision-support tools;Simulation analysis

Abstract In an effort to maintain safety while satisfying growing air traffic demand,air navigation service providers are considering the inclusion of advisory systems to identify potential conflicts and propose resolution commands for the air traffic controller to verify and issue to aircraft.To understand the potential workload implications of introducing advisory conflict-detection and resolution tools, this paper examines a metric of controller taskload: how many resolution commands an air traffic controller issues under the guidance of an advisory system.Through a simulation study, the research presented here evaluates how the underlying protocol of a conflict-resolution tool affects the controller taskload (system demands) associated with the conflict-resolution process, and implicitly the controller workload(physical and psychological demands).Ultimately,evidence indicates that there is significant flexibility in the design of conflict-resolution algorithms supporting an advisory system.

1. Introduction

From 2020 to 2040, the number of Instrument Flight Rules(IFR)aircraft operations handled by Federal Aviation Administration(FAA)en route traffic centers is predicted to increase from approximately 44 million flights to 60 million flights.1Consequently, over the past two decades the FAA, and other Air Navigation Service Providers (ANSP) around the world,are seeking to improve the capacity and throughput of existing airspaces by means of Trajectory Based Operations (TBO),new traffic management tools, and automated data communication and navigation systems.2-6

One paradigm to increase airspace capacity is to integrate conflict-detection and resolution tools into air traffic management. A number of researchers hypothesize that conflictdetection and resolution tools will reduce or transform controller workload by decreasing the amount of time and mental effort controllers spend detecting and resolving potential conflicts.7-12Indeed,the conflict-detection and resolution process can be time consuming. Under current operations, one study estimates the average time required from controllers to identify a potential conflict and then generate and communicate resolution commands to pilots is 27.6 s.13Meanwhile, in another laboratory-based study it was reported that 59% of resolutions took less than 30 s, however, the expected time for resolving conflicts could exceed 60 seconds depending on traffic volume and conditions.11It is worth noting that in both cases the time spent monitoring pilot conformance to the commands was not considered.

Examples of conflict-resolution algorithms are numerous,14-18with a comprehensive survey of proposed models presented in the review by Kuchar and Yang.19The majority of these works address a completely automated conflictdetection and resolution system. Such an automated system is consistent with the proposal that the tactical role of radar air traffic controllers should eventually transition into one of supervisory control of aircraft; an example discussion of this paradigm is provided in the work by Erzberger and Paielli.20Other recent efforts have been directed at mixed-levels of automation with consideration of the air traffic controller.ERASMUS, a EUROCONTROL funded project, introduced the concept of ‘subliminal control’. In this approach, significant portions of traffic are deconflicted or further spaced with imperceptible automated speed control commands to ease both controller taskload and controller workload.21-25

Despite the appearance of potential reductions in controller workload by displacing some or all separation tasks to a computer system, there remains limitations and concerns. Fully automated conflict-resolution systems require advanced digital communication and navigation sub-systems to directly communicate with and control aircraft, potentially removing the pilot from the loop as well.Furthermore,the safety guarantees of underlying conflict-resolution algorithms in high-density operations have yet to be established, particularly in accordance with flight regulations and aircraft dynamics.

Human-factors research has also identified potential hazards associated with automated systems. When acting in a supervisory role,under greater levels of automation,air traffic controllers lose situational awareness and are unable to identify all future conflicts.26Thus, if automated conflictdetection and resolution systems fail to provide a safe solution or the resolution command is not implemented properly, then it is unlikely an air traffic controller, acting in a supervisory role, will be able to identify the failure. Additionally, the option of supervisory control is deemed unsuitable by many researchers because such a framework ultimately leads to skill atrophy.27,28With regards to subliminal-control, studies have indicated that mixed-modes of operation that include dynamic allocation of separation tasks leads to ambiguity about who is in control and who is responsible for recovery in the case of system failure.29

As an alternative, the research presented here focuses on the inclusion of advisory conflict-detection and resolution decision-support tools to aid air traffic controllers, without replacing them. A schematic diagram of the control structure for human-in-the-loop control with advisory conflictdetection and resolution decision-support tools is illustrated in Fig. 1. In a human-in-the-loop framework, conflictdetection and resolution decision-support tools identify conflicts and propose resolution commands for the air traffic controller to verify and issue to aircraft using standard voice communication (and data communication if available).

Fig. 1 Conflict-detection and resolution decision-support tools provide possible resolution solutions to air traffic controllers.

Accordingly, the introduction of advisory systems maintains a framework similar to today’s operations while providing an avenue for increased automation in the future. That said, while overcoming some of the concerns of fullyautomated systems,there remains the potential of skill atrophy of air traffic controllers and brittleness of advisory tools.30,31

In contrast to automated systems, we believe the inclusion of human-in-the loop decision-support tools in human-based operations requires a fundamentally different approach to the design and implementation of conflict-detection and resolution algorithms.The algorithms must explicitly acknowledge the role of the air traffic controller and accommodate their abilities. Furthermore, there is a need to establish that the inclusion of conflict-resolution decision-support tools will reduce, or at the very least not worsen, workload, while improving service. Along these lines, recent efforts have explored the workload implications of human-in-the-loop decision-support tools,11,12however, these works have not considered the potential important of the design of the tools themselves.

In an effort to understand the potential workload implications of introducing advisory conflict-detection and resolution tools into air traffic control systems, the research presented here examines how the tactical protocols of conflictresolution algorithms affect the taskload requirements to resolve traffic.More specifically,this study analyzes how many resolution commands air traffic controllers issue in order to separate traffic under the guidance of a conflict detection and resolution decision-support tool, hereby defined as conflict-resolution taskload. Such an approach is valid given the importance of the conflict-resolution process to influencing controller workload.

In this paper, the analysis of the conflict-resolution taskload associated with advisory tools is made possible through the introduction of a framework to abstract the behaviors and characteristics of conflict-detection and resolution systems. The primary benefit of the abstraction is that the methods and results presented here apply generally to a range of conflict-detection and resolution advisory systems, as oppose to focusing on a particular algorithm or implementation.Accordingly, the major contributions of this paper cover the analysis methodology and the resulting conclusions.

In the next section, we present a brief review of previous research on controller workload and the conflict-resolution process.Section 3 follows with a description of how graph representations are used to model conflict relationships and the conflict-detection and resolution process. Section 4 provides a framework to abstract conflict-detection and resolution systems, while presenting numerous tactical conflict-resolution protocols. Section 6 introduces the simulation environment to test the conflict-detection and resolution systems. Analysis results follow in Section 7. Finally, conclusions are presented in Section 9.

2. Background

Controller workload associated with air traffic control corresponds to the stress,or‘‘...the amount of effort,both physical and psychological, expended in response to system demands(task load) and also in accordance with the operators internal standard of performance”.32In the review by Mogford et al.,33the authors identify four factors that influence controller workload:air traffic control complexity,quality of equipment,individual differences, and controller cognitive strategies. Air traffic control complexity is a source factor that refers to a set of descriptions of the prevailing air traffic patterns and sector characteristics that aid or hinder in the management of aircraft. The next three factors (equipment, individual differences,and strategies)are referred to as mediating factors.

Early technical practitioners attempted to characterize controller workload through a set of intrinsic properties associated with source factors, without directly dealing with the mediating factors.34-37Termed dynamic density, researchers used human-in-the-loop experiments to generate regression models estimating controller workload.35In accounting for half the variance in controller workload, dynamic density established that the number of potential conflicts and aircraft maneuvers,in addition to the local density of aircraft and other measures,are strong factors in predicting controller workload. More recent efforts have sought to consider workload or establish measures of complexity using different features than those accounted for in dynamic density;38-42that said, a common theme to all is consideration of aircraft conflicts and interactions (or lack thereof).

There should be no surprise that aircraft interactions and conflicts are sources of complexity and controller workload.The primary objective of the air traffic controller is to ensure the proper separation of aircraft, thereby avoiding collisions,at all times. Thus, conflict resolution takes precedence over any other management tasks.

Unaccounted for in the modeling of Mogford is the feedback between source factors and mediating factors. In human factors research there is a recognition that ‘‘workload is not something imposed upon a passive [air traffic controller] but,rather, is something the [air traffic controller] actively manages”.43In virtually all aspects of their role, air traffic controllers adjust their strategies in response to system changes,future occurrences, and perceived workload.44,45We hypothesize that consideration of both source and mediating factors will enable the design of advisory conflict-detection and resolution tools that are both technologically sound and consistent with modes of human work-practice. Specifically, we account for both source and mediating factors here by studying the number of potential conflicts that are resolved according to set advisory polices/strategies.

To date there has only been limited consideration of how the design and implementation of conflict-detection and resolution algorithms effect controllers in practice. While it is true that studies have considered human-in-the-loop control for separation,46the underlying formulations behind the algorithms have not been thoroughly explored with regards to human-factors -this is despite the plethora of knowledge concerning human factors research.Instead of explicitly designing algorithms to work with controllers,the compatibility between users and conflict-detection and resolution systems appears to be an afterthought, tested upon completion. That said, some notable exceptions exist outside of subliminal control.47,48Perhaps most interesting are recent works that explore the premise of advisory conflict-resolution systems mimicking humandecision making.49-51

3.A graph representation of the conflict-detection and resolution process

To understand the relationship between advisory systems and conflict-resolution taskload, a dynamic conflict graph representation is introduced and applied to describe aircraft,potential aircraft conflicts, and the conflict-resolution process.Dynamic conflict graphs are modeled to grow and shrinks incrementally with the arrival and departure of aircraft, and the identification and resolution of potential conflicts during any time-step.This graph-based representation is an extension of the static case presented by Granger and Durand52, which has since been extended upon here and elsewhere,53and utilized in similar forms by other researchers.41,54,55

Consider a set of M aircraft, A = {A1, A2, ..., AM}, traveling through an airspace, as illustrated in Fig. 2(a). Aircraft trajectories are assumed to occur in 3D space across multiple flight-levels.A potential conflict between two aircraft is defined to exist if, according to available trajectory information and predictions, the two aircraft might come into conflict if no action is taken. Within the en route environment, two aircraft are in conflict when they come within 5 NM(1 NM=1.852 km) laterally and 1000 ft (1 ft=0.3048 m)vertically of each other.

A representation of the potential conflicts identified prior to and in time-step k for the example in Fig. 2(a) is given by the undirected conflict graph, G(k) = (V(k), E(k)), depicted in Fig. 2(b). Aircraft are represented by nodes in the vertex set V(k) = {n1, n2..., nM}, where node nicorresponds to aircraft Aipresent during the time-step k. Potential conflicts are indicated by an undirected edge in the edge set E(k). That is to say for a potential conflict between aircraft Aiand Aj,(ni, nj)∈E(k).

Working in this framework, if the graph is completely disconnected, then the airspace is conflict-free and requires no action from a conflict-resolution advisory system or the air traffic controller. Otherwise, if edges exist within the graph, then the conflict-resolution advisory system should consider proposing resolution commands for the air traffic controller to issue aircraft. The act of issuing resolution commands to aircraft, assuming appropriate selection and implementation of the maneuvers, removes edges in the conflict graph.

Fig. 2 Example graph representation of aircraft and potential conflict relationships.

A portion of the conflict-resolution process is illustrated in Fig. 2 for the example provided. Aircraft A1is selected to be maneuvered, and a resolution command is proposed, as indicated in Fig. 2(c). Following issuance of the resolution commands, potential conflicts are considered resolved and edges are removed from the graph G(k), as depicted in Fig. 2(d).

Let CRP represent a Conflict-Resolution Procedure (CRP)as part of an advisory system.The procedure takes as its input G(k)and returns M,the set of nodes corresponding to maneuvering aircraft, i.e. M=CRP(G(k)). The conflict-resolution advisory system supported through CRP is not required to issue resolution commands for all existing potential conflicts.However,at the very least,pending potential conflicts that will become realized prior to the next time-step without action must be resolved to maintain a safe airspace.

Moving forward, the next section provides greater detail describing the implementation and capabilities of advisory systems to detect and resolve potential conflicts through CRP.In particular, conflict-detection and resolution advisory systems are abstracted in a framework consistent with the dynamic conflict graphs presented here.

4. Abstraction of conflict-detection and resolution tools

Abstracting the behaviors and characteristics of conflictdetection and resolution tools enables broader statements on the relationship between the design of algorithms and conflict-resolution taskload. So instead of specifying the exact implementation of an advisory conflict-detection and resolution tool,conflict detection and resolution systems are codified and parameterized according to the following properties:

(1) The aircraft spacing distance used to identify potential conflicts.

(2) The growth rate of uncertainty in predicting aircraft trajectories.

(3) The amount of future trajectory information used in making conflict resolution decisions.

(4)The length of time resolution trajectories can be guaranteed to be conflict free.

(5)The solve-time of the conflict-resolution algorithm.And by extension, the rate at which trajectory information is updated in the conflict-resolution process.

(6)The policy a conflict-resolution algorithm uses in deciding which aircraft to maneuver.

The first two properties relate to the conflict-detection process.Specifically,they correspond to the capability of position sensing systems and trajectory prediction systems to measure and forecast aircraft positions.The next two properties are primarily associated with conflict-resolution algorithms;however,they also depend on trajectory prediction tools. Additionally,the solve-time is a coupling factor between the conflictdetection and conflict-resolution processes.

The immediate concern of this paper strictly corresponds to the last property - the underlying policy a conflict-resolution system uses in deciding which aircraft to maneuver.That said,the remaining design factors may influence the efficacy of any policy and its corresponding conflict-resolution taskload.Accordingly, later in Section 7 when numerous conflictresolution policies are compared, they are compared across all possible design factors.

In the next subsections,the abstraction of conflict-detection and resolution systems is made in regard to the properties listed above. First, a receding horizon control model is proposed for describing the conflict-detection and resolution process; next a framework for abstracting how potential conflicts are identified is described;the capabilities of conflict-resolution systems are then parameterized. Lastly, different policies for selecting maneuvering aircraft are presented.

4.1. Receding-horizon control

For the dynamic conflict-graph model presented in Section 3,the process of iteratively identifying and resolving potential conflicts finds correspondence to the receding-horizon control framework represented in Fig. 3.

Starting at the current time t,a conflict-detection tool looks at least TRminutes into the future to check for any potential conflicts. When potential conflicts are detected, the conflictresolution tool can limit its scope to only consider a subset of potential conflicts within a set time-range. Specifically, those pending conflicts that occur within a finite time window of length HD. Based on the potential conflicts within the HDdecisionhorizon time window,the conflict-resolution problem is solved.

According to the conflict-resolution algorithm, a set of advisory solution trajectories are generated.The modeling procedure assumes that each trajectory solution is guaranteed to be conflict-free for at least HRminutes beyond the initial TRif implemented by the controller. In the case of recedinghorizon control,only the resolution commands associated with the potential conflicts occurring within a δt time-window are implemented. Resolution of potential conflicts beyond the [t+TR, t+TR+δt] implementation window are postponed until future time-steps when more accurate trajectory information is available.

The complete conflict-detection and resolution process is then repeated δt minutes later, ad infinitum. At each δt time step, the positions of aircraft are updated and new resolution advisories are generated as necessary

Fig. 3 Conflict-resolution problem solved in a receding-horizon control framework.

4.2. Parameterization of conflict-detection systems

Fig. 4 Safety region around an aircraft (not to scale).

Fig. 5 Potential conflicts are indicated by overlapping safety regions; safety regions may grow in time due to uncertainty.

4.3. Parameterization of conflict-resolution systems

Much like conflict-detection tools, the capabilities and behaviors of conflict-resolution algorithms can be abstracted and parameterized. Here, the abstraction of conflict-resolution tools focuses on the following properties: (A) the amount of future trajectory information used in making conflictresolution decisions;(B)the length of time resolution trajectories can be guaranteed to be conflict-free.(C)the solve-time of the conflict-resolution algorithm, and by extension, the rate at which trajectory information is updated in the conflictresolution process. The abstraction uses the parameters, HD,HR,and δt first described in reference to receding-horizon control. Henceforth, HD, HR, and δt are referred to as the decision-horizon time, the conflict-free resolution time, and the solve-time parameter.

When solving the conflict-resolution problem within the receding-horizon control framework, the conflict-resolution procedure CRP need not consider all potential conflicts.Instead, CRP can trim the current conflict graph G(k) to limit the amount of information it considers when resolving potential conflicts. The size of the trimmed graph is parameterized according to the decision horizon time,HD.An example application of adjusting the decision-horizon time is illustrated in Fig. 6. When HDis small, CRP only considers a single potential conflict between aircraft A1and A2(see Figs.6(a)and(b)).Consequently, the conflict-resolution procedure generates a resolution command for one of the aircraft assuming that aircraft A3and A4continue on their intended trajectories. When HDis larger, the graph is expanded to include the potential conflicts between aircraft A1and A4, and between aircraft A2and A3.Thus,when deciding how to resolve the potential conflict between A1and A2,the future potential conflicts involving A3and A4are considered.

In parameterizing the strength of conflict-resolution algorithms, the guaranteed conflict-free resolution time, HR, is used. The value of HRrepresents the amount of time a conflict-resolution algorithm can ensure that a resolution command is conflict-free beyond the initial look ahead of TRminutes.

4.4. Conflict-resolution policies

Fig. 6 Representation of potential conflicts that are considered in the decision-making process.

Once potential conflicts are identified,one role of the advisory conflict-resolution algorithm is to select which aircraft should receive resolution commands.This subsection introduces eight underlying policies for selecting the maneuvering aircraft. The first policy implements a simple First-Come First-Served(FCFS) heuristic. The second policy randomly selects aircraft to maneuver until all potential conflicts are resolved.The third policy is the Minimum Conflict-Resolution Taskload(MCRT)policy, it minimizes the number of resolution commands used to deconflict traffic. These first three policies are specifically chosen to better understand the bounds on conflictresolution taskload. The remaining five policies reflect other possible heuristics (e.g. first-exit first-serve). The eight policies are representative of non-cooperative aircraft selection policies; only aircraft involved in potential conflicts are available for maneuvering. In contrast, cooperative policies allow for any aircraft to maneuver,even those not immediately involved in the potential conflict;this is sometimes beneficial when seeking to reduce the overall fuel-burn of a resolution solution at the expense of a larger number of avoidance commands.

First-come first-served. The First-Come First-Served Policy(FCFS)is a straightforward heuristic that uses sequential path planning to generate safe aircraft trajectories. When implemented, potential conflicts are resolved sequentially in order of expected occurrence until none remain. For each conflictpair,(Ai,Aj),the aircraft arriving first into the sector is given priority, and thus, the aircraft arriving later is issued an advisory resolution command.

The primary advantage of the FCFS policy is that it provides a straightforward procedure for deciding which aircraft are issued resolution commands.One disadvantage of the policy is the possibility of consistently favoring aircraft traveling along specific routes over others (based on the relative time between entry to an airspace and the intersection between routes).

Random Policy. The introduction of a random policy to select maneuvering aircraft serves two purposes. First, in contrast to the FCFS policy, a random policy does not contain biases that favor particular routes. Second, a random policy serves as a reference standard to compare the conflictresolution taskload of other policies. For example, if the conflict-resolution taskload of the FCFS policy is greater than that for the random policy,then it can be stated that the FCFS policy yields excessive conflict-resolution taskload. Like the FCFS policy, the random policy resolves potential conflicts in the order they are predicted to occur

Minimum Conflict-Resolution Taskload Policy.Thus far,the two policies introduced have relied on fixed procedures to determine which aircraft should be issued a resolution command. Further, none of the policies explicitly consider the potential repercussions on controller conflict-resolution taskload. The Minimum Conflict-Resolution Taskload policy(MCRT), overcomes this short-coming by issuing the least number of resolution advisories to separate aircraft.

Determining the minimum number of resolution commands is equivalent to applying the minimum vertex cover problem for graphs.In graph theory the minimum vertex cover problem asks: ‘What is the minimum number of nodes that can be removed from a graph, such that the remaining graph is completely disconnected?’65The corresponding act of removing a node nifrom a conflict graph G(k), is equivalent to issuing the aircraft Aia resolution command.An example application of the minimum vertex cover problem is shown in Fig.7.Note,the minimum vertex cover problem can have multiple solutions.

Remaining Policies. Five additional policies are considered as part of the analysis. They include a FCFS policy that ignores the temporal order in which potential conflicts are expected occur; a first-exit first-served policy that sequentially resolves potential conflicts; and a first-exit first-served policy that ignores the temporal ordering of potential conflicts.Additionally, a token-based heuristic is also considered; it issues resolution commands to the aircraft with the least number of prior maneuvers. The last policy is a simplified version of the Resolution Aircraft and Maneuver Selector (RAMS) system.RAMS forms the backbone of the Automated Airspace Concept,10an automated conflict-detection and resolution system designed by NASA. The knowledge-based policy RAMS follows rules approximating the decision-making of human air traffic controllers in selecting which aircraft to maneuver.

5. Clearance-based control versus trajectory-based operations

At this stage, with the exception of the parameter HR, no assumptions are made concerning the nature of the resolution commands provided by a conflict-resolution advisory tool. In particular, each resolution command can consist of any number and type of maneuvers (heading, speed, or altitude changes) of arbitrary magnitude. Moving forward, a clearer distinction into the nature of resolution commands in required to better understand and quantify conflict-resolution taskload.

Under the future FAA NextGen system, the manner in which aircraft are issued resolution commands is likely to change through the inclusion of 4D Trajectory-Based Operations (TBO). In today’s clearance-base control air traffic controllers verify and clear each aircraft maneuver. Accordingly,should an aircraft be issued a heading maneuver to avoid a potential conflict, the air traffic controller may be required to provide a new and distinct heading clearance in order for the aircraft to resume its original trajectory. In the case of TBO,instead of clearing and issuing two unique and reciprocal heading maneuvers, a complete trajectory is approved and communicated to the aircraft.The transmission of the new trajectory information can be communicated in multiple ways,however, the most likely manner will be through digital data channels. Ideally, the pilot approves the resolved trajectory through the Flight Management System.

Fig. 7 Example application of the minimum vertex cover problem, with the initial problem and resulting solution.

In the case of TBO, the conflict-resolution taskload corresponding to each policy is equal to the number of commands an air traffic controller will issue when following an advisory system. However, in the case of clearance-based control, the conflict-resolution taskload potentially under-reports the total number of maneuvers an air traffic controller will issue;it does not account for any subsequent maneuvers required to return an aircraft on its original trajectory following an avoidance maneuver. As such, conflict-resolution taskload represents a lower bound on the total number of maneuvers when using clearance-based control.

6. Simulation environment

This section details the simulation environment used to assess the conflict-detection and resolution policies described in Section 4.First,focusing on Minneapolis Center,the ensuring subsection provides a traffic model of uncontrolled aircraft trajectories used to simulate potential conflicts. Next, the prior graph-based frameworks are mapped onto the uncontrolled aircraft traffic model. And lastly, key implementation properties for the abstracted conflict-detection and resolution advisory systems are provided.

6.1. Simulation model

Here, a process for generating an uncontrolled open-loop air traffic model is briefly presented, with additional detail provided in other work by the author.66The uncontrolled traffic model approximates air traffic within an airspace as if aircraft flew irrespective of each other and without controller input.The model aims to replicate potential conflicts that would be commonly resolved in real-world operations-in both location and aircraft encounter configurations. The traffic model is based on a resampling of historical aircraft trajectories starting from a seed day.By resampling historical trajectories it is possible to replicate variations commonly found in air traffic,even for aircraft trajectories with the same origin and destination.Ultimately, the output of the process is 50 traffic scenarios in Minneapolis center.

The traffic model of uncontrolled flight trajectories is based on 28 days of Performance Data Analysis and Reporting System (PDARS) data1PDARS data consists of radar tracks for the following days: May 21, 2007 - June 17, 2007. The PDARS data set includes aircraft radar position information nominally sampled every 12 seconds. The complete data set contains 107,671 high-altitude flights that pass at or above 20000 ft at some point in their trajectory. From the 28 days, June 14, 2007, the busiest traffic day, is selected as the seed day from which to create 50 new traffic scenarios of uncontrolled flight trajectories.

The first step in the resampling process is to index all flights according to origin-destination pairs,and to identify the entry and exit times of the aircraft. In the PDARS data, the origin and destination information of the flight plan is described according to fixes (e.g. NASAL), airports (e.g. KATL), and latitude-longitude data(e.g.4510 N/10354 W).Origin and destination pairs that are described by fixes and airports are indexed directly. For approximately 4% of the flights (4329 trajectories),the origin data is described by latitude and longitude.In these cases,the origins are manually clustered by location and indexed.

Following clustering and indexing,a total of 11,014 origindestination pairs are identified.Ranking the origin-destination pairs,ROBBY to KMSP is the most common,occurring 2442 times. The fix ROBBY is located outside and to the south of ZMP, near the border with Chicago Center; KMSP corresponds to Minneapolis St. Paul International Airport. There are 224 origin-destination pairs repeat at least 100 times over 28 days and account for ～ 52% of the traffic. Origindestination pairs that occur less than 10 times are declared to be rare. Rare origin-destination pairs account for 15% of all flights, yet constitute 9639 of the 11,014 pairs. The classification of rare origin-destination pairs is later used by the sampling procedure in creating new uncontrolled flight trajectories.

The last step of the sampling procedure is to parse aircraft trajectories according to the sectors they pass through. The result is a set of trajectories corresponding to a traffic scenario for specified sectors.Traffic scenarios for individual sectors are of particular interest because each airspace corresponds to a control volume managed by a single air traffic controller.

The methodology presented here to model uncontrolled air traffic is an alternative to simulating air traffic along the historical flight plans with stochastic properties as done by other simulation engines.67,68Further, the method described here is an alternative to using NASA software68which was inaccessible due to institution restrictions. That said, properties of the methodology for generating high-intensity traffic are verified to be consistent with the software68and find correspondence with other results69-71that also demonstrate quadratic growth in potential conflict rate as a function of traffic loading. More so,the proposed methodology provides flexibility in simulating actualized flight trajectories while not requiring overspecification of every flight plan,which is necessary in airspace simulation models.68

6.2. Simulation implementation

The 50 generated traffic scenarios containing uncontrolled aircraft trajectories can be represented by static conflict graphs G= (V, E) over the complete time-frame. That said, these uncontrolled conflict graphs are not directly applicable to the dynamic graphs, G(k), modeled as part of the recedinghorizon control in Section 4.1. For simulations, a proxy for the dynamic graph is required because the realization of secondary conflicts is not directly possible without simulating an actual conflict-resolution algorithm.Here,a secondary conflict is defined to be a potential conflict resulting from changes to an aircraft’s trajectory as part of the conflict-resolution process. To approximate dynamic graphs and the generation of secondary conflicts,the uncontrolled conflict graphs are incrementally and deterministically sampled. The deterministic sampling of the uncontrolled conflict graph adds and removes nodes and edges as a proxy for the dynamic graph, thereby mimicking entering and exiting aircraft and the detection and resolution of potential conflicts.

The next steps correspond to the conflict-resolution process. Based on the approximated dynamic graph G(k), an approximated decision-graph^G (k ), is constructed to include only those potential conflicts within TR+HDof the current time. Next, the conflict-decision policy (e.g. FCFS, MCRT,random) is applied through the function CRP(^G (k )) in Step 7. Implicit in the function call is that any other additional information required in deciding which aircraft to maneuver(e.g.arrival times,flight phase,etc)is included.After applying the decision policy, the output of the function is the set of maneuvering aircraft M. Based on which aircraft are maneuvered,the uncontrolled conflict-graph,G=(V,E),is updated.For an aircraft Aithat is issued a resolution command at time t, all future potential conflicts between [t+TR, t+TR+-HR],represented in the edge set E,are removed.The procedure is then repeated until the time-span for the traffic scenario, as defined by tsim, is completed.

Procedure 1. Simulating conflict-detection and resolution process 1. G(k)=(V, E)2. k=0, t=0 3. while t ＜tsim do 4. k=k+1, t=t+δt 5. ～G(k)=CD(G, t,Dmin sep，Drsep)6. ^G (k )=(^V (k )， ^E (k ))where～^V (k )= ～V (k ) ^E (k )={(ni,nj)|(ni,nj) ∈E (k ) & tci，j ≤t+TR+HD}7. M=CRP(^G (k ),Dmin sep，Dr sep)8. Er = {(Ai,Aj) | Ai ∈M, tci，j ≤t+TR+HR}9. E=EEr 10. end while

The final Steps 8 and 9 of the simulation procedure are key to approximating secondary conflicts. When a resolution command is guaranteed to be conflict-free, the probability of another potential conflict during the interval[t,t+TR+HR]is considered to be zero. Following TR+HRminutes, potential conflicts represented in the uncontrolled conflict graph G are maintained even after resolution commands are implemented. In this way, the simulation approximates keeping the probability of conflict outside the time interval [t, t+TR+HR] constant when a resolution command is issued.Not only does the probability of potential conflict remain statistically similar for the open interval (t, t+TR+HR, ∞),but so does the set of aircraft for which potential conflicts might involve.

Resolution commands often take aircraft off their intended paths, either due to altitude changes or lateral movements. As such, the aircraft maneuvers might create interactions that would not have occurred if aircraft maintained their desired routes.However,there is currently no experimental validation supporting either claim that conflict probabilities TR+HRminutes after a resolution command remain the same or change.Hence,asserting that conflict probabilities remain similar after any resolution command represents an assumption of the simulation environment worth noting.

6.3. Parameter settings and traffic scenarios

A wide variety of parameter settings and traffic cases are considered in the execution of the abstracted conflict-detection and resolution tools.In line with the Joint Planning and Development Office original intent of supporting a 3X traffic demand by 2025, simulations consider 50 traffic scenarios for intensities from 1X to 3X current traffic levels;traffic scenarios are parsed down to consider only the peak 10-hour window between 10AM and 8PM. Explicitly the traffic intensities, I,come from the set, {1, 1.25, 1.5, ... , 2.75, 3}X.

The traffic simulations cover the three sectors ZMP12,ZMP16,and ZMP42,which are shown in Fig.8.As illustrated in Fig. 9, analysis indicates that as traffic intensity increases across Minneapolis center, the number of uncontrolled potential conflicts in each sector increases as well. Considering all sectors, ZMP42 contains the greatest average number of uncontrolled conflicts over the 24 h time period at each traffic intensity, prompting its inclusion for analysis. Overall, the three sectors are representative of distinct classes of airspaces commonly found in en route centers.ZMP42 is a high altitude sector with the most traffic flowing east-bound or west-bound;the majority of traffic in ZMP16 is beginning its initial descent into Minneapolis St-Paul International Airport;and ZMP12 is a large high-altitude sector with numerous crossing routes,which results in complex potential conflicts with diverse crossing angles.

Fig. 8 Traffic density map of ZMP center, highlighting sectors of interest.

Fig.9 Conflicttotalsfor sectorsinMinneapolis center over a 24hourtimeperiodwhenD=9NM.

Fig. 10 Fraction of pairwise uncontrolled conflicts.

The sectors ZMP42 and ZMP12 are of particular interest because they contain some of the most complex potential conflict scenarios. As shown in Fig. 10, as traffic intensity grows,the fraction of pairwise conflicts decreases, with ZMP42 and ZMP12 having the largest fraction multi-aircraft conflicts in the center. Such a result implies that with multiplying traffic intensity, the ability of humans and conflict-resolution tools to remain applicable while still using simple decision-making policies may become increasingly limited.

Across the 8 decision policies described in Section 4.4, a total of 45662400 simulations were run, covering a range of airspaces, traffic intensities, decision policies, and design configurations.

7. Policy analysis

Using the abstracted models in Section 4, and the simulation environment in Section 6, the conflict-resolution taskload of advisory conflict-detection and resolution tools are analyzed for the sectors ZMP12, ZMP16, and ZMP42. As noted in Section 6 these three sectors represent well-trafficked airspaces in ZMP center,each with distinct demand patterns and potential conflict configurations. Within the context of the MCRT policy, the ultimate goal is to understand the value of designing advisory systems that actively seek to reduce conflictresolution taskload. In this framework the analysis presented here examines how the tactical protocols of conflictresolution algorithms affect the taskload requirements to resolve traffic over both long and short time-durations.Examination of the conflict-resolution taskload applies both statistical hypothesis testing and a sensitivity analysis across all possible traffic intensities and design options (e.g. solve-time,decision-horizon time). If there are significant differences in the conflict-resolution taskload between the policies,statistical testing should identify them. Next, in the case when statistical differences exist,there is a pending need to quantify the difference in a meaningful way: Will the reduction in conflictresolution taskload provide a noticeable benefit to the air traffic controller.

Within the context of the MCRT policy,the ultimate goal is to understand the value of designing advisory systems that actively seek to reduce conflict-resolution taskload. In this framework the analysis presented here examines how the tactical protocols of conflict-resolution algorithms affect the taskload requirements to resolve traffic over both long and short time-durations. Examination of the conflict-resolution taskload applies both statistical hypothesis testing and a sensitivity analysis across all possible traffic intensities and design options(e.g. solve-time, decision-horizon time). If there are significant differences in the conflict-resolution taskload between the policies, statistical testing should identify them. Next, in the case when statistical differences exist, there is a pending need to quantify the difference in a meaningful way:will the reduction in conflict-resolution taskload provide a noticeable benefit to the air traffic controller.

7.1. Policy comparison over long durations

In this section, a more detailed consideration of the expected conflict-resolution taskload as a function of the decision policy is taken. Using statistical tests, A-B comparisons are made to determine the value of minimizing the conflict-resolution taskload over long time-durations. Ultimately, hypothesis testing demonstrates that the decision policy has at most a minor effect on the conflict-resolution taskload.

When the null hypothesis,H0,is accepted,then the conflictresolution taskload of the two policies are considered similar.Otherwise, acceptance of the alternative hypothesis implies that the policies result in different conflict-resolution taskloads. With 8 treatments (i.e. 8 policies) over each 50 traffic scenarios, the degrees of freedom for Tukey’s HSD test is 392 (8×50-8).

Table 1 Policy Comparisons: ZMP12.

Table 2 Policy Comparisons: ZMP16.

Table 3 Policy Comparisons: ZMP42.

Conjecture 1. There is no significant difference in the conflictresolution taskload between any two rule-based heuristic policies.

Fig. 11 Percent of configurations for which the MCRT policy is statistical different from a rule-based heuristic policy (reject H0).

Fig.12 Maximum difference in the average conflict-resolution taskload between the MCRT policy and the random policy over a range of configurations.

Conjecture 2. WhenconsideringthefutureintroductionofTBOand GPSenabledAutomaticDependentSurveillance-Broadcast(ADSB) systems to replace current radar systems, which will reduce separation standards and implicitly D,there is no meaningful benefittoactivelyminimizetheconflict-resolutiontaskload.

Further:

Conjecture 3. Even in a busy sector with large separation standards, there are not significant reductions in the longduration conflict-resolution taskload between MCRT and any of the other decision-policies. As such, it is unlikely air traffic controllers will notice the benefit of minimizing the conflictresolution taskload.

7.2. Policy comparison over short durations

A similar taskload analysis can be extended to shorter timewindows of 2.5 minutes. While 10 less resolution commands over 10 hours may appear insignificant, if the deductions are concentrated during a short burst of activity,then there might be some benefit of the MCRT policy in reducing controller workload. Fig. 13 contains example distributions of the number of resolution commands used to space aircraft during the busiest 2.5 minute time periods for the 1X, 2X, and 3X traffic levels over ZMP42(configuration:=6,=0,δt=0).Using a two-sample Kolmogorov-Smirnov goodness-of-fit test(KS test) with significance level α=0.01, the conflictresolution taskload distributions are tested to see if they come from different populations. Accordingly, the following null hypothesis and alternative hypothesis are set:

H0: Samples are drawn from the same distribution

Ha: Samples are drawn from different distributions

If the null hypothesis is not rejected, then it reasonable to believe there is no distinction in the conflict-resolution taskload between the two policies in the short-term.

Application of the KS test reveals that there is no statistical difference between the MCRT policy and the random policy at the 1X and 2X traffic intensities for the configuration corresponding to Fig. 13. However, at the 3X traffic level, the null hypothesis is rejected, implying that there is a difference between the distributions of the conflict-resolution taskload.Fig. 13(c) illustrates that the distribution of the conflictresolution taskload for the MCRT policy is skewed to the left in comparison to the random policy. Accordingly, one might argue that the MCRT policy is effective in managing controller workload during short-duration bursts of traffic at the 3X traffic intensity (this point is addressed in Conjecture 5).

Fig. 13 Probability distributions of the conflict-resolution taskload for the busiest 2.5-minute time period in traffic intensity scenarios 1X, 2X, and 3X.

Table 4 Configurations with ≤5 NM for which there is a statistical difference in conflict-resolution taskload distribution over 2.5 minute period for ZMP42 at the 3X traffic intensity.

Table 4 Configurations with ≤5 NM for which there is a statistical difference in conflict-resolution taskload distribution over 2.5 minute period for ZMP42 at the 3X traffic intensity.

Dmin （■■ ■■≥2 sep(NM) Drsep NM/min( ) δt (min) HD (min) HR (min) P Nrandom i -NMCRTi）10 15 0.18 5 0 0 15 15 0.10 5 0 0 15 20 0.16 5 0 0 15 100 0.10 5 0 0 20 100 0.14 5 0.167 0 15 20 0.18 5 0.167 0 15 100 0.16 5 0.167 0 20 100 0.12 5 0.333 0 15 15 0.10 5 0.500 0 8 10 0.12 5 0.500 0 10 20 0.12 5 0.500 0 15 20 0.14 5 0 0

When applying the same testing procedure to ZMP12 and ZMP16, there are no differences found for any configurations with≤6 NM, regardless of the traffic intensity. In the case of ZMP42, the only configurations for which the MCRT policy outperforms the random policy is when the solve-times is δt=0 minutes. A complete list of configurations for which the null hypothesis of the KS test is rejected at the 3X traffic level,when≤5NM,is provided in Table 4.Also included as part of the table is the probability that the MCRT policy reduces the conflict-resolution taskload by at least two resolution commands. Based on the results, the simulation study indicates that the MCRT policy does not provide benefit over other heuristics at 1X or 2X traffic intensity.

As indicated in Table 4, for the majority of cases when the null hypothesis is rejected, the guaranteed conflict-free time,HR, is greater than or equal to 15 minutes. Likewise, the decision-horizon times are long. By current standards of performance, HR=15 minutes is quite large, especially when one considers that the look ahead time for potential conflicts is typically greater than 5 minutes (i.e. TR≥5 minutes). As it stands, state-of-the-art trajectory prediction tools are optimistically capable of detecting potential conflicts 20 minutes into the future.73It is also worth noting that the solve-time of δt=0 refers to event-based conflict-detection and resolution implementation. For event-based implementations, as soon as a potential conflict is identified, it is immediately resolved.

According to Table 4,there is a measurable percent of traffic scenarios (≤18%) for which the MCRT policy reduces the number of advisory commands by two or more. Additional analysis indicates that between 35%-53%of the traffic scenarios show no improvement in conflict-resolution taskload across each configuration set.

As stated previously, when considering traffic intensities less than 3X, there are no cases with≤5 NM and HR≤20 minutes for which the MCRT policy has a statistically different conflict-resolution taskload distribution from the random policy. Thus it can be argued that the MCRT policy does not pose a substantial benefit over any other rule-based heuristic policy at traffic intensities 2X and below. Furthermore, extending the KS test to the other rulebased policies, there is no statistical difference found between them.

Based on the discussion above the following conjecture is made:

Conjecture 4. With traffic intensities less than 3X and traffic separation standards supporting≤6 NM there is no meaningful benefit of MCRT over other policies in reducing the shortduration conflict-resolution taskload.

Further, given that the above analysis holds for only the busiest 2.5-minute time periods, and that for majority of time the conflict-resolution taskload is equal between all policies,an addition conjecture is made:

Conjecture 5. When high traffic intensities (i.e. 3X traffic) are present, rule based tactical policies are equivalent or similar to MCRT in managing the conflict-resolution taskload over shorttime durations for the majority of scenarios.That said,it may be beneficial to run the MCRT policy in parallel with another rule based policy in order to identify scenarios in which minimizing conflict-resolution taskload may significantly reduced controller taskload in the short-term.

7.3. Summary statements

Working with the assumption that improvements in position sensing and trajectory prediction, enabled by ADS-B and TBO, will allow for reductions in en route aircraft separation standards from 5 NM to 3 NM, implicitly reducing spacing(≤5 NM) and uncertainty, and that complete airspace redesigns will occur before 3X traffic,an even stronger conjecture can be made:

Conjecture 6. There are no significant differences in the conflictresolution taskload between any two decision-policies.

The previous conjecture has implications to the value of the decision-horizon time, HD. As it stands, the MCRT policy is the only policy that is designed to benefit by extending the decision-horizon time. In contrast, an increase in the value of HDhas no meaningful effect on conflict-resolution taskload of the rule-based heuristic policies. Any differences in the conflict-resolution taskload between the MCRT policy and any other policy are small for the same configuration (regardless of the value of HD).Thus,it can be stated that any increase in HD,while potentially resulting in statistical differences over 10 h time windows, does not effectively reduce the conflictresolution taskload. Hence the corollary below.

Corollary 1. The air traffic controller is unlikely to detect any benefit in reduced conflict-resolution taskload due to an increase in the decision-horizon time, HD.

The major result of the statistical analysis and sensitivity analysis presented here is that in the majority of cases the decision policy and the decision-horizon time has limited or imperceivable effects on the conflict-resolution taskload of an advisory decision-support tool.

8. Auxiliary discussion

The analysis presented in this paper is strictly focused on a singular measurement (i.e. conflict-resolution taskload). And as such,when performing the abstracted simulation analysis there is an assumption underpinning the resulting conjectures in Section 7,specifically that the advisories generated by any conflict resolution tools are similar in nature regardless of the decision-policy determining which aircraft to maneuver. That is to say,that the instantiation of the resolution advisories that result from a MCRT policy are of similar nature and salience of those advisories resulting from a FCFS policy.This assumption leads to questions of how specific or generalized implementations of a conflict-detection and resolution tool advisory tool might alter the behaviors air traffic controllers thereby leading to unintended or undesirable consequences.As noted elsewhere, the introduction of one tool (in this case a conflict detection decision-support tool) was found to affect the performance of an air traffic controller when performing conflict resolution tasks.11,74,75The authors lend credence to the notion that the introduction of decision-support tools‘‘are not without cost”, which aligns with early discussions of the ‘‘use, misuse and abuse” of automation.30

9. Conclusions

Historically, engineers, researchers, and designers of conflictresolution algorithms for air traffic systems have largely and implicitly ignored human factors issues by designing algorithms to replace, rather than support air traffic controllers.So while human factors and cognitive engineering researchers have highlighted key aspects and requirements for the successful design of decision support tools, there has been little actualization of these concepts into mathematically rigorous algorithms. As such, the major contribution of this study is to begin to overcome this disconnect through the introduction and analysis of a model to understand the conflict-resolution taskload associated with an advisory decision-support tool.The research presented here seeks to understand how the underlying policy of conflict-resolution tools affect the controller taskload associated with the conflict-resolution process,and implicitly controller workload.

Based on a statistical analysis and sensitivity study of advisory conflict detection and resolution tools,it has been demonstrated that the decision policy of a conflict-resolution algorithm for selecting which aircraft to maneuver has an imperceivable to insignificant effect on the conflict-resolution taskload of an air traffic controller in the majority of cases.While such a null result may appear fruitless, it in fact has a significant implication on the design of conflict-resolution advisory systems. As a result of this near invariance, we now know there is significant leeway in the design of conflictresolution algorithms. Ultimately, we conclude that research and development efforts into conflict-resolution algorithms can best be placed into other areas like minimizing fuel-burn,replicating human decision-making, or ensuring human performance, without significant concern of increasing a controller’s conflict-resolution taskload. That said, in the early stages of development, prior to human-in-the-loop testing,engineers of such conflict-resolution advisory systems should still verify that the systems have a null or positive impact on reducing the conflict-resolution taskload, or alternatively,engineers could purposely design systems to regulate conflictresolution taskload in an effort to promote the benefits or be aware of limits of cognitive arousal.75

Lastly,in spite of the conjectures and conclusions presented here,one must recognize that an evolving airspace and air traffic demand may engender new spatial and temporal traffic patterns that are disruptive to traditional decision processes. We recognize that present-day airspace designs and traffic patterns(i.e. structures) within centers, sectors, and terminal airspace are the result of an engineered process to allow for humanbased management of air traffic while maintaining efficiency goals. The end result of this process are traffic flows that ensure the majority of conflicts are pairwise (see Fig. 10).These structural elements are critical factors in the decisionmaking strategies and cognitive workload of air traffic controllers.76As such, with the introduction of unmanned aerial vehicles and urban air mobility it may become necessary to re-evaluate the conjectures and conclusions drawn in this paper. However, the methodology of using a simulationbased approach remains relevant and will serve as a vital tool when addressing an evolving airspace system.

Declaration of Competing Interest

The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.

Acknowledgements

This study was funded by NASA (No.NNX08AY52A); FAA Award (No.07-C-NEGIT), Amendment (Nos. 005, 010, 020);and Air Force Contract (No.FA9550-08-1-0375).