вход по аккаунту



код для вставкиСкачать
AIAA 2011-6659
AIAA Guidance, Navigation, and Control Conference
08 - 11 August 2011, Portland, Oregon
Distributed Logic-Based Conflict Resolution of Multiple
Aircraft in Planar En-Route Flight
Downloaded by UNIVERSITY OF ADELAIDE on October 28, 2017 | | DOI: 10.2514/6.2011-6659
A. Alaeddini1 and H. Erzberger2 and W. Dunbar3
University of California, Santa Cruz, Santa Cruz, CA, 95064
In this paper, the problem of designing conflict-free maneuvers for planar multipleaircraft encounters in en-route flight is studied. An algorithm for automated and distributed
conflict resolution for two or more aircraft is developed. The algorithm is intended for use in
the future air traffic system, which may be implemented in a distributed way that permits
free flight. The proposed algorithm searches several different scenarios for conflict
resolutions between multiple aircraft while preventing secondary conflicts where possible.
The multiple aircraft resolution algorithm generalizes the ground-based centrally
coordinated pair-wise conflict resolution algorithm that was developed previously at NASA
Ames Research Center. The proposed algorithm can in principle resolve a conflict involving
any number of aircraft. Simulations are done for up to 5 times the current air traffic density.
In these simulations conflicts between 2, 3, 4 and 5 aircraft are observed and resolved by the
X A, Y A
position of aircraft A in the plane
ground speed of aircraft A
Heading angle of aircraft A
turn radius
Bank angle
Heading change angle
X component of the relative velocity
Y component of the relative velocity
time to minimum separation in the straight-line segment beginning at the end of the turn
minimum separation achieved in the straight-line segment beginning at the end of the turn
Look-ahead time, 3-5 minutes
Turn resolution time, less than 1 minutes
time the conflict is detected
start time of conflict resolution maneuver
time of conflict occurrence
number of conflicting aircraft
number of background aircraft
number of maneuvering aircraft
I. Introduction
ECADES of operational experience have demonstrated that the current airspace structure is safe. But this
structure suffers from some drawbacks, such as indirect routes from origin to destination and lack of flight path
freedom for airlines and pilots. The growth of air transportation in recent years makes this structure, which is based
on pre-determined corridors, inefficient and not sustainable. Distributed Air-Ground Traffic Separation (DAG-TS)
has proposed a solution for expanding airspace capacity limits. The concept of distributed air traffic management
offers the possibility of a free flight implementation as well as increasing the capacity of the airspace system. Free
Graduate Research Assistant, Department of Aeronautics and Astronautics, University of Washington, WA.
Professor, Department of Electrical Engineering, 1156 High Street, CA.
Professor, Department of Computer Engineering, 1156 High Street, Santa Cruz, CA.
American Institute of Aeronautics and Astronautics
Copyright © 2011 by the American Institute of Aeronautics and Astronautics, Inc. All rights reserved.
Downloaded by UNIVERSITY OF ADELAIDE on October 28, 2017 | | DOI: 10.2514/6.2011-6659
flight is defined as a safe and efficient flight operating capability under IFR4 in which operators have the freedom to
select their path and speed in real time (Ref. 4). As the traffic density increases, the workload due to safe separation
assurance of traffic would exceed human capabilities. The current airspace system, which is generally based on
ground-centralized controllers, is likely to reach saturation levels as the traffic increases. In Ref. 1, the loss of
scheduled air carriers due to delay in 1995 was estimated to be $3.5 billion. This amount of loss shows the necessity
of designing new algorithms for a more efficient use of airspace. One of the methods is a special kind of SelfSeparation concept, as suggested in Ref. 15, in which flight crews could use avionics to monitor and separate
themselves along specific pre-defined corridors. This is similar to the current air-space structure, which relies on the
pre-defined fixed airways. These pre-defined airways will not be able to handle the increased traffic level projected
for the future.
A fundamental design requirement for next-generation air traffic control system, whether ground or air-to-air
centered, is a highly reliable and safe method for automating separation assurance. Several independent and
redundant systems for separation assurance are necessary to achieve that requirement. A candidate for the nextgeneration system, referred to as the Automated Airspace Concept (AAC) incorporates three levels of protection
against conflicts and collisions (Ref. 11). The second level of protection handles close-in conflicts, which are the
conflicts that are not detected until loss of separation is less than 3 minutes. These conflicts have not been resolved
in the first level. The algorithms that try to resolve these conflicts are called tactical separation assurance algorithms.
Tactical schemes that achieve separation when all aircraft independently maneuver are presented in Ref. 8 and 9.
These algorithms use only state, and not intent, information to predict the aircraft trajectory. Due to this limited level
of information the algorithm has little time to solve the conflict. This paper focuses on the design of tactical
separation assurance algorithm for resolving close-in conflicts (2-5 min to loss of separation).
The airborne self-separation concept, introduced in Ref. 5, works only in sufficiently low traffic density. In that
approach each pilot solves conflicts sequentially and in an uncoordinated way. When the traffic density gets higher,
multiple conflicts can occur that require coordination between aircraft. Coordination can be achieved by assigning
priorities to the conflicting aircraft. The priorities can be pre-determined by a set of rules. Ref. 14 tries to introduce a
set of rules of the road. As it is expressed in Ref. 12, this method might work just for two aircraft cases and it may
required many additional rules to handle all situations arising when more than two aircraft are involved.
In Ref. 3 a method of distributed conflict resolution is presented which is called KB2D (two dimensional) and
KB3D (three dimensional). These algorithms compute resolution maneuvers based on velocity vector modification.
This method does not include aircraft limits on lateral and vertical acceleration and can fail to properly resolve
close-in conflicts.
There are many studies that are based on resolution of conflicts involving two aircraft. For instance the authors
of Ref. 13 introduce an algorithm that minimizes a certain energy cost function. This algorithm basically works for
two aircraft, but they use an approximation to compute a suboptimal two-legged solution for multiple aircraft
As the conflict resolution of aircraft is a real-time problem, computing time is very important. Therefore an
algorithm is needed to solve the problem in negligible time compared to the time scales of en-route flight dynamics.
Many authors use this criterion to compare the acceptability of their proposed algorithm. For instance, the authors of
Ref. 2 claim that their algorithm works ten times faster than genetic algorithm. But it can only solve the conflicts of
five aircraft.
II. Analytical background
The main task of ATM system is separation assurance between aircraft, which will prevent any two aircraft from
coming closer together than a minimum allowed horizontal separation R and a minimum allowed vertical separation
H. R is set equal to 5 nautical miles in en-route airspace and 3 nautical miles inside the Terminal Radar Approach
Control facilities (TRACONs). H is 1000ft.
The objective of this work is to develop an algorithm that resolves all short-range conflicts by horizontal
maneuvers. The following is the summary of analytical formulation for horizontal separation assurance between two
aircraft (Ref. 11 and 16). These formulations are the basis for the equations for the pair-wise and multiple aircraft
conflict resolution.
Instrument Flight Rules, which are regulations and procedures for flying aircraft by referring only to the aircraft
instrument panel for navigation.
American Institute of Aeronautics and Astronautics
XAt = XAt0 +VA  ( t  t0 ) sin A
YAt = YAt0 +VA  ( t  t0 ) cos A
In these equations, XA ,YA is the position of aircraft at time t and XA0 ,YA 0
) is the position of aircraft at time
is the heading angle of aircraft. The following equations are the relations
t0 , V is the air speed of aircraft and
between turn radius (R), aircraft velocity (V), bank angle (  ) and turning time (t).
Downloaded by UNIVERSITY OF ADELAIDE on October 28, 2017 | | DOI: 10.2514/6.2011-6659
 =
