c Cost function

d Predicted miss distance

h Altitude

r Range

tr Response time

v Speed

v 2D or 3D velocity vector

x 2D or 3D position

P(C) Probability of conflict

c Bearing

f Bank angle

y Heading

t Predicted time to closest point of approach

A number modeling approaches have been applied in the past for conflict detection and resolution in aerospace, ground vehicle, and maritime applications. These models include a wide variety of techniques from varying viewpoints, but are all intended to provide an analytical basis for designing and evaluating conflict detection and resolution systems. Because the problem is complex and of high current interest, a categorization and evaluation of the different approaches would be valuable in providing a taxonomy of models and as a vehicle to point out salient advantages and limitations.

This paper provides a summary and comparative evaluation of the approaches that have been used to perform conflict detection and resolution. The intent is not to specifically recommend any given model, since each is application-specific. Rather, the intent is to point out the advantages and disadvantages of each method and to identify common issues that should be considered.

The different approaches are examined in the context of the free flight environment. To provide a generic framework for discussion, a representation of the conflict detection and resolution process is outlined below.

Any traffic management system in which vehicles are monitored and controlled to prevent collisions has certain basic functional requirements. At a high level, these requirements can be categorized into several phases, shown in Figure 1.

As shown in Fig. 1, the traffic environment must first be monitored and appropriate state information must be collected and disseminated using sensors and communications equipment. These states provide an estimate of the current traffic situation (e.g., current aircraft position and velocity). Due to sensor errors, there is, in general, some uncertainty in the values of these states.

A dynamic model is also required to project the states into the future in order to predict whether a conflict will occur. This projection may be based solely on current state information (e.g., a straight-line extrapolation of the current velocity vector) or may be based on additional, procedural information such as a flight plan. As with the current state information, there is generally some uncertainty in the estimate of the future trajectory.

Fig. 1 Conflict Detection and Resolution

Information regarding the current and predicted states can then be combined to derive metrics used to make traffic management decisions. Some examples include predicted time to closest point of approach, and predicted minimum separation. Whereas the current and projected states can generally be estimated separately for each aircraft, the conflict metrics require some form of aggregation of the states of the different vehicles involved.

Given the conflict metrics, a discrete decision (Conflict Detection) is then made regarding whether action is needed to maintain traffic separation. Often, this decision is based upon a simple check against thresholds (e.g., take action if predicted time to impact is less than some value), but could involve a more complex rule-based expert system.

When action is needed, the Conflict Resolution phase involves determining an appropriate course of action and transmitting that information to the operators. For example, the Traffic Alert and Collision Avoidance System (TCAS) issues Resolution Advisories to the pilot that indicate a target rate of climb or descent to avoid a collision.

Either or both Conflict Detection and Conflict Resolution may be automated or may be handled manually through procedures. For example, current Visual Flight Rules (VFR) place the responsibility for collision avoidance on the pilot, who must visually scan for traffic (conflict detection) and if a threat is perceived, take appropriate action according to a set of "rules of the road" (conflict resolution). Under current Instrument Flight Rules (IFR), an Air Traffic Controller monitors traffic separation using radar and issues vectors to aircraft when a conflict is projected to occur. If conflicts are not resolved by the human operators, resolution information is automatically issued by TCAS.

The phases represented in Figure 1 provide a generic framework by which conflict detection and resolution models can be compared. For the purposes of this paper, conflict detection can be thought of as the process of deciding when action should be taken, and conflict resolution involves determining how or what action should be performed. In practice, however, it is not always clear how to separate conflict detection from conflict resolution. For example, deciding when action is required may depend on the type of action that will be performed. Similarly, the type of action that is required may depend on how early that action begins.

