InTech uses cookies to offer you the best online experience. By continuing to use our site, you agree to our Privacy Policy.

Engineering » Aerospace Engineering » "Aerospace Technologies Advancements", book edited by Thawar T. Arif, ISBN 978-953-7619-96-1, Published: January 1, 2010 under CC BY-NC-SA 3.0 license. © The Author(s).

Chapter 17

An Aircraft Separation Algorithm with Feedback and Perturbation

By White, Allan L.
DOI: 10.5772/6927

Article top

Overview

Two aircraft on nearly coincident course.
Figure 1. Two aircraft on nearly coincident course.
The minimum points (0,0) and (a,b) for the two aircraft.
Figure 2. The minimum points (0,0) and (a,b) for the two aircraft.
The changes in flight-path angle according to the location of the minimum-distance point.
Figure 3. The changes in flight-path angle according to the location of the minimum-distance point.
Flight paths when the minimum-distance point lies in the first sector.
Figure 4. Flight paths when the minimum-distance point lies in the first sector.
The separation maneuver when the minimum-distance point lies in the first sector.
Figure 5. The separation maneuver when the minimum-distance point lies in the first sector.
The separation maneuver when the minimum-distance point lies in the second sector.
Figure 6. The separation maneuver when the minimum-distance point lies in the second sector.
The separation maneuver when the minimum-distance point lies in the third sector.
Figure 7. The separation maneuver when the minimum-distance point lies in the third sector.
The separation maneuver when the minimum-distance point lies in the fourth sector.
Figure 8. The separation maneuver when the minimum-distance point lies in the fourth sector.
Path of maneuvering aircraft moving with feedback. The marks on the axes indicate five-mile intervals.
Figure 9. Path of maneuvering aircraft moving with feedback. The marks on the axes indicate five-mile intervals.
Path of maneuvering aircraft in the presence of perturbations. The marks on the axes are five-mile increments.
Figure 10. Path of maneuvering aircraft in the presence of perturbations. The marks on the axes are five-mile increments.
Subsector inside a sector.
Figure 11. Subsector inside a sector.

An Aircraft Separation Algorithm with Feedback and Perturbation

Allan L. White1

1. Introduction

An open question in air traffic management is whether or not algorithms can be realistically shown to meet Federal Aviation Administration (FAA) safety requirements.

This current work shows such a demonstration is possible for a separation algorithm with perturbations from feedback control and atmospheric turbulence in a local setting. This project can accept a three to four magnitude increase in complexity and still remain viable, but clearly this is not enough of a margin to include every detail in a global analysis. Future work is needed in sensitivity analysis to determine what must be included in the simulation. Section two contains a probability and statistical analysis of a recent FAA requirement, and it is this analysis that most distinguishes this paper from other efforts. Section three presents the assumptions about the aircraft and flight space. Section four shows that the minimum-distance point determines the relative angle of approaching aircraft, and section five gives a pictorial description of the separation maneuver. Section six gives the precise description of the maneuver and a proof that it maintains separation if no perturbations are present.

The aircraft proceed along their flight paths by means of feedback control, and section seven presents the control equations. The algorithm is simple and generic and needs more development. In its current state, it is intended to represent either control-with-pilot-in-the-loop or future-automatic-control. Once feedback control is introduced, it is possible to include perturbations in a realistic manner, and section eight describes its stochastic nature while section nine offers more commentary. The approach to perturbation in this paper is to examine distributions of increasing severity. If the algorithm can survive these distributions, then it can survive the real world perturbations. The severity of the examined perturbations can be seen in figure 10 in section nine.

This paper does not include a test of any decision algorithm since such a test should include the uncertainty due to instrumentation error where the position and heading of the aircraft are not precisely known.

2. Representative FAA requirement

2.1. Probability

The stated FAA goals are changing, but this paper addresses a recently expressed goal which was stated in terms of a moving average: no more than three incidents (of all types) over the last three years. Since there are about ten million flights per year, this translates into one or fewer incidents per 10 million (107) flights. The examination compares this moving average to a goal stated in terms of one year. There are two comments. First, future FAA goals or their interpretation may be different from the ones examined below, but the examination below outlines an approach to analyzing any stated goal. Second, as they stand, these goals are not probability statements, and they require interpretation.

In the absence of information and for simplicity, the typical assumption is that all flights are equivalent and independent, and the typical interpretation of the goal is that the expected number of incidents for 10 million flights be equal to one. Using the expectation does not require any more information from the FAA, but it does have a disadvantage as will be seen below.

The disadvantage of this interpretation appears when we consider the probability of more than one incident during 10 million flights. It’s reasonable to want the probability of more than one incident to be low, but it will be shown that using the expectation-interpretation does not guarantee this. On the other hand, the low-probability approach raises the question of how low the FAA wishes the probability to be.

