基于 Levy 飞行的动态调整策略改进 SPSO 算法无人机三维航迹规划

Dynamic adjustment strategy based on Levy flight to improve SPSO algorithm for UAV three-dimensional trajectory planning

摘要

针对三维环境中无人机航迹规划问题，在球面矢量粒子群优化算法 (Spherical vector-based particle swarm optimization algorithm, SPSO) 的基础上提出了一种新的基于 Levy 飞行的动态调整策略改进球面矢量粒子群优化算法 (Spherical vector particle swarm optimization algorithm for dynamic adjustment strategy based on Levy flight，LDS-SPSO)，以解决收敛速度慢和易陷入局部最优解的问题. 首先，将航迹规划问题转化为多约束目标优化问题，构造了基于航迹长度、障碍物威胁、平滑度和高度变化的适应度目标函数；其次，提出了学习因子动态调整策略，提升收敛速度；然后，当粒子陷入局部最优解时，引入 Levy 飞行扰动因子促使粒子迅速逃出局部最优解；最后，在三维环境下对提出的算法进行了仿真测试，在 4 个复杂度不同的数字高程三维场景下开展三维航迹规划仿真. 仿真结果验证了改进算法的性能：该算法生成的航迹在保证避障安全的前提下，航迹代价更低、质量更高、路径更平滑，具有更优的寻优精度和更快的收敛速度. 在障碍物密集的场景下，LDS-SPSO 算法相比传统的粒子群算法 (Particle Swarm Optimization, PSO)、惯性权重线性递减基于球面矢量的改进粒子群算法 (Improved Particle Swarm Optimization algorithm, IPSO) 和 SPSO 算法的最佳适应度值分别减少了 22.92%、0.51%、0.34%，平均适应度值分别减少了 31.18%、6.33%、4.54%，最差适应度值分别减少了 36.45%、16.73%、14.77%. 研究结果表明，LDS-SPSO 算法在三维航迹规划中展现出更快的收敛性、更好的稳定性和可靠性.

Abstract

To solve the trajectory planning problem of unmanned aerial vehicles in three-dimensional (3D) environments, a dynamic adjustment strategy based on Levy flight is proposed to improve the spherical vector-based particle swarm optimization (SPSO) algorithm, thus forming the SPSO algorithm based on Levy flight dynamic adjustment strategy (LDS-PSO). This algorithm balances the global and local search capabilities, and alleviates the problems of slow convergence speed and being trapped in local optima. First, the trajectory planning problem is transformed into a multi-constraint objective optimization problem, and a fitness objective function is constructed based on trajectory length, obstacle threat, smoothness, and height changes. Second, the PSO algorithm is analyzed based on spherical vectors. In the initial stage of the search, the algorithm needs to expand the search range to ensure population diversity. In the later stage, it needs to achieve rapid convergence and improve accuracy for inter-group collaboration. Therefore, a strategy for dynamically adjusting learning cognitive factors based on power exponent inertia weight factors and quadratic functions is proposed. Compared with the fixed learning cognitive factors of traditional PSO and SPSO algorithms, this strategy not only balances global and local search capabilities, but also improves the convergence speed. Third, when the difference between the fitness values of particles in adjacent iterations is smaller than a preset small constant, the particles are considered to be trapped in a local optimum. The Levy flight disturbance factor is introduced to prompt particles to quickly escape from local optima. Finally, the effectiveness and convergence speed of the algorithm in a 3D environment are evaluated through simulation testing. Based on the flight environment of drones, four 3D elevation environment models with different obstacle densities were established, and simulation experiments of 3D trajectory planning using the proposed algorithm were carried out in each environment. The simulation results validate the performance of the improved algorithm. The trajectory generated by this algorithm has a lower cost and higher quality while ensuring obstacle avoidance safety, and it exhibits better optimization accuracy and faster convergence speed. In scenarios with sparse obstacles, the performance of this algorithm is consistent with that of the SPSO algorithm. In scenarios with dense obstacles, there are differences in the fitness and convergence speed between this algorithm and the SPSO algorithm. The LDS-PSO algorithm has a lower fitness value, faster convergence speed, and smoother path compared with the SPSO algorithm. In dense obstacle scenarios, various algorithms were run repeatedly 20 times to reduce random errors. Compared with the traditional PSO, linearly decreasing inertia weight IPSO (Improved particle swarm optimization algorithm), and SPSO algorithms, the LDS-PSO algorithm has the best stability and the lowest trajectory cost. In the 20 tests, the average best fitness value of the LDS-PSO algorithm decreased by 22.92%, 0.51%, and 0.34% compared with the above three algorithms respectively; the average fitness value decreased by 31.18%, 6.33%, and 4.54% respectively; and the average worst fitness value decreased by 36.45%, 16.73%, and 14.77% respectively. The research results indicate that the LDS-PSO algorithm has faster convergence speed, better stability, and higher reliability in 3D trajectory planning.