Additionally, a number of models have been developed to perform macroscopic studies of air traffic management.2 Examples are TAAM, RAMS, or TMAC, which are summarized along with a number of other similar models in Ref. 2. Conflict detection and resolution is only one of several submodels in these macroscopic tools. It is at the level of the submodels that this paper is directed. Thus, this paper does not compare TAAM against RAMS, for example, but does discuss the types of underlying algorithms that those models use. Additionally, some effort is underway investigating the human factors issues associated with conflict detection and resolution.3,4 However, this paper is directed only at numerical models for evaluating traffic conflict scenarios, not at human-centered issues.

Table 1 shows the 33 models that were examined, listed alphabetically according to author identifier and reference number. Also shown is a brief summary of the key capability or application of the model. Each model is subsequently described in more detail below. Three of the models shown in Table 1 are existing operational systems: the Traffic Alert and Collision Avoidance System (TCAS)32, Ground Proximity Warning System (GPWS)16, and the Parallel Runway Monitor (PRM)25. The remaining models range from abstract representations of airspace to prototype conflict warning systems. Three of these models were developed for naval applications (Coenen et al.11, Iijima et al.19, Taylor31), but are still applicable to aviation.

Table 2 categorizes the models according to the approach each takes in the State Estimation, Dynamic Model, and Metric Definition blocks from Fig. 1. For brevity, the reference numbers for each model are not shown, but can be determined by cross-referencing with Table 1. Five columns describe the categorization: Dimensions, States, Propagation, Uncertainty, and Metrics, each of which is described below. Models are grouped first according to their Propagation method, and then according to their Dimensions.

The Dimensions column shows whether the model involves purely the horizontal plane (H), vertical plane (V), or both (HV). Again, some models may be easily extended to cover additional dimensions, but such extension is not explicitly described in the reference. The majority of models cover either three-dimensions or the horizontal plane; only GPWS focuses solely on the vertical plane. It also must be noted that coverage of the horizontal plane does not necessarily mean that a complete description of the horizontal situation exists. For example, TCAS uses range and range-rate measurements to determine if a conflict exists; its alerting logic does not use bearing or a full description of a target's 3D position.

The States column outlines the primary state variables used by the model, according to the list in the Nomenclature section. In general, the states x and v are used to represent knowledge of current aircraft position and velocity vectors. In some cases, this information may be determined indirectly through range and bearing measurements; in others, there may be an assumed state vector datalink between aircraft. The notation flight plan indicates that the model requires not only the current state of the aircraft but also its future waypoints along its flight path.

Propagation shows how the model then uses the states to predict future trajectories. Three fundamental extrapolation methods are defined, termed Nominal (N), Probabilistic (P), and Worst-Case (W), and shown schematically in Figure 2. In the Nominal method, the current states are projected into the future without direct consideration of uncertainties. An example would be extrapolating the aircraft's position based on its current velocity vector or turn rate (as shown in Fig. 2). In the Probabilistic method, uncertainties in the model are used to develop a set of possible future trajectories, each weighted by its probability of occurring. For example, a distribution of future aircraft positions could be obtained by modeling uncertainty in along- and cross-track guidance. In the Worst-Case method, some states are assumed to take on extreme values and used to propagate the states into the future. An example here could be assuming that the aircraft turns directly toward other traffic, even though such an event may be unlikely.

Fig. 2 Propagation Method Schematic

Metrics shows what parameters are derived from the states to make conflict decisions in the model. This generally involves estimated time to closest point of approach, miss distance, current range, expected maneuvering cost, or probability of conflict. One model (Wangermann & Stengel34,35) also requires a series of utility functions to be defined by which aircraft and controllers make decisions.

Table 3 shows the Conflict Detection and Conflict Resolution capabilities of each model. Models are organized first based on conflict detection, and then based on their approach to conflict resolution.

The Detection column indicates (with a check mark) whether each model explicitly defines when action is required. The upper third of Table 3 shows models that do not provide this explicit threshold. These models (e.g., Paielli & Erzberger24) provide valuable, detailed tools and metrics upon which conflict detection decisions can be made, but do not explicitly draw the line between conflict and non-conflict. Models that are shown to provide conflict detection may use an extremely simple criterion (e.g., current range) to determine when a conflict exists or may use a complex threshold (e.g., based on probability of conflict). Thus, one must be careful not to discount models just because they are shown to not provide conflict detection. As described above, these models may in fact provide a rigorous understanding of a conflict but just do not explicitly define a threshold.