With the assumption that the flights are equivalent and independent, the distribution is binomial with the probability of an incident equal to 10-7 per flight. The binomial distribution with parameter p gives the probability of zero or one incidents during 10 million flights as

= (1p)10000000+ 10000000 p (1p)9999999= 0.7358 if p=1e7
(1)

The probability of two or more incidents for p = 1e-7 is 1-Q = 0.2642. Hence, if the probability of an incident is equal to 10-7 per flight, then the probability of more than one incident during 10 million flights is greater than 1/4.

If the goal is a less than one in a hundred chance of more than one incident per ten million flights, then a little numerical work gives that for p = 1.5e-8, Q = 0.9898 and 1-Q = 0.0102.

The moving average reduces the likelihood of not achieving the goal provided the probability of an incident during a flight is smaller than required.

Suppose the probability of an incident is equal to 10-7 per flight. Then

Prob{more than one incident in a year | p=1e-7} = 0.26.

Prob{more than three incidents in three years | p=1e-7} = 0.35.

Whereas

Prob{more than one incident in a year | p=1e-8} = 0.0047.

Prob{more than three incidents in three years | p=1e-8} = 0.0003.

The crossover point appears to be p=7e-8.

Prob{more than one incident in a year | p=7e-8} = 0.16.

Prob{more than three incidents in three years | p=7e-8} = 0.16.

Returning to the interpretation of the FAA goal as a probability statement, one possibility is that the FAA would desire there is only 1 in N chance the goal not be met. A reasonable choice for N is some number between 10 and 100. Looking at the extremes, the computations below give values for p = probability of an incident during a flight if the requirement is a 1 in N chance the goal not be met.

For N=10:

The Prob{more than one incident in a year } = 0.10 requires p = 5.3e-8.

The Prob{more than three incidents in three years} = 0.10 requires p = 5.8e-8.

For N=100:

The Prob{more than one incident in a year} = 0.01 requires p = 1.5e-8.

The Prob{more than three incidents in three years} = 0.01 requires p = 2.7e-8.

2.2. Probabilities and confidence levels for the simulation

A problem in establishing that a loss-of-separation-algorithm meets the FAA goal is that loss-of-separation is one incident among many. Hence, showing that the probability of loss-of-separation during a flight is less than 1e-7 may not be sufficient since there are other incidents and their probabilities accumulate.

The problem is compounded since when studying incidents, especially the prevention of incidents, it is useful to distinguish between the potential for an incident and the incident itself. For instance, two aircraft on a collision course is a potential for an incident, but successful maneuvering will result in no incident. In addition, there may be multiple causes for an incident or an incident may require multiple causes. There may be no cause for alarm if two aircraft are on a collision course unless some malfunction prevents successful maneuvering.

Hence, a precise probability analysis for loss-of-separation requires an encyclopedic knowledge of incidents and their causes which the author, at least, does not currently posses. Nevertheless, an elementary, incomplete analysis can offer some guidance. One approach in such an analysis is to be conservative: in the absence of complete information, use probabilities that overestimate the likelihood of dire events.

We begin with a simplified scenario and then generalize it. Suppose there are K types of incidents. Let C i be the set of causes for incident i. Let B (for benign) be the set no causes for an incident. The initial simplifying assumption is that the C i and B partition the set of flight conditions. That is, the intersection of two different sets is empty, and their union is the entire set. This initial simplifying assumption is justified if incidents are rare and flights with more than one incident are rare enough to be ignored.

With this approach, the study of an incident i consists of the study of the effect of the set Ci. For instance, for this study of loss-of-separation, the causes are deviations from the flight paths due to feedback control and external perturbations. The realism of the simulation is increased by adding more causes.

Let P(A i| C i) be the conditional probability of an incident given that its causes appear. Then we want

P(A1| C1) P(C1) + P(A2| C2) P(C2) + + P(AK| CK) P(CK)  p
(2)

Based on the assumption that there is a positive probability that a flight is routine (no cause for an incident appears), we have

P(C1) + + P(CK)  1
(3)

Using this assumption, one way to accomplish this is to have P(A i | C i ) ≤ p for all i since this gives

P(A1| C1) P(C1) + P(A2| C2) P(C2) + + P(AK| CK) P(CK) p P(C1) + p P(C2) + + p P(CK)  p [ P(C1) + + P(CK) ]  p
(4)

The generalization of the above eliminates the partition requirement. That is, different C i can have a non-empty intersection, allowing for more than one incident per flight. The reasoning above still holds if P(C 1 ) + …+ P(C K ) ≤ 1, which this paper will assume.

There are two cases where the approach above requires modification. First, if the sets C i have significant overlap, then the probabilities can sum to greater than 1. If a bound for the sum of probabilities is known and it is less than M, then it is sufficient to demonstrate P(A i | C i ) ≤ q where q M ≤ 1, although if there is significant overlap, then the studies will have to examine the probability that a single set of causes produces several incidents.

