The International Arab Journal of Information Technology (IAJIT)


Optimization of Quadrotor Route Planning with Time and Energy Priority in Windy Environments

Route planning studies are of great importance for quadrotors, which are widely used in military and civil fields, to perform their duties autonomously and efficiently. In the study, a method is proposed that enables Quadrotor Route Planning (QRP) to be optimized with time priority and energy priority by using Genetic Algorithm (GA). For the proposed method, the Wind Effected QRP-App (WEQRP-App) desktop software was developed with the Visual Studio C# programming language. In the developed WEQRP-App, real location information from GMAP.Net map plugin and real wind data from the website of the General Directorate of Meteorology were used. Using Wind Effected Quadrotor Route Planning (WEQRP) method, more realistic planning was made before the flight and the flight efficiency was increased in terms of time and energy priority. Thus, it is foreseen that safer and less costly autonomous flights will take place when compared to the Standard QRP (SQRP) created without taking into account the wind effect, by avoiding the problems that arise due to unexpected energy consumption during the flight mission. When the results obtained from the proposed method were examined, it has been observed that WEQRP provides the improvements up to 13,5% in flight times and up to 27,4% in energy consumption according to SQRP.

[1] Alexis K., Nikolakopoulos G., and Tzes A., “Constrained-control of a Quadrotor Helicopter for Trajectory Tracking Under Wind-gust Disturbances,” in Proceedings of the Melecon 15th IEEE Mediterranean Electrotechnical Conference, Valletta, pp. 1411-1416, 2010. DOI: 10.1109/MELCON.2010.5476026

[2] Andreica A. and Chira C., “Best-order Crossover for Permutation-based Evolutionary Algorithms,” Applied Intelligence, vol. 42, no. 4, pp. 751-776, 2015. DOI:10.1007/s10489-014-0623-0

[3] Chen Y., He Y., and Zhou M., “Decentralized PID Neural Network Control for a Quadrotor Helicopter Subjected to Wind Disturbance,” Journal of Central South University, vol. 22, no. 1, pp. 168-179, 2015. DOI:10.1007/s11771-015- 2507-9

[4] Cordeau J., Gendreau M., Laporte G., Potvin J., and Semet F., “A Guide to Vehicle Routing Heuristics,” Journal of the Operational Research Society, vol. 53, no. 5, pp. 512-522, 2002.

[5] Dorling K., Heinrichs J., Messier G., and Magierowsk S., “Vehicle Routing Problems for Drone Delivery,” IEEE Transactions on Systems, Man, and Cybernetics: Systems, vol. 47, no. 1, pp. 70-85, 2016. DOI: 10.1109/TSMC.2016.2582745 794 The International Arab Journal of Information Technology, Vol. 20, No. 5, September 2023

[6] Erdoğan G., “An Open Source Spreadsheet Solver for Vehicle Routing Problems,” Computers and Operations Research, vol. 84, pp. 62-72, 2017.

[7] Guerrero J. and Bestaoui Y., “UAV Path Planning for Structure Inspection in Windy Environments,” Journal of Intelligent and Robotic Systems, vol. 69, no. 1-4, pp. 297-311, 2013. DOI:10.1007/s10846-012-9778-2

[8] Guerrero J., Escareño J., and Bestaoui Y., “Quad- rotor MAV Trajectory Planning in Wind Fields,” in Proceedings of the IEEE International Conference on Robotics and Automation, Karlsruhe, pp. 778-783, 2013. DOI: 10.1109/ICRA.2013.6630661

[9] Ha Q., Deville Y., Pham Q., and Hà M., “On the Min-cost Traveling Salesman Problem with Drone,” Transportation Research Part C: Emerging Technologies, vol. 86, pp. 597-621, 2018.

[10] Holland J., Adaptation in Natural and Artificial Systems, The MIT Press, 1992. on-in-natural-and-artificial-systems/

[11] Hwang M., Cha H., and Jung S., “Practical Endurance Estimation for Minimizing Energy Consumption of Multirotor Unmanned Aerial Vehicles,” Energies, vol. 11, no. 9, pp. 2221, 2018.

[12] Keenan P., Panadero J., Juan A., Martí R., McGarraghy S., “A Strategic Oscillation Simheuristic for the Time Capacitated Arc Routing Problem with Stochastic Demands,” Computers and Operations Research, vol. 133, pp. 105377, 2021.

[13] Khoufi I., Laouiti A., and Adjih C., “A Survey of Recent Extended Variants of the Traveling Salesman and Vehicle Routing Problems for Unmanned Aerial Vehicles,” Drones, vol. 3, no. 3, pp. 66, 2019.

[14] Kim H., Lim D., and Yee K., “Flight Control Simulation and Battery Performance Analysis of a Quadrotor under Wind Gust,” in Proceedings of the International Conference on Unmanned Aircraft Systems, Athens, pp. 1782-1791, 2020. DOI: 10.1109/ICUAS48674.2020.9214058

[15] Laporte G., “The Vehicle Routing Problem: An Overview of Exact and Approximate Algorithms,” European Journal of Operational Research, vol. 59, no. 3, pp. 345-358, 1992.

[16] Lei Y. and Wang H., “Aerodynamic Performance of a Quadrotor MAV Considering the Horizontal Wind,” IEEE Access, vol. 8, pp. 109421-109428, 2020. DOI: 10.1109/ACCESS.2020.3002706

[17] Luo H., Liang Z., Zhu M., Hu X., and Wang G., “Integrated Optimization of Unmanned Aerial Vehicle Task Allocation and Path Planning Under Steady Wind,” Plos One, vol. 13, no. 3, pp. 1-24, 2018.