The Resolution column shows the basis by which responses to conflicts are determined. Three categories are included here: Prescribed (P), Optimized (O), and Force field (F).

Prescribed resolution maneuvers are determined a priori based on a set of procedures. For example, GPWS issues a standard "Pull Up" warning when a conflict with terrain exists. GPWS does not perform additional computation to determine an optimal escape maneuver. AILS5 and Carpenter & Kuchar10 assume that a combined climbing-turn maneuver is always performed to avoid traffic on parallel approach.

Optimized conflict resolution can involve a rule-based decision or determining which of several avoidance options minimizes a given cost function. Several sub-categories are included for some of the Optimization cases. Rule indicates that the situation is compared against a series of pre-defined rules to determine the course of action. TCAS, for example, searches through a set of potential climb or descend maneuvers and chooses the least-aggressive maneuver that still provides adequate protection. OCT indicates that an approach based on optimal control theory is used: cost functions and constraints are defined and an optimal solution is determined. Game and GA indicate the use of game theory or genetic algorithms, respectively.

Force field approaches model each aircraft as a charged particle and use modified electrostatic equations to determine resolution maneuvers. The repulsive forces between aircraft are used to define the maneuver each performs to avoid a collision.

A "-" in the Resolution column indicates that the model does not provide an explicit output of an avoidance action. Thus, the center third of Table 3 is made of models that perform conflict detection but do not explicitly consider conflict resolution. In some cases, successful conflict resolution is presumed - the focus of the model is then on detecting or counting conflicts. The lower third of Table 3 includes models that perform both conflict detection and conflict resolution.

The Maneuvers column indicates what types of resolution maneuvers are allowed. Possible maneuvers include Turns (T), Vertical maneuvers (V), and Speed changes (S). The notation TV, for example, means that either turns or vertical maneuvers may be performed (but not both simultaneously). In some cases, combined maneuvers may be performed, indicated by C(). Thus, C(TV), for example, indicates that a simultaneous climbing or descending turn may be performed.

The Cooperation column shows whether the model accepts some form of cooperative solution between aircraft. This includes: Assumed cooperation (A), in which all aircraft are assumed to coordinate their actions; Non-cooperative (N), in which other aircraft are assumed to act without coordination; and Optional cooperation, in which the model may be used in both Assumed and Non-cooperative cases.

Finally, the Multi-A/C column describes how the model handles more than two aircraft simultaneously. This can take two forms: Pairwise (P), in which multiple conflicts are addressed sequentially in pairs; and Global (G), in which the entire traffic situation is examined simultaneously to determine the resolution maneuver.

The most important difference between modeling approaches involves the method by which the current state is projected into the future. This extrapolation forms a major part of how conflicts are managed. The Nominal projection method is the most straightforward, and provides a first-order estimate of where and how conflicts will occur. Nominal projections, however, do not account for the possibility that an aircraft does not behave as predicted by the dynamic model. This uncertainty is especially important in long-term, strategic conflict detection.

The other extreme of dynamic modeling is to examine the Worst-case projection. Here, the potential for a conflict is determined assuming that an aircraft performs the most detrimental maneuver; thus Worst-case approaches are conservative. It may be the case, however, that such worst-case maneuvers are extremely unlikely, and protecting against them may severely reduce overall traffic capacity. Still, the worst-case approach allows one to set bounds on achievable performance and may be appropriate for concepts of free flight in which aircraft are constrained to remain within a given maneuvering corridor.

A Probabilistic approach appears to provide a reasonable balance between relying too heavily on an aircraft adhering to the dynamic model vs. relying too heavily that an aircraft performs worst-case maneuvers. The advantage of a Probabilistic approach is that decisions can be made on the fundamental likelihood of a conflict; safety and unnecessary alert rate can be considered directly. However, the logic behind a probability-based system can be difficult to convey to operators, possibly reducing their confidence.39 There may also be difficulty in modeling the probabilities with which different future trajectories will be followed.