关键词

航迹规划 / 无人机 / 粒子群算法 / 适应度函数 / 莱维飞行

Key words

trajectory planning / UAV / particle swarm optimization algorithm / fitness function / Levy flight

参考文献

[1] Li R J, Dong S G. Simulation of UAV fire extinguishing path planning based on particle swarm optimization algorithm[J]. Comput Simul, 2023, 40（9）: 43

[2] （李锐君, 董素鸽. 基于粒子群算法的无人机灭火路径规划仿真[J]. 计算机仿真, 2023, 40（9）： 43）

[3] Jiao S M, Shou Y F, Bai J P, et al. Research on hierarchical motion planning method for UAV substation inspection[J]. J Syst Simul, 2023, 35（9）: 1975

[4] （焦嵩鸣, 首云锋, 白健鹏, 等. 变电站巡检无人机分层运动规划方法研究[J]. 系统仿真学报, 2023, 35（9）： 1975）

[5] Huang Z F, Liu Y H. Low altitude path planning of urban UAV based on improved lion swarm optimization[J]. Inf Control, 2023, 52（6）: 747

[6] （黄志锋, 刘媛华. 基于改进狮群算法的城市无人机低空路径规划[J]. 信息与控制, 2023, 52（6）： 747）

[7] Wang R B, Wang W F, Geng F D, et al. UAV path planning in mountain areas based on a hybrid parallel compact arithmetic optimization algorithm[J]. Neural Comput & Applic, 2025, 37（27）: 22353

[8] Puente—Castro A, Rivero D, Pazos A, et al. A review of artificial intelligence applied to path planning in UAV swarms[J]. Neural Comput & Applic, 2022, 34（1）: 153

[9] Mandloi D, Arya R, Verma A K. Unmanned aerial vehicle path planning based on A* algorithm and its variants in 3D environment[J]. Int J Syst Assur Eng Manag, 2021, 12（5）: 990

[10] Zhang Z, Wu J, Dai J Y, et al. A novel real—time penetration path planning algorithm for stealth UAV in 3D complex dynamic environment[J]. IEEE Access, 2020, 8: 122757

[11] Banerjee A, Sufian A, Paul K K, et al. EDTP: Energy and delay optimized trajectory planning for UAV—IoT environment[J]. Comput Netw, 2022, 202: 108623

[12] Chen J T, Li H Y, Ren H R, et al. Cooperative indoor path planning of multi—UAVs for high—rise fire fighting based on RRT—forest algorithm[J]. Acta Autom Sin, 2023, 49（12）: 2615

[13] （陈锦涛, 李鸿一, 任鸿儒, 等. 基于 RRT 森林算法的高层消防多无人机室内协同路径规划[J]. 自动化学报, 2023, 49（12）： 2615）

[14] Schacht—Rodríguez R, Ponsart J C, García—Beltrán C D, et al. Path planning generation algorithm for a class of UAV multirotor based on state of health of lithium polymer battery[J]. J Intell Robot Syst, 2018, 91（1）: 115

[15] Wu Y, Wu S B, Hu X T. Cooperative path planning of UAVs & UGVs for a persistent surveillance task in urban environments[J]. IEEE Internet Things J, 2021, 8（6）: 4906

[16] Phung M D, Quach C H, Dinh T H, et al. Enhanced discrete particle swarm optimization path planning for UAV vision—based surface inspection[J]. Autom Constr, 2017, 81: 25

[17] Yu Z H, Si Z J, Li X B, et al. A novel hybrid particle swarm optimization algorithm for path planning of UAVs[J]. IEEE Internet Things J, 2022, 9（22）: 22547

