(Universitas Katolik Indonesia Atma Jaya, Indonesia)(2) * Gregorius Airlangga
(Universitas Katolik Indonesia Atma Jaya, Indonesia)(3) Widodo Widjaja Basuki
(Universitas Katolik Indonesia Atma Jaya, Jakarta, Indonesia)(4) Yoel Kristian
(Universitas Katolik Indonesia Atma Jaya, Indonesia)(5) Radyan Rahmananta
(Universitas Katolik Indonesia Atma Jaya, Indonesia)(6) Lai Ferry Sugianto
(Fujen Catholic University, Taiwan)(7) Oskar Ika Adi Nugroho
(National Chung Cheng University, Taiwan)*corresponding author
AbstractThis study evaluates the performance of various path planning algorithms for multi-UAV systems in dynamic and cluttered environments, focusing on critical metrics such as path length, path smoothness, collision avoidance, and computational efficiency. We examined several algorithms, including A*, Genetic Algorithm, Modified A*, and Particle Swarm Optimization (PSO), using comprehensive simulations that reflect realistic operational conditions. Key evaluation metrics were quantified using standardized methods, ensuring the reproducibility and clarity of the findings. The A* Path Planner demonstrated efficiency by producing the shortest and smoothest paths, albeit with minor collision avoidance limitations. The Genetic Algorithm emerged as the most robust, balancing path length, smoothness, and collision avoidance, with zero violations and high feasibility. Modified A* also performed well but exhibited slightly less smooth paths. In contrast, algorithms like Cuckoo Search and Artificial Immune System faced significant performance challenges, especially in adapting to dynamic environments. Our findings highlight the superior performance of the Genetic Algorithm and Modified A* under these specific conditions. We also discuss the potential for hybrid approaches that combine the strengths of these algorithms for even better performance. This study's insights are critical for practitioners looking to optimize multi-UAV systems in challenging scenarios.
KeywordsUAV; Path Planning; Rural; Comparative
|
DOIhttps://doi.org/10.31763/ijrcs.v4i4.1555 |
Article metrics10.31763/ijrcs.v4i4.1555 Abstract views : 729 | PDF views : 216 |
Cite |
Full Text Download
|
References
[1] N. Mohamed, J. Al-Jaroodi, F. Mohammed, I. Jawhar, A. Idries, F. Mohammed, “Unmanned aerial vehicles applications in future smart cities,†Technological Forecasting and Social Change, vol. 153, p. 119293, 2020, https://doi.org/10.1016/j.techfore.2018.05.004.
[2] N. S. Labib, M. R. Brust, G. Danoy and P. Bouvry, “The Rise of Drones in Internet of Things: A Survey on the Evolution, Prospects and Challenges of Unmanned Aerial Vehicles,†IEEE Access, vol. 9, pp. 115466-115487, 2021, https://doi.org/10.1109/ACCESS.2021.3104963.
[3] F. Ahmed, J. C. Mohanta, A. Keshari, and P. S. Yadav, “Recent advances in unmanned aerial vehicles: a review,†Arabian Journal for Science and Engineering, vol. 47, pp. 7963-7984, 2022, https://doi.org/10.1007/s13369-022-06738-0.
[4] A. Chamuah and R. Singh, “Responsible governance of civilian unmanned aerial vehicle (UAV) innovations for Indian crop insurance applications,†Journal of Responsible Technology, vol. 9, p. 100025, 2022, https://doi.org/10.1016/j.jrt.2022.100025.
[5] D. Mourtzis, J. Angelopoulos, and N. Panopoulos, “Unmanned Aerial Vehicle (UAV) manipulation assisted by Augmented Reality (AR): The case of a drone,†IFAC-PapersOnLine, vol. 55, no. 10, pp. 983-988, 2022, https://doi.org/10.1016/j.ifacol.2022.09.483.
[6] S. A. H. Mohsan, M. A. Khan, F. Noor, I. Ullah, and M. H. Alsharif, “Towards the unmanned aerial vehicles (UAVs): A comprehensive review,†Drones, vol. 6, no. 6, p. 147, 2022, https://doi.org/10.3390/drones6060147.
[7] S. Demir, M. Dedeouglu, and L. Bacsayiugit, “Yield prediction models of organic oil rose farming with agricultural unmanned aerial vehicles (UAVs) images and machine learnaing algorithms,†Remote Sensing Applications: Society and Environment, vol. 33, p. 101131, 2024, https://doi.org/10.1016/j.rsase.2023.101131.
[8] M. A. Istiak et al., “Adoption of Unmanned Aerial Vehicle (UAV) imagery in agricultural management: A systematic literature review,†Ecological Informatics, vol. 78, p. 102305, 2023, https://doi.org/10.1016/j.ecoinf.2023.102305.
[9] G. Wang et al., “Field evaluation of spray drift and environmental impact using an agricultural unmanned aerial vehicle (UAV) sprayer,†Science of The Total Environment, vol. 737, p. 139793, 2020, https://doi.org/10.1016/j.scitotenv.2020.139793
[10] P. Joshi, K. S. Sandhu, G. S. Dhillon, J. Chen, and K. Bohara, “Detection and monitoring wheat diseases using unmanned aerial vehicles (UAVs),†Computers and Electronics in Agriculture, vol. 224, p. 109158, 2024, https://doi.org/10.1016/j.compag.2024.109158.
[11] A. Otto, N. Agatz, J. Campbell, B. Golden, and E. Pesch, “Optimization approaches for civil applications of unmanned aerial vehicles (UAVs) or aerial drones: A survey,†Networks, vol. 72, no. 4, pp. 411-458, 2018, https://doi.org/10.1002/net.21818.
[12] H. Puppala, P. R. T. Peddinti, J. P. Tamvada, J. Ahuja, and B. Kim, “Barriers to the adoption of new technologies in rural areas: The case of unmanned aerial vehicles for precision agriculture in India,†Technology in Society, vol. 74, p. 102335, 2023, https://doi.org/10.1016/j.techsoc.2023.102335.
[13] Y. Liu, H.-N. Dai, Q. Wang, M. K. Shukla, and M. Imran, “Unmanned aerial vehicle for internet of everything: Opportunities and challenges,†Computer Communications, vol. 155, pp. 66-83, 2020, https://doi.org/10.1016/j.comcom.2020.03.017.
[14] M. A. Radi, M. N. AlMallahi, A. S. Al-Sumaiti, C. Semeraro, M. A. Abdelkareem, and A. G. Olabi, “Progress in artificial intelligence-based visual servoing of autonomous unmanned aerial vehicles (UAVs),†International Journal of Thermofluids, vol. 21, p. 100590, 2024, https://doi.org/10.1016/j.ijft.2024.100590.
[15] I. Khoufi, A. Laouiti, and C. Adjih, “A survey of recent extended variants of the traveling salesman and vehicle routing problems for unmanned aerial vehicles,†Drones, vol. 3, no. 3, p. 66, 2019, https://doi.org/10.3390/drones3030066.
[16] P. Du, X. He, H. Cao, S. Garg, G. Kaddoum, and M. M. Hassan, “AI-based energy-efficient path planning of multiple logistics UAVs in intelligent transportation systems,†Computer Communications, vol. 207, pp. 46-55, 2023, https://doi.org/10.1016/j.comcom.2023.04.032.
[17] H. Lee and C. Lee, “Research on logistics of intelligent unmanned aerial vehicle integration system,†Journal of Industrial Information Integration, vol. 36, p. 100534, 2023, https://doi.org/10.1016/j.jii.2023.100534.
[18] H. Lee, “Research on multi-functional logistics intelligent Unmanned Aerial Vehicle,†Engineering Applications of Artificial Intelligence, vol. 116, p. 105341, 2022, https://doi.org/10.1016/j.engappai.2022.105341.
[19] R. A. Saeed, M. Omri, S. Abdel-Khalek, E. S. Ali, and M. F. Alotaibi, “Optimal path planning for drones based on swarm intelligence algorithm,†Neural Computing and Applications, vol. 34, pp. 10133-10155, 2022, https://doi.org/10.1007/s00521-022-06998-9.
[20] L. Liu, X. Wang, X. Yang, H. Liu, J. Li, and P. Wang, “Path planning techniques for mobile robots: Review and prospect,†Expert Systems with Applications, vol. 227, p. 120254, 2023, https://doi.org/10.1016/j.eswa.2023.120254.
[21] Y. Zhu, G. Zhang, R. Chu, H. Xiao, Y. Yang, and X. Wu, “Research on escape route planning analysis in forest fire scenes based on the improved A* algorithm,†Ecological Indicators, vol. 166, p. 112355, 2024, https://doi.org/10.1016/j.ecolind.2024.112355.
[22] M. G. Mohanan and A. Salgoankar, “A survey of robotic motion planning in dynamic environments,†Robotics and Autonomous Systems, vol. 100, pp. 171-185, 2018, https://doi.org/10.1016/j.robot.2017.10.011.
[23] S. MahmoudZadeh, A. Yazdani, Y. Kalantari, B. Ciftler, F. Aidarus, and M. O. A. Kadri, “Holistic Review of UAV-Centric Situational Awareness: Applications, Limitations, and Algorithmic Challenges,†Robotics, vol. 13, no. 8, p. 117, 2024, https://doi.org/10.3390/robotics13080117.
[24] V. C. S. S and A. H. S, “Nature inspired meta heuristic algorithms for optimization problems,†Computing, vol. 104, pp. 251-269, 2022, https://doi.org/10.1007/s00607-021-00955-5.
[25] T. M. Shami, A. A. El-Saleh, M. Alswaitti, Q. Al-Tashi, M. A. Summakieh and S. Mirjalili, “Particle Swarm Optimization: A Comprehensive Survey,†IEEE Access, vol. 10, pp. 10031-10061, 2022, https://doi.org/10.1109/ACCESS.2022.3142859.
[26] C. Wang, S. Zhang, T. Ma, Y. Xiao, M. Z. Chen, Lei Wang, “Swarm intelligence: A survey of model classification and applications,†Chinese Journal of Aeronautics, 2024, https://doi.org/10.1016/j.cja.2024.03.019.
[27] S. Wu, B. He, J. Zhang, C. Chen, and J. Yang, “PSAO: An enhanced Aquila Optimizer with particle swarm mechanism for engineering design and UAV path planning problems,†Alexandria Engineering Journal, vol. 106, pp. 474-504, 2024, https://doi.org/10.1016/j.aej.2024.08.021.
[28] Y. Li, L. Zhang, B. Cai, and Y. Liang, “Unified path planning for composite UAVs via Fermat point-based grouping particle swarm optimization,†Aerospace Science and Technology, vol. 148, p. 109088, 2024, https://doi.org/10.1016/j.ast.2024.109088.
[29] R. D. Goswami, S. Chakraborty, and B. Misra, “Variants of genetic algorithms and their applications,†Applied Genetic Algorithm and Its Variants, pp. 1-20, 2023, https://doi.org/10.1007/978-981-99-3428-7_1.
[30] O. Rodriguez-Abreo, J. Rodriguez-Reséndiz, A. Garcia-Cerezo, and J. R. Garcia-Martinez, “Fuzzy logic controller for UAV with gains optimized via genetic algorithm,†Heliyon, vol. 10, no. 4, p. e26363, 2024, https://doi.org/10.1016/j.heliyon.2024.e26363.
[31] Y. V. Pehlivanoglu and P. Pehlivanoglu, “An enhanced genetic algorithm for path planning of autonomous UAV in target coverage problems,†Applied Soft Computing, vol. 112, p. 107796, 2021, https://doi.org/10.1016/j.asoc.2021.107796.
[32] C. Hsu, “An adaptive simulated annealing-based computational offloading scheme in UAV-assisted MEC networks,†Computer Communications, vol. 224, pp. 118-124, 2024, https://doi.org/10.1016/j.comcom.2024.06.008.
[33] O. Ozkan, “Optimization of the distance-constrained multi-based multi-UAV routing problem with simulated annealing and local search-based matheuristic to detect forest fires: The case of Turkey,†Applied Soft Computing, vol. 113, p. 108015, 2021, https://doi.org/10.1016/j.asoc.2021.108015.
[34] M. T. R. Khan, M. M. Saad, Y. Ru, J. Seo, and D. Kim, “Aspects of unmanned aerial vehicles path planning: Overview and applications,†International Journal of Communications Systems, vol. 34, no. 10, p. e4827, 2021, https://doi.org/10.1002/dac.4827.
[35] X. Zhou, Z. Tang, N. Wang, C. Yang, and T. Huang, “A novel state transition algorithm with adaptive fuzzy penalty for multi-constraint UAV path planning,†Expert Systems with Applications, vol. 248, p. 123481, 2024, https://doi.org/10.1016/j.eswa.2024.123481.
[36] V. Garg, S. Niranjan, V. Prybutok, T. Pohlen, and D. Gligor, “Drones in last-mile delivery: A systematic review on Efficiency, Accessibility, and Sustainability,†Transportation Research Part D: Transport and Environment, vol. 123, p. 103831, 2023, https://doi.org/10.1016/j.trd.2023.103831.
[37] C. Cheng, Q. Sha, B. He, and G. Li, “Path planning and obstacle avoidance for AUV: A review,†Ocean Engineering, vol. 235, p. 109355, 2021, https://doi.org/10.1016/j.oceaneng.2021.109355.
[38] S. Aggarwal and N. Kumar, “Path planning techniques for unmanned aerial vehicles: A review, solutions, and challenges,†Computer Communications, vol. 149, pp. 270-299, 2020, https://doi.org/10.1016/j.comcom.2019.10.014.
[39] S. Poudel, M. Y. Arafat, and S. Moh, “Bio-inspired optimization-based path planning algorithms in unmanned aerial vehicles: A survey,†Sensors, vol. 23, no. 6, p. 3051, 2023, https://doi.org/10.3390/s23063051.
[40] S. Darvishpoor, A. Darvishpour, M. Escarcega, and M. Hassanalian, “Nature-inspired algorithms from oceans to space: A comprehensive review of heuristic and meta-heuristic optimization algorithms and their potential applications in drones,†Drones, vol. 7, no. 7, p. 427, 2023, https://doi.org/10.3390/drones7070427.
[41] T. N. Larsen, H. Ø. Teigen, T. Laache, D. Varagnolo, and A. Rasheed, “Comparing deep reinforcement learning algorithms’ ability to safely navigate challenging waters,†Frontiers in Robotics and AI, vol. 8, p. 738113, 2021, https://doi.org/10.3389/frobt.2021.738113.
[42] A. Paredes, “Structural Bias in Heuristic Search (Student Abstract),†Proceedings of the International Symposium on Combinatorial Search, vol. 16, no. 1, pp. 196-197, 2023, https://doi.org/10.1609/socs.v16i1.27311.
[43] C. Ziegler and J. Adamy, “Anytime Tree-Based Trajectory Planning for Urban Driving,†IEEE Open Journal of Intelligent Transportation Systems, vol. 4, pp. 48-57, 2023, https://doi.org/10.1109/OJITS.2023.3235986.
[44] M. N. A. Wahab, C. M. Lee, M. F. Akbar and F. H. Hassan, “Path Planning for Mobile Robot Navigation in Unknown Indoor Environments Using Hybrid PSOFS Algorithm,†IEEE Access, vol. 8, pp. 161805-161815, 2020, https://doi.org/10.1109/ACCESS.2020.3021605.
[45] L. Wenzheng, L. Junjun and Y. Shunli, “An Improved Dijkstra's Algorithm for Shortest Path Planning on 2D Grid Maps,†2019 IEEE 9th International Conference on Electronics Information and Emergency Communication (ICEIEC), pp. 438-441, 2019, https://doi.org/10.1109/ICEIEC.2019.8784487.
[46] S. Srivastava, “Graph Theoretic Algorithms Adaptable to Quantum Computing,†University of Michigan, 2021, https://public.websites.umich.edu/~veeras/papers/Srivastava_Thesis.pdf.
[47] H. P. Peng, N. Shen, H. Liao, H. Xue, and Q. Wang, “Uncertainty factors, methods, and solutions of closed-loop supply chain—A review for current situation and future prospects,†Journal of Cleaner Production, vol. 254, p. 120032, 2020, https://doi.org/10.1016/j.jclepro.2020.120032.
[48] X. Zhu, F. Vanegas, F. Gonzalez and C. Sanderson, “A Multi-UAV System for Exploration and Target Finding in Cluttered and GPS-Denied Environments,†2021 International Conference on Unmanned Aircraft Systems (ICUAS), pp. 721-729, 2021, https://doi.org/10.1109/ICUAS51884.2021.9476820.
[49] A. Kumar, M. Nadeem, and H. Banka, “Nature inspired optimization algorithms: a comprehensive overview,†Evolving Systems, vol. 14, pp. 141-156, 2023, https://doi.org/10.1007/s12530-022-09432-6.
[50] J. A. Abdulsaheb and D. J. Kadhim, “Classical and heuristic approaches for mobile robot path planning: A survey,†Robotics, vol. 12, no. 4, p. 93, 2023, https://doi.org/10.3390/robotics12040093.
[51] M. Shafiq, Z. A. Ali, A. Israr, E. H. Alkhammash, and M. Hadjouni, “A multi-colony social learning approach for the self-organization of a swarm of UAVs,†Drones, vol. 6, no. 5, p. 104, 2022, https://doi.org/10.3390/drones6050104.
[52] I. Hussain et al., “Optimizing energy consumption in the home energy management system via a bio-inspired dragonfly algorithm and the genetic algorithm,†Electronics, vol. 9, no. 3, p. 406, 2020, https://doi.org/10.3390/electronics9030406.
[53] R. Liu, P. Yang, and J. Liu, “A dynamic multi-objective optimization evolutionary algorithm for complex environmental changes,†Knowledge-Based Systems, vol. 216, p. 106612, 2021, https://doi.org/10.1016/j.knosys.2020.106612.
[54] K. A. Alnowibet, S. Mahdi, M. El-Alem, M. Abdelawwad, and A. W. Mohamed, “Guided hybrid modified simulated annealing algorithm for solving constrained global optimization problems,†Mathematics, vol. 10, no. 8, p. 1312, 2022, https://doi.org/10.3390/math10081312.
[55] A. Ait-Saadi, Y. Meraihi, A. Soukane, A. Ramdane-Cherif, and A. B. Gabis, “A novel hybrid chaotic Aquila optimization algorithm with simulated annealing for unmanned aerial vehicles path planning,†Computers and Electrical Engineering, vol. 104, p. 108461, 2022, https://doi.org/10.1016/j.compeleceng.2022.108461.
[56] S. Agarwal, N. Rani, and A. Vajpayee, “Bioinspired Algorithms: Opportunities and Challenges,†Bioâ€Inspired Optimization for Medical Data Mining, 2024, https://doi.org/10.1002/9781394214211.ch1.
[57] R. G. Ribeiro, L. P. Cota, T. A. M. Euzébio, J. A. RamÃrez and F. G. Guimarães, “Unmanned-Aerial-Vehicle Routing Problem With Mobile Charging Stations for Assisting Search and Rescue Missions in Postdisaster Scenarios,†IEEE Transactions on Systems, Man, and Cybernetics: Systems, vol. 52, no. 11, pp. 6682-6696, 2022, https://doi.org/10.1109/TSMC.2021.3088776.
[58] T. M. Cabreira, L. B. Brisolara, P. R. F. Jr, “Survey on coverage path planning with unmanned aerial vehicles,†Drones, vol. 3, no. 1, p. 4, 2019, https://doi.org/10.3390/drones3010004.
[59] Z. Yüksel, D. E. Epcim, and S. Mete, “First Cluster Second Route Approach with Collaboration Unmanned Aerial Vehicle in Post-Disaster Humanitarian Logistic,†Journal of Transportation and Logistics, vol. 8, no. 2, pp. 97-111, 2023, http://dx.doi.org/10.26650/JTL.2023.1372701.
[60] R. Zhang, S. Li, Y. Ding, X. Qin, and Q. Xia, “UAV path planning algorithm based on improved Harris Hawks optimization,†Sensors, vol. 22, no. 14, p. 5232, 2022, https://doi.org/10.3390/s22145232.
[61] M. M. Iqbal, Z. A. Ali, R. Khan, and M. Shafiq, “Motion planning of UAV swarm: Recent challenges and approaches,†Aeronautics - New Advances, 2022, https://doi.org/10.5772/intechopen.106270.
Refbacks
- There are currently no refbacks.
Copyright (c) 2024 Gregorius Airlangga
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
| About the Journal | Journal Policies | Author | Information |
International Journal of Robotics and Control Systems
e-ISSN: 2775-2658
Website: https://pubs2.ascee.org/index.php/IJRCS
Email: ijrcs@ascee.org
Organized by: Association for Scientific Computing Electronics and Engineering (ASCEE), Peneliti Teknologi Teknik Indonesia, Department of Electrical Engineering, Universitas Ahmad Dahlan and Kuliah Teknik Elektro
Published by: Association for Scientific Computing Electronics and Engineering (ASCEE)
Office: Jalan Janti, Karangjambe 130B, Banguntapan, Bantul, Daerah Istimewa Yogyakarta, Indonesia