Skip to main content

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

See other formats


• INiCAL REPORT SECTION 
NAV ... POSTCtftADUATC SCHOOLi 
MONTEREY. CAUPOHNfA V 



NPS-53FE72071A 



NAVAL POSTGRADUATE SCHOOL 

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 



NAVAL POSTGRADUATE SCHOOL 
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. 



This task was supported by: ADVANCED MODULAR CONCEPTS DIVISION 

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 , 

.„ ad 

^'- — 

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 

Naval Postgraduate School 
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 
Naval Postgraduate School 
Monterey, California 93940 

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

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



-18- 



UNCLASSIFIED 



Security Classification 



KEY WO R D S 



Air Traffic Control 



Aircraft Carrier 



LINK A 



ROLE W T 



LINK B 



LINK C 



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) 

Naval Postgraduate School 
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 



12. SPONSORING MILITARY ACTIVITY 



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