Another important factor to consider in a model is the overall computational engine that is used to make conflict detection and resolution decisions. Examples include optimization techniques, expert systems, force field modeling, or simple thresholds.

Optimization approaches typically combine a kinematic model with a set of cost metrics. An optimal resolution strategy is then determined by solving for the trajectories with the lowest cost. This requires the definition of appropriate cost functions - a process that may be fairly straightforward for economic costs but difficult for modeling subjective human utilities. Costs typically include fuel or time, but could also cover workload or safety. Because free flight concepts are generally centered on strategic resolution of conflicts before immediate tactical maneuvering is required, economic costs and operator workload will be important to the alerting decision.

Expert system methods use rule-bases to categorize conflicts and decide whether to alert and/or resolve a conflict. These models can be complex and require a large number of rules to completely cover all possible encounter situations. Additionally, it may be difficult to certify that the system always operates as intended, and the "experts" used to develop or train the system may in fact not use the best strategy in resolving conflicts. However, the rule-base, by design, may be easier to follow and understand than a complex mathematical algorithm.

A force field method, while attractive in the sense that a conflict resolution solution is continuously available using relatively simple equations, has some pathologies that make it difficult to be used in operation. For example, a solution from a force field model may require that an aircraft continually make a series of gradual turns and speed changes. This requires a high level of guidance on the flight deck and increases complexity beyond issuing simple heading vectors. Additionally, some solutions may include cusps or other non-physical trajectories that must be corrected in post-processing.

The use of thresholds is currently the standard method in operational systems such as TCAS, GPWS, or PRM. These systems use a relatively simple threshold based on time to impact or time to closest point of approach. These systems are generally well-understood by operators but only implicitly consider aircraft performance and the geometry of a conflict. For example, certain geometries may require more time to resolve than others, but temporal approaches do not take geometry directly into account. Instead, the temporal threshold is selected through an analysis of different types of encounters so as to maximize safety while reducing unnecessary alerts as much as possible.

Coordinating conflict resolution between aircraft has two primary benefits. First, the required magnitude of maneuvering is reduced when both aircraft maneuver when compared against a case in which only one aircraft maneuvers. Second, coordination helps ensure that both aircraft do not maneuver in a direction which could prolong or intensify the conflict. However, a system designed assuming coordination should also be evaluated in cases in which coordination is not carried out as planned. This would provide some measure of the robustness of the system to datalink failure or pilot error.

In a realistic traffic environment, it will be necessary that a conflict detection and resolution system be able to manage more than one conflict at a time. As mentioned earlier, there are basically two methods by which multiple conflicts can be handled. In the first, each pair of conflicts is examined and solved sequentially. If a conflict solution produces a new conflict, the original solution may be modified until a conflict-free solution is found. This is the approach taken by TCAS, and is effective but also could potentially fail in certain situations. A global solution involves considering the entire traffic situation when detecting and resolving conflicts, and while more complex, may be more robust. For example, consider the situation shown in Fig. 3. On the left, a pairwise solution is shown. The host aircraft detects a conflict with a coaltitude threat and attempts to climb or descend. Neither solution is acceptable since it produces a conflict with another aircraft. On the right, a global solution considers all three threat aircraft simultaneously and determines that the climb or descent maneuver must begin earlier than required for any one threat in order to safely resolve the conflict. At the least, models should be examined in multi-aircraft situations to determine their robustness to this type of problem.

Fig. 3 Multi-Aircraft Conflict Resolution

1 Final Report of RTCA Task Force 3: Free Flight Implementation, RTCA, Washington DC, October 26, 1995.

2 Odoni, Bowman, Delahaye, Deyst, Feron, Hansman, Khan, Kuchar, Pujet, and Simpson, "Existing and Required Modeling Capabilities for Evaluating ATM Systems and Concepts", MIT Dept. of Aeronautics and Astronautics, March 1997.

