# 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