gtan 
t  g tan 
Therefore, the relation between heading change angle of two maneuvering aircraft (aircraft A and B) is inversely
related with the relation of their speed. This is given by equation 5.
 B =
 A
Based on these equations and some manipulations, the minimum distance between aircraft in straight line flight
and the time to the minimum distance can be found.
(  , ) = ( x
 xA , yB  yA )
VR = VB  VA
( xA , y A ) is the position of aircraft A and ( xB , y B ) is the position of aircraft B. VR = (VRx ,VRy ) is the relative
velocity of aircraft B with respect to aircraft A.
tms =
d ms =
(  x )2 + (  y )
  xVRx +  yVRy
) 0
(  x +VRx  tms )2 + (  y +VRy  tms )
The aircraft are in conflict if for some time 0  t  C , the predicted
is less than the minimum separation (5
nmi). The time  is the look-ahead time. In some studies like Ref. 3 and 8 this time is 5 min. These equations are
used for calculating the minimum distance between aircraft during their nominal flight. Based on the results the
algorithm can detect if there is a conflict. So, if
tms   c 
  Aircraft A and B are in conflict .
d ms < 5
American Institute of Aeronautics and Astronautics
Downloaded by UNIVERSITY OF ADELAIDE on October 28, 2017 | | DOI: 10.2514/6.2011-6659
III. Timing Schedule of a Conflict
The Modeling of the communication and data exchange process between aircraft in the conflict region is an
important task in ATM. In this paper, a simple model is presented. Although it begins to consider the details of
conflict, there are many important issues unresolved that will be the subject of the future research.
We first provide definitions used to formulate the problem. Figure 1 shows a timing scheme for the logic we are
developing, a scheme that is implemented for each aircraft when in conflict with any other aircraft. The timing
scheme shown starts at
, the time the conflict is detected, and ends at time
, the time the
conflict is completely resolved. We now describe the timing logic steps. We also consider any other secondary
conflict that might occur at any point during this time interval. It is assumed conflicts are detected within a 50-mile
range and they are detected to occur within 3-5
Here is an explanation of the notation for
Figure 1:
: Time the conflict is detected
: Time of conflict occurrence, unless
: Time the resolution maneuver is started.
Maneuver will be a straight or a turning path as
determined by the resolution logic.
( 3min   c  5min) .
: Turn resolution time
 = tC  (tS +  t )
