Path planning based on unmanned aerial vehicle performance with segmented cellular genetic algorithm

Yıl 2025, , 135 - 154, 16.08.2024

Ahmet Gezer , Onder Turan , Tolga Baklacıoğlu

https://doi.org/10.17341/gazimmfd.1156817

Öz

Unmanned Aerial Vehicles (UAV) have a wide range of use on industrial, military and commercial areas. Comprehensive and error-free sub-systems are needed to provide planning, management and coordination of UAVs which are designed for variable purposes with different capabilities and sizes. An important part of UAV technological development consists of improvements in the scope of path planning. Different choices can be made in path planning according to operational priorities, it may be preferred to reach the destination as fast as possible or to increase the airtime by compromising speed. Fuel data of cruise, climb and descent phases are used in the path planning algorithm for every speed and altitude that the UAV can fly. Thus, economical and airtime-maximizing paths could be produced on the basis of performance characteristics compatible with the kinematic constraints customized for the UAV. In this thesis, Cellular (cGA) and Segmented Cellular Genetic Algorithm (scGA) are proposed. The novel overprotective algorithm which has a fixed initial population and segmented chromosome structure achieves a high convergence speed to optimal solution and can generate paths which have 5.2 times higher fitness value on average compared with a conventional Genetic Algorithm (GA). It has been observed that scGA improves the initial population in terms of the best solutions 1.9 times and the general population 5.8 times better compared with GA.

Anahtar Kelimeler

Path Planning, Trajectory Planning, Genetic Algorithm, Evolutionary Algorithm, UAV, Aircraft Performance

Parçalı hücresel genetik algoritma ile insansız hava aracı performansına dayalı yol planlama

Öz

İnsansız Hava Araçları (İHA), endüstriyel, askerî ve ticari geniş bir uygulama alanına sahiptir. Değişken amaçlar için tasarlanmış farklı yeteneklere ve boyutlara sahip İHA’ların; planlama, yönetme ve koordinasyonunu sağlayabilmek için hatasız çalışan kapsamlı alt sistemlere ihtiyaç vardır. İHA teknolojik gelişiminin önemli bir parçası, yol planlama alanındaki iyileştirmelerden oluşmaktadır. Yol planlamada operasyonel önceliklere göre farklı tercihler yapılabilir, varış noktasına en hızlı şekilde ulaşılması veya hızdan ödün vererek havada kalma süresinin uzatılması istenebilir. Bir İHA’ya ait uçabildiği her hız ve her irtifa için; seyir, tırmanma ve alçalma fazlarına ait yakıt verileri yol planlama algoritmasında kullanılmıştır. Böylece, bir İHA için özelleştirilmiş kinematik kısıtlara uyumlu performans özellikleri temelinde ekonomik ve havada kalma süresini uzatan yollar üretilebilmiştir. Bu tez çalışmasında, Hücresel (cGA) ve Parçalı Hücresel Genetik Algoritma (scGA) önerilmiştir. Sabit başlangıç popülasyonu ve parçalı kromozom yapısına sahip aşırı korumacı yeni algoritma; optimal çözüme yüksek yakınsama hızı elde etmiş, geleneksel bir genetik algoritmaya (GA) kıyasla ortalama 5,2 kat daha yüksek uygunluk değerine sahip yollar üretebilmiştir. scGA’nın GA’ya kıyasla, başlangıç popülasyonuna göre en iyi çözümü 1,9 kat ve genel popülasyonu 5,8 kat daha iyi geliştirdiği gözlenmiştir.

Anahtar Kelimeler

Yol Planlama, Yörünge Planlama, Genetik Algoritma, Evrimsel Algoritma, İHA, Hava Aracı Performansı

Kaynakça