Second, a scenario that would require a different type of analysis is if a set of causes had a high probability of producing an incident. That is, for some j, P(A j| C j) cannot be made small. In this case, the alternative is to arrange things so that C j is small.

2.3. Confidence levels for the simulation

The driver for Monte Carlo is the required confidence level which is a quantitative statement about the quality of the experiment. The frequency interpretation is that a confidence level of 100( 1 - h )% means there is a 100h % or less chance that the experiment has misled us. This paper takes the point of view that the quality of the experiment should match the quality of the desired results. That is, if the probability to be established is p, then the confidence level should be at least 100( 1 - p )%. Hence, this paper will seek confidence levels of at least 100( 1 – 1e-7 )%. The confidence level may need to be even higher because loss-of-separation is only one incident among many. The final confidence level must combine the confidence level of a number of experiments. A result in combining confidence levels is the following.

Theorem: Suppose (a j, b j ) is a 100( 1 - h j )% confidence interval for θ j for 1 ≤ j ≤ n, then [ (a 1, b 1 ), … (a n, b n ) ] is a 100( 1 - h 1 - … - h n )% confidence interval for (θ 1, …, θ n ).

For example, if there are 10 parameters to be estimated with a desired overall confidence level of 100( 1 – 1e-7 )%, then it is sufficient to estimate each of the parameters at the 100( 1 – 1e-8 )% level. In general, the individual confidence intervals do not need to be the same although the lack of confidence must have a sum less than or equal to 1e-7. Assuming all the trials are successful and given a desired probability p and confidence level h, the formula for computing the number of trials is

The reasoning is that ( 1-p ) is the probability of success (equivalently the non-occurrence of a failure) and repeated successes (n of them) implies that p is small. The probabilities (values of p) that appear in table 1 are those computed in section 2.1.

2.4. Baseline for simulation effort

Since the primary concern of this paper (and future efforts) is introducing realism while maintaining enough efficiency to establish the algorithms at the required probability and confidence levels, it is worthwhile to state what this study says about such efforts.

The case chosen is that the requirement is the probability of more than 3 incidents in 3 years is 0.10 and there are 100 types of incidents. This requires 370,000,000 trials. Using a desktop

RequirementValue of p per flightTypes of incidents is 100 Confidence level is 1 - p ×~ (1e-2) Number of trialsTypes of incidents is 1000 Confidence level is 1- p ×~ (1e-3) Number of trials
Expected number of incidents per year is 11.0e-72.1e+82.3e+8
Probability more than 1 incident a year is 0.105.3e-84.0e+84.5e+8
Probability more than 1 incident a year is 0.011.5e-81.5e+91.7e+9
Probability more than 3 incidents in 3 years is 0.105.8e-83.7e+84.1e+8
Probability more than 3 incidents in 3 years is 0.012.7e-88.2e+89.0e+8

Table 1.

Number of trials given requirement and number of types of incidents.

computer, it took 25 hours to run this many trials. Assuming that it is feasible to run the program for half a year, that it is feasible to use 10 to 100 desktop computers, and that more efficient programs and faster computers are available, this implies it would be possible to run a simulation that is three or four orders of magnitude more complex.

3. Assumptions

As an early effort (for the author), there are a number of assumptions. (1) Only two aircraft at a time are considered. (2) All aircraft have the same speed and maintain this speed. (3) All scenarios are two-dimensional: all maneuvering is at a constant altitude. (4) The position and heading of all aircraft is precisely known. (5) Both aircraft know which one will make the collision-avoidance maneuver and what the maneuver will be. (6) Only approaching aircraft are considered for the reason below.

This study restricts itself to approaching aircraft since for aircraft on nearly coincident courses, it is possible that a simple jog will not prevent loss-of-separation as illustrated in figure 1

media/image6.jpg

Figure 1.

Two aircraft on nearly coincident course.

The solution is either trivial: have one aircraft perform a circle for delay, or it is global: have one aircraft change altitude or arrange traffic to avoid such circumstances. Hence, the examination of nearly-coincident flight paths is postponed to a later study.

4. The minimum point and flight angles

For algebraic and geometric convenience, we establish the coordinate system such that the first aircraft travels along the x-axis and the two aircraft are their minimum distance apart when this first aircraft is at the origin. Initially, we let the second aircraft approach the first at any angle although we later restrict the study to aircraft with opposite headings.

The first result is that the minimum-point for the second aircraft determines its flight angle except for the special case where the minimum point is (0,0). Let the minimum point for the second aircraft be (a,b).

The graph is

media/image7.jpg

Figure 2.

The minimum points (0,0) and (a,b) for the two aircraft.

The parametric equations for the original paths for the first and second aircraft are

x1=ty1=0x2=+ tcosαy2=+ tsinα
(6)

The distance-squared and its first and second derivative are

s2=[+ tcosα-t]2+[+ tsinα]2d(s2)dt=2[+ tcosα-t][cos-1]+2[+ tsinα][sinα]d2(s2)dt2=2[cosα-1]2+2[sinα]2
(7)