1.5  tC  tS  3.5min : The maneuver cannot
start before 3.5 min to the time of conflict
Figure 1. Timing of the logic with total resolution time occurrence.
equal to 4.5 min
The requirement of air-to-air conflict
resolution is to guarantee that every aircraft has
all the required information about the traffic in its neighborhood. If several aircraft are equipped with CD&R5
systems, aircraft coordination will be a major safety issue. The word coordination is often used in CD&R literature
to convey different concepts. In this context, coordination means exchange of intent and state information. Usually it
is assumed that this goal can be achieved through a reception of the broadcast of other aircraft, like ADS-B. For
each aircraft, the following relevant information is included in ADS-B message: aircraft identifier, position, velocity
and reporting time. As stated in Ref. 6, this type of communication might be affected by some limitations, like
interference problems and therefore may not be perfect. However, we do not address imperfect communication in
this work.
To see what happens during the solve time, lets focus on this time interval more carefully in Figure 2. The solvetime interval has two sub-intervals: first, data receiving, and second, computation time. Aircraft use datalink
capabilities to access and exchange information, including information on positions, velocities, and intent of other
aircraft in the vicinity. Since conflict detection is assumed to be asynchronous, the first step of the algorithm is to
synchronize all the aircraft involved in the conflict. Assume there is a conflict between aircraft i and j. The notation
in Figure 1 is modified to denote this specific conflict. In particular, the i-j conflict detection time
that aircraft i
observes is denoted
Conflict Detection and Resolution
American Institute of Aeronautics and Astronautics
: Receiving time
: Synchronized detection time
i j
j i
tcomp = max tDi j +  rec
, tDji +  rec
i j
j i
rec , rec
) <10sec
As it can be seen in Figure 2, aircraft i and j might
detect their conflict at different times. At time
aircraft i detects the conflict and broadcasts it at time
Downloaded by UNIVERSITY OF ADELAIDE on October 28, 2017 | | DOI: 10.2514/6.2011-6659
At some time later but very close to
, aircraft j detects
the conflict too. We call this time
. It requires some
time for these aircraft to receive the complete information
about the conflict, including the time other aircraft detects
the conflict. Aircraft j receives
. The same
is true for Aircraft i. After
, both aircraft have enough
Figure 2. The details of solve time logic
information on their conflict and the algorithm can start to
solve the conflict synchronously.
Let’s take a more detailed look at some terms used in Figure 1 and Figure 2:
Updating time (
): During this time period, all the potential conflicts that may arise in the future are
detected. The detection is based on the future position of aircraft using the available information on their current
positions. All aircraft continuously receive broadcasted information from other aircraft in a specified area. This area
is a sphere as shown in Figure 3. As can be seen in this figure, the aircraft should be able to see its surrounding area
as far as ~55 nmi. Current ADS-B radio proposals specify maximum ADS-B radio communication range of 80 to
105 nmi (Ref. 10). This checking process should be done for all aircraft either in nominal flight or the maneuvering
phase. At this time, it is determined that aircraft i is involved in any kind of conflict in
is highly dependent on the ADS-B range of the aircraft.
Solve time (1 min): During this time, after
communication and synchronization, the algorithm
solves the conflict and recommends a solution. This
solution should be broadcast to all other neighboring
aircraft. As it is shown in Figure 2, the major part of the
Solve time is Computation time. The algorithm has one
minute to solve the conflict. During computation time,
the logic solves the conflict with a maneuver that starts
at time . We will explore cases where secondary
conflicts are detected during computation time. It is
worthy to note that the running time of the algorithm is
very negligible less than one minute.
Recommendation time: Recom time is a set period
of 30 sec, providing the recommended resolution to the
pilot. It is not reasonable to push the pilot to do a
maneuver without delay, which would increase the
probability of human errors. Based on the research has
Figure 3. Detection area of aircraft i
been done at NASA Ames, pilots tended to have a
response time of roughly 20 seconds, from receiving
the command to initiation of evasive maneuver, but here, we take this time equal to 30 seconds to be compatible
with the time scheduling pattern that is based on 30 second intervals.
American Institute of Aeronautics and Astronautics
Maneuver time: This time includes the time when aircraft is turning to resolve the conflict and the time after the
turn that the aircraft cannot do another maneuver. Maneuver time is a set period of 3 min, and has 2 periods inside:
1. Turning maneuver time
: provided by algorithm, required to be less than 1 min.
2. No-turn maneuver time
: the straight-line segment of the maneuver.
Downloaded by UNIVERSITY OF ADELAIDE on October 28, 2017 | | DOI: 10.2514/6.2011-6659
IV. Logic-Based Conflict Resolution Algorithm
Every conflict situation involves two kinds of aircraft. The first group is called “Conflicting Aircraft”. These
aircraft are the ones that are going to be in conflict in the next 3-5 min. The conflicts of these aircraft are detected.
We can say that the conflicts of these aircraft are primary conflicts.
Other group is called “Background Aircraft”. These aircraft are not involved in the conflict, but they are very
close to the conflicting aircraft. These aircraft are conflict-free, but they might be involved in a secondary conflict.
Ignoring these aircraft might be problematic. By solving a two-aircraft conflict without taking into consideration the
background aircraft, a new conflict with a third aircraft might be generated. For every conflicting aircraft, there may
be background aircraft that restrict the maneuverability of the conflicting aircraft. The background aircraft are the
aircraft within a specific area around the conflicting aircraft. This area is called the Background Area and is shown
in Figure 4.
In Figure 4,we can see a conflicting aircraft flying with velocity V. In this figure,  t is the turn time and R is the
minimum allowable separation. In this figure, Vmax is the maximum speed of aircraft (it will be explained that the
max speed for the simulations is 500 kts). The radius of turn is shown in the figure, depends on the velocity and
bank angle. The turn rate of the aircraft and the turn radius are given by equation equations 11 and 12:
˙ =
Rturn =
gtan 
=V ˙
gtan 
The background aircraft should not change their direction as long as the conflicting aircraft are maneuvering.
Even if the background aircraft detects another conflict during the turn time, it should wait at least 1.5 min to start its
maneuver. During this time, the conflicting aircraft has finished its turn and the background aircraft is free to
implement a turn.
The total number of aircraft in a conflict situation is given in equation 13:
In this equation,
is the number of conflicting aircraft and
is the
number of background aircraft. The algorithm generates a set of maneuvers that
satisfy the minimum separation requirement. This set consists of both single
aircraft maneuvers and cooperative maneuvers. In so-called “cooperative
maneuvers”, all conflicting aircraft simultaneously execute resolution maneuvers.
In this situation, the total number of conflict resolution strategies is
Each conflicting aircraft can turn right, left or continue its straight path.
Obviously it is not possible to resolve the conflict if all aircraft continue their
original flight. That accounts for the -1 in the equation. The background aircraft
are not supposed to participate in any conflict resolution maneuver. The
background aircraft can eliminate some part of the acceptable strategies or even
all of them. Figure 5 shows a conflict situation. Aircraft C does not involve in any
conflict, but it should be considered, because if aircraft A turns left and ignores
Figure 4. Background area aircraft C, the secondary conflict might happen. Aircraft C is in the background
of an aircraft
area of aircraft A. Therefore, aircraft A is allowed to implement a left-turn as long
as it does not produce a conflict with aircraft C. In this case, the total number of
American Institute of Aeronautics and Astronautics
Downloaded by UNIVERSITY OF ADELAIDE on October 28, 2017 | | DOI: 10.2514/6.2011-6659
strategies is 8, but background aircraft can
reduce the number of acceptable strategies.
There are 4 separation-diagrams for every
pair of conflicting aircraft (A and B):
 A turns left/right, B flies straight
 B turns left/right, A flies straight
 A turns left/right, B turns right
 A turns left/right, B turns left
