An Aircraft Separation Algorithm with Feedback and Perturbation

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 (10⁷) 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

$$\begin{array}{l}\text{Q }={\left(\text{1}-\text{p}\right)}^{\text{1}0000000}+\text{ 1}0000000\text{ p }{\left(\text{1}-\text{p}\right)}^{\text{9999999}}\\ =0.\text{7358} \text{if p}=\text{1e}-\text{7}\end{array}$$ E1

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 C_i. 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

$$\text{P}\left({\text{A}}_{\text{1}}|{\text{ C}}_{\text{1}}\right)\text{ P}\left({\text{C}}_{\text{1}}\right)+\text{ P}\left({\text{A}}_{\text{2}}|{\text{ C}}_{\text{2}}\right)\text{ P}\left({\text{C}}_{\text{2}}\right)+\dots +\text{ P}\left({\text{A}}_{\text{K}}|{\text{ C}}_{\text{K}}\right)\text{ P}\left({\text{C}}_{\text{K}}\right) \le \text{ p}$$ E2

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

$$\text{P}\left({\text{C}}_{\text{1}}\right)+\dots + \text{P}\left({\text{C}}_{\text{K}}\right)\text{ 1}$$ E3

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

$$\begin{array}{l}\text{P}\left({\text{A}}_{\text{1}}|{\text{ C}}_{\text{1}}\right)\text{ P}\left({\text{C}}_{\text{1}}\right)+\text{ P}\left({\text{A}}_{\text{2}}|{\text{ C}}_{\text{2}}\right)\text{ P}\left({\text{C}}_{\text{2}}\right)+\dots +\text{ P}\left({\text{A}}_{\text{K}}|{\text{ C}}_{\text{K}}\right)\text{ P}\left({\text{C}}_{\text{K}}\right)\\ \le \text{ p P}\left({\text{C}}_{\text{1}}\right)+\text{ p P}\left({\text{C}}_{\text{2}}\right)+\dots +\text{ p P}\left({\text{C}}_{\text{K}}\right)\le \text{ p }\left[ \text{P}\left({\text{C}}_{\text{1}}\right)+\dots + \text{P}\left({\text{C}}_{\text{K}}\right)\right] \le \text{ p}\end{array}$$ E4

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 ₁ ) + …+ 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 ₁, b ₁ ), … (a _n, b _n ) ] is a 100( 1 - h ₁ - … - h _n )% confidence interval for (θ ₁, …, θ _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

$${\left(\text{1-p}\right)}^{\text{n}}=\text{h}$$ E5

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

Requirement	Value of p per flight	Types of incidents is 100 Confidence level is 1 - p ×~ (1e-2) Number of trials	Types of incidents is 1000 Confidence level is 1- p ×~ (1e-3) Number of trials
Expected number of incidents per year is 1	1.0e-7	2.1e+8	2.3e+8
Probability more than 1 incident a year is 0.10	5.3e-8	4.0e+8	4.5e+8
Probability more than 1 incident a year is 0.01	1.5e-8	1.5e+9	1.7e+9
Probability more than 3 incidents in 3 years is 0.10	5.8e-8	3.7e+8	4.1e+8
Probability more than 3 incidents in 3 years is 0.01	2.7e-8	8.2e+8	9.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

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

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

$$\begin{array}{l}{\text{x}}_{\text{1}}=\text{t}\\ {\text{y}}_{\text{1}}=0\\ {\text{x}}_{\text{2}}=\text{a }+\text{ t}\text{cos}\alpha \\ {\text{y}}_{\text{2}}=\text{b }+\text{ t}\text{sin}\alpha \end{array}$$ E6

The distance-squared and its first and second derivative are

$$\begin{array}{l}{\text{s}}^{\text{2}}={\left[\text{a }+\text{ t}\text{cos}\alpha \text{-t}\right]}^2+{\left[\text{b }+\text{ t}\text{sin}\alpha \right]}^2\\ \frac{\text{d}\left({\text{s}}^{\text{2}}\right)}{\text{dt}}=2\left[\text{a }+\text{ t}\text{cos}\alpha \text{-t}\right]\left[\text{cos-1}\right]+2\left[\text{b }+\text{ t}\text{sin}\alpha \right]\left[\text{sin}\alpha \right]\\ \frac{{\text{d}}^{\text{2}}\left({\text{s}}^{\text{2}}\right)}{{\text{dt}}^{\text{2}}}=2{\left[\text{cos}\alpha \text{-1}\right]}^2+2{\left[\text{sin}\alpha \right]}^2\end{array}$$ E7

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=\text{a}\left[\text{cos}\alpha \text{-}\text{1}\right]+\text{b}\text{sin}\alpha$$ E8

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

$$\text{cos}\alpha =\frac{{\text{a}}^{\text{2}}{\text{-b}}^{\text{2}}}{{\text{a}}^{\text{2}}+{\text{b}}^{\text{2}}},1$$ E9

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

$$\begin{array}{l}\text{cos}\alpha =\frac{{\text{a}}^{\text{2}}{\text{-b}}^{\text{2}}}{{\text{a}}^{\text{2}}+{\text{b}}^{\text{2}}}\\ \text{sin}\alpha =\frac{\text{2}\text{a}\text{b}}{{\text{a}}^{\text{2}}+{\text{b}}^{\text{2}}}\end{array}$$ E10

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.

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.

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.

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.

Figure 6.

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

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

Figure 8.

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

$$\begin{array}{l}{\text{x}}_{\text{1}}(\text{t})=\text{a}-4\text{cos}\alpha +\text{t}\text{cos}\alpha \\ {\text{y}}_{\text{1}}(\text{t})=\text{b}-4\text{sin}\alpha +\text{t}\text{sin}\alpha \\ {\text{x}}_{\text{2}}(\text{t})=-4+\frac{\sqrt{\text{2}}}{\text{2}}\text{t}\\ {\text{y}}_{\text{2}}(\text{t})=0-\frac{\sqrt{\text{2}}}{\text{2}}\text{t}\\ \text{for 0}\le \text{t}\le \text{2}\sqrt{\text{2}}\end{array}$$ E11

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

$$\begin{array}{l}{\text{x}}_{\text{1}}(\text{t})=\text{a}-(4-2\sqrt{2}\text{)}\text{cos}\alpha +\text{t}\text{cos}\alpha \\ {\text{y}}_{\text{1}}(\text{t})=\text{b}-(4-2\sqrt{2})\text{sin}\alpha +\text{t}\text{sin}\alpha \\ {\text{x}}_{\text{2}}(\text{t})=-2+\text{t}\\ {\text{y}}_{\text{2}}(\text{t})=-2\\ \text{for 0}\le \text{t}\le 4\end{array}$$ E12

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

$$\begin{array}{l}{\text{x}}_{\text{1}}(\text{t})=\text{a}+2\sqrt{2}\text{cos}\alpha +\text{t}\text{cos}\alpha \\ {\text{y}}_{\text{1}}(\text{t})=\text{b}+2\sqrt{2}\text{sin}\alpha +\text{t}\text{sin}\alpha \\ {\text{x}}_{\text{2}}(\text{t})=+2+\frac{\sqrt{\text{2}}}{\text{2}}\text{t}\\ {\text{y}}_{\text{2}}(\text{t})=-2+\frac{\sqrt{\text{2}}}{\text{2}}\text{t}\\ \text{for 0}\le \text{t}\le \text{2}\sqrt{\text{2}}\end{array}$$ E13

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

$$\begin{array}{l}\left(\text{-4,}\text{0}\right);\left(\text{a}-4\text{cos}\alpha ,\text{b}-4\text{sin}\alpha \right)\\ {\text{s}}^{\text{2}}={\left[\text{a}-4\text{cos}\alpha +4\right]}^2+{\left[\text{b}-4\text{sin}\alpha \right]}^2\end{array}$$ E14

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

$$\begin{array}{l}\left(-2\text{,}\text{-2}\right)\text{;}\left(\text{a}-(4-2\sqrt{2}\text{)}\text{cos}\alpha ,\text{b}-(4-2\sqrt{2}\text{)}\text{sin}\alpha \right)\\ {\text{s}}^{\text{2}}={\left[\text{a}-(4-2\sqrt{2}\text{)}\text{cos}\alpha +2\right]}^2+{\left[\text{b}-(4-2\sqrt{2}\text{)}\text{sin}\alpha +2\right]}^2\end{array}$$ E15

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

$$\begin{array}{l}\left(-2\text{,}\text{-2}\right)\text{;}\left(\text{a}+2\sqrt{2}\text{cos}\alpha ,\text{b}+2\sqrt{2}\text{sin}\alpha \right)\text{for}\text{t}=\text{0}\\ {\text{s}}^{\text{2}}={\left[\text{a}+2\sqrt{2}\text{cos}\alpha -2\right]}^2+{\left[\text{b}+2\sqrt{2}\text{sin}\alpha +2\right]}^2\end{array}$$ E16

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

$$\begin{array}{l}\left(+\text{4,}\text{0}\right);\left(\text{a}+4\sqrt{2}\text{cos}\alpha ,\text{b}+4\sqrt{2}\text{sin}\alpha \right)\\ {\text{s}}^{\text{2}}={\left[\text{a}+4\sqrt{2}\text{cos}\alpha -4\right]}^2+{\left[\text{b}+4\sqrt{2}\text{sin}\alpha \right]}^2\end{array}$$ E17

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

$$\begin{array}{l}{\text{s}}^{\text{2}}={\left[\text{a}-4\text{cos}\alpha +\text{t}\text{cos}\alpha +4-\frac{\sqrt{2}}{2}\text{t}\right]}^2\\ +{\left[\text{b}-4\text{sin}\alpha +\text{t}\text{sin}\alpha +\frac{\sqrt{2}}{2}\text{t}\right]}^2\\ \text{for 0}\le \text{t}\le \text{2}\sqrt{\text{2}}\end{array}$$ E18

Now, ( -4 + t ) cosα is greater than or equal to zero, and $$4-\frac{\sqrt{2}}{2}\text{t}$$ 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

$$\begin{array}{l}{\text{s}}^{\text{2}}={\left[\text{a}-(4-2\sqrt{2}\text{)}\text{cos}\alpha +\text{t}\text{cos}\alpha +2t-\text{t}\right]}^2\\ +{\left[\text{b}-(4-2\sqrt{2})\text{sin}\alpha +\text{t}\text{sin}\alpha +2\right]}^2\end{array}$$ E19

The derivative is

$$\begin{array}{l}\frac{\text{d}\left({\text{s}}^{\text{2}}\right)}{\text{dt}}=2\left[\text{a}-(4-2\sqrt{2}\text{)}\text{cos}\alpha +\text{t}\text{cos}\alpha +2t-\text{t}\right]\left[\text{cos}\alpha -\text{1}\right]\\ +2\left[\text{b}-(4-2\sqrt{2})\text{sin}\alpha +\text{t}\text{sin}\alpha +2\right]\left[\text{sin}\alpha \right]\end{array}$$ E20

The second derivative is

$$\frac{{\text{d}}^{\text{2}}\left({\text{s}}^{\text{2}}\right)}{{\text{dt}}^{\text{2}}}=2{\left[\text{cos}\alpha -\text{1}\right]}^2+2{\left[\text{sin}\alpha \right]}^2$$ E21

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

$$\text{t}=\text{3-}\sqrt{\text{2}}+\frac{\text{sin}\alpha }{\text{-1}+\cos \alpha }$$ E22

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

$$\begin{array}{l}{\text{s}}^{\text{2}}={\left[\text{a}+(-1+\sqrt{2}\text{)}\text{cos}\alpha \text{ -1}+\sqrt{\text{2}}+\text{sin}\alpha \right]}^2\\ +{\left[\text{b}+(-1+\sqrt{2})\text{sin}\alpha \text{-}\text{cos}\alpha +1\right]}^2\end{array}$$ E23

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

$$\begin{array}{l}{\text{s}}^{\text{2}}={\left[\text{a}+2\sqrt{2}\text{cos}\alpha +\text{t}\text{cos}\alpha -2-\frac{\sqrt{\text{2}}}{\text{2}}\text{t}\right]}^2\\ +{\left[\text{b}+2\sqrt{2}\text{sin}\alpha +\text{t}\text{sin}\alpha +2-\frac{\sqrt{\text{2}}}{\text{2}}\text{t}\right]}^2\\ \text{for 0}\le \text{t}\le \text{2}\sqrt{\text{2}}\end{array}$$ E24

Now, $$2\sqrt{2}\text{cos}\alpha +\text{t}\text{cos}\alpha -2-\frac{\sqrt{\text{2}}}{\text{2}}\text{t}\le$$ $$0-2-\frac{\sqrt{\text{2}}}{\text{2}}\text{t}\le$$ -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

$$\begin{array}{l}\text{a}\left(\text{k}+\text{1}\right)=\alpha \text{a(k)}+\beta \left[{\text{v(k)-v}}_{\text{d}}(\text{k)}\right]+\delta \left[{\text{s(k)-s}}_{\text{d}}\text{(k)}\right]\\ \\ \text{v(k}+\text{1)}=\text{v(k)}+\tau \text{a(k)}\\ =\text{v(k)}+\tau \left\{\alpha \text{a(k)}+\beta \left[{\text{v(k)-v}}_{\text{d}}(\text{k)}\right]+\delta \left[{\text{s(k)-s}}_{\text{d}}\text{(k)}\right]\right\}\\ \\ \text{s(k}+\text{1)}=\text{s(k)}+\tau \text{v(k)}+\frac{{\tau }^2}{2}\text{a(k)}\\ =\text{s(k)}+\tau \text{v(k)}\\ +\frac{{\tau }^2}{2}\left\{\alpha \text{a(k)}+\beta \left[{\text{v(k)-v}}_{\text{d}}(\text{k)}\right]+\delta \left[{\text{s(k)-s}}_{\text{d}}\text{(k)}\right]\right\}\end{array}$$ E25

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

$$\begin{array}{l}\text{s(k)}+\tau \text{v(k)}={\text{s}}_{\text{d}}\text{(k)}+\tau {\text{v}}_{\text{d}}\text{(k)}+\left(\text{s(k)}\text{-}{\text{s}}_{\text{d}}\text{(k)}\right)+\tau \left(\text{v(k)}-{\text{v}}_{\text{d}}\text{(k)}\right)\\ ={\text{s}}_{\text{d}}\text{(k}+\text{1)}+\left(\text{s(k)}\text{-}{\text{s}}_{\text{d}}\text{(k)}\right)+\tau \left(\text{v(k)}-{\text{v}}_{\text{d}}\text{(k)}\right)\end{array}$$ E26

This gives

$$\begin{array}{l}\text{a}\left(\text{k}+\text{1}\right)=\alpha \text{a(k)}+\beta \left[{\text{v(k)-v}}_{\text{d}}(\text{k)}\right]+\delta \left[{\text{s(k)-s}}_{\text{d}}\text{(k)}\right]\\ \\ \text{v(k}+\text{1)}\text{-}{\text{v}}_{\text{d}}\text{(k}+\text{1)}=\alpha \tau \text{a(k)}+(1+\beta \tau )\left[{\text{v(k)-v}}_{\text{d}}(\text{k)}\right]+\delta \tau \left[{\text{s(k)-s}}_{\text{d}}\text{(k)}\right]\\ \\ \text{s(k}+\text{1)}\text{-}{\text{s}}_{\text{d}}\text{(k}+\text{1)}=\frac{{\tau }^2}{2}\alpha \text{a(k)}+\left(\tau +\frac{{\tau }^2}{2}\beta \right)\left[{\text{v(k)-v}}_{\text{d}}(\text{k)}\right]\\ +\left(1+\frac{{\tau }^2}{2}\delta \right)\left[{\text{s(k)-s}}_{\text{d}}\text{(k)}\right]\end{array}$$ E27

This gives the coefficient matrix

$$\left[\begin{array}{ccc}\alpha & \beta & \delta \\ \alpha \tau & 1+\beta \tau & \delta \tau \\ \alpha \frac{{\tau }^2}{2}& \tau +\beta \frac{{\tau }^2}{2}& 1+\delta \frac{{\tau }^2}{2}\end{array}\right]$$ E28

For the time and gain values

$$\begin{array}{l}\tau =\text{ 1}\\ \alpha =-0.00\text{1}\\ \beta =-0.\text{5}\\ \delta =-0.\text{2}\end{array}$$ E29

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 σ ².

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 σ ². Then x _k+1 is given by

$$\begin{array}{l}{\text{x}}_{\text{k}+\text{1}}=\text{c}{\text{x}}_{\text{k}}+{\text{z}}_{\text{k}+\text{1}}\\ =\text{c}\left(\text{c}{\text{x}}_{\text{k-1}}+{\text{z}}_{\text{k}}\right)+{\text{z}}_{\text{k}+\text{1}}\\ ={\text{c}}^{\text{k}}{\text{z}}_{\text{1}}+{\text{c}}^{\text{k-1}}{\text{z}}_{\text{2}}+\dots +\text{c}{\text{z}}_{\text{k}}+{\text{z}}_{\text{k}+\text{1}}\end{array}$$ E30

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

$$\begin{array}{l}\text{mean}\left({\text{x}}_{\text{k}}\right)=\text{mean}\left({\text{c}}^{\text{k-1}}{\text{z}}_{\text{1}}+{\text{c}}^{\text{k-2}}{\text{z}}_{\text{2}}+\dots +{\text{z}}_{\text{k}}\right)=0\\ \text{var}\left({\text{x}}_{\text{k}}\right)=\text{var}\left({\text{c}}^{\text{k-1}}{\text{z}}_{\text{1}}+{\text{c}}^{\text{k-2}}{\text{z}}_{\text{2}}+\dots +{\text{z}}_{\text{k}}\right)\\ ={\text{c}}^{\text{2}\text{k-2}}{\sigma }^2+{\text{c}}^{\text{2}\text{k-4}}{\sigma }^2+\dots +{\text{c}}^{\text{2}}{\sigma }^2+{\sigma }^2\\ =\left(\frac{1-{\text{c}}^{\text{2}\text{k}}}{1-{\text{c}}^{\text{2}}}\right){\sigma }^2\text{if c }\ne \text{1}\\ =\text{k}{\sigma }^2\text{if c }=\text{1}\end{array}$$ E31

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

$$\begin{array}{l}\text{E}\left[\left({\text{x}}_{\text{n}+\text{k}}-0\right)\left({\text{x}}_{\text{n}}-0\right)\right]\\ =\text{E}[\left({\text{c}}^{\text{n}+\text{k-1}}{\text{z}}_{\text{1}}+\dots +{\text{c}}^{\text{k}}{\text{z}}_{\text{n}}+{\text{c}}^{\text{k-1}}{\text{z}}_{\text{n}+\text{1}}\dots +{\text{z}}_{\text{n}+\text{k}}\right)\\ \times \left({\text{c}}^{\text{n-1}}{\text{z}}_{\text{1}}+\dots +{\text{z}}_{\text{n}}\right)]\\ =\text{E}\left[{\text{c}}^{\text{2}\text{n}+\text{k-2}}{\text{z}}_{\text{1}}^{\text{2}}+\dots +{\text{c}}^{\text{k}}{\text{z}}_{\text{n}}^{\text{2}}\right]\\ =\left[{\text{c}}^{\text{k}}{\displaystyle \sum _{\text{j}=\text{1}}^{\text{n}}{\text{c}}^{\text{2}\text{n-2}\text{j}}}\right]{\sigma }^2\\ ={\text{c}}^{\text{k}}\frac{1-{\text{c}}^{\text{2}\text{n}}}{1-{\text{c}}^{\text{2}}}{\sigma }^2\text{if c}\ne \text{1}\\ =\text{n}{\sigma }^2\text{if c}=\text{1}\end{array}$$ E32

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.

$$\begin{array}{l}\text{y(1)}=\text{A}\text{y(0)}+\text{B}\text{x(0)}\\ \text{y(2)}=\text{A}\text{y(1)}+\text{B}\text{x(1)}\\ ={\text{A}}^{\text{2}}\text{y(0)}+\text{A}\text{B}\text{x(0)}+\text{B}\text{x(1)}\\ ⋮\\ \text{y(n)}={\text{A}}^{\text{n}}\text{y(0)}+{\displaystyle \sum _{\text{k}=\text{0}}^{\text{n-1}}{\text{A}}^{\text{n-1-k}}\text{B}\text{x(k)}}\end{array}$$ E33

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

$$\text{f(t)}=\{\begin{array}{l}\text{2}\text{for 0}\le \text{t}\le \text{1/2}\\ 0\text{for 1/2}\le \text{t}\le \text{1}\end{array}$$ E34

At time t=1, the velocity and position are

$$\begin{array}{l}\text{v}=\text{f(t)}\left[\frac{\text{1}}{\text{2}}\right]=\text{1}\\ \text{s}=\frac{\text{f(t)}}{\text{2}}{\left[\frac{\text{1}}{\text{2}}\right]}^2+\left(1\right)\left(1/2\right)=3/4\end{array}$$ E35

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

$$\begin{array}{l}\text{v}=\text{1}=\alpha \left(\text{1}\right)=\alpha \\ \text{s}=3/4=\frac{\alpha }{2}{\left[1\right]}^2=\alpha /2\end{array}$$ E36

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.

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.

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.

Figure 11.

Subsector inside a sector.

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

$$\begin{array}{l}\text{A}=\frac{\left(\pi {\text{r}}_{\text{2}}^{\text{2}}-\pi {\text{r}}_{\text{1}}^{\text{2}}\right)\left(\frac{{\beta }_2-{\beta }_1}{2\pi }\right)}{\frac{\pi }{8}}\\ =\frac{4}{\pi }\left({\beta }_1-{\beta }_2\right)\left({\text{r}}_{\text{2}}^{\text{2}}-{\text{r}}_{\text{1}}^{\text{2}}\right)\end{array}$$ E37

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 n₁ and n₂ independently from a uniform distribution, and form the point with angle $$\frac{\pi }{4}+\frac{\pi }{4}{\text{n}}_{\text{1}}$$ and radius $$\sqrt{{\text{n}}_{\text{2}}}$$ . Then

$$\begin{array}{l}\text{Prob}\left\{{\beta }_1\le \frac{\pi }{4}+\frac{\pi }{4}{\text{n}}_{\text{1}}\le {\beta }_2\text{and}{\text{r}}_{\text{1}}\le \sqrt{{\text{n}}_{\text{2}}}\le {\text{r}}_{\text{2}}\right\}\\ =\text{Prob}\left\{{\beta }_1\le \frac{\pi }{4}+\frac{\pi }{4}{\text{n}}_{\text{1}}\le {\beta }_2\right\}\\ \times \text{Prob}\left\{{\text{r}}_{\text{1}}\le \sqrt{{\text{n}}_{\text{2}}}\le {\text{r}}_{\text{2}}\right\}\\ =\text{Prob}\left\{\frac{4}{\pi }{\beta }_1-1\le {\text{n}}_{\text{1}}\le \frac{4}{\pi }{\beta }_2-1\right\}\\ \times \text{Prob}\left\{{\text{r}}_{\text{1}}^{\text{2}}\le {\text{n}}_{\text{2}}\le {\text{r}}_{\text{2}}^{\text{2}}\right\}\\ =\frac{4}{\pi }\left({\beta }_1-{\beta }_2\right)\left({\text{r}}_{\text{2}}^{\text{2}}-{\text{r}}_{\text{1}}^{\text{2}}\right)\end{array}$$ E38

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

$$\begin{array}{l}{\alpha }_{\text{k}}=\pi /\text{4 }+\text{ k }\pi /\text{4}000 \text{for k }=\text{ 1},\dots ,\text{ 1}000 \\ {\text{r}}_{\text{k}} =\text{ sqrt }\left(\text{ k}/\text{1}000\right) \text{for k }=\text{ 1},\dots ,\text{ 1}000\end{array}$$ E39

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.

Conditions	mean	std	99% int
Pert1=pert2 Std = 1/10 C = 0	67.3279	1.5910	67.3238 67.3320
Pert1=pert2 Std = 1 C = 0	65.9497	1.7335	65.9452 65.9542
Std = 1/10 C = 0	67.1959	1.6200	67.1917 67.2001
Std = 1 C = 0	63.0055	2.8300	62.9981 63.0129
Pert1=pert2 Std = 1/10 C = 1/2	67.2951	1.5941	67.2910 67.2992
Pert1=pert2 Std = 1/10 C = 1/2	65.3106	1.8880	65.3057 65.3155
Std = 1/10 C = 1/2	67.0579	1.6499	67.0536 67.0622
Std = 1 C = 1/2	60.5988	3.6930	60.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.