[18] Phung M D, Ha Q P. Safety—enhanced UAV path planning with spherical vector—based particle swarm optimization[J]. Appl Soft Comput, 2021, 107: 107376

[19] Shi L, Xu S K. UAV path planning with QoS constraint in device—to—device 5G networks using particle swarm optimization[J]. IEEE Access, 2020, 8: 137884

[20] Xu C F, Duan H B, Liu F. Chaotic artificial bee colony approach to Uninhabited Combat Air Vehicle （UCAV） path planning[J]. Aerosp Sci Technol, 2010, 14（8）: 535

[21] Wu J F, Wang H L, Wang Y X, et al. UAV reactive interfered fluid path planning[J]. Acta Autom Sin, 2023, 49（2）: 272

[22] （吴健发, 王宏伦, 王延祥, 等. 无人机反应式扰动流体路径规划[J]. 自动化学报, 2023, 49（2）： 272）

[23] Singla A, Padakandla S, Bhatnagar S. Memory—based deep reinforcement learning for obstacle avoidance in UAV with limited environment knowledge[J]. IEEE Trans Intell Transp Syst, 2021, 22（1）: 107

[24] Wen S H, Zhao Y F, Yuan X, et al. Path planning for active SLAM based on deep reinforcement learning under unknown environments[J]. Intel Serv Robotics, 2020, 13（2）: 263

[25] Lin W X, Xie W J, Zhang P, et al. UAV 3D path planning based on grouping optimization improved particle swarm algorithm[J]. Fire Control Command Control, 2023, 48（1）: 20

[26] （蔺文轩, 谢文俊, 张鹏, 等. 基于分组优化改进粒子群算法的无人机三维路径规划[J]. 火力与指挥控制, 2023, 48（1）： 20）

[27] Xu J X, Sun W, Ma C. UAV 3D path planning based on improved particle swarm optimization[J]. Electron Opt Control, 2023, 30（6）: 15

[28] （徐建新, 孙纬, 马超. 基于改进粒子群算法的无人机三维路径规划[J]. 电光与控制, 2023, 30（6）： 15）

[29] Shi Y, Eberhart R. A modified particle swarm optimizer[C]// 1998 IEEE International Conference on Evolutionary Computation Proceedings. IEEE World Congress on Computational Intelligence, 1998: 69

[30] Fang Q, Xu Q. 3D route planning for UAV based on improved PSO algorithm[J]. J Northwest Polytech Univ, 2017, 35（1）: 66

[31] （方群, 徐青. 基于改进粒子群算法的无人机三维航迹规划[J]. 西北工业大学学报, 2017, 35（1）： 66）

[32] Zhu R Z, Zhao J, Jiang G P, et al. UAV 3D path planning based on improved particle swarm optimization algorithm[J]. J Nanjing Univ Posts Telecommun （Nat Sci）, 2024, 44（6）: 120

[33] （朱润泽, 赵静, 蒋国平, 等. 基于改进粒子群算法的无人机三维路径规划[J]. 南京邮电大学学报（自然科学版）, 2024, 44（6）： 120）

[34] Wu X W, Guo M Y, Hu A J, et al. Path planning for UAV based on improved hybrid genetic particle swarm algorithm[J]. Chin J Sci Instrum, 2025, 46（4）: 315

[35] （武晓雯, 郭孟营, 胡阿建, 等. 基于改进遗传粒子群算法的无人机路径规划[J]. 仪器仪表学报, 2025, 46（4）： 315）

[36] Lu L L, Dai J Y, Ying J. Distributed multi—UAV cooperation for path planning by an NTVPSO—ADE algorithm[C]// 2022 41st Chinese Control Conference （CCC）, 2022: 5973

[37] Wang W T, Ye C, Tian J. 3D UAV path planning method based on multi—strategy improved artificial rabbit optimization algorithm[J]. Acta Electr Sin, 2024, 52（11）: 3780

[38] （王文涛, 叶晨, 田军. 基于多策略改进人工兔优化算法的三维无人机路径规划方法[J]. 电子学报, 2024, 52（11）： 3780）

基金资助

陕西省自然科学基础研究计划(2023JCYB194)

陕西省自然科学基础研究计划(2024JCYBMS169)

陕西省教育科学“十四五”规划课题(SGH24Y2488)

西安航空学院校级科研基金(2024KY1204)