[18] Mohanta J., Parhi D., and Patel S., “Path Planning Strategy for Autonomous Mobile Robot Navigation Using Petri-GA Optimisation,” Computers and Electrical Engineering, vol. 37, no. 6, pp. 1058-1070, 2011. 07

[19] Murray C. and Chu A., “The Flying Sidekick Traveling Salesman Problem: Optimization of Drone-assisted Parcel Delivery,” Transportation Research Part C: Emerging Technologies, vol. 54, pp. 86-109, 2015.

[20] Müdürlüğü Meteoroloji Genel,, Last Visited, 2021.

[21] Palomaki R., Rose N., Bossche M., Sherman T., and De Wekker S., “Wind Estimation in the Lower Atmosphere Using Multirotor Aircraft,” Journal of Atmospheric and Oceanic Technology, vol. 34, no. 5, pp. 1183-1191, 2017. DOI: 10.1175/JTECH-D-16-0177.1

[22] Pinto V., Galvão R., Rodrigues L., and Gomes J., “Mission Planning for Multiple UAVs in a Wind Field with Flight Time Constraints,” Journal of Control, Automation and Electrical Systems, vol. 31, no. 4, pp. 959-969, 2020. DOI:10.1007/s40313-020-00609-5

[23] Qu Y., Wu X., Xiao B., and Wang K., “Dynamic Modeling and Control of Small-size Quadrotor Considering Wind Field Disturbance,” in Proceedings of the Chinese Control and Decision Conference, Nanchang, pp. 937-942, 2019. DOI: 10.1109/CCDC.2019.8833065

[24] Rojas Viloria D., Solano-Charris E., Muñoz- Villamizar A., and Montoya-Torres J., “Unmanned Aerial Vehicles/Drones in Vehicle Routing Problems: A Literature Review,” International Transactions in Operational Research, vol. 28, no. 4, pp. 1626-1657, 2021.

[25] Saripalli S., Montgomery J., and Sukhatme G., “Visually Guided Landing of an Unmanned Aerial Vehicle,” IEEE Transactions on Robotics and Automation, vol. 19, no. 3, pp. 371-380, 2003. DOI: 10.1109/TRA.2003.810239

[26] Selecký M., Váňa P., Rollo M., and Meiser T., “Wind Corrections in Flight Path Planning,” International Journal of Advanced Robotic Systems, vol. 10, no. 5, pp. 248, 2013.

[27] Shakhatreh H., Sawalmeh A., Al-Fuqaha A., Dou Z., Almaita I., Othman N., Khreishah A., and Optimization of Quadrotor Route Planning with Time ... 795 Guizani M.,“Unmanned Aerial Vehicles (UAVs): A Survey on Civil Applications and Key Research Challenges,” IEEE Access, vol. 7, pp. 48572-48634, 2019. DOI: 10.1109/ACCESS.2019.2909530

[28] Shokouhifar M., Jalali A., and Torfehnejad H., “Optimal Routing in Traveling Salesman Problem using Artificial Bee Colony and Simulated Annealing,” in Proceedings of the 1st National Road ITS Congress, Tehran, pp. 1-6, 2015.

[29] Sivanandam S. and Deepa S., Introduction to Genetic Algorithms, Springer, 2008. DOI:10.1007/978-3-540-73190-0

[30] Sydney N., Smyth B., and Paley D., “Dynamic Control of Autonomous Quadrotor Flight in an Estimated Wind Field,” in Proceedings of the 52nd IEEE Conference on Decision and Control, Firenze, pp. 3609-3616, 2013. DOI: 10.1109/CDC.2013.6760438

[31] Techy L. and Woolsey C., “Minimum-Time Path Planning for Unmanned Aerial Vehicles In Steady Uniform Winds,” Journal of Guidance, Control, and Dynamics, vol. 32, no. 6, pp. 1736- 1746, 2009.

[32] Thibbotuwawa A., Nielsen P., Zbigniew B., and Bocewicz G., “Energy Consumption in Unmanned Aerial Vehicles: A Review of Energy Consumption Models and Their Relation to the UAV Routing,” in Proceedings of the 39th International Conference Information Systems Architecture and Technology, Nysa, pp. 173-184, 2018. DOI:10.1007/978-3-319-99996-8_16

[33] Thibbotuwawa A., Bocewicz G., Nielsen P., and Banaszak Z., “Unmanned Aerial Vehicle Routing Problems: A Literature Review,” Applied Sciences, vol. 10, no. 13, pp. 4504, 2020.

[34] Toth P. and Vigo D., The Vehicle Routing Problem, SIAM, 2002.

[35] Tran N., Bulka E., and Nahon M., “Quadrotor Control in a Wind Field,” in Proceedings of the International Conference on Unmanned Aircraft Systems, Colorado, pp. 320-328, 2015. DOI: 10.1109/ICUAS.2015.7152306

[36] Ware J. and Roy N., “An Analysis of Wind Field Estimation and Exploitation for Quadrotor Flight in the Urban Canopy Layer,” in Proceedings of the IEEE International Conference on Robotics and Automation, Stockholm, pp. 1507-1514, 2016. DOI: 10.1109/ICRA.2016.7487287

[37] Zafar Z., Awais M., Jalee A., and Majeed F., “A Distributed Framework of Autonomous Drones for Planning and Execution of Relief Operations during Flood Situations,” The International Arab Journal of Information Technology, vol. 18, no. 1, pp. 16-24, 2021.

[38] Zhang J., Campbell J., Sweeney D., and Hupman A., “Energy Consumption Models for Delivery Drones: A Comparison and Assessment,” Transportation Research Part D: Transport and Environment, vol. 90, pp. 102668, 2021.