[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Log in

Efficient 3D Path Planning for Drone Swarm Using Improved Sine Cosine Algorithm

  • Original Research
  • Published:
SN Computer Science Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Algorithm 1
Algorithm 2
Algorithm 3
Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14
Fig. 15

Similar content being viewed by others

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, Vachtsevanos GJ, editors. Handbook of unmanned aerial vehicles, vol. 1. Dordrecht: Springer; 2015.

    Google Scholar 

  3. Al-Hourani A, Kandeepan S, Lardner S. Optimal LAP altitude for maximum coverage. IEEE Wirel Commun Lett. 2014;3(6):569–72.

    Article  Google Scholar 

  4. Gharibi M, Boutaba R, Waslander SL. Internet of drones. IEEE Access. 2016;4:1148–62.

    Article  Google Scholar 

  5. Huo L, Zhu J, Wu G, Li Z. A novel simulated annealing based strategy for balanced UAV task assignment and path planning. Sensors. 2020;20(17):4769.

    Article  ADS  PubMed  PubMed Central  Google Scholar 

  6. Ma Y, Hu M, Yan X. Multi-objective path planning for unmanned surface vehicle with currents effects. ISA Trans. 2018;75:137–56.

    Article  PubMed  Google Scholar 

  7. YongBo C, YueSong M, JianQiao Y, XiaoLong S, Nuo X. Three-dimensional unmanned aerial vehicle path planning using modified wolf pack search algorithm. Neurocomputing. 2017;266:445–57.

    Article  Google Scholar 

  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.

    Article  Google Scholar 

  9. Bayili S, Polat F. Limited-damage A*: a path search algorithm that considers damage as a feasibility criterion. Knowl Based Syst. 2011;24(4):501–12.

    Article  Google Scholar 

  10. Baumann M, Leonard S, Croft EA, Little JJ. Path planning for improved visibility using a probabilistic road map. IEEE Trans Robot. 2010;26(1):195–200.

    Article  Google Scholar 

  11. Brubaker MA, Geiger A, Urtasun R. Map-based probabilistic visual self-localization. IEEE Trans Pattern Anal Mach Intell. 2015;38(4):652–65.

    Article  Google Scholar 

  12. Kothari M, Postlethwaite I. A probabilistically robust path planning algorithm for UAVs using rapidly-exploring random trees. J Intell Robot Syst. 2013;71(2):231–53.

    Article  Google Scholar 

  13. Moon CB, 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–90.

    Article  Google Scholar 

  14. Chen Y, Yu J, Su X, Luo G. Path planning for multi-UAV formation. J Intell Robot Syst. 2015;77(1):229–46.

    Article  Google Scholar 

  15. Chen YB, Luo GC, Mei YS, Yu JQ, Su XL. UAV path planning using artificial potential field method updated by optimal control theory. Int J Syst Sci. 2016;47(6):1407–20.

    Article  MathSciNet  Google Scholar 

  16. Zhang X, Duan H. An improved constrained differential evolution algorithm for unmanned aerial vehicle global route planning. Appl Soft Comput. 2015;26:270–84.

    Article  Google Scholar 

  17. Besada-Portas E, de la Torre L, Jesus M, de Andrés-Toro B. Evolutionary trajectory planner for multiple UAVs in realistic scenarios. IEEE Trans Robot. 2010;26(4):619–34.

    Article  Google Scholar 

  18. Zheng C, Li L, Xu F, Sun F, Ding M. Evolutionary route planner for unmanned air vehicles. IEEE Trans Robot. 2005;21(4):609–20.

    Article  Google Scholar 

  19. Ma Y, Zamirian M, Yang Y, Xu Y, Zhang J. Path planning for mobile objects in four-dimension based on particle swarm optimization method with penalty function. Math Probl Eng. 2013. https://doi.org/10.1155/2013/613964.

    Article  Google Scholar 

  20. Ma Y, Hu M, Yan X. Multi-objective path planning for unmanned surface vehicle with currents effects. ISA Trans. 2018;75:137–56.

    Article  PubMed  Google Scholar 

  21. Ma H, Shen S, Yu M, Yang Z, Fei M, Zhou H. Multi-population techniques in nature inspired optimization algorithms: a comprehensive survey. Swarm Evol Comput. 2019;44:365–87.

    Article  Google Scholar 

  22. Zhao Y, Zheng Z, Liu Y. Survey on computational-intelligence-based UAV path planning. Knowl Based Syst. 2018;158:54–64.

    Article  Google Scholar 

  23. Roberge V, Tarbouchi M, 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–41.

    Article  Google Scholar 

  24. Karaboga D, Basturk B. A powerful and efficient algorithm for numerical function optimization: artificial bee colony (ABC) algorithm. J Glob Optim. 2007;39(3):459–71.

    Article  MathSciNet  Google Scholar 

  25. Dorigo M, Birattari M, Stutzle T. Ant colony optimization. IEEE Comput Intell Mag. 2006;1(4):28–39.

    Article  Google Scholar 

  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, Chu SC. A hybrid differential evolution algorithm and its application in unmanned combat aerial vehicle path planning. IEEE Access. 2020;8:17691–712.

    Article  Google Scholar 

  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.

    Article  MathSciNet  Google Scholar 

  31. Mirjalili S. SCA: a sine cosine algorithm for solving optimization problems. Knowl Based Syst. 2016;96:120–33.

    Article  Google Scholar 

  32. Gupta S, Deep K. Improved sine cosine algorithm with crossover scheme for global optimization. Knowl Based Syst. 2019;165:374–406.

    Article  Google Scholar 

  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–80.

    Article  Google Scholar 

  34. Elaziz A, Mohamed DO, Xiong S. An improved opposition-based sine cosine algorithm for global optimization. Expert Syst Appl. 2017;90:484–500.

    Article  Google Scholar 

  35. Duan H, Qiao P. Pigeon-inspired optimization: a new swarm intelligence optimizer for air robot path planning. Int J Intell Comput Cybern. 2014;7:24–37.

    Article  MathSciNet  Google Scholar 

  36. Wang G, Guo L, Duan H, Liu L, Wang H. A modified firefly algorithm for UCAV path planning. Int J Hybrid Inf Technol. 2012;5(3):123–44.

    Google Scholar 

  37. Zhu W, Duan H. Chaotic predator–prey biogeography-based optimization approach for UCAV path planning. Aerosp Sci Technol. 2014;32(1):153–61.

    Article  Google Scholar 

  38. Ahmed G, Sheltami T, Mahmoud A, Yasar A. IoD swarms collision avoidance via improved particle swarm optimization. Transp Res Part A Policy Pract. 2020;142:260–78.

    Article  Google Scholar 

  39. Weisstein EW. Hemisphere. 2002. https://mathworld.wolfram.com/.

  40. Yang P, Tang K, Lozano JA, Cao X. Path planning for single unmanned aerial vehicle by separately evolving waypoints. IEEE Trans Robot. 2015;31(5):1130–46.

    Article  Google Scholar 

  41. Gupta S. Enhanced sine cosine algorithm with crossover: a comparative study and empirical analysis. Expert Syst Appl. 2022;198:116856.

    Article  Google Scholar 

  42. Shao S, Peng Y, He C, Du Y. Efficient path planning for UAV formation via comprehensively improved particle swarm optimization. ISA Trans. 2020;97:415–30.

    Article  PubMed  Google Scholar 

  43. Tian D, Shi Z. MPSO: modified particle swarm optimization and its applications. Swarm Evol Comput. 2018;41:49–68.

    Article  Google Scholar 

Download references

Acknowledgements

Author Jagdish Chand Bansal acknowledges the funding from Liverpool Hope University UK.

Author information

Authors and Affiliations

Authors

Contributions

PP: Conceptualization, methodology, writing original draft. KP, AN: Review, JCB: Supervision, review.

Corresponding author

Correspondence to Jagdish Chand Bansal.

Ethics declarations

Conflict of interest

The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.

Ethical approval

This article does not contain any studies with human participants or animals performed by any of the authors.

Informed consent

Informed consent was obtained from all individual participants included in the study.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

This article is part of the topical collection “Emerging Applications of Data Science for Real-World Problems” guest edited by Satyasai Jagannath Nanda, Rajendra Prasad Yadav and Mukesh Saraswat.

Rights and permissions

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.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Pachung, P., Pandya, K., Nagar, A. et al. Efficient 3D Path Planning for Drone Swarm Using Improved Sine Cosine Algorithm. SN COMPUT. SCI. 5, 286 (2024). https://doi.org/10.1007/s42979-024-02605-x

Download citation

  • Received:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s42979-024-02605-x

Keywords

Navigation