Since the second derivative is positive, the zero-value of the first derivative gives a minimum. Skipping some algebraic steps, setting the first derivative equal to zero gives

0=a[cosα-1]+bsinα
(8)

Placing sine and cosine on opposite sides of the equation, squaring, substituting, and solving the quadratic gives

cosα=a2-b2a2+b2,1
(9)

The value 1 corresponds to the two aircraft flying in parallel a constant distance apart. That case will not be considered in this study.

Hence, except for the point (0,0), the minimum-distance point determines the flight path of the second aircraft with

cosα=a2-b2a2+b2sinα=2aba2+b2
(10)

Since we are considering approaching aircraft, the cosine for the flight path of the second aircraft is negative. Hence, for the minimum-point (a,b), b > a.

5. Description of modified flight paths

The trigonometric result in the last section makes it natural to divide the region containing the minimum=distance points into four sectors where the angles range from π/4 to π/2, from π/2 to 3π/4, from 5π/4 to 3π/2, and from 3π/2 to 7π/4.

The sine of the trajectory is positive in the first sector, negative in the second, positive in the third, and negative in the fourth. This change is illustrated in figure 3.

media/image13.jpg

Figure 3.

The changes in flight-path angle according to the location of the minimum-distance point.

The basic algorithm is that the second aircraft to reach the point of path-intersection turns into the path of the other aircraft. This algorithm does not cover parallel paths when the minimum-point lies on the y-axis, but for this study, this event has probability zero and is temporarily ignored since more robust algorithms must handle uncertainty due to instrumentation error.

As an example, consider two aircraft whose initial minimum distance point is in the first sector which is displayed in figure 4.

media/image14.jpg

Figure 4.

Flight paths when the minimum-distance point lies in the first sector.

The burden of maneuver falls on the aircraft moving along the x-axis. This is illustrated in figure 5.

media/image15.jpg

Figure 5.

The separation maneuver when the minimum-distance point lies in the first sector.

The maneuvers for sectors 2, 3, and 4 are given in figures 6, 7, and 8.

Because of the symmetrical nature of the separation maneuvers, it is sufficient to examine the case where the minimum-distance point lies in the first sector and the maneuver is given in figure 5.

media/image16.jpg

Figure 6.

The separation maneuver when the minimum-distance point lies in the second sector.

media/image17.jpg

Figure 7.

The separation maneuver when the minimum-distance point lies in the third sector.

6. Analytical demonstration of separation

We will scale the required minimum distance to 1.

Showing the two paths maintain separation is an exercise in calculus. The idealized paths are either a single straight line or a sequence of straight lines. The demonstration pivots on the path that is a sequence of straight lines. Each segment is examined at its endpoints and zero value of the derivative of the distance when traversing the straight line segment.

First, there are the endpoints and parametric equations for each of the segments.

The first segment goes from (-4,0) to (-2,-2) along the path

media/image18.jpg

Figure 8.

The separation maneuver when the minimum-distance point lies in the fourth sector.

x1(t)=a4cosα +tcosαy1(t)=b4sinα+tsinαx2(t)=4+22ty2(t)=022tfor 0t22
(11)

The second segment goes from (-2,-2) to (+2,-2) along the path

x1(t)=a(422)cosα +tcosαy1(t)=b(422)sinα+tsinαx2(t)=2+ty2(t)=2for 0t4
(12)

The third segment goes from (+2,-2) to (+4,0) along the path

x1(t)=a+22cosα +tcosαy1(t)=b+22sinα+tsinαx2(t)=+2+22ty2(t)=2+22tfor 0t22
(13)

We can first check the distances at the endpoints, which correspond to the corners for the path of the aircraft making the maneuver.

The first endpoint and distance-squared from equations (11) are

(-4,0);(a4cosα,b4sinα)s2=[a4cosα+4]2+[b4sinα]2
(14)

Since cosine is less than or equal to zero, the expression inside the first bracket is greater than or equal to 4, which implies the distance is greater than or equal to 4.

The second endpoint and distance-squared from equations (12) are

(2,-2);(a(422)cosα,b(422)sinα)s2=[a(422)cosα+2]2+[b(422)sinα+2]2
(15)

Since cosine is negative, the term inside the first bracket is greater than or equal to 2, which implies the distance is greater than or equal to 2.

The third endpoint and distance-squared from equations (13) are

(2,-2);(a+22cosα,b+22sinα)fort=0s2=[a+22cosα2]2+[b+22sinα+2]2
(16)

Since sine is positive, the term inside the second bracket is greater than or equal to 2, which implies the distance is greater than or equal to 2.

The fourth endpoint and distance-squared from equations (13) are

(+4,0);(a+42cosα,b+42sinα)s2=[a+42cosα4]2+[b+42sinα]2
(17)