The separation-diagrams are not unique and
every conflict has a different looking diagram.
These diagrams are used for conflict analysis.
They show the separation between aircraft for
different bank angles. By entering these graphs
at a chosen value of turn angle, turn direction,
and at one of the discrete values of bank angle,
one can read off the graph both the separation
during the turn and the minimum separation in
Figure 5. Conflict situation consists of 2 conflicting aircraft the straight-line segment of the maneuver. A
(aircraft A and aircraft B) and a background aircraft complete explanation of these diagrams and the
(aircraft C)
pair-wise conflict resolution algorithm is given
in Ref. 11.
Figure 6 shows the 15 deg bank angle
case corresponding to the first option (A
turns left/right, B flies straight). We
assume that aircraft B does not turn and
flies straight. The curve of separation at
the end of turn has two minimum points
(shown by small diamonds in Figure 6).
If the heading change angle is less than
these minimums (positive or negative),
the minimum separation will occur after
the turn. Otherwise the minimum
separation will be at the end of turn. That
means the aircraft are getting farther
apart from each other after the end of the
turn. The initial separation of two aircraft
is 17 nmi (shown by × in the figure) and
if they don’t implement any conflict
resolution maneuver, the separation will
decrease to 2 nmi (shown by + in the
figure). Regarding this diagram, aircraft
A can turn 30 deg to the right to resolve
Figure 6. Minimum separations between aircraft A and aircraft B the conflict. A 90 deg turn to left will
before and after the turn versus aircraft A turning angle (left or also resolve the conflict, but the
right). Since aircraft C restricts the maneuverability of aircraft A, then
secondary conflict with aircraft C is
aircraft A cannot turn 80-120 deg. to left.
inevitable. If aircraft A turns 80-120 deg
to the left, it will be in conflict with
aircraft C. This restricted area is
specified in Figure 6. The angle exclusion range is determined by separation diagram for aircraft A vs. aircraft C. It
should be clarified that the separation diagram for aircraft A and C includes one part, that is “Aircraft A turns
left/right, Aircraft C flies straight”.
In this approach, each aircraft computes a list of resolution advisories based on its state and the state information
of the aircraft flying in its neighborhood. In this work, we prefer to resolve the conflicts by having a minimum
number of aircraft maneuvering. If N m is the number of maneuvering aircraft, then the range for N m is
American Institute of Aeronautics and Astronautics
Downloaded by UNIVERSITY OF ADELAIDE on October 28, 2017 | | DOI: 10.2514/6.2011-6659
1  N m  N c . If the conflict does not resolve when N m = N c , this conflict cannot be solved by this method. To sum
up, the algorithm has 3 subsets:
Conflict Type Detection – In this part, the conflicting aircraft is detected using equations 8-10. The input is the
state information of the aircraft. When this part of the algorithm is done, it will specify the conflicting aircraft,
background aircraft and the conflict type (pair-wise or multiple-aircraft conflict). When the difference between
TFLS6 of two conflicts is less than 30 sec, we will consider these two conflicts as a multiple-aircraft conflict. The
flowchart in Figure 7 shows the step-by-step process of this part of the algorithm.
Strategy Selection – After knowing the details of the conflict, the conflict resolution strategy should be
determined. As it is mentioned before, we desire the minimum number of maneuvering aircraft (minimizing N m ).
Considering that, Strategy Selection section of the algorithm will decide the best strategy that is specified which
aircraft should turn and what is the turn direction for each aircraft. In order to clarify how the algorithm work, the
flowchart in Figure 8, shows the step-by-step process of the 2nd part of the algorithm.
Maneuver Details Calculation – When it is specified the aircraft should implement the resolution maneuver, this
part of the algorithm will calculate the details of maneuver. Because the velocities of aircraft involved in the conflict
can differ, the heading change angle is not the same for all maneuvering aircraft as shown by equation 5. In addition
to heading change angle, the time of maneuver start is
determined here.
Figure 7. Flowchart of the Conflict Type
Detection part of the algorithm
Figure 8. Flowchart of Strategy Selection part of the
algorithm. The loop in this flowchart iterate through the
number of aircraft required to maneuver to resolve the
Time to First Loss of Separation
American Institute of Aeronautics and Astronautics
V. Multiple-Aircraft Conflict Resolution Using Conflict-Tree
Downloaded by UNIVERSITY OF ADELAIDE on October 28, 2017 | | DOI: 10.2514/6.2011-6659
The process of finding a resolution maneuver for multiple-aircraft conflict is still based on pair-wise conflict
resolution with some extensions. In order to understand this procedure, let’s look at the procedure of resolving threeaircraft conflict using pair-wise algorithm. Let aircraft A, B and C be simultaneously in conflict with each other
within a small interval of time, such as 30 seconds. The conflict-tree corresponding to the 3 conflicting aircraft is
shown in Figure 9.
In this example, NC = 3. The conflict tree has NC stages (in our
example, 3 stages). The number of vertices in kth stage is equal to
 NC  k