• The Regulatory Horizons Council, The Regulation of Drones: An exploratory study, Department for Business, Energy & Industrial Strategy (BEIS), UK, 2021.
• Atr-Aircraft. Fuel Saving. https://www.atraircraft.com/userfiles/files/Fuel_Saving_2011.pdf Yayın tarihi Ocak 30, 2011. Erişim tarihi Ağustos 9, 2016.
• Mayer, R., A flight trajectory model for a pc-based airspace analysis tool, AIAA Modeling and Simulation Technologies Conference and Exhibit, 1-10, 2002.
• Eurocontrol. Base of aircraft data. https://www.eurocontrol.int/model/bada Yayın tarihi 16.01.2009. Erişim tarihi 20.03.2022.
• Li, D.C., Cheng, N., Cheng, P., Song, J.Y., Design and Development of an Integrated Flight Planning and Rehearsal System Based on GIS and Navigation Database, Applied Mechanics and Materials, Trans Tech Publ, 169-177, 2012.
• Labonte, G., Simple formulas for the fuel of climbing propeller driven airplanes, Advances in aircraft and spacecraft science, 2(4), 367-389, 2015.
• Roberge, V., Tarbouchi, M., Labonté, G., Fast genetic algorithm path planner for fixed-wing military UAV using GPU, IEEE Transactions on Aerospace and Electronic Systems, 54(5), 2105-2117, 2018.
• Langelaan, J.W., Gust energy extraction for mini and micro uninhabited aerial vehicles, Journal of guidance, control, and dynamics, 32(2), 464-473, 2009.
• Langelaan, J., Long distance/duration trajectory optimization for small UAVs, AIAA Guidance, Navigation and Control Conference and Exhibit, 1-14, 2007.
• Williams, A., Yakimenko, O., Persistent mobile aerial surveillance platform using intelligent battery health management and drone swapping, 2018 4th International Conference on Control, Automation and Robotics (ICCAR), IEEE, 237-246, 2018.
• Fujii, K., Higuchi, K., Rekimoto, J., Endless flyer: a continuous flying drone with automatic battery replacement, 2013 IEEE 10th international conference on ubiquitous intelligence and computing and 2013 IEEE 10th international conference on autonomic and trusted computing, IEEE, 216-223, 2013.
• Qi, Y.C., Zhao, Y.J., Energy-efficient trajectories of unmanned aerial vehicles flying through thermals, Journal of Aerospace Engineering, 18(2), 84-92, 2005.
• Kniffin, C.A., Dogan, A., Blake, W.B., Formation flight for fuel saving in coronet mission-part a: Sweet spot determination, AIAA Atmospheric Flight Mechanics Conference, 1-14, 2016.
• Russell, S., Norvig, P., Intelligence artificielle: Avec plus de 500 exercices, Pearson Education, Paris, 2010.
• Li, S., Sun, X., Xu, Y., Particle swarm optimization for route planning of unmanned aerial vehicles, Information Acquisition, 2006 IEEE International Conference on, IEEE, 1213-1218, 2006.
• Gao, D., Gong, G., Wang, J., Han, L., Multi-resolution path planning for Miniature Air Vehicles with wind effect, Industrial Informatics (INDIN), 2012 10th IEEE International Conference on, IEEE, 167-171, 2012.
• Yılmaz, N., Gencer, C., Integration of sensor vision capabilities on UAV flight route optimization: a linear model and a heuristic algorithm proposal, Journal of the Faculty of Engineering and Architecture of Gazi University, 34, 2019.
• Holland, J.H., Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence, MIT press, Massachusetts, 1992.
• Fu, X., Gao, X., Genetic algorithm with adaptive immigrants for dynamic flight path planning, 2010 IEEE International Conference on Intelligent Computing and Intelligent Systems, IEEE, 630-634, 2010.
• Durmaz, E.D., Şahin, R., Çok Amaçlı Tek Sıra Tesis Düzenleme Probleminin Çözümü için Nsga-II ve Hedef Programlama Yaklaşımı, Journal of the Faculty of Engineering and Architecture of Gazi University, 32(3), 2017.
• Okay, F.Y., Özdemİr, S., Kablosuz Algilayici Ağlarda Kapsama Alaninin Çok Amaçli Evrimsel Algoritmalar İle Artirilmasi, Journal of the Faculty of Engineering and Architecture of Gazi University, 30(2), 2015.
• Xiao, J., Michalewicz, Z., Zhang, L., Trojanowski, K., Adaptive evolutionary planner/navigator for mobile robots, IEEE transactions on evolutionary computation, 1(1), 18-28, 1997.
• Yıldırım, M., Akay, R., Fast path planning in multi-obstacle environments for mobile robots, Journal of the Faculty of Engineering and Architecture of Gazi University, 36(3), 2021.
• Nikolos, I.K., Valavanis, K. P., Tsourveloudis, N. C., Kostaras, A. N., Evolutionary algorithm based offline/online path planner for UAV navigation, IEEE Trans Syst Man Cybern B Cybern, 33(6), 898-912, 2003.
• Roberge, V., Tarbouchi, M., Labonte, G., Comparison of parallel genetic algorithm and particle swarm optimization for real-time UAV path planning, IEEE Transactions on Industrial Informatics, 9(1), 132-141, 2013.
• Fu, Y.-G., Zhou, C.-P., Hu, H.-P., Research on Differential Evolution Algorithm for Path Planning for Unmanned Aerial Vehicle in Ocean Environment, Acta Armamentarii, 3, 1-9, 2012.
• Fu, S.-Y., Han, L.-W., Tian, Y., Yang, G.-S., Path planning for unmanned aerial vehicle based on genetic algorithm, Cognitive Informatics & Cognitive Computing (ICCI* CC), 2012 IEEE 11th International Conference on, IEEE, 140-144, 2012.
• Zheng, R., Feng, Z.-M., Lu, M.-Q., Application of Particle Genetic Algorithm to Path Planning of Unmanned Aerial Vehicle, Computer Simulation, 6, 88-92, 2011.
• Alba, E., Dorronsoro, B., Cellular genetic algorithms, 42, Springer Science & Business Media, Heidelberg, 2009.
• Whitley, L.D., Cellular genetic algorithms, Proceedings of the 5th International Conference on Genetic Algorithms, 1-12, 1993.
• Manderick, B., Spiessens, P., Fine-grained parallel genetic algorithms, Proceedings of the third international conference on Genetic algorithms, Morgan Kaufmann Publishers Inc., 428-433, 1989.
• Robertson, G.G., Parallel implementation of genetic algorithms in a classifier system, Genetic algorithms and their applications: proceedings of the second International Conference on Genetic Algorithms, Hillsdale, NJ: L. Erlhaum Associates, Massachusetts Institute of Technology, Cambridge, 140-147, 1987.
• Wright, S., Isolation by distance, Genetics, 28(2), 114-138, 1943.
• Alba, E., Dorronsoro, B., Solving the vehicle routing problem by using cellular genetic algorithms, Evolutionary Computation in Combinatorial Optimization, Springer, Heidelberg, 2004.
• Alba, E., Alfonso, H., Dorronsoro, B., Advanced models of cellular genetic algorithms evaluated on SAT, Proceedings of the 2005 conference on Genetic and evolutionary computation, ACM, 1123-1130, 2005.
• Folino, G., Pizzuti, C., Spezzano, G., Combining cellular genetic algorithms and local search for solving satisfiability problems, Tools with Artificial Intelligence, 1998. Proceedings. Tenth IEEE International Conference on, IEEE, 192-198, 1998.
• Murata, T., Gen, M., Cellular genetic algorithm for multi-objective optimization, Proc. of the 4th Asian Fuzzy System Symposium, 538-542, 2002.
• Mantere, T., Image ordering by cellular genetic algorithms with TSP and ICA, Evolutionary Computation, 2009. CEC'09. IEEE Congress on, IEEE, 822-829, 2009.
• Gezer, A., Turan, Ö., Baklacıoğlu, T., UAV path planning using segmented cellular evolutionary algorithm, International Journal of Sustainable Aviation, 2(3), 222-234, 2016.
• Gezer, A., Turan, Ö., Baklacıoğlu, T., Hücresel Genetik Algoritma ile İnsansız Hava Araçlarında Yol Planlama, Proceeding 3rd International Conference on Applied Engineering and Natural Sciences, Konya, Türkiye, 1346-1350, 2022.
• Gezer, A., Turan, Ö., Baklacıoğlu, T., İnsansız Hava Aracı Performansına Dayalı Yol Planlama, Proceeding 3rd International Conference on Applied Engineering and Natural Sciences, Konya, Türkiye, 2055-2061, 2022.
• Boulos, M.N.K., Web GIS in practice III: creating a simple interactive map of England's strategic Health Authorities using Google Maps API, Google Earth KML, and MSN Virtual Earth Map Control, 4(22), 1-8, 2005.
• Schmidt, M., Weiser, P., Web mapping services: development and trends, Online maps with APIs and WebServices, Springer, 2012.
• Özalp, N., Sahingoz, O.K., Optimal UAV path planning in a 3D threat environment by using parallel evolutionary algorithms, 2013 International conference on unmanned aircraft systems (ICUAS), IEEE, 308-317, 2013.
• Spiessens, P., Manderick, B., A massively parallel genetic algorithm: Implementation and first analysis, Proceedings of the Fourth International Conference on Genetic Algorithms, 279-286, 1991.
• Alba, E., Troya, J.M., Improving flexibility and efficiency by adding parallelism to genetic algorithms, Statistics and Computing, 12(2), 91-114, 2002.
• Petty, C., Diffusion (cellular) models, Handbook of evolutionary computation, Oxford Univ. Press, Oxford, 1997.
• Sarma, J., De Jong, K., An analysis of the effects of neighborhood size and shape on local selection algorithms, International Conference on Parallel Problem Solving From Nature, Springer, 236-244, 1996.
• Lee, K.-Y., Han, S.-N., Roh, M.-I., An improved genetic algorithm for facility layout problems having inner structure walls and passages, Computers & Operations Research, 30(1), 117-138, 2003.
• Nogueras, R., Cotta, C., Using distribution-based operators in genetic algorithms, Proceedings of the 6th Metaheuristic International Conference, págs, 707-712,
• Chiarella, C., Tô, T.-D., The multifactor nature of the volatility of futures markets, Computational Economics, 27(2), 163-183, 2006.
• Shim, Y., Husbands, P., Incremental embodied chaotic exploration of self-organized motor behaviors with proprioceptor adaptation, Frontiers in Robotics and AI, 2, 1-7, 2015.
• Homaifar, A., Qi, C.X., Lai, S.H., Constrained optimization via genetic algorithms, Simulation, 62(4), 242-253, 1994.
• Xia, S., Zhang, X., Constrained path planning for unmanned aerial vehicle in 3D terrain using modified multi-objective particle swarm optimization, Actuators, Multidisciplinary Digital Publishing Institute, 255-265, 2021.
• Mcmanus, I.A., Walker, R.A., Multidisciplinary approach to intelligent unmanned-airborne-vehicles mission planning, Journal of Aircraft, 43(2), 318-335, 2006.
• Li, S.D., Liu, S., Ai, Q., Li, J., Fast 3D Path Pre-Planning Method for UAVs, Applied Mechanics and Materials, 278, 1676-1681, 2013.
• Zheng, C., Ding, M., Zhou, C., Real-Time Route Planning for Unmanned Air Vehicle with an Evolutionary Algorithm, International Journal of Pattern Recognition and Artificial Intelligence, 17(01), 63-81, 2011.
• Lin, L., Goodrich, M.A., UAV intelligent path planning for wilderness search and rescue, Intelligent Robots and Systems, 2009. IROS 2009. IEEE/RSJ International Conference on, 709-714, 2009.
• Sun, T.Y., Huo, C.L., Tsai, S.J., Liu, C.C., Optimal UAV flight path planning using skeletonization and particle swarm optimizer, 2008 Ieee Congress on Evolutionary Computation, Vols 1-8, 1183-1188, 2008.
• Holland, G.J., Mcgeer, T., Youngren, H., Autonomous aerosondes for economical atmospheric soundings anywhere on the globe, Bulletin of the American Meteorological Society, 73(12), 1987-1998, 1992.
• Sliwinski, J., Gardi, A., Marino, M., Sabatini, R., Hybrid-electric propulsion integration in unmanned aircraft, Energy, 140, 1407-1416, 2017.
• Al-Habahbeh, O.M., Configuration of hybrid fuel-electric airplane model based on full flight path performance, Jurnal Teknologi, 84(3), 59-67, 2019.
• Lobit Cerrato, A., Simulación de vuelo de múltiples UAVs de ala fija, Universidad de Sevilla, Sevilla, 2016.
• Bayraktar, O., Özdemir, F., Çetin, Ö., Yılmaz, G., İnsansız Hava Araçları İçin Otonom İniş Sistemi Simülatörü Tasarımı, Bilişim Teknolojileri Dergisi, 5(2), 1-8, 2012.
• Kıvanç, Ö.C., Mungan, T.E., Atila, B., Tosun, G., An integrated approach to development of unmanned ground vehicle: design, analysis, implementation and suggestions, Journal of the Faculty of Engineering and Architecture of Gazi University, 34(4), 1957-1973, 2019.
• Dynamics, U. Aerosim Toolbox. http://www.u-dynamics.com/aerosim/ Yayın tarihi Şubat 1, 2014. Erişim tarihi Şubat 1, 2014.
• Yingxun, W., Zongji, C., Genetic algorithms (GA) based flight path planning with constraints, J. Beijing Univ. Aeronaut. Astronaut.(China), 25(3), 355-358, 1999.
• Schopferer, S., Pfeifer, T., Performance-aware flight path planning for unmanned aircraft in uniform wind fields, Unmanned Aircraft Systems (ICUAS), 2015 International Conference on, IEEE, 1138-1147, 2015.
• Yakovlev, K., Makarov, D., Baskin, E., Automatic path planning for an unmanned drone with constrained flight dynamics, Scientific and Technical Information Processing, 42(5), 347-358, 2015.
• Myers, D., Batta, R., Karwan, M., A real-time network approach for including obstacles and flight dynamics in UAV route planning, The Journal of Defense Modeling and Simulation, 13(3), 291-306, 2016.
• Faa, Pilot's handbook of aeronautical knowledge, Skyhorse Publishing Inc., New York, 2009.
• Madaan, R., Gyde, N., Vemprala, S., Brown, M., Nagami, K., Taubner, T., Cristofalo, E., Scaramuzza, D., Schwager, M., Kapoor, A., Airsim drone racing lab, NeurIPS 2019 Competition and Demonstration Track, PMLR, 177-191, 2020.
• Perry, A.R., The flightgear flight simulator, Proceedings of the USENIX Annual Technical Conference, 1-53, 2004.
• Spencer, J., Lee, J., Paredes, J.A., Goel, A., Bernstein, D., An Adaptive PID Autotuner for Multicopters with Experimental Results, ArXiv, 2109(12797), 1-7, 2021.
• Wright, T., West, A., Licata, M., Hawes, N., Lennox, B., Simulating Ionising Radiation in Gazebo for Robotic Nuclear Inspection Challenges, Robotics, 10(3), 86-102, 2021.
• Henriques, L.C.F., De Souza, C.P., Development of an Embedded Longitudinal Flight Control Based on X-Plane Flight Simulator, IEEE Latin America Transactions, 19(10), 1684-1691, 2021.
• Mueller, M., Casser, V., Lahoud, J., Smith, N., Ghanem, B., Ue4sim: A photo-realistic simulator for computer vision applications, arXiv, 1708(05869), 1-18, 2017.
• Elsadig, M.A., Elbakri, M.A., Design of autopilot platform using HILS approach, Communication, Control, Computing and Electronics Engineering (ICCCCEE), 2017 International Conference on, IEEE, 1-6, 2017.
• Huang, H., Xu, Y.-P., Deng, Z.-W., Real-time visual flight simulation system based on flightgear simulator, Journal of System simulation, 19(19), 780-785, 2007.
• Sorton, E., Hammaker, S., Simulated flight testing of an autonomous unmanned aerial vehicle using flightgear, Infotech@ Aerospace, 1-11, 2005.
• Joscelyne, R., Young, T., An approach to formulate and model aerodynamic drag on aircraft landing gear, 11th AIAA Aviation Technology, Integration, and Operations (ATIO) Conference, including the AIAA Balloon Systems Conference and 19th AIAA Lighter-Than, 1-21, 2011.
• Romaniuk, S., Gosiewski, Z., Ambroziak, L., A Ground control station for the UAV flight simulator, acta mechanica et automatica, 10(1), 28-32, 2016.
• Zhao, X., Wang, Y., Zhang, W., Zhang, X., Personal Desktop-Level Jet Fighter Simulator for Training or Entertainment, International Conference on Intelligent Robotics and Applications, Springer, 417-427, 2017.
• Garcia-Najera, A., Bullinaria, J.A., A multi-objective density restricted genetic algorithm for the vehicle routing problem with time windows, 2008 UK Workshop on Computational Intelligence, 47-52, 2008.
• Userbenchmark. UserBenchmark: AMD Ryzen 5 2400G vs Intel Core i9-12900KS. https://cpu.userbenchmark.com/Compare/Intel-Core-i9-12900KS-vs-AMD-Ryzen-5-2400G/m1821519vsm433194 Yayın tarihi Mayıs 4, 2022. Erişim tarihi Mayıs 4, 2022.
• Cpu-Monkey. AMD Ryzen Threadripper PRO 3995WX vs AMD Ryzen 5 2400G. https://www.cpu-monkey.com/en/compare_cpu-amd_ryzen_threadripper_pro_3995wx-1899-vs-amd_ryzen_5_2400g-858 Yayın tarihi Mayıs 4, 2022. Erişim tarihi Mayıs 4, 2022.