Since cosine is negative, the expression inside the first bracket is less than or equal to a-4, and since a is less than or equal to 1, the expression is less than or equal to -3, which implies the distance is greater than or equal to +3.

Next we consider the distances while traversing the segments between the endpoints.

The distance while traversing the first segment in terms of the parametric equations (11) is

s2=[a4cosα +tcosα+422t]2+[b4sinα+tsinα+22t]2for 0t22
(18)

Now, ( -4 + t ) cosα is greater than or equal to zero, and 422t is greater than or equal to 2. Hence, the distance is greater than or equal to 2.

The distance while traversing the second segment in terms of the parametric equations (12) is

s2=[a(422)cosα +tcosα+2tt]2+[b(422)sinα+tsinα+2]2
(19)

The derivative is

d(s2)dt=2[a(422)cosα +tcosα+2tt][cosα1]+2[b(422)sinα+tsinα+2][sinα]
(20)

The second derivative is

d2(s2)dt2=2[cosα1]2+2[sinα]2
(21)

which is positive. Hence the zero value for the first derivative gives a minimum.

Setting the derivative equal to zero and solving for t gives

t=3-2+sinα-1+cosα
(22)

Substituting this value for t into the original distance formula and some algebra give

s2=[a+(1+2)cosα -1+2+sinα]2+[b+(1+2)sinα-cosα+1]2
(23)

Since all the terms in the expression in the second bracket are positive, the distance is greater than or equal to 1.

The distance while traversing the second segment in terms of the parametric equations (13) is

s2=[a+22cosα +tcosα222t]2+[b+22sinα+tsinα+222t]2for 0t22
(24)

Now, 22cosα +tcosα222t 0222t -2. Since a is less than or equal to 1, the expression inside the first bracket is less than or equal to -1, which implies the distance is greater than or equal to 1.

7. The feedback equations

Both aircraft are guided by onboard digital controllers. Hence, the desired flight path is given by a sequence of points: the positions the aircraft should be at the end of a control cycle.

The feedback control law is a modified PID (Position-Integral-Derivative) that pivots on the velocity vector. If it pivoted on distance, the aircraft would be constantly lurching forward to the next point on its path. Hence, for this controller, the velocity vector plays the role of P, the acceleration plays the role of D, and the error between the actual point of the aircraft and the desired point plays the role of I.

The aircraft is treated as a constant point of mass 1. Hence, the acceleration is proportional to the applied force. The distance between points is also normalized to 1. This last normalization is different from the normalization used in the analytic derivations for the idealized paths. This last normalization, of control-distance equal to 1, will be the one used for the rest of this paper and in the computer simulation.

At the time interval k, let

a(k) = current acceleration at time k

v(k) = current velocity at time k

s(k) = current position at time k

v d (k) = desired velocity at time k

s d (k) = desired position at time k

τ = control time interval

The equations for the next time interval are

a(k+1)=αa(k)+β[v(k)-vd(k)]+δ[s(k)-sd(k)]v(k+1)=v(k)+τa(k)=v(k)+τ{αa(k)+β[v(k)-vd(k)]+δ[s(k)-sd(k)]}s(k+1)=s(k)+τv(k)+τ22a(k)=s(k)+τv(k)+τ22{αa(k)+β[v(k)-vd(k)]+δ[s(k)-sd(k)]}
(25)

The acceleration is constant throughout the interval [k, k+1] while v(k+1) and s(k+1) are the values at the end of the interval.

For the second equation, subtract v d (k) from both sides and use v d (k) = v d (k+1). For the third equation, write

s(k)+τv(k)=sd(k)+τvd(k)+(s(k)-sd(k))+τ(v(k)vd(k))=sd(k+1)+(s(k)-sd(k))+τ(v(k)vd(k))
(26)

This gives

a(k+1)=αa(k)+β[v(k)-vd(k)]+δ[s(k)-sd(k)]v(k+1)-vd(k+1)=ατa(k)+(1+βτ)[v(k)-vd(k)]+δτ[s(k)-sd(k)]s(k+1)-sd(k+1)=τ22αa(k)+(τ+τ22β)[v(k)-vd(k)]+(1+τ22δ)[s(k)-sd(k)]
(27)

This gives the coefficient matrix

[αβδατ1+βτδτατ22τ+βτ221+δτ22]
(28)

For the time and gain values

τ = 1α=  0.001β=  0.5δ=  0.2
(29)

The eigenvalues are 0, 0.1995+0.2433i, and 0.1995-0.2433i, which are less than one. Hence the system is stable. A more realistic study would include a more detailed model of the aircraft and base the control parameters on the aircraft’s performance.

Continuing to choose numbers convenient for scaling, this study assumes an aircraft speed of 600 knots and a control-time interval of one second, which implies the five nautical mile separation requirement translates into a distance of 30 units in the simulation.

The control law above can take the aircraft through the required turn of π/4 radians. As expected, there is a small overshoot at the corners. The effect of the overshoot is displayed and examined in section nine.

