# Full text of "A method for solution of an air traffic control problem"

## See other formats

```• INiCAL REPORT SECTION
MONTEREY. CAUPOHNfA V

NPS-53FE72071A

Monterey, California

A METHOD FOR SOLUTION

OF AN

AIR TRAFFIC CONTROL PROBLEM

by

RICHARD FRANKE
25 JULY 1972

Approved for public release; distribution unlimited.

FEDDOCS

D 208.14/2:NPS-53FE72071A

Monterey, California

Rear Admiral M. B. Freeman M. U. Clauser

Superintendent Provost

Abstract: A method is given for computing flight plans for aircraft
returning to the carrier after a mission. The basic goal is to minimize
the total flight time for the landing aircraft, while maintaining various
individual and interactive constraints on the aircraft.

NAVAL ELECTRONICS LABORATORY CENTER
SAN DIEGO, CALIFORNIA

^-^^

1. Introduction

The problem to be considered is that of computing flight plans for
aircraft returning to a carrier after completion of a mission. The aircraft
will be picked up at long range, say 100 n.m. or more, and a flight plan
computed for each, to a point where an automatic landing device takes
control of the aircraft. This point is called the four mile gate, and
the aircraft must have, to within some tolerance, a specified location
and velocity at that distance.

The object will be to minimize the total flight time of all aircraft
to be landed. The flight plans are subject to various individual constraints,
as well as constraints on the positions of the aircraft relative to each
other.

We shall list constraints which might by typical of the kind required,
and values for them.

I. Individual constraints

(a) Velocity: between 110 n.m./hr. and 600 n.m./hr.

(b) Rate of descent/ascent: between -4000 ft./min. and
1500 ft./min.

(c) Turn rate: 3 degrees/sec. normal, 6 degrees/sec. emergency

(d) Fuel: Maximum time to land, due to limited fuel supply

(e) Aircraft performance: Some assumptions as to the acceleration/
deceleration rates should probably be made. We assume these

to be constant.
II. Interactive Constraints

(a) Separation: at least 1000 ft. vertically and/or 2 n.m.
horizontally

(b) Time separation at gate: 1 minute

We note that it is desired to have the aircraft reach the gate at one
minute intervals. Thus the aircraft must automatically approach at least a
certain separation in the latter stages of the approach. With a speed at the
gate >_ 2n.m./min., this separation is >_2n.m., as required.

As the aircraft are picked up at ranges of 100 n.m. or more, it is possible
that one or more groups of aircraft may be returning in formation, thus not
satisfying the separation requirements initially. It is felt that this should
not cause undue concern, as long as the flight plans allow all or part of the
formation to continue. As the aircraft pursue their individual flight plans it
is necessary that the separation increase until the minimum is achieved, and
then it is to be maintained.

A more difficult problem would seem to be the possibility (or necessity) of
one or more aircraft "passing" others. In this instance it is clear that we must
maintain the appropriate separation at all times.

The full solution of the overall problem requires the optimization of the
flight paths in terms of order of landings, as well as individually, subject to
the individual and interactive constraints. Certainly an analytical solution is
impossible, and within the real-time constraint, a numerical solution is likely
impossible also. Thus it is necessary to make some assumptions about the
order of landing and/or the flight plans. It is felt that the most critical of
the two is the type of flight plan to be assumed. The order of landing probably
has a small affect as long as a "reasonable: order is assumed. Within the
constraints of the problem, it is likely that there is not a unique landing order,
2. Assumed flight plan

As we noted above, it is felt that this part is the most important
aspect of the optimization problem. If one makes as assumption of flight

-2-

plan which does not contain enough flexibility, it may become impossible
to solve the resulting problem; indeed, it may then have no solution.
Even if there is a solution, it may be far from optimum because of
artificial restrictions. On the other hand, it is desirable that one be
able to describe the flight plan, with a few parameters, for convenience
in representation, and for checking and maintaining the interactive
constraints. It is also important to be able to verify the individual
constraints without difficulty. The individual constraints could be built
into the assumed flight plan, thus automatically satisfying them. The
flight plan we propose does just that.

The necessary time increment between arrivals at the gate assures one
of the appropriate separation near the end of the flight plan. If that
time interval is achieved at higher speeds, of course the separation
criterion is sure to be satisfied. Thus it seems to be advantageous to
continue at cruise speed (or maximum allowed speed, perhaps) until necessary
to slow down to delay time of arrival at the gate to the desired time. This
will tend to "naturally" achieve the desired separation between aircraft.

Our assumed flight plan will be broken into eight time intervals (some
of which may be of zero length) . The first six will be along a straight
line (when projected into the x-y plans; altitude changes will be permitted),
the seventh will be a circular turn onto the axis of the landing deck, and
the eighth a short interval for final course corrections. The last will be
the same for all aircraft, thus we need not consider it. In fact, for
convenience we shall write as though the gate is reached at time t^ ,
although in practice it is not necessary that this be so. If separation
requirements disallow the straight line path during the first six time

-3-

intervals, a deviation can be incorporated. In some instances it may be
necessary to lengthen the flight path (in distance) to allow an aircraft to
be able to reach the gate under our assumed flight plan.

We are going to approximate the first six segments of the flight path
by straight line segments. The corners are to be quite small, and the
approximate circular transition can be computed. With only small changes in
direction, the difference in the time required to traverse the circular arc
and the theoretical time along the straight line segments is quite small, less
than one percent. Since time in the turn is small, the total difference
compared to total flight time is very small. We assume the aircraft is heading
very nearly in the correct direction when picked up. If not, a correction
could be required before they are placed in the landing "stack."

The horizontal projection of the flight path is given in Figure 1. All

accelerations, decelerations, and descents are to be made at constant rates.

Velocities are along the actual flight path; they are indicated at each of

the times t , t n ,...,t .
o ± o

v.

V,

Figure 1

-4-

The action during each of the time intervals is as follows:

[t , t, ] - accelerate from initial speed V to speed V, at the

1 o v 1

rate A , level flight

max b

[t 1} t„] - constant speed V in level flight

1 2. r max °

If V. < V , t = t..
1 max 2 1

[t„, t_] - decelerate to speed V, at constant rate, A . .
I J d min

[t„, t . ] - descend a vertical distance AZ at rate of descent Z . ,
J 4 min

constant speed V .

[t., t c ] - decelerate to speed V at constant rate A . , level
4 5 a min

flight
[t,., t,] - constant speed V , level flight
[t,, t ? ] - Circular approach tofinal direction, radius r, angle 6,

constant speed V , level flight

a.

[t , t Q ] - any final maneuvers required

The time intervals involved can be given in terms of other parameters
for all but the level flight constant speed intervals. Thus we have the
following relationships, where At. = t. _ - t..

V.-V

At -JL-O

° A

max

mm

At 3 =

Z .
mm

-5-

V -V ,

^'- —

min

r6
At 6 = "

V
a

We will assume that deceleration rates are negative, and that AZ and

•

Z . are negative,
min b

We note that if a flight path is required which is not a straight

line (when projected into the x-y plane) through time t fi , the value

of 6 will need to be recomputed, as will At,..

We assume that V and V.. are bounded by V . The distance
o 1 max

traveled horizontally during descent will be At- Lei

v/v*

2
mm

be the length of the horizontal projection of the path, starting at time
t , to time t,. Then we need to select the various parameters to
satisfy the equation

V -V V-+V V -V n V.+V.

r> 1 o • 1 o , TT Aju d 1 . d 1

R = — - — + V At. + i — ^ —

o A 2 max 1 A . 2

max mxn

+ 4 V

V -V, V +v

V 2 -z 2 . +T^ * -V 1 +V At_.
d mln A min 2 a 5

The total time to the gate is T ■ t, - t . We need to be able to

/ o

compute the minimum value of T for a given path, as well as a flight
plan which takes a given time.

-6-

In order to try to alleviate the separation problem, we follow the
discussion given previously and seek to choose V, as large, and At,.

as small as possible within the constraints of the problem. Likewise, we
accelerate to as large a value for V. as permitted, or possible.

We first give a method for computing the minimum time, T . . Let

V -V V +V

a o . a o , A ^ / TT 2 ^2

2- + At, /v 2 -z :

3 y a i

1 A . 2 3*J a min

mxn

the minimum distance required to slow to speed V , and descend at that

3.

speed. If R ^_ D , the flight path length must be D-. The resulting

V -V

T . is T . = ~r — ~ + At„ + At,.
min mm A . 3 o
mxn

Now assume R > D n . Then we can descend at a higher speed than V .
o — 1 a

Let

D 2 = At 3> /*o

, , V -V V +V

2_«2 a o . a o

min A . 2
mm

the distance required to descend at speed V and decelerate to speed V .

o a

If D„ > R , we descend at a rate of speed between V and V , V, being
2 — o a o a

given by the equation

o

= At 3 /

V -V V +v

2*2 a o . a o
R = At„-*/ V, -Z . +

d min A . 2
mm

T . is given by
mm &

V -V

T . = 7^—2+ At„ + At,,
mm A . 3 o
mm

-7-

Now suppose thet R iL^o* Then we can accelerate to a higher speed

than V . provided V < V .We make a tentative calculation for At, ,
o » o max 1 '

assuming we accelerate to speed V and descend at that speed. We obtain

[V -V V +V r-z s — V -V V +V

. max o . max o / 2 _«2 a max . a max

o A 2 3 V max min A .

. _ max min

1 = V

max

If At.. >_ 0, we have completed the calculation, and we have

V -V V -V

_, max o a max _

X = — + /\t n + At« + — : + At,

mm A 1 3 A . 6

max min

If At.. < 0, we accelerate to speed V- and descend at that speed, V 1

being the solution of

3 V 1 mi

V.-V V-+V , s— ^ V -V. V +V,

r = -i-° • -A_° + At^V^-Z 2 . 4- -£_1 ' -S-l

o A 2 3 V 1 mm A . 2

max mm

T . is given by

mm ° J

V..-V V -v 1

T . = -j±— 2- + At, + -r— - + At, .

mm A 3 A . 6

max mxn

This completes all possibilities for the minimum time flight plan.

We must consider a flight plan to get an aircraft to the desired point

in a specified time (T > T . ) . As noted before, we desire to make At c
r — mm 5

as small as possible and V as large as possible.

Two times are of interest to us as aids in doing this computation.

One is the maximum time to the gate without lengthening the flight path,

the second is an intermediate time, assuming At,. = and V, = V ,

reaching as rapidly as possible the point where descent is started.

T is easily computed. Recall that D n is the distance covered in
max 1

slowing to speed V and then descending. Thus a distance R - D^ is

-8-

to be covered at speed V . Then

a

V -V R -D

T = -£■ — - + At + _2 — L + At
max A . 3 V 6
mxn a

We note that if D, > R we have already discussed the situation.

For the intermediate time T* we travel a distance R - D..

o 1

which is to be covered as rapidly as possible, starting and ending at

V . We calculate a tentative value of At, by
o 1 J

V -V V +V V -V V +V

„ _ max o . max o AJ _ . „ o max . max o

R - D.. = — r + At- V + — ; ; ^

o 1 A 2 1 max A . 2
max mm

If At.. >^ 0, we have completed the computation, and

V -V V -V

T * = max ° + At + a max + + >

A 1 A . 3 6

max min

If At.. < 0, we do not have sufficient distance to accelerate to speed

V , thus we compute V n from
max 1

V,-V V,+V V -V, V +V n

R - D. = ^ ' -^ + ^2_1 ' -2-A
o 1 A 2 A . 2
max min

V -V V -V

and T* = -p^- 2 - + -r^— - + At. + At, .
A A . 3 6
max mxn

The purpose of the intermediate calculation is to simplify the

computation of a flight plan taking T seconds. If the desired time to

the final correction lee is T, and T < T < T*, then V > V , which

mm a a

we compute. If T* < T < T , than V, = V , and we must compute At
r max da ->

First assume that T . < T < T*. We must satisfy the equations

mm

■9-

V--V V,+V V -V, V +v n

max min

+ At_\/v, 2 -Z 2 . , and

'3 v d min

V -V V -V

T = - + At, + A a + At. + At,, with

A 1 A . 3 6

max mm

V = V
1 max

We make a tentative calculation for At., by

At- - T -

V -V V -V
max o , a max , Kt _ . Kt _

— - + -_ + A t + At

A min A . 3 o
min

If At, • 0, then calculate V, from (*), with V, = V . . If At, < 0,
1 — d 1 max 1

we take At = and calculate V from

V -V V -V..

T = -i-2. + At, + -r— - + At,.
A 3 A . 6
max mm

V , is then calculated from (*) .
a

Now, if T* < T < T , we descend at speed V and need to

max r a

determine At.. . Now we must satisfy

V,-V V n +V V -V. V +V.

r = -L_o • -L-° + VAt. + -JL-A • -S-A

o A 2 1 1 A . 2

max mm

(**) + At Vv 2 -Z 2 . + V At c
3 y a mm a 5

V -V V -V

T = -r — - + At n + -jr — - + At„ + At, + At,.

A 1 A . 3 5 6

max mm

-10-

We now make a tentative calculation for At,, and At r , assuming V, = V ,

1 5 ° 1 max

by solving (**) . If At.. < or At_ < 0, we do not have sufficient

distance to accelerate to speed V , and must have At, = 0. With

max 1

At 1 = 0, we can then solve (**) for V.. and At-. We then have the flight
plan computed.

Example: We consider an example to illustrate the calculations and to
show the flexibility available in a typical set of initial conditions. We
assign the following values.

V = 8 n.m. /min
o

V = 2 n . m . /min
a

V =10 n.m. /min
max

R = 100 n.m.
o

2
A =2 n.m. /min
max

2
A . = -2 n.m. /min
mm

AZ = -4 n.m.

Z . = -2/3 n.m. /min
min

We find that

" 4 / 4-4/9 =15+8 / 2 , and

u l -2 2 2/3

-11-

D 2 = 6 Z64-4/9 + 3^ ' ^ = 15 + 4 /l43

Since R > D , we make the tentative calculation for At- , obtaining

100 - [9+6 /1Q0-4/9 + 24] [67 - 16 /[4]
1 " 10 10

This value is positive, thus acceptable, and

t . - 1 + [67 'I 6 ^ + 6 + 4 + At, = 177 -" m + At, ■ 11.7 + At,
mm 10 6 10 6 6

T is easily computed, and

max

T . 3 + 6 100 - (15 + 8 Ji) . 103 - 8 ^ + . 45 _ 7

max 2 6 2 6 6

To compute T*, we find a tentative value for At , by solving

100 - (15 + 8 •£) = 9 + 10At 1 + 9, or hx. =(1/10) [67 - 8 ^2]
Thus, we have

T* = 1 + 1/10 [67-8 t^] + 6 + 4 + At 6

177 Tn 8 ^ + A ^ " 16.6 + At,
10 6 6

We now consider two different times for the flight plan, giving the
calculations for each. First consider T = 13 + At,. We then calculate
a tentative value of At by

-12-

At x = 13 + At 6 - [1 + 4 + 6 + At ] = 2. Thus we compute V from (*) ,

100 = 9 + 20 + 24 + 6 /v\ 2 -4/9 , or

d

V d 2 = 4/9 + (47/6) 2 = 16 + \\ 1)2 , giving V d - 7.9

The pertinent details of the flight plan, along with others, is
given in Table 1.

Now, consider T = 20 + At,. We set V n = V , tentatively, and

o 1 max ' '

solve (**) for At and At 5 « We have

100 = 9 + lOAt +24+8 /2 + 2At

20 + 2At, = 1 + At, + 4 + 6 + At c + At,, or
o 1 5 6

10At 1 + 2At 5 =67-8/2

A^ + At 5 = 9

This gives At x - 49 - 8 8 -ft '.4.7 and Atj = 2L±±Jl . 4 . 3

The results are again tabulated in Table 1.

Table 1 gives the approximate flight plans for the above initial
conditions for various flight times. If one considers several aircraft
returning in formation, it is easily seen that the interactive constraints
are satisfied (in the sense that the separation increases) once an aircraft
leaves the formation. In each case At„ = 6.

-13-

TABLE 1

T-At, At At. At„ At. At c V,

6 o 1 2 4 5 d

12 11 .25 3.75 9.5

13 1 2 1 3.0 8

14 1 3 2 2.0 6

15 14 2.75 1.25 4.5

16 15 3.5 .50 3

17 1 5.44 4.0 .46 2
20 1 4.7 4.0 4.3 2
40 .8 3.8 29.4 2

-14-

3. Order of landing

We give a method for determining the order of landing. In connection
with the assumed flight plan, it should tend to minimize the possibility
of violation of the interactive constraints. The three pieces of infor-
mation to be considered, in decreasing order of importance, are

(a) Maximum time due to fuel constraint

(b) Minimum time to gate

(c) Distance from gate (approximated by R )

We first determine the minimum time to the gate for each aircraft

(individually, without regard to interactive constraints). The first

aircraft in the landing sequence, A.. , will be the one which has the

smallest minimum time to the gate, T . The ordering is completed in an

inductive manner. Assume A, has been chosen, and he will reach the gate

at time T, . We must look ahead to determine if any aircraft is fuel

constrained to land before time T, + 2. If so, he becomes A, .. , with

T. , n = max (T . , T. + 1) . If no fuel constrained aircraft enters, we
k+1 min k

consider the set of all remaining aircraft with minimum time to gate being

<_ T, + 1. If the set is not empty, take A, - to be the aircraft of the

set with the smallest R . If the set is empty, take A,,, to be the

aircraft with the smallest T . , then T. . - ■ T . . In the event that

min k+1 min

"ties" occur, such as for aircraft returning in formation, the ordering
is a matter of convenience. Position in the formation should likely be
considered.

As a position is determined for an aircraft, its flight plan should
be calculated and any correction due to interactive constraints should be
made. It is possible that A, . could not satisfy the interactive

-15-

constraints and still reach the gate by time T . It is felt this

would be unlikely, however, since the ordering and flight plans are

designed to minimize this sort of interference. The exception might

occur in the case of a fuel constrained aircraft entering into the

ordering. He would then "pass" some aircraft, perhaps, causing them to

have to take some evasive action, since they would follow in the landing

order.

When interactive constraints are violated, it is anticipated that

a slight deviation in course away from the point of violation will

correct it. This will slightly lengthen the flight path, and change At ,

thus new values for T . , T* and T will have to be calculated,

min max

and the new flight plan tested for satisfaction of the interactive constraints,
No major problem is anticipated for a "reasonable" number of aircraft.

4. Conclusions

As noted previously, we emphasize the idea that the most important
factor in this problem is a realistic, but easily computed, flight plan.
The more closely the assumed flight plan approximates the actual capabilities
of the aircraft, the closer one can come to optimizing the operation.

It is felt that the above ideas can be programmed for a computer and
shown to be feasible in a large number of cases. This should be done by
making liberal use of subprograms so that various aspects of the overall
calculation can be easily changed, and perhaps even improved. Some
experience would likely lead to better assumed flight plans; more general
ones would perhaps be needed. Experience might also lead to better methods
of ordering the aircraft to help minimize the interactive constraint
problem.

-16-

Distribution List

Defense Documentation Center 12

Cameron Station
Alexandria, Virginia

Library 2

Monterey, California 93940

Naval Electronics Laboratory Center 2

Research Library, Code 6700
San Diego, California 92152

NELC 8

Mr. W. J. Dejka, Code 4300
San Diego, California 92152

NELC 1

Mr. S. Snyder, Code 4000
San Diego, California 92152

NELC 1

Mr. H. T. Mortimer, Code 0220
San Diego, California 92152

NELC 1

Mr. M. Lamendola, Code 5200
San Diego, California 92152

NELC 1

Mr. W. Loper, Code 5200

San Diego, California 92152

NELC 1

Dr. R. Kolb, Code 3300

San Diego, California 92152

NELC 1

Mr. E. E. McCown, Code 3100
San Diego, California 92152

NELC 1

Mr. H. F. Wong, Code 3200
San Diego, California 92152

NELC 1

Dr. P. C. Fletcher, Code 2000
San Diego, California 92152

-17-

Distribution List

Dean C. E. Menneken, Code 023
Monterey, California 93940

Professor W. M. Woods, Code 53Wo
Chairman, Department of Mathematics
Monterey, California 93940

Professor Richard Franke, Code 53Fe
Department of Mathematics
Monterey, California 93940

-18-

UNCLASSIFIED

Security Classification

KEY WO R D S

Air Traffic Control

Aircraft Carrier

ROLE W T

ROLE W T

ROLE W T

D , F °o1"„1473 (BA«,

UNCLASSIFIED

0101-807-6821

Security Classification

A- 3 1 409

UNCLASSIFIED

Security Classification

DOCUMENT CONTROL DATA -R&D

Security classification of title, body of abstract and indexing annotation mu.-.f be entered when the overall report is classified)

1 ORIGINATING activity (Corporate author)

Monterey, California

2a. REPORT SECURITY CLASSIFICATION

UNCLASSIFIED

2fc. GROUP

3 REPORT TITLE

A Method for Solution of an Air Traffic Control Problem

4. DESCRIPTIVE NOTES (Type of report and. inclusive dates)

Technical Report, 1972

5 au THOR(S) (First name, middle initial, last name)

Richard H. Franke

6 REPOR T DATE

25 July 1972

7a. TOTAL. NO. OF PAGES

22

76. NO. OF REFS

8a. CONTRACT OR GRANT NO.

b. PROJEC T NO

9a. ORIGINATOR'S REPORT NUMBER(S)

NPS-53FE72071A

9b. OTHER REPORT NO(S) (Any other numbers that may be assigned
this report)

10. DISTRIBUTION STATEMENT

Approved for public release; distribution unlimited

II. SUPPLEMENTARY NOTES

Naval Electronics Laboratory Center
San Diego, California

13. ABSTRACT

A method is given for computing flight plans for aircraft returning to
the carrier after a mission. The basic goal is to minimize the total
flight time for the landing aircraft, while maintaining various
individual and interactive constraints on the aircraft.

DD

FORM I47O

I NOV 65 I ™T # W

S/N 0101 -807-681 1

(PAGE 1)

UNCLASSIFIED

Security Classification

A-31

U1A8225

DUDLEY KNOX

L.BHABY- RESEARCH REPORTS

5 6853 01057966 7

```