AUTHORS: Giuseppe Sirigu, Mario Cassaro, Manuela Battipede, Piero Gili

Download as PDF

ABSTRACT: The antithetical needs of increasing the air traffic, reducing the air pollutant and noise emissions, jointly with the prominent problem of airport congestion spur to radically innovate the entire ground operation system and airport management. In this scenario, an alternative autonomous system for engine-off taxiing (dispatch towing) attracts the interest of the civil aviation world. Even though structural and regulatory limitations undermine the employment of the already existing push-back tractors to this purpose, they remain the main candidates to accomplish the mission. New technologies are already under investigation to optimize towbarless tractor joints, so as to respond to the structure safety requirements. However, regulation limitations will soon be an issue. In this paper, a software solution for a route selection problem in a discretized airport environment is presented, in the believe that a full-authority control system, including tractors’ selection logic, path planning and mission event sequencing algorithms will possibly meet the regulation requirements. Four different algorithms are implemented and compared: two Hopfield-type neural networks and two algorithms based on graph theory. They compute the shortest path, accounting for restricted airport areas, preferential directions and dynamic obstacles. The computed route checkpoints serve as a reference for the tractor autopilot. Two different missions are analyzed, concerning the towing of departing and arriving aircraft respectively. A single mission consists of three different events, called phases: Phase 1 goes from the actual tractor position (eventually the parking zone) to the selected aircraft (parked or just landed); Phase 2 is the actual engine-off taxi towing; Phase 3 is the tractor return to its own parking zone. Both missions are simulated and results are reported and compared.

KEYWORDS: Route selection, Airport Taxiing, Neural Network, Hopfield, Dijkstra, A*

REFERENCES:

[1] Bondy A.J. and Murty U.S.R. Graph Theory with Applications.

[2] Goldberg A.V. and Tarjan R.E. Expected performance of dijkstra’s shortest path algorithm. Technical report, NEC RESEARCH INSTITUTE REPORT, 1996.

[3] Bonet B. and Geffner H. Planning as heuristic search. Artificial Intelligence, 129(12):5 – 33, 2001.

[4] Hilburn B. Head down time in aerodrome operations: a scope study. 2004.

[5] M. Battipede, A. Della Corte, M. Vazzola, and D. Tancredi. Innovative airplane ground handling system for green operations. In 27th International Congress Of The Aeronautical Sciences ICAS, 2010.

[6] Baker B.M. and Ayechew M.A. A genetic algorithm for the vehicle routing problem. Computers and Operations Research, 30(5):787–800, 2003.

[7] Lesire C. An iterative a* algorithm for planning of airport ground movements. In Proceedings of the 2010 Conference on ECAI 2010: 19th European Conference on Artificial Intelligence, pages 413–418, 2010.

[8] Dijkstra E.W. A note on two problems in connexion with graphs. Numerische Mathematik, 1(1):269–271, 1959.

[9] S. Haykin. Neural Networks: A Comprehensive Foundation. Prentice Hall PTR, Upper Saddle River, NJ, USA, 2nd edition, 1998.

[10] ICAO. Manual on the prevention of runway incursions. Technical Report Doc 9870 AN/463, International Civil Aviation Organization, 2007.

[11] Hopfield J.J. Neural networks and physical systems with emergent collective computational abilities. Proceedings of the National Academy of Sciences, 79(8):2554–2558, 1982.

[12] Hopfield J.J. and Tank D.W. Neural computation of decisions in optimization problems. Biological Cybernetics, 52(3):141–152, 1985.

[13] Hopfield J.J. and Tank D.W. Computing with neural circuits: a model. Science, 233(4764):625–633, 1986.

[14] J.Y. Kim, Aktay K., Aktay K., and Ropp T.D. Ants-automated nextgen taxi system. FAA Design Competition 2009-2010, 2010.

[15] Lufthansa. Innovative taxibot now used in real flight operations, 2015.

[16] Gendreau M., Guertin F., J.Y. Potvin, and Taillard . Parallel tabu search for real-time vehicle routing and dispatching. Transportation Science, 33(4):381–390, 1999.

[17] Xu M.H., Liu Y.Q., Huang Q.L., Zhang Y.X., and Luan G.F. An improved dijkstras shortest path algorithm for sparse network. Applied Mathematics and Computation, 185(1):247 – 254, 2007.

[18] Ali M.K.M and Kamoun F. Neural networks for shortest path computation and routing in computer networks. Neural Networks, IEEE Transactions on, 4(6):941–954, Nov 1993.

[19] Christofides N. Graph Theory: An Algorithmic Approach. Computer Science and Applied Mathematics.

[20] Kojic N., Reljin I., and Reljin B. Route selection problem based on hopfield neural network. Radioengineering, 22(4):1182–1193, 2013.

[21] Wasserman P.D. Advanced Methods in Neural Computing. John Wiley & Sons, Inc., New York, NY, USA, 1st edition, 1993.

[22] Hart P.E., Nilsson N.J., and Raphael B. A formal basis for the heuristic determination of minimum cost paths. Systems Science and Cybernetics, IEEE Transactions on, 4(2):100–107, July 1968.

[23] S.A. Rahman, M.S. Ansari, A.A. Moinuddin, and et al. Solution of linear programming problems using a neural network with non-linear feedback. Radioengineering, 21(4):1171, 2012.

[24] Khebbache-Hadji S., Prins C., Yalaoui A., and Reghioui M. Heuristics and memetic algorithm for the two-dimensional loading capacitated vehicle routing problem with time windows. Central European Journal of Operations Research, 21(2):307–336, 2013.

[25] Mitrovi-Mini S., Krishnamurti R., and Laporte G. Double-horizon based heuristics for the dynamic pickup and delivery problem with time windows. Transportation Research Part B: Methodological, 38(8):669 – 685, 2004.

[26] Zeng W. and Church R.L. Finding shortest paths on real road networks: The case for a*. Int. J. Geogr. Inf. Sci., 23(4):531–543, April 2009.

[27] Zhong Y., Shirinzadeh B., and Tian Y. A new neural network for robot path planning. In Advanced Intelligent Mechatronics, 2008. AIM 2008. IEEE/ASME International Conference on, pages 1361–1366, July 2008.