8. The turbulence model

This section describes the external turbulence applied to the aircraft. The assumption is that turbulence is the accumulation of small effects which implies it has a normal distribution. Since the flight path is two-dimensional, the turbulence has an x-component and a y-component. In this study, the x-component and y-component are independent.

For both components, the force is a constant over the control interval of one second. The generality of this assumption will be studied later in this section.

The variants are the variance of the normal distribution, the correlation between the aircraft, and the correlation in time. This paper uses standard deviations of 1/10 and 1 for the normal distribution. For correlation between the aircraft, the two aircraft experience the same turbulence or experience independent turbulence. Time correlation is more complicated.

Time correlation is introduced by having the mean of the distribution for step k+1 depend on the values chosen for step k. If x k is the value for the turbulence in step k, then the value for the turbulence in step k+1 is chosen from a normal distribution with mean c x k for some positive constant c. All the distributions have the same variance σ 2.

Suppose x k is the value for step k, and suppose the z i ‘s are from a normal distribution with mean zero and variance σ 2. Then x k+1 is given by

xk+1=cxk+zk+1=c(cxk-1+zk)+zk+1=ckz1+ck-1z2++czk+zk+1
(30)

Using the standard results for the means and variances of independent variables, the means and variances for this stochastic process are

mean(xk)=mean(ck-1z1+ck-2z2++zk)=0var(xk)=var(ck-1z1+ck-2z2++zk)=c2k-2σ2+c2k-4σ2++c2σ2+σ2=(1c2k1c2)σ2if c 1=kσ2if c =1
(31)

Using the result on expectation that E[ z i z j] = 0 if the z’s are independent variables with zero means, the covariance of the process is

E[(xn+k0)(xn0)]=E[(cn+k-1z1++ckzn+ck-1zn+1+zn+k)×(cn-1z1++zn)]=E[c2n+k-2z12++ckzn2]=[ckj=1nc2n-2j]σ2=ck1c2n1c2σ2if c1=nσ2if c=1
(32)

It can be seen that if c < 1, then the covariance goes to zero as k, the distance between the two points, becomes large. Also, as n becomes large, the process approaches a stationary process: the covariance depends only on the distance between the variables.

We next look at the effect of the turbulence (the stochastic process) on the control states of acceleration, velocity, and distance. There is a slight shift in notation since we follow the control theory convention of indexing the initial parameters with zero. Let y be the state vector and x the stochastic input.

y(1)=Ay(0)+Bx(0)y(2)=Ay(1)+Bx(1)=A2y(0)+ABx(0)+Bx(1)y(n)=Any(0)+k=0n-1An-1-kBx(k)
(33)

Since the system is stable, the first term converges to the desired acceleration, velocity, and position(s). Since the x(k)’s are normal with mean zero, the error from turbulence (the stochastic process) is normal with mean zero. No attempt has been made to derive the variance of the error although it could be obtained empirically from simulation. Section nine estimates the mean and variance for one set of turbulence parameters.

The final topic in this section asks if the turbulence model technique of applying a constant force for a discrete interval is completely general. Can some type of average duplicate the effect of any function of force over that interval? The answer is no. Consider a point of mass 1, a time interval of 1, and the force function