3 Knecht, W. R., "Developing a Probabilistic Metric of Midair Collision Risk", Submitted to Transportation Research Record, 1997.

4 Barhydt, R., "Experimental Studies of the Effect of Intent Information on Cockpit Traffic Displays", S.M. Thesis, MIT, Cambridge, MA, May, 1997.

5 Waller, M. C. and C. H. Scanlon, eds., "Proceedings of the NASA Workshop on Flight Deck Centered Parallel Runway Approaches in Instrument Meteorological Conditions", NASA Conference Publication 10191, Hampton, VA, December, 1996.

6 Andrews, J. W., "A Relative Motion Analysis of Horizontal Collision Avoidance", SAFE Journal, Vol. 8, No. 2, 1978.

7 Bakker, G. J. and H. A. P. Blom, "Air Traffic Collision Risk Modeling", Proceedings of the 32nd IEEE Conference on Decision and Control, Vol. 2, San Antonio, TX, December, 1993.

8 Bilimoria, K. D., Sridhar, B., and G. B. Chatterji, "Effects of Conflict Resolution Maneuvers and Traffic Density of Free Flight", AIAA Guidance, Navigation, and Control Conference, San Diego, CA, 1996.

9 Burgess, D. W., Altman, S. I., and M. L. Wood, "TCAS: Maneuvering Aircraft in the Horizontal Plane", Lincoln Laboratory Journal, Vol. 7, No. 2, 1994.

10 Carpenter, B. and J. Kuchar, "Probability-Based Collision Alerting Logic For Closely-Spaced Parallel Approach", Paper AIAA-97-0222, 35th AIAA Aerospace Sciences Meeting and Exhibit, Reno, NV, January 6-10, 1997.

11 Coenen, F. P., Smeaton, G. P., and A. G. Bole, "Knowledge-Based Collision Avoidance", Journal of Navigation, Vol. 42, No. 1, 1989.

12 Durand, N., Alliot, J., and O. Chansou, "Optimal Resolution of En Route Conflicts", Air Traffic Control Quarterly, Vol. 3, No. 3. pp. 139-161, 1995.

13 Eby, M. S., "A Self-Organizational Approach for Resolving Air Traffic Conflicts", Lincoln Laboratory Journal, Vol. 7, No. 2, 1994.

14 Ford, R. L., "The Conflict Resolution Process for TCAS II and Some Simulation Results", Journal of Navigation, Vol. 40, No. 3, 1987.

15 Ford, R. L., and D. L. Powell, "A New Threat Detection Criterion for Airborne Collision Avoidance Systems", Journal of Navigation, Vol. 43, No. 3, 1990.

16 Radio Technical Committee on Aeronautics (RTCA), "Minimum Performance Standards - Airborne Ground Proximity Warning Equipment", Document No. RTCA/DO-161A, Washington, D.C., May 27, 1976.

17 Havel, K. and J. Husarcik, "A Theory of the Tactical Conflict Prediction of a Pair of Aircraft", Journal of Navigation, Vol. 42, No. 3, 1989.

18 Heuvelink, G. and H.A.P. Blom, "An Alternative Method to Solve a Variational Inequality Applied to an Air Traffic Control Example", Analysis and Optimization of Systems: 8th International Conference, 1988.

19 Iijima, Y., Hagiwara, H., and H. Kasai, "Results of Collision Avoidance Maneuver Experiments Using a Knowledge-Based Autonomous Piloting System", Journal of Navigation, Vol. 44, No. 2, 1991.

20 Kosecka, J., Tomlin, C., Pappas, G., and S. Sastry, "Generation of Conflict Resolution Maneuvers for Air Traffic Management", Submitted for the International Conference on Robotics and Intelligent Systems, Sept. 1997.

21 Krozel J., Mueller, T., and G. Hunter, "Free Flight Conflict Detection and Resolution Analysis" Paper AIAA-96-3763, AIAA Guidance, Navigation, and Control Conference, San Diego, CA, 1996.

