A Modified Self-Adaptive Sparrow Search Algorithm for Robust Multi-UAV Path Planning

Abstract

With the advancement of technology, the collaboration of multiple unmanned aerial vehicles(multi-UAVs) is a general trend, both in military and civilian domains. Path planning is a crucial step for multi-UAV mission execution, it is a nonlinear problem with constraints. Traditional optimization algorithms have difficulty in finding the optimal solution that minimizes the cost function under various constraints. At the same time, robustness should be taken into account to ensure the reliable and safe operation of the UAVs. In this paper, a self-adaptive sparrow search algorithm(SSA), denoted as DRSSA, is presented. During optimization, a dynamic population strategy is used to allocate the searching effort between exploration and exploitation; a t-distribution perturbation coefficient is proposed to adaptively adjust the exploration range; a random learning strategy is used to help the algorithm from falling into the vicinity of the origin and local optimums. The convergence of DRSSA is tested by 29 test functions from the Institute of Electrical and Electronics Engineers(IEEE) Congress on Evolutionary Computation(CEC) 2017 benchmark suite. Furthermore, a stochastic optimization strategy is introduced to enhance safety in the path by accounting for potential perturbations. Two sets of simulation experiments on multi-UAV path planning in three-dimensional environments demonstrate that the algorithm exhibits strong optimization capabilities and robustness in dealing with uncertain situations.

Keywords

multiple unmanned aerial vehicle(multi-UAV) / path planning / sparrow search algorithm(SSA) / stochastic optimization

References

[1] PUENTE-CASTRO A, RIVERO D, PAZOS A, et al. A review of artificial intelligence applied to path planning in UAV swarms[J]. Neural Computing and Applications, 2022, 34(1):153-170.

[2] QIU H X, DUAN H B. A multi-objective pigeon-inspired optimization approach to UAV distributed flocking among obstacles[J]. Information Sciences, 2020,509:515-529.

[3] AGGARWAL S, KUMAR N. Path planning techniques for unmanned aerial vehicles:a review,solutions,and challenges[J]. Computer Communications, 2020,149:270-299.

[4] TANG J, DUAN H B, LAO S Y. Swarm intelligence algorithms for multiple unmanned aerial vehicles collaboration:a comprehensive review[J]. Artificial Intelligence Review, 2023, 56(5):4295-4327.

[5] TAN Y, DING K. A survey on GPU-based implementation of swarm intelligence algorithms[J]. IEEE Transactions on Cybernetics, 2016, 46(9):2028-2041.

[6] PENG J L, SUN X X, ZHU F, et al. 3D path planning with multi-constrains based on genetic algorithm[C]//27th Chinese Control Conference. NewYork: IEEE, 2008:94-97.

[7] SHAO S K, PENG Y, HE C L, et al. Efficient path planning for UAV formation via comprehensively improved particle swarm optimization[J]. ISA Transactions, 2020,97:415-430.

[8] DEWANGAN R K, SHUKLA A, GODFREY W W. Three dimensional path planning using grey wolf optimizer for UAVs[J]. Applied Intelligence, 2019, 49(6):2201-2217.

[9] XU C, XU M, YIN C J. Optimized multi-UAV cooperative path planning under the complex confrontation environment[J]. Computer Communications, 2020,162:196-203.

[10] ZHANG D F, DUAN H B. Social-class pigeon-inspired optimization and time stamp segmentation for multi-UAV cooperative path planning[J]. Neurocomputing, 2018,313:229-246.

[11] COLOMI A, DORIGO M, MANIEZZO V. Distributed optimization by ant colonies [C].Proceedings of the First European Conference on Artificial Life. Cambridge: MIT Press, 1991:134-142.

[12] XU H Q, XING H X, LIU Y. Path planning of UAV by combing improved ant colony system and dynamic window algorithm[J]. Journal of Donghua University (English Edition), 2023, 40 (6):676-683.

[13] KENNEDY J, EBERHART R. Particle swarm optimization[C]//Proceedings of ICNN’95 International Conference on Neural Networks. New York: IEEE, 2002:1942-1948.

[14] XUE J K, SHEN B. A novel swarm intelligence optimization approach:sparrow search algorithm[J]. Systems Science & Control Engineering, 2020, 8(1):22-34.

[15] AWADALLAH M A, AL-BETAR M A, ABU DOUSH I, et al. Recent versions and applications of sparrow search algorithm[J]. Archives of Computational Methods in Engineering, 2023, 30(5):2831-2858.

[16] KAEDI M, AHN C W. Robust optimization using Bayesian optimization algorithm:early detection of non-robust solutions[J]. Applied Soft Computing, 2017,61:1125-1138.

[17] YAN S Q, LIU W D, YANG P, et al. Optimization of UAV cooperative path planning mathematical model based on personalized multigroup sparrow search algorithm in complex environment[J]. Journal of Function Spaces, 2022,2022:2521737.

[18] HAN T, TANG A D, ZHOU H, et al. Multiple UAV cooperative path planning based on LASSA method[J]. Systems Engineering and Electronics. 2022, 44(1):233-241. (in Chinese)

[19] HO S L, YANG S Y. A fast robust optimization methodology based on polynomial chaos and evolutionary algorithm for inverse problems[J]. IEEE Transactions on Magnetics, 2012, 48(2):259-262.

[20] AWAD N H, ALI M Z, LIANG J J, et al. Problem definitions and evaluation criteria for the CEC 2017 special session and competition on single objective bound constrained real-parameter numerical optimization[D]. Singapore: Nanyang Technological University, 2016.

[21] LYU X, MU X D, ZHANG J, et al. Chaos sparrow search optimization algorithm[J]. Journal of Beijing University of Aeronautics and Astronautics, 2021, 47(8):1712-1720. (in Chinese)

Funding

National Natural Science Foundation of China(62303108)

Fundamental Research Funds for the Central Universities,China(CUSF-DH-T-2023065)