Efficient 3D Path Planning for Drone Swarm Using Improved Sine Cosine Algorithm
Abstract
Path planning is one of the most important steps in the navigation and control of swarm of drones. It is primarily concerned with avoiding collision among drones and environmental obstacles while determining the most efficient flight path to the region of interest. Whenever there is a high density and complex mission, path planning becomes the most challenging and indispensable task. The problem of path planning is not only relevant to finding the optimum path from the start point to the destination point but also to provide a mechanism for preventing collisions on the path. Hence, an appropriate algorithm is needed to plan the optimal path for the swarm of drones. This paper proposes an efficient methodology for drone swarm path planning problems in 3D environments. An improved population-based meta-heuristic algorithm, Sine Cosine Algorithm (SCA), has been proposed to solve this problem. As part of the improvements, the population of SCA is initialized using a chaotic map, and a non-linearly decreasing step size is used to balance the local and global search. In addition, a convergence factor is employed to increase the convergence rate of the original SCA. The performance of the proposed improved SCA (iSCA) is tested over the drone swarm path planning problem, and the results are compared with those of the original SCA, and other state-of-the-art meta-heuristic algorithms. The experimental results show that the drone swarm 3D path planning problem can be efficiently handled with the proposed improved SCA.
References
[1]
Mozaffari M, Saad W, Bennis M, Debbah M. December. Drone small cells in the clouds: design, deployment and performance analysis. In: 2015 IEEE global communications conference (GLOBECOM). IEEE;2015. pp. 1–6.
[2]
Valavanis KP and Vachtsevanos GJ Handbook of unmanned aerial vehicles 2015 Dordrecht Springer
[3]
Al-Hourani A, Kandeepan S, and Lardner S Optimal LAP altitude for maximum coverage IEEE Wirel Commun Lett 2014 3 6 569-572
[4]
Gharibi M, Boutaba R, and Waslander SL Internet of drones IEEE Access 2016 4 1148-1162
[5]
Huo L, Zhu J, Wu G, and Li Z A novel simulated annealing based strategy for balanced UAV task assignment and path planning Sensors 2020 20 17 4769
[6]
Ma Y, Hu M, and Yan X Multi-objective path planning for unmanned surface vehicle with currents effects ISA Trans 2018 75 137-156
[7]
YongBo C, YueSong M, JianQiao Y, XiaoLong S, and Nuo X Three-dimensional unmanned aerial vehicle path planning using modified wolf pack search algorithm Neurocomputing 2017 266 445-457
[8]
Pehlivanoglu YV A new vibrational genetic algorithm enhanced with a Voronoi diagram for path planning of autonomous UAV Aerosp Sci Technol 2012 16 1 47-55
[9]
Bayili S and Polat F Limited-damage A*: a path search algorithm that considers damage as a feasibility criterion Knowl Based Syst 2011 24 4 501-512
[10]
Baumann M, Leonard S, Croft EA, and Little JJ Path planning for improved visibility using a probabilistic road map IEEE Trans Robot 2010 26 1 195-200
[11]
Brubaker MA, Geiger A, and Urtasun R Map-based probabilistic visual self-localization IEEE Trans Pattern Anal Mach Intell 2015 38 4 652-665
[12]
Kothari M and Postlethwaite I A probabilistically robust path planning algorithm for UAVs using rapidly-exploring random trees J Intell Robot Syst 2013 71 2 231-253
[13]
Moon CB and Chung W Kinodynamic planner dual-tree RRT (DT-RRT) for two-wheeled mobile robots using the rapidly exploring random tree IEEE Trans Ind Electron 2014 62 2 1080-1090
[14]
Chen Y, Yu J, Su X, and Luo G Path planning for multi-UAV formation J Intell Robot Syst 2015 77 1 229-246
[15]
Chen YB, Luo GC, Mei YS, Yu JQ, and Su XL UAV path planning using artificial potential field method updated by optimal control theory Int J Syst Sci 2016 47 6 1407-1420
[16]
Zhang X and Duan H An improved constrained differential evolution algorithm for unmanned aerial vehicle global route planning Appl Soft Comput 2015 26 270-284
[17]
Besada-Portas E, de la Torre L, Jesus M, and de Andrés-Toro B Evolutionary trajectory planner for multiple UAVs in realistic scenarios IEEE Trans Robot 2010 26 4 619-634
[18]
Zheng C, Li L, Xu F, Sun F, and Ding M Evolutionary route planner for unmanned air vehicles IEEE Trans Robot 2005 21 4 609-620
[19]
Ma Y, Zamirian M, Yang Y, Xu Y, and Zhang J Path planning for mobile objects in four-dimension based on particle swarm optimization method with penalty function Math Probl Eng 2013
[20]
Ma Y, Hu M, and Yan X Multi-objective path planning for unmanned surface vehicle with currents effects ISA Trans 2018 75 137-156
[21]
Ma H, Shen S, Yu M, Yang Z, Fei M, and Zhou H Multi-population techniques in nature inspired optimization algorithms: a comprehensive survey Swarm Evol Comput 2019 44 365-387
[22]
Zhao Y, Zheng Z, and Liu Y Survey on computational-intelligence-based UAV path planning Knowl Based Syst 2018 158 54-64
[23]
Roberge V, Tarbouchi M, and Labonté G Comparison of parallel genetic algorithm and particle swarm optimization for real-time UAV path planning IEEE Trans Ind Inf 2012 9 1 132-141
[24]
Karaboga D and Basturk B A powerful and efficient algorithm for numerical function optimization: artificial bee colony (ABC) algorithm J Glob Optim 2007 39 3 459-471
[25]
Dorigo M, Birattari M, and Stutzle T Ant colony optimization IEEE Comput Intell Mag 2006 1 4 28-39
[26]
Konatowsłiowski P. Ant colony optimization algorithm for UAV path planning. In: 2018 14th International conference on advanced trends in radio electronics, telecommunications and computer engineering (TCSET). IEEE;2018. pp. 177–182.
[27]
Price KV. Differential evolution: a fast and simple numerical optimizer. In: Proceedings of North American fuzzy information processing. IEEE;1996. pp. 524–527.
[28]
Pan JS, Liu N, and Chu SC A hybrid differential evolution algorithm and its application in unmanned combat aerial vehicle path planning IEEE Access 2020 8 17691-17712
[29]
James K, Russell E. Particle swarm optimization. In: Proceedings of ICNN’95-international conference on neural networks, vol. 4. IEEE;1995.
[30]
Bansal JC et al. Spider monkey optimization algorithm for numerical optimization Memet Comput 2014 6 1 31-47
[31]
Mirjalili S SCA: a sine cosine algorithm for solving optimization problems Knowl Based Syst 2016 96 120-133
[32]
Gupta S and Deep K Improved sine cosine algorithm with crossover scheme for global optimization Knowl Based Syst 2019 165 374-406
[33]
Nayak DR et al. Combining extreme learning machine with modified sine cosine algorithm for detection of pathological brain Comput Electr Eng 2018 68 366-380
[34]
Elaziz A, Mohamed DO, and Xiong S An improved opposition-based sine cosine algorithm for global optimization Expert Syst Appl 2017 90 484-500
[35]
Duan H and Qiao P Pigeon-inspired optimization: a new swarm intelligence optimizer for air robot path planning Int J Intell Comput Cybern 2014 7 24-37
[36]
Wang G, Guo L, Duan H, Liu L, and Wang H A modified firefly algorithm for UCAV path planning Int J Hybrid Inf Technol 2012 5 3 123-144
[37]
Zhu W and Duan H Chaotic predator–prey biogeography-based optimization approach for UCAV path planning Aerosp Sci Technol 2014 32 1 153-161
[38]
Ahmed G, Sheltami T, Mahmoud A, and Yasar A IoD swarms collision avoidance via improved particle swarm optimization Transp Res Part A Policy Pract 2020 142 260-278
[39]
Weisstein EW. Hemisphere. 2002. https://mathworld.wolfram.com/.
[40]
Yang P, Tang K, Lozano JA, and Cao X Path planning for single unmanned aerial vehicle by separately evolving waypoints IEEE Trans Robot 2015 31 5 1130-1146
[41]
Gupta S Enhanced sine cosine algorithm with crossover: a comparative study and empirical analysis Expert Syst Appl 2022 198 116856
[42]
Shao S, Peng Y, He C, and Du Y Efficient path planning for UAV formation via comprehensively improved particle swarm optimization ISA Trans 2020 97 415-430
[43]
Tian D and Shi Z MPSO: modified particle swarm optimization and its applications Swarm Evol Comput 2018 41 49-68
Recommendations
Ant colony based path planning for swarm robots
AIR '15: Proceedings of the 2015 Conference on Advances In RoboticsA Swarm Robotic System consists of a number of robots working together and coordinating like a team. In these systems, the real time navigation and coordination throughout the workspace is the major task and path planning for swarm robots plays a major ...
Application of Improved Particle Swarm Optimization Algorithm in UCAV Path Planning
AICI '09: Proceedings of the International Conference on Artificial Intelligence and Computational IntelligenceFor the calculation complexity and the convergence in Unmanned Combat Aerial Vehicle (UCAV) path planning, the path planning method based on Second-order Oscillating Particle Swarm Optimization (SOPSO) was proposed to improve the properties of solutions,...
Optimal path planning for drones based on swarm intelligence algorithm
AbstractRecently, Drones and UAV research were becoming one of the interest topics for academia and industry, where it has been extensively addressed in the literature back the few years. Path planning of drones in an area with complex terrain or unknown ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
© The Author(s), under exclusive licence to Springer Nature Singapore Pte Ltd 2024. Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 24 February 2024
Accepted: 03 January 2024
Received: 29 September 2023
Author Tags
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 21 Dec 2024