NC !2 k
, which is the number of k-aircraft
 k 
k!( NC  k )!
 
maneuvers ( N m = k ). For our case, the number of 2-aircraft maneuvers
is 12. The number of all possible scenarios for NC conflicting aircraft is
given by equation (14).
NC !2 k
= 3NC 1
k =1
In order to read the tree, for every vertex, follow the path from that
vertex to the root. Every aircraft, which you meet along the path, is a
maneuvering aircraft, and all the aircraft that you did not meet are the
aircraft that will not cooperate in resolution maneuver. As can be seen in
Figure 9, aircraft A is just seen in the 1st stage, aircraft B in the 1st and
2nd stages and etc. the number of A’s children is always 2*2=4, B’s
children is 2*1=1 and C-vertices do not have any children. The property
of this tree is that there is not any path in the tree that contains vertices
with the same color. The other property of the conflict-tree is that there
is no duplicate scenario.
To add another aircraft (say aircraft D) to this tree, it is enough to
Figure 9. Conflict-Tree for 3 add two vertices of D(L) and D(R) in the 1st stage and add two children
conflicting aircraft
(D(L) and D(R)) to all the vertices of the tree we had before. On the
other hand, the number of possible scenarios for NC +1 conflicting
aircraft is equal to the summation of the number of all scenarios for NC aircraft plus double the number of vertices
NC +1
for NC aircraft plus 2. As can be seen in equation (15), the number of all possible scenarios will be 3
which is the relation we had for NC +1 aircraft.
1 + 2  3NC 1 + 2 = 3 3NC 1 + 2 = 3NC +1 1
1 ,
As was explained above, the conflict-tree can be built for any number of aircraft. Now let’s look at the process of
finding a solution by the algorithm using the conflict-tree.
We first use the pair-wise algorithm to compute all single aircraft resolutions, starting with any pair, say A vs. B.
The pair-wise algorithm generates up to 4 maneuvers, left and right turns for A and left and right turns for B. In
general, fewer than 4 maneuvers will yield eligible maneuvers. We check the eligible maneuvers for secondary
conflicts, considering aircraft C as a background aircraft. Aircraft C flies straight in this step and it will be
maneuvered in the next step. The best maneuver is retained. Next we apply the pair-wise algorithm to C vs. B. In
this step, the pair-wise algorithm generates up to 2 maneuvers, left and right turns for C. This time only C is eligible
to be maneuvered and Aircraft A is a Background Aircraft. On the other hand, we check the successful maneuvers of
C (up to 2) for secondary conflicts, treating A as a secondary aircraft. If this process yields a solution, the solutions
compares together and the minimum time one is selected and so the problem is considered solved.
American Institute of Aeronautics and Astronautics
Downloaded by UNIVERSITY OF ADELAIDE on October 28, 2017 | | DOI: 10.2514/6.2011-6659
If the attempted single aircraft resolutions have failed, the algorithm sets an acceptable range of heading angle
for the aircraft in stage one and goes to the next stage. An acceptable range of heading angles for every vertex in the
1st stage is [ ,0], if it is x(L) and [0, ] if the vertex is x(R). We proceed with computing 2-aircraft cooperative
resolutions for the three possible pairs: (A,B), (A,C) and (B,C). Each pair can yield up to 4 eligible resolutions
(left/left, left/right, right/left and right/right). Assume we start with pair (A,B). We check the eligible resolutions for
secondary conflicts, where C is treated as a non-maneuvering background aircraft. In addition, we also determine the
range of turn angles within which we obtain successful resolutions. If no secondary conflicts are found for at least
one of the eligible maneuvers, we are done. If not, we will try 3-aircraft maneuvering. Before going to 3rd stage, the
allowed range should be calculated. To specify the acceptable range for vertex “x”, the algorithm eliminates the
angles that violate the allowable distance between x and its parent from its current acceptable range.
The 3-aircraft maneuvering is the same as 2-aircraft cooperative resolution, but this time we let the third aircraft
turn left or right. Assume we start with pair (A,B). First we assume aircraft C turns right. Now we look at either
(C,A) or (C,B) pair, say (C,A) and turn C to an angle within the allowed range of A as computed above. The
algorithm checks if there is any resolution in this acceptable range that satisfies the separation between aircraft A
and C and B and C. The same process should be done for aircraft C turning left. Therefore, the algorithm generates 8
maneuvers. If no solution is found that avoids loss of separation, we are left with repeating the above process using
the Max-Min criterion.
There are some scenarios in conflict-tree that it is not possible to resolve the conflict. For example, look at the
two types of 3-aircraft conflicts in Figure 10. In this figure, two conflict types and their corresponding conflict-graph
are shown. The aircraft are shown with a vertex in this graph. Every two conflicting aircraft are connected with an
edge. This graph is an undirected connected graph. This graph will be used for checking the possibility of a
maneuver. It is enough to remove the vertices corresponding to the maneuvering aircraft and all the edges, which are
connected to these vertices. If any edge remains after this elimination, the scenario is not acceptable. On the other
hand, this resolution scenario will not resolve the conflict. For instance, for type a, there is not any possible singleaircraft maneuver to resolve the conflict and at least two maneuvering aircraft is needed to resolve the conflict. So,
the algorithm ignores the 1st stage and goes directly to the 2nd stage. In this case, the number of all possible scenarios
reduces from 26 to 20. From the conflict-graph of type b, it can be shown that aircraft B or C cannot resolve the
conflict alone, but aircraft A maneuvering is possible to
resolve the conflict.
In Figure 11, another examples of conflict-graph for 4aircraft conflict can be seen. In this example, there is not
any single-aircraft maneuver. Evan after elimination of
vertex B, that is the highest degree one in the graph, and all
edges connected to it, the conflict would not be resolved
and there is still a conflict between aircraft A and C. So,
there is not any single-aircraft maneuver. All pairs of
(A,C), (A,D) and (C,D) are also impossible pairs for 2aircrfat maneuvers. In this case, 12 maneuvers are
eliminated from conflict-tree.
Figure 10. Two types of 3-aircraft conflict
Figure 11. Conflict-graph for a 4-aircraft conflict
VI. Analysis of Simulation Results
There is an impractical assumption commonly used in the literature on conflict resolution. For instance in Ref.
12, It is assumed that a group of aircraft flying in a certain region of airspace has been isolated, so that only conflicts
among aircraft in this group need to be considered during the time interval of interest. In order to avoid this
assumption and cover all cases that might happen in reality, a large number of Monte Carlo simulations have been
American Institute of Aeronautics and Astronautics
Downloaded by UNIVERSITY OF ADELAIDE on October 28, 2017 | | DOI: 10.2514/6.2011-6659
done in this study. Monte Carlo simulations of randomly generated traffic have been run to validate the conflict
resolution algorithm derived in this paper. In this work, a Monte Carlo framework is presented.
The traffic density varies from 5 to 45 aircraft in a rectangular area of 250 nmi by 250 nmi. The minimum
separation between aircraft is considered 5.5 nmi. We set 0.5 nmi more than the standard minimum separation as a
buffer. In Ref. 7, it is determined how much buffer is needed for the minimum separation between aircraft to
compensate for uncertainties in strategic separation functions. The density is held constant during the simulation
time; as an aircraft exits from the area, another aircraft enters the area along the boundary at a random location. The
heading angle of entering aircraft in uniformly distributed The simulation code ensures that there is no initial
conflict between aircraft and all aircraft follow straight trajectories at constant speed at the state of each simulation.
The speed of aircraft is also uniformly distributed in the range of 300-500 kts. A plot of the recorded trajectories is
shown in Figure 12 for a half an hour
simulation with an average of 10 aircraft
within the specified area.
The simulation time is 50 hours for
each simulation. For every traffic density,
the simulation is repeated 10 times, each
starting from a different randomly chosen
initial condition. The reported number of
conflicts for each traffic density is the
average of these ten simulations. These
results of the simulations can be seen in
Table 1. The 1st column of the table is the
traffic density, which is the number of
aircraft flying in the simulation area. The
2nd column is the number of all conflicts in
50 hours simulation. The 3rd to 6th columns
are the number of 2, 3, 4 and 5-aircraft
conflicts. And the last column shows the
number of conflicts that are solved by MaxMin strategy.
Figure 12. Recorded trajectories of 10 aircraft in 35 minutes
Based on the simulation results
for various traffic densities from 5 to
45 aircraft, more than 94 percent of
the conflicts are pair-wise. As the
traffic density increases, the number
conflicts are 4-aircraft conflicts. It is
worthy to say that in multiple aircraft
conflict situations, all aircraft
3429 133.8 7.6
involved in the conflict do not
necessarily maneuver ( N m  N c ).
4182 205.5
For ~70% of the multiple (>2)
aircraft conflicts, just one or two
aircraft maneuver. One example of 3-aircraft conflict is shown in Figure 13. Aircraft A, B and C are in conflict. The
difference between TFLS of (B,C) and TFLS of (B,D) is 40 seconds (>30sec); therefore, aircraft D is not involved in
this conflict. But this aircraft plays the role of the background aircraft for this conflict. This case reveals the
necessity of considering aircraft D as background aircraft; if the conflict between aircraft A, B and C is solved while
ignoring aircraft D, the resolution maneuvers could easily result in a secondary conflict. The 3-aircraft (multipleaircraft) conflict is resolved with cooperation of 2 aircraft. Aircraft A and B turn while aircraft C flies its straight
Table 1. Number of various kinds of conflicts for different number of
traffic densities of aircraft
No. of
American Institute of Aeronautics and Astronautics
Downloaded by UNIVERSITY OF ADELAIDE on October 28, 2017 | | DOI: 10.2514/6.2011-6659
We can say that almost all conflicts are solved in our simulations, but there are some conflicts that cannot be
solved by our method. When all of the scenarios for conflicting aircraft result in loss of separation, we call this
situation an unsolvable conflict. In these cases, even if all aircraft involved in the conflict maneuver, the conflict is
Figure 14. Unsolvable conflicts due to high traffic. The local
Figure 13 An example of 3-aircraft conflict
traffic is 5 aircraft in 25  25 nmi 2 .
To solve the problem of unsolvable situations, we use the “max-min distance” as described in Ref. 11. In
situations where there is no solution that satisfies the minimum allowed distance, this method chooses one from the
set of maneuvers for which the resulting minimum distance between aircraft is more than others. Although the
separation distance is less than the minimum
allowable distance, the method avoids a collision.
Some conflict cases cannot be resolved because
of high local traffic density. On the other hand, there
are too many aircraft close to the conflicting aircraft
(high local density). One of these cases is shown in
Figure 14.The area of the rectangle that is shown in
this figure is 1% of our standard simulation area,
which is 250 250 nmi 2 . In this case, aircraft A,
B and C are in conflict. As it is shown, aircraft D
and E are background aircraft. Aircraft C cannot
turn right due to restriction of aircraft D and aircraft
B cannot turn left because of aircraft E. The first
time to separation loss is 37 sec. Aircraft D has also
detected a conflict with aircraft A, but aircraft D is
not considered as conflicting aircraft, because the
difference between two values of TFLS’s is more
than 30 sec. There is not any solution to satisfy the
minimum separation condition. The max-min Figure 15. The max-min resolution maneuver of the
distance strategy suggests a resolution maneuver. conflict given in Figure 14
Aircraft B should turn 50 deg. to left and aircraft C
should turn 44 deg. to right. The minimum distance
between aircraft is 3.1 nmi. It should be emphasized that this loss of separation does not necessarily occur during the
turn, but it might happen every time during the maneuver time (3 min starting from tS ). To clarify this, the
suggested resolution maneuver is given in Figure 15.In this example, aircraft B and E lose their separation 15 sec
after ending the turn.
American Institute of Aeronautics and Astronautics
Downloaded by UNIVERSITY OF ADELAIDE on October 28, 2017 | | DOI: 10.2514/6.2011-6659
In order to investigate the minimum separation at higher traffic densities, the size of the area is reduced from
250 250nmi 2 to 100 100nmi 2 . The number of aircraft in this area is 16. The density is 0.0016 aircraft nm 2 that
is equivalent to 100 aircraft in our previous area and it is ~9 times of the current air traffic density (Ref. 7). The
current traffic density is defined based on the traffic density levels for high altitude, en-route airspace sectors in the
NAS7. In Figure 16 the minimum distance between aircraft in this high traffic situation is shown. The mean value
for the minimum distance in this density is 4.1 nmi and the standard deviation is 0.6 nmi. The minimum value
among these numbers is 2.5 nmi. This distance is currently acceptable only in landing.
Figure 16. Minimum distances between aircraft of some unsolvable cases in high traffic density.
These results are from max-min distance strategy.
One important criterion for pilots is the number of conflicts per aircraft
per flight hour. In Table 2, the average number of conflicts per flight hour
is given for different traffic densities.
As the traffic density increases, the number of conflicts increases and
the percentage of time each aircraft is involved in a conflict also increases.
The number of conflicts appears to increase as the square of traffic density
(Figure 17). In this figure, the quadratic fitting curve is also shown. In Ref.
14 the number of conflicts is also modeled by binomial random variable
and it is shown that the relation between number of conflicts and traffic
density is a quadratic function. This model also predicts the aircraft
density at which the airspace becomes saturated.
It is expected that the time each aircraft is involved in a conflict
situation increases with the traffic density. This is shown in Figure 18. In
this figure the percentage of time each aircraft is involved in a conflict
Table 2 Average numbers of
conflicts per flight hour in
different traffic densities
# Conflicts
per hour
Figure 17 average number of total conflicts versus traffic density.
National Airspace System
American Institute of Aeronautics and Astronautics
Downloaded by UNIVERSITY OF ADELAIDE on October 28, 2017 | | DOI: 10.2514/6.2011-6659
compared to the total time that aircraft exists in the area is shown.
It seems that if the traffic density increases, we would eventually reach a saturation condition where the aircraft
are almost always in conflict. If we use a linear approximation for data fitting, the aircraft are in conflict
approximately 100% of their time on average when the traffic is approximately 130 aircraft in 250nmi 250nmi
simulation area.
Figure 18 Average times each aircraft involves in conflict.
VII. Conclusion
In this paper, a new approach for automated and distributed separation assurance for en-route flight is developed.
The algorithm works under realistic flight and inter-aircraft communication conditions. This algorithm has extended
and used the pair-wise resolution algorithm in [18]. In addition, detailed design and analysis for handling secondary
conflicts are addressed in the algorithm, while explicitly accommodating some worst-case inter-aircraft
communication delay. The algorithm was tested in Monte Carlo simulations for likelihood of any loss of separation
while varying air traffic density. Extensive simulations show the effectiveness of this algorithm. Our work showed
that, at current air traffic density level, more than 99% of the conflicts can be solved by pair-wise conflict resolution
algorithm, with a small extension to the pair-wise conflict resolution algorithm that is presented in [18]. The
proposed algorithm includes modeling of aircraft dynamics in a turn. The bank angle is fixed and the velocity of
aircraft determines the behavior of aircraft during the turn, i.e. how fast an aircraft can execute the turn. This work
represents a step towards the implementation of an effective conflict resolution algorithm in practical situations.
Ultimately, it is desired our work will lead to an independent system for resolving close-range conflicts with
pilots remaining in the loop, with supervisory control. An improved close-in conflict resolution system should
reduce the likelihood of TCAS alerts, thereby improving the overall robustness of the next-generation system. More
work should be done, for instance a more detailed and accurate model of inter-aircraft communication is needed, to
clarify the effect of communication limitations on performance of the algorithm. In this work, we tried to examine
the heretofore inadequately explored issue of degree of air-to-air coordination required, i.e., how much
communicated information about the traffic is necessary/sufficient, to ensure safety under various en-route conflict
scenarios. We established a logic-based timing schedule to determine when and what information should be
broadcasted. Comparing the results with the results in [18] shows that this new method could dramatically reduce
the rate of detected secondary conflicts in Monte Carlo simulations. For example, at 4-times of the current traffic
density, only 0.02% of the conflicts cannot be solved by this method and will result in loss of separation. To avoid
collision in these rare cases, a max-min distance strategy suggests a resolution maneuver that does not satisfy the
minimum allowable separation maximizes the minimum distance between aircraft.
American Institute of Aeronautics and Astronautics
Downloaded by UNIVERSITY OF ADELAIDE on October 28, 2017 | | DOI: 10.2514/6.2011-6659
“Concept definition for Distributed Air/Ground Traffic Management (DAG-TM)”, version 1.0, Advanced Air
Transportation Technologies (AATT) Project, NASA Ames Research Center, NASA Langley Research Center, 1999.
Alami J. and El Imrani A., "Cultural Algorithms for Air Traffic Conflict Resolution Problem," Proceedings of the 2nd
IEEE/EURASIP – ISCCSP 2006, Marrakech, Morocco, 2006.
André, L., G., César, M. and Mauricio A., R., “Formal Verification of an Optimal Air Traffic Conflict Resolution and
Recovery Algorithm,” WoLLIC 2007, pp. 177-188.
Ballin, M. G., Wing, D. J., Hughes, M. F. and Conway, S. R., “Airborne Separation Assurance and Traffic Management:
Research of Concepts and Technology,” AIAA Paper, pp. 99-3989, August 1999.
Blom, H., A., Obbink, B., K. and Bakker, G., J., “Simulated Collision Risk of an Uncoordinated Airborne Self Separation
Concept of Operation,” 7th EUROCONTROL Innovative Research Workshop & Exhibition, France, December 2008.
Casek, P. and Keinrath, C., “Airborne System for Self Separation in a Trajectory-Based Airspace,” 7th EUROCONTROL
Innovative Research Workshop & Exhibition, France, December 2008.
Consiglio, M., Hoadley, S. and Allen, B., D., "Estimation of Separation Buffers for Wind-Prediction Error in an Airborne
Separation Assistance System," ATM Seminar, Jun 2009.
Dowek, G., Muñoz, C. and Carreño, V., A., “Provably safe coordinated strategy for distributed conflict resolution,”
Proceedings of the AIAA guidance navigation, and control conference and exhibit, AIAA-2005-6047, 2005.
Dowek, G., Munoz, C. and Geser, A., "Tactical conflict detection and resolution in a 3-d airspace," ICASE, NASA Langley
Research Center, Hampton, VA, Technical Report NASaircraftR-2001-210853, 2001.
Eby, M., S. and Kelly III, W., E., “Free Flight Separation Assurance Using Distributed Algorithms,” Proceedings of the
1999 IEEE Aerospace Conference, 1999.
Erzberger, H., Heere, K., “Algorithm and Operational Concept for Resolving Short-Range Conflicts,” Proceedings of the
Institution of Mechanical Engineers, Part G: Journal of Aerospace Engineering, Vol. 224, No. 2, pp. 225-243, 2010.
Frazzoli, E., Mao, Z., H., Oh, J., H. and Feron, E., “Resolution of conflicts involving many aircraft via semidefinite
programming,” AIAA Journal of Guidance, Control and Dynamics, V24 i1, pp. 79-86.
Hu, J., Prandini, M., and Sastry, S., “Optimal coordinated maneuvers for three-dimensional aircraft conflict resolution,”
AIAA Journal of Guidance, Control, and Dynamics, 25(5), pp. 888—900, 2002.
Johnson, N., H., Canton, R., Battiste, V. and Johnson, W., “Distributed air/ground traffic management en-route free
maneuvering rules of the road: requirements and implementation for a simulation of en-route self-separation,” Proceedings of the
12th International Symposium on Aviation Psychology, Oklahoma City, OK, 2005.
Mundra, A. and Simons, E., “Self-Separation Corridors,” 26th Digital Avionics Systems Conference, Dallas, TX, October
Trapani, A., Erzberger, H. and Dunbar, W. B., “Performance Analysis of a Horizontal Separation Assurance Algorithm for
Short-Range Conflicts,” AIAA Guidance, Navigation and Control Conference, AIAA-2009-5746, Chicago, IL, 2009.
American Institute of Aeronautics and Astronautics
Без категории
Размер файла
3 340 Кб
6659, 2011
Пожаловаться на содержимое документа