A Review of Conflict Detection and Resolution Modeling Methods <s> VI. CONCLUDING REMARKS <s> This paper describes preliminary studies towards a navigational Knowledge-based System currently in progress within the School of Engineering and Technology Management at Liverpool Polytechnic <s> BIB001 </s> A Review of Conflict Detection and Resolution Modeling Methods <s> VI. CONCLUDING REMARKS <s> Maneuver option manager (MOM) is part of an air traffic control automation project, sponsored by the Federal Aviation Administration (FAA), in which the computer for the first time assumes responsibility for separation assurance between en route aircraft. MOM's purpose is to detect and simplify certain complex air traffic control problems, identified here as sets of interrelated potential pairwise separation problems. MOM determines which of six types of maneuver options is available (free of possible separation problems) for each aircraft. MOM simplifies a complex problem by protecting (for future use) an available maneuver option for one or more of the involved aircraft. Routinely, a single maneuver option resolves multiple pairwise problems. MOM's actions cause complex problems to be iteratively broken down into independent, smaller, and less complex problems. > <s> BIB002 </s> A Review of Conflict Detection and Resolution Modeling Methods <s> VI. CONCLUDING REMARKS <s> Stream Option Manager (SOM) is a proposed concept for automated integration of aircraft separation, merging and stream management, using linear programming techniques. It was developed as part of a research and development initiative for air traffic control (ATC) automation concepts, sponsored by the Federal Aviation Administration (FAA) and performed by MITRE Corporation. SOM is research; it has not been approved by the FAA for use in future ATC. SOM's purpose is to resolve possible problems involving multiple aircraft with given flight paths. Each aircraft must be separated by a minimum distance from every other aircraft at all times, and certain sets of aircraft (e.g., those about to land at a particular airport) must be merged or metered (lined up, or separated in trail by a given distance). Aircraft in sets called streams must be separated in the along-route direction at all times. Each aircraft is also subject to certain speed limits. Given the pilot-preferred flight paths, and separation, metering, stream, and speed requirements, SOM finds modified flight paths for each aircraft that satisfy all the requirements yet stay as close as possible to the pilot-preferred paths. SOM's algorithm represents the (x, y, z) positions of each aircraft at future times as variables in a linear program. The requirements are expressed or approximated by linear inequalities or equalities. Pilot preferences are approximated by a linear objective function. The SOM algorithm has been implemented successfully in a prototype simulation in 2D. Scenarios with up to 15 aircraft and 24 separation and/or merging problems have been resolved. > <s> BIB003 </s> A Review of Conflict Detection and Resolution Modeling Methods <s> VI. CONCLUDING REMARKS <s> Air Traffic Management (ATM) combines the roles of Air Traffic Control (ATC) and Traffic Flow Management (TFM). Generally, TFhl is concerned with the smooth and efficient flow of traffic in the airspace while ATC has the responsibility for maintaining the separation between aircraft. The challenge for the ATM system is to accommodate growth in air traffic while maintaining the same level of safety and increased operator flexibility. This can only be achieved by introducing the technological innovations in Communication, Navigation and Surveillance (CNS) and by the development of decision support tools for controllers, pilots and airline operations. Basic components of these decision support tools are algorithms and software for conflict detection and resolution. This paper takes a detailed look at the standard approach to conflict detection in order to reduce the number of computations. The number of computations are reduced by posing the conflict detection problem in two steps: (a) spatial separation and (b) temporal separation. Three algorithms for conflict detection are described. The first method describes the standard approach. It computes the Euclidean distance between all aircraft pairs and compares the distance to the allowable minimum separation distance. The number of computations required by this method are of the order of n2 where n is the number of aircraft. The second algorithm transforms the planned trajectories of the aircraft into a sequence of discrete spatial regions which are then sorted to locate regions in airspace where conflict is possible. The number of computations in this case are of the order of nlog, n. The third algorithm uses an accumulator driven by the transformed trajectories to locate regions where conflict is possible. It is shown that the computational complexity of this algorithm is of the order of n. Algorithmic details of the sorting-based and accumulator-based algorithms are provided. Numerical examples are presented to demonstrate the theoretical computational advantage of using the sorting-based and accumulator-based conflict detection algorithms over the standard method. <s> BIB004 </s> A Review of Conflict Detection and Resolution Modeling Methods <s> VI. CONCLUDING REMARKS <s> This paper studies strategies for resolving two aircraft conflicts in a free flight environment for air traffic management. In a free flight environment, pilots of individual aircraft can change flight paths in real time. As a result, resolving conflicts among aircraft becomes a key priority for controllers. In this paper, a pointmass level flight aircraft model is used. Resolution of a two-aircraft conflict is formulated as deterministic nonlinear optimal control problems. Performance indices are selected to minimize deviations of both aircraft from their originally-intended flight paths or to minimize banking angles, subject to a minimum separation requirement. In addition, terminal constraints are included that force each aircraft to return to its original path after conflict avoidance maneuvers. In an unrestricted region, it is assumed that aircraft are originally flying with a constant heading. In general, the two aircraft would turn the same way (left or right) by roughly the same amount to avoid a conflict. When the intersecting angle is small, however, one aircraft needs to take a path stretching to avoid the other aircraft. In the terminal region where aircraft converge to the same gate, one aircraft needs to stretch its flight paths to avoid the other aircraft. If the two aircraft have the same speed, either aircraft can perform the path stretching. If the two aircraft have different speeds, the slower aircraft should perform the path stretching. <s> BIB005 </s> A Review of Conflict Detection and Resolution Modeling Methods <s> VI. CONCLUDING REMARKS <s> With a Free Flight policy, the emphasis for air traffic control is shifting from active control to passive air traffic management with a policy of intervention by exception. Aircraft will be allowed to fly user preferred routes, as long as safety Alert Zones are not violated. If there is a potential conflict, two (or more) aircraft must be able to arrive at a solution for conflict resolution without controller intervention. Thus, decision aid tools are needed in Free Flight to detect and resolve conflicts, and several problems must be solved to develop such tools. In this report, we analyze and solve problems of proximity management, conflict detection, and conflict resolution under a Free Flight policy. For proximity management, we establish a system based on Delaunay Triangulations of aircraft at constant flight levels. Such a system provides a means for analyzing the neighbor relationships between aircraft and the nearby free space around air traffic which can be utilized later in conflict resolution. For conflict detection, we perform both 2-dimensional and 3-dimensional analyses based on the penetration of the Protected Airspace Zone. Both deterministic and non-deterministic analyses are performed. We investigate several types of conflict warnings including tactical warnings prior to penetrating the Protected Airspace Zone, methods based on the reachability overlap of both aircraft, and conflict probability maps to establish strategic Alert Zones around aircraft. <s> BIB006 </s> A Review of Conflict Detection and Resolution Modeling Methods <s> VI. CONCLUDING REMARKS <s> Conflict detection and resolution has a long history of investigation, but further investigation is necessary as a result of new Free Flight policies removing many constraints; new data link, GPS, ... <s> BIB007 </s> A Review of Conflict Detection and Resolution Modeling Methods <s> VI. CONCLUDING REMARKS <s> Recent advances in navigation and data communication technologies make it feasible for individual aircraft to plan and fly their trajectories in the presence of other aircraft in the airspace. This way, individual aircraft can take advantage of the atmospheric and traffic conditions to optimally plan their paths. This capability is termed as the free flight concept. While the free flight concept provides new degrees of freedom to the aircraft operators, it also brings-in complexities not present in the current air traffic control system. In the free flight concept, each aircraft has the responsibility for navigating around other aircraft in the airspace. While this is not a difficult task under low speed, low traffic density conditions, the complexities of dealing with potential conflict with multiple aircraft can significantly increase the pilot’s work load. This paper presents the development of a conflict resolution algorithm based on the quasilinearization method to enable the practical implementation of the free flight concept. The algorithm development uses nonlinear point-mass aircraft models, and incorporates realistic operational constraints on individual aircraft. The analytical framework can also incorporate information about ambient atmospheric conditions. Realistic conflict resolution scenarios are illustrated. Due to their speed of execution, these conflict resolution algorithms are suitable for implementation on-board aircraft. <s> BIB008 </s> A Review of Conflict Detection and Resolution Modeling Methods <s> VI. CONCLUDING REMARKS <s> Recent advances in air traffic Communication Navigation and Surveillance (CNS) have encouraged investigations into the concept following which Air Traffic Control functions can be delegated to the flight deck, allowing more freedom of movement to airspace users. In late 1995, an initiative, known under the project name FREER, for Free-Route Experimental Encounter Resolution, was introduced at EUROCONTROL to investigate the feasibility of this concept. In this paper, we present the initial results obtained from the Autonomous Aircraft Operations study (FREER-I) that targets full delegation of ATC to aircraft operating in low-density airspace. Specific issues of Autonomous Aircraft Operations (AAO) supporting free-route, free flight and user-preferred routing are discussed. A description of the current prototype illustrating the Airborne Interactive Conflict Resolution Advisory service is included. <s> BIB009 </s> A Review of Conflict Detection and Resolution Modeling Methods <s> VI. CONCLUDING REMARKS <s> A novel collision cone approach is proposed as an aid to collision detection and avoidance between irregularly shaped moving objects with unknown trajectories. It is shown that the collision cone can be effectively used to determine whether collision between a robot and an obstacle (both moving in a dynamic environment) is imminent. No restrictions are placed on the shapes of either the robot or the obstacle, i.e., they can both be of any arbitrary shape. The collision cone concept is developed in a phased manner starting from existing analytical results that enable prediction of collision between two moving point objects. These results are extended to predict collision between a point and a circular object, between a point and an irregularly shaped object, between two circular objects, and finally between two irregularly shaped objects. Using the collision cone approach, several strategies that the robot can follow in order to avoid collision, are presented. A discussion on how the shapes of the robot and obstacles can be approximated in order to reduce computational burden is also presented. A number of examples are given to illustrate both collision prediction and avoidance strategies of the robot. <s> BIB010 </s> A Review of Conflict Detection and Resolution Modeling Methods <s> VI. CONCLUDING REMARKS <s> Air Tra c Management (ATM) of the future allows for the possibility of free ight, in which aircraft choose their own optimal routes, altitude and speed. In a free ight environment, the trajectories of di erent aircraft may be con icting, in which case aircraft may or may not cooperate in resolving the con ict. In this paper, both cooperative and noncooperative con ict resolution methods are presented. Noncooperative methods are based on game theory in which each aircraft models the actions of other aircraft as disturbances and chooses its actions to be safe against the worst possible disturbance. The solutions to the games partition the state space into safe and unsafe sets and the control strategies are abstracted into discrete protocols on hybrid automata. In cooperative methods, aircraft perform coordinated maneuvers in order to avoid con ict. The merging of inter-aircraft coordination protocols with the individual continuous control laws of each aircraft gives rise to hybrid systems which have been made safe by design. Two examples of con ict resolution using speed and heading changes are worked out in detail. <s> BIB011 </s> A Review of Conflict Detection and Resolution Modeling Methods <s> VI. CONCLUDING REMARKS <s> This paper presents a new approach to the aircraft collision avoidance problem. This approach gives a recommended avoidance trajectory in both the horizontal and vertical planes of motion based on the geometric relationship between aircraft and threats. A new concept, the "threat map", is introduced to describe moving threats as static threats. Thus, motion planning for dynamic threats is reduced to path planning for stationary threat avoidance. At every time interval, the threat map is updated and the velocity direction of the aircraft is calculated to avoid the threats. The "risk space" is used to model a threat By avoiding the risk space, the aircraft avoids the threat while keeping a safe separation. Some simulation studies show the effectiveness of the proposed approach. <s> BIB012 </s> A Review of Conflict Detection and Resolution Modeling Methods <s> VI. CONCLUDING REMARKS <s> An antenna and antenna coupling apparatus is provided in which a receiving antenna is used with a super regenerative transponder receiver. The antenna comprises a coaxial cable which has the outer conductor stripped away from the inner conductor at one end and both the outer conductor and inner conductor bent so as to be at right angles. At the other end of the cable the outer conductor is also stripped away from the inner conductor and both are also bent at right angles. The coaxial cable passes through a shield enclosing the receiver and is soldered at the center of the bottom of the shield thus coupling the antenna to the receiver. <s> BIB013 </s> A Review of Conflict Detection and Resolution Modeling Methods <s> VI. CONCLUDING REMARKS <s> Many of the nation's airspace users desire more freedom in selecting and modifying their routes. This desire has been expressed in the free flight concept, which has gained increased attention in the last few years. Free flight offers the potential for more efficient routes, decreased fuel costs, and less dependence on air traffic control. The greatest challenge, however, is maintaining the safe separation between aircraft. This problem is often referred to as conflict detection and resolution (CD and R). This paper describes a technique by which aircraft may simultaneously and independently determine collision-free flight operational environment. The technique derived from potential-field has demonstrated tremendous robustness in of scenarios ranging from simple two-aircraft conflicts and contrived geometric formations to complex, randomized multi-aircraft conflicts. Communication failures and restrictive maneuverability constraints have also been considered. The results of this work suggest that potential field algorithms are an extremely robust solution to the problem of CD and R. The results also show that these algorithms can be adapted to a situation requiring distributed computation and resolution. The advantage of a distributed approach is the decreased reliance on a central command authority. <s> BIB014 </s> A Review of Conflict Detection and Resolution Modeling Methods <s> VI. CONCLUDING REMARKS <s> Many of the nation's airspace users desire an increase in efficiency in the air traffic control system. Some feel that an increase in efficiency can be achieved by moving away from a centralized control paradigm towards a distributed control paradigm. In a distributed control paradigm, the cockpit crew would have more freedom in selecting and modifying their routes. This new paradigm is part of the Free Flight concept. Increased autonomy of operations will require increases in cockpit information, pilot responsibility, and avionics capability. One of the key enabling capabilities will be the detection and resolution of air traffic conflicts. CDR a baseline conflict detection algorithm based on instantaneous state vectors; and an analysis of the algorithm's performance for flight data from the ADS-B Operational Evaluation. <s> BIB015 </s> A Review of Conflict Detection and Resolution Modeling Methods <s> VI. CONCLUDING REMARKS <s> The objective of this research was to design and demonstrate an agent-based modeling and analysis tool for evaluating air traffic controller (ATC) performance under free flight air traffic management (ATM), and to develop a distributed decision-making model to investigate the potential for collaborative problemsolving under free flight. We developed a set of intelligent agent models representing ATC and pilot behavior in free flight. These models contain simplified representations of information processing and situation assessment applied to air traffic conflict detection. They also contain detailed air traffic conflict resolution models applying collaborative decisionmaking via inter-agent negotiation. We demonstrated the operation of a limited-scope prototype in a set of simulation trials designed to exercise the multi-agent decision-making model under a spectrum of free flight air traffic configurations. The results showed that our agent models are capable of performing on-line learning to support global situation awareness (SA) in the air traffic environment. The nature of conflict resolution maneuvers negotiated by the agents varied with conflict geometry in a manner consistent with intuitive expectation. <s> BIB016 </s> A Review of Conflict Detection and Resolution Modeling Methods <s> VI. CONCLUDING REMARKS <s> An artificial intelligence (AI) knowledge model is proposed as a basis for automated conflict management in close free-flight air space. A conceptual framework of the model is developed. The problem of air traffic control (ATC) within a group of potentially conflicting vehicles is represented as an autonomous, self-organizing process. This process incorporates the principles of collective behavior observed in nature (bird flocking, fish schooling, insect swarming, etc.) and comprehensive knowledge of the "pilot vehicle-operational environment" system dynamics derived from special computer experiments. Through this process, real-time knowledge-based predictions of near term flight paths are made to prevent and resolve conflicts in a group of vehicles under normal and demanding conditions. The model may be useful for prototyping intelligent technologies for assisted and automatic collision avoidance in close air space. <s> BIB017 </s> A Review of Conflict Detection and Resolution Modeling Methods <s> VI. CONCLUDING REMARKS <s> Under the concept of Free Flight, future air traffic operations may permit the transfer of responsibility for various tasks, including conflict detection and resolution, from ground-based air traffic controllers to the flight crew. While aircraft-based conflict resolution is attractive from a user-preferences standpoint, the degree to which it can efficiently resolve complex conflicts among several interacting aircraft remains a significant issue. The objective of this study is to compare the performance of a decentralized conflict resolution strategy against that of a benchmark centralized conflict resolution strategy. A generalized methodology for such a comparison does not exist; therefore two qualitatively different conflict scenarios, characterized by complex interactions among multiple aircraft, were constructed to conduct simulation studies using an idealized model. Preliminary investigations indicate that a decentralized resolution strategy can successfully solve complex multiple-aircraft problems in real time, albeit with some performance degradation relative to a centralized strategy. Research Scientist, Automation Concepts Research Branch; Mail Stop 210-10; E-mail; kbilimoria@mail.arc.nasa.gov. Associate Fellow, AIAA. f Software Specialist, Raytheon ITSS. Research Assistant, Dept. of Aeronautics and Astronautics. Associate Professor, Dept. of Aeronautics and Astronautics; E-mail: feron@mit.edu. Senior Member, AIAA. Copyright © 2000 by the American Institute of Aeronautics and Astronautics, Inc. No copyright is asserted in the United States under Title 17, U.S. Code. The U.S. Government has a royalty-free license to exercise all rights under the copyright claimed herein for Governmental purposes. All other rights are reserved by the copyright owner. Introduction The advent of new technologies for Air Traffic Management (ATM) has the potential to change the operational paradigm of the air transportation system by delegating more responsibility to the flight deck for airplane trajectory management functions; this includes conflict detection and resolution (CDR this is an idealized representation of a situation where several "free flying" aircraft are simultaneously attempting to arrive at some terminal area entry point. The second scenario features two closelyspaced traffic streams (each consisting of several aircraft) intersecting at a common point; this is an idealized representation of aircraft flying along intersecting "free routes" in en route airspace. The performance of a reactive decentralized resolution method that provides sequential, pairwise conflict resolutions based on a geometric optimization approach10 is compared against that of a proactive centralized resolution method that provides a single coordinated conflict resolution based on a global optimization algorithm.5 Although determining a fully coordinated optimal solution to conflicts involving multiple aircraft is computationally challenging, the centralized conflict resolution method described in Ref. 5 is able to compute these solutions, which are used as benchmarks for the best performance that can be achieved. The performance of decentralized strategies is then compared against these benchmark solutions. This paper is organized as follows: First, the mathematical models used for aircraft trajectories and conflict avoidance are presented. The centralized and decentralized conflict resolution methods used in this study are then outlined. Next, performance measures for conflict resolution are defined, and two conflict scenarios are described. Finally, a comparison of the performance of the decentralized conflict resolution strategy relative to the centralized conflict resolution strategy is presented, along with some general observations about their characteristics. <s> BIB018 </s> A Review of Conflict Detection and Resolution Modeling Methods <s> VI. CONCLUDING REMARKS <s> An auto-sequencing associative store provides outputs during a read operation which at least partially forms the search argument for the next store cycle to improve the speed of operation in a data processor. <s> BIB019 </s> A Review of Conflict Detection and Resolution Modeling Methods <s> VI. CONCLUDING REMARKS <s> Designing a Control Simulator involves many difficult problems: modeling conflict detection, trajectory uncertainties, solving conflict inside sectors, respecting military areas constraints, coordinating aircraft between sectors, etc\ldots Moreover, the n-aircraft conflict resolution problem is highly combinatorial and cannot be optimally solved using classical mathematical optimization techniques. The set of admissible solutions is made of many unconnected subsets enclosing different local optima, but the subset enclosing the optimum cannot be found a priori. In this paper, we present a conflict solver and its implementation in an Air Traffic simulator, with statistical results on real traffic in a French Sector. This solver, which takes into account real flight plans, solves every conflict inside a sector or over the French airspace on a loaded day. <s> BIB020
It is clear from this survey of models that there are a large number and variety of approaches to the conflict detection and resolution problem. In regard to future approaches, however, it will be important that a larger set of issues is considered than has typically been the case in the models discussed here. These issues include the effects of uncertainty, ability to handle multiple conflicts, coordination, computational requirements, implementation issues, pilot and controller acceptance, robustness to degradation or failure, integration with other hazard information such as weather, and verification and certification requirements. The majority of the models covered here do not yet adequately address these concerns. Additionally, a consistent benchmarking method for analyzing and validating models is required. This is difficult due to the variety of operational modes and conditions to which CD&R systems may be exposed, but will be necessary in order to select the most effective systems for implementation in the field.  H -O T P Bilimoria BIB018 H -O C(ST) P & G Chakravarthy BIB010 H -O C(ST) P Frazzoli BIB019 H -O C(ST) G Tomlin BIB011 H -O T G Irvine  HV -O C(STV) P Ota BIB012 HV -O C(TV) G Kosecka  H -F C(ST) G Zeghal  H -F C(ST) G Eby  BIB014 HV -F C(STV) G Sridhar BIB004 H √ --P EGPWS  HV √ ---Havel  HV √ --P Kelly BIB015 HV √ --P TCAD  HV √ --P GPWS  V √ P V -PRM  H √ P C(TV) P Bilimoria  HV √ P STV P Burgess  H √ O TV P Coenen BIB001 H √ O ST P Gazit  H √ O VT P Harper BIB016 H √ O C(ST) G Iijima  H √ O ST P Niedringhaus BIB003 H √ O C(ST) G Zhao BIB005 H √ O T P Burdun BIB017 HV √ O C(STV) P Durand BIB020 HV √ O T G Ford  HV √ O V P Krozel BIB006 BIB007 HV √ O STV P Love  HV √ O TV P Menon BIB008 HV √ O C(STV) G Niedringhaus BIB002 HV √ O STV G Schild BIB013 HV √ O C(TV) P TCAS  HV √ O V P Hoekstra  HV √ F C(STV) P Zeghal  HV √ F C(STV) G Duong BIB009 HV √ M / F C(STV) P Tables 1-3 