f(t)={2for 0t1/20for 1/2t1
(34)

At time t=1, the velocity and position are

v=f(t)[12]=1s=f(t)2[12]2+(1)(1/2)=3/4
(35)

To duplicate the result, a constant force α over the interval must satisfy the equations

v=1=α(1)=αs=3/4=α2[1]2=α/2
(36)

which is not possible.

9. Miscellany on perturbations

The graph in figure 9 shows the aircraft making the separation-maneuver moving under feedback control with no perturbation present. Note the overshoot at the corners.

The mean and standard deviation of the error for distance were estimated. The path in figure 9 lasts 320 seconds which is 320 discrete control intervals. At the end of each control interval the difference between actual position and desired position was computed. This computation was performed for 3000 flight paths or 960,000 points. The results are mean = 3.7298e-4 and std = 0.1531.

The graph in figure 10 shows the aircraft making the separation-maneuver moving under feedback control with perturbation present. This perturbation is one of the more extreme ones with the variables initially chosen from the normal with standard deviation 1 and then given time correlation with c = 1/2.

media/image48.jpg

Figure 9.

Path of maneuvering aircraft moving with feedback. The marks on the axes indicate five-mile intervals.

Once again, there were 3000 trials with 320 points per trial. For this case, the error had mean = 0.0068 and std = 4.3898.

media/image49.jpg

Figure 10.

Path of maneuvering aircraft in the presence of perturbations. The marks on the axes are five-mile increments.

There are additional areas for investigation for perturbations. One item not covered in this study is when the perturbation has a drift, a constant non-zero value for its mean.

Another item is whether or not it is possible to establish a high probability envelope for the path of the aircraft in the presence of perturbations. Such an envelope would imply that a separation algorithm that allowed for the envelope could be proved, and the need for studying the separation in the presence of perturbations would be eliminated.

10. Choosing the minimum distance point in a sector

Randomly choosing the minimum-distance point in the sector for a trial brings up two problems. The first problem is what is the actual distribution for air traffic. This is not known to the author. Since the usual response to such lack of information is to use the uniform distribution, the second problem is obtaining a distribution and demonstrating it is uniform.

Suppose the sector is part of a circle of radius 1. Consider an arbitrary subsector as in figure 11.

media/image50.jpg

Figure 11.

Subsector inside a sector.

Suppose the subsector lies between angles β1 and β2 and radii r1 and r 2. The area of the subsector divided by the area of the one-eighth circle is

A=(πr22πr12)(β2β12π)π8=4π(β1β2)(r22r12)
(37)

We have a uniform distribution in the sector if the probability of a point being in the subsector equals its proportional area.

To this end, choose n1 and n2 independently from a uniform distribution, and form the point with angle π4+π4n1 and radius n2 . Then

Prob{β1π4+π4n1β2andr1n2r2}=Prob{β1π4+π4n1β2}×Prob{r1n2r2}=Prob{4πβ11n14πβ21}×Prob{r12n2r22}=4π(β1β2)(r22r12)
(38)

Hence, the probability that the point is in the subsector is equal to the relative area of the subsector which gives a uniform distribution for points in the sector.

11. The simulation cases

Eight Monte Carlo experiments were performed, each with 370,000,000 trials.

The aircraft had identical perturbations or independent perturbations.

The initial random variable was chosen with std = 1/10 or std = 1.

The correlation constant was c = 0 or c = ½.

There was no loss of separation in any of the trials.

For each case, the experiment showed that the probability of more than 3 incidents in three years is less than 0.10 at the 100( 1 - 1e-9 ) confidence level, which is the confidence level appropriate if there are 100 types of incidents.

12. Minimum distance estimation

It’s satisfying that the separation algorithm handled all the perturbation cases, but it gives no insight with respect to the effect of the perturbations. This section attempts to remedy this by estimations of minimum distance. For each set of conditions, one million (1e+6) trials were conducted, and the minimum distance of the two aircraft was recorded for each trial. For each set of conditions, the mean, standard deviations, and 99% confidence interval for the minimum distance were computed.

Since this comparison of conditions is not related to any FAA requirement, the investigation does not require meeting the confidence level of incidents, and the 99% confidence interval is sufficient to compare results.

To make the results more comparable, each experiment used the same set of (1e+6) points in the sector. The points were chosen according to the uniform-criteria in section ten with the angles and radii given by

αk= π/+ k π/4000 for k = 1, , 1000 rk = sqrt ( k/1000 ) for k = 1, , 1000 
(39)

The parameters that were varied were

The perturbations for the two aircraft were either identical (pert2=pert1) or independent (Ind).

The initial random variable was chosen from a normal distribution with mean = 0 and std = 1/10 or std = 1.

The correlation constant was 0 or ½.

The results for the eight cases are given in table 2.

From an examination of the table, the major factor is the standard deviation of the original normal distribution. Once this standard deviation is large, the correlation factor becomes significant.

Conditionsmeanstd99% int
Pert1=pert2 Std = 1/10 C = 067.32791.591067.3238 67.3320
Pert1=pert2 Std = 1 C = 065.94971.733565.9452 65.9542
Std = 1/10 C = 067.19591.620067.1917 67.2001
Std = 1 C = 063.00552.830062.9981 63.0129
Pert1=pert2 Std = 1/10 C = 1/267.29511.594167.2910 67.2992
Pert1=pert2 Std = 1/10 C = 1/265.31061.888065.3057 65.3155
Std = 1/10 C = 1/267.05791.649967.0536 67.0622
Std = 1 C = 1/260.59883.693060.5892 60.6084

Table 2.

Estimated mean, standard deviation, and 99% confidence interval for minimum distance.

13. Conclusions

The primary objective of this paper is to establish that an air traffic algorithm meets the FAA requirements in the presence of perturbations.

There is a discussion of a representative FAA requirement, its probabilistic interpretation, and the number of trials needed in a Monte Carlo simulation. The algorithm chosen is flight separation for approaching aircraft. It is first shown that the minimum-distance point of the aircraft determines their flight angles. With this result in hand, the algorithm is described and an analytical proof of the algorithm is given for idealized flight paths.

Next, two items are introduced for realism. A modified PID control law is proposed and shown to be stable. Once the control law is in place, perturbations can be introduced as external forces. The parameters of the perturbation are the standard deviation, the correlation between aircraft, and the time correlation. The stochastic properties of the perturbation are derived. Monte Carlo simulation shows the separation-algorithm meets a chosen FAA requirement for eight cases of the perturbation. A minimum-distance study shows the different perturbations have different effects. The natural extensions to this effort are to consider more than two aircraft, a more global setting, wind, and instrumentation errors. Wind, for instance, can be included by letting the random variables have a nonzero mean. How much can be established by realistic simulation remains an open problem. The method presented in this paper depends on the ability to execute the algorithm 100,000 times faster than real time. Whether such speeds can be achieved for realistic algorithms is an open question.

There is no lack of publications about separation assurance or, when things get more desperate, collision avoidance. In comparing this effort to other publications, the salient points are (1) examination of the FAA requirements as probability conditions, (2) integrating the combined realism of feedback control and perturbations, and (3) determining and performing the necessary Monte Carlo trials. The paper [Kuchar & Yang 2000] sets up a framework to review 68 conflict detection and resolution methods, but there is no discussion of their verification. The paper [Christodoulou & Kodazakis 2006] examines a three dimensional algorithm for collision avoidance, but there are no perturbations, and only a few test cases. The paper [Sullivan & Malsam 2002] includes human in the loop with the intent of moving from sector to global implications to improve efficiency, but there is no mention of FAA safety requirements. The paper [Sweet et al 2002] identifies possible areas to investigate for improvement of efficiency, but there is no mention of FAA safety requirements. The paper [Farley & Erzbereger 2007] proposed a conflict resolution algorithm and tested it using real data where it appeared to be about 97% successful. The paper [McNally & Gong] develops and tests an operating concept and a laboratory analysis methodology to examine how four-dimensional trajectory analysis methods could support higher levels of automation for separation assurance while recognizing that trajectory prediction uncertainties can be on the same order of magnitude as safe separation criteria, which implies that uncertainty is an important consideration, but there is no reference to the FAA requirements. The paper [Paielli] looks at vertical maneuvers when loss of separation is imminent, and these methods were tested on archived data from 100 actual operational errors. The paper [Alam & Abbass 2008] attempts a global simulation of the Australian airspace to study the feasibility of free flight. It contains numerous realistic elements, but there is no quantitative study of safety with confidence levels. The paper [Pallottino et al 2002] applies integer programming to solve conflict resolution for multiple aircraft, and several examples are presented, but the program is not established at any confidence level.There is a school of thought that believes simulation alone will not establish safety requirements and proof by formal methods is necessary. The papers [Dowek & Munoz] and [Geser & Munoz] are representative.

References

1 - S. Alam, H. Abbass, 2008 ATOMS: Air Traffic Operations and Management Simulator, IEEE Transactions on Intelligent Systems, 9 2 June, 209 225 .
2 - R. Butler, C. Munoz, 2008 NASA Langley’s Formal Methods Research in Support of the Next Generation Air Transport System, http://shemesh.larc.nasa.gov/LFM2008/slides/InvitedTalks/Butler.pdf.
3 - M. Christodoulou, S. Kodazakis, 2006 Automatic Commercial Aircraft-Collision Avoidance in Free Flight: The Three Dimensional Problem, IEEE Transactions on Intelligent Systems, 7 2 June, 242 249 .
4 - G. Dowek, C. Munoz, ConflictDetection.Resolution 12 1,2, …, N Aircraft, 7th AIAAAviation Technology, Integration and Operations Confrence.
5 - T. Farley, H. Erzberger, 2007 Fast-Time Simulation Evaluation of a Conflict Resolution Algorithm Under High Air Traffic Demand, Proceedings of 7th USA/Europe ATM 2007 R&D Seminar, Barcelona, Spain, 2 5 July.
6 - A. Geser, C. Munoz, 2002 A Geometric Approach to Strategic Conflict Detection and Resolution, Proceedings of the 21st Digital Avionics Systems Conference, 2002.
7 - J. Kuchar, Yang, 2000 2000. A review of conflict Detection and resolution Modeling Methods, IEEE Transactions on Intelligent Systems, 1 4 December, 179 189 .
8 - D. Mc Nally, C. Gong, Concept and Laboratory Analysis of Trajectory-Based Automation for Separation Assurance, Air Traffic Control Quarterly, 15 151 35 63 .
9 - L. Pallottino, E. Feron, A. Bicchi, 2002 Conflict Resolution Problems for Air Traffic Management Systems Solved With Mixed Integer Programming, IEEE Transactions on Intelligent Systems, 3 1 March, 3 11
10 - B. Sullivan, S. Malsam, 2002 Development of a Real-Time Virtual Airspace Simulation Capability for Air Traffic Management Research, Proceedings of AIAA Modeling and Simulation Technologies Conference and Exhibit, 5 8 August, Monterey.
11 - D. Sweet, D. Manikonda, V. Aronson, V. Roth, M. Blake, 2002 Fast-Time simulation System for Analysis of Advanced Air Transportation Concepts, Proceedings of AIAA Modeling and Simulation Technologies Conference and Exhibit, 5 8 August, Monterey, California.