22 Krozel, J., and M. Peters, "Conflict Detection and Resolution for Free Flight", Accepted for publication in Air Traffic Control Quarterly, 1997.

23 Love, D., "TCAS III: Bringing Operational Compatibility to Airborne Collision Avoidance", AIAA/IEEE 8th Digital Avionics Systems Conference, 1988.

24 Paielli, R. A. and H. Erzberger, "Conflict Probability Estimation for Free Flight", Journal of Guidance, Control, and Dynamics, Vol. 20, No. 3, May-June, 1997.

25 Federal Aviation Administration, "Precision Runway Monitor Demonstration Report", Document DOT/FAA/RD-91/5, February, 1991.

26 Ratcliffe, S., "Automatic Conflict Detection Logic for Future Air Traffic Control", Journal of Navigation, Vol. 42, No. 3, 1989.

27 Rome, H. J. and R. Kalafus, "Impact of Automatic Dependent Surveillance and Navigation System Accuracy on Collision Risk on Intersecting Tracks", Proceedings of the National Technical Meeting of the Institute of Navigation, 1988.

28 Shepard, T., Dean, T., Powley, W., and Y. Akl, "A Conflict Prediction Algorithm Using Intent Information", 36th Annual Air Traffic Control Assoc. Conference Proceedings, Fall 1991.

29 Shewchun, M., and E. Feron, "Linear Matrix Inequalities for Analysis of Free Flight Conflict Problems", Paper submitted to IEEE Conference on Decision and Control, 1997.

30 Sridhar, B. and G. B. Chatterji, "Computationally Efficient Conflict Detection Methods For Air Traffic Management", Proceedings of the American Control Conference, Albuquerque, NM, June 3-5, 1997.

31 Taylor, D. H., "Uncertainty in Collision Avoidance Maneuvering", Journal of Navigation, Vol. 43, No. 2, 1990.

32 Radio Technical Committee on Aeronautics (RTCA), "Minimum Performance Specifications For TCAS Airborne Equipment", Document No. RTCA/DO-185, Washington, D.C., September, 1983.

33 Tomlin, C., Pappas, G. J., and S. Sastry, "Conflict Resolution for Air Traffic Management: a Case Study in Multi-Agent Hybrid Systems", University of California at Berkeley, 1996.

34 Wangermann, J. P. and R. F. Stengel, "Principled Negotiation Between Intelligent Agents: A Model for Air Traffic Management", ICAS-94-8.6.3, ICAS Proceedings, Vol. 3. pp. 2197-2207, 1994.

35 Wangermann, J. P. and R. F. Stengel, "Optimization and Coordination of Multi-Agent Systems Using Principled Negotiation", AIAA-96-3853, AIAA Guidance, Navigation, and Control Conference, San Diego, CA, July 29-31, 1996.

36 Williams, P. R., "Aircraft Collision Avoidance using Statistical Decision Theory", Proceedings from Sensors and Sensor Systems for Guidance and Navigation II, 1992.

37 Yang, L. and J. Kuchar, "Prototype Conflict Alerting Logic for Free Flight", Paper AIAA-97-0220, 35th AIAA Aerospace Sciences Meeting and Exhibit, Reno, NV, January 6-10, 1997.

38 Zeghal, K, "Towards the Logic of an Airborne Collision Avoidance System which Ensures Coordination with Multiple Cooperative Intruders", ICAS-94-8.6.4, ICAS Proceedings.,Vol. 3. pp. 2208-2218, 1994.

39 Pritchett, A. R., "Pilot Non-Conformance to Alerting System Commands During Closely Spaced Parallel Approaches", Sc.D. Thesis, Department of Aeronautics and Astronautics, MIT, Cambridge, MA, December, 1996.

Reprint: AIAA-97-3732 AIAA Guidance, Navigation, and Control Conf., New Orleans, LA, August 11-13, 1997