UAV Three-Dimension Path Planning Based on Multi-strategy Evolution Mechanism in Multi-Obstacle Scenarios
-
摘要: 针对无人机(UAV)在三维多障碍物场景下路径规划存在的收敛精度低、稳定性不足等问题, 提出一种多策略进化粒子群算法(MSEPSO). 在初始化阶段, 针对粒子群算法(PSO)对粒子初始位置敏感的问题, 采用拉丁超立方采样(LHS)优化粒子初始分布, 提高种群多样性; 在进化阶段, 设计“平衡−记忆−增强”进化框架, 即利用非线性迭代策略来平衡全局开发和局部搜索, 采用个体历史记忆启发机制(PHMM)增强算法的全局开发能力, 并引入进化粒子, 增强种群对于群体极值附近空间的探索能力, 降低算法陷入局部最优的概率. 在CEC2020测试函数集上与山地/城市场景下的对比实验结果表明, MSEPSO展现出了稳定的寻优性能, 可以规划长度更短、平滑度更高的安全路径.Abstract: Aiming at the problems such as low convergence accuracy and insufficient stability in path planning for unmanned aerial vehicles (UAVs) in three-dimensional multi-obstacle scenarios, a multi-strategy evolutionary particle swarm optimization (MSEPSO) algorithm is proposed. In the initialization stage, aiming at the problem that particle swarm optimization is sensitive to the initial position of particles, the initial distribution of particles is optimized through Latin hypercube sampling to improve the population diversity; During the evolutionary stage, a “balance-memory-enhancement” evolutionary framework was designed, which utilized a nonlinear iterative strategy to balance global development and local search. The personal history memory mechanism was adopted to enhance the global exploitation ability of the algorithm. Evolutionary particles were introduced to enhance the exploration ability of the population in the vicinity of the group's extreme values, reducing the probability of the algorithm getting stuck in local optima. Experimental results from comparisons on the CEC2020 test function set and in mountain/urban scenarios demonstrate that MSEPSO exhibits stable optimization performance, enabling the planning of safer paths with shorter lengths and higher smoothness.
-
Key words:
- uav /
- 3D path planning /
- particle swarm optimization /
- multi-strategy evolution
-
表 1 基于10-D CEC2020基准函数的数值实验
Table 1 Numerical experiments based on 10-D CEC2020 benchmark functions
PSO LPSO PSO-SA ACVPSO WOA SHO HHO DBO MSEPSO F1 B 1.893E+07 1.000E+03 7.981E+06 5.071E+03 9.614E+05 1.105E+06 5.737E+04 4.140E+09 1.001E+02 W 5.174E+09 4.415E+09 1.142E+10 6.100E+09 1.230E+10 4.426E+09 2.765E+06 3.774E+10 1.274E+04 M 9.222E+08 3.598E+08 1.914E+09 7.338E+07 6.539E+08 3.973E+08 5.985E+05 1.913E+10 3.744E+03 V 7.913E+17 4.678E+17 2.644E+18 1.237E+17 1.492E+18 3.631E+17 9.071E+10 3.617E+19 1.101E+07 F2 B 1.300E+03 1.176E+03 1.234E+03 1.236E+03 1.328E+03 1.236E+03 1.274E+03 2.547E+03 1.129E+03 W 3.009E+03 3.023E+03 3.809E+03 3.296E+03 3.494E+03 2.860E+03 2.729E+03 3.913E+03 2.422E+03 M 2.325E+03 2.034E+03 2.455E+03 2.190E+03 2.337E+03 2.061E+03 2.010E+03 3.352E+03 1.815E+03 V 6.864E+04 1.092E+05 2.010E+05 1.225E+05 1.283E+05 5.768E+04 7.708E+04 5.539E+04 1.003E+04 F3 B 7.410E+02 7.100E+02 7.260E+02 7.180E+02 7.290E+02 7.270E+02 7.220E+02 7.880E+02 7.090E+02 W 8.890E+02 7.870E+02 9.500E+02 8.560E+02 9.090E+02 8.090E+02 8.440E+02 1.340E+03 7.870E+02 M 7.870E+02 7.390E+02 7.620E+02 7.630E+02 7.910E+02 7.590E+02 7.850E+02 1.010E+03 7.450E+02 V 1.790E+02 1.810E+02 5.140E+02 5.020E+02 5.780E+02 1.710E+02 4.530E+02 1.260E+04 1.740E+02 F4 B 1.904E+03 1.900E+03 1.902E+03 1.901E+03 1.902E+03 1.904E+03 1.900E+03 3.410E+03 1.900E+03 W 1.526E+05 3.840E+03 1.098E+05 3.440E+03 8.571E+04 8.797E+04 1.921E+03 3.074E+06 1.905E+03 M 2.227E+03 1.987E+03 2.545E+03 1.924E+03 3.048E+03 2.713E+03 1.908E+03 2.978E+05 1.902E+03 V 2.280E+07 4.104E+04 2.202E+07 6.884E+03 3.645E+07 1.817E+07 8.804E+00 7.966E+10 7.103E-01 F5 B 4.636E+03 1.758E+03 4.178E+03 1.812E+03 3.518E+03 3.116E+03 2.690E+03 7.260E+04 1.754E+03 W 4.258E+06 2.942E+06 4.426E+06 2.588E+06 4.022E+06 6.114E+05 2.762E+05 5.436E+07 1.660E+04 M 1.524E+05 2.609E+04 3.046E+05 1.652E+04 5.891E+05 1.250E+05 3.694E+04 4.845E+06 2.425E+03 V 2.207E+11 4.834E+10 6.701E+11 2.670E+10 5.060E+11 1.719E+10 1.624E+09 4.373E+13 3.242E+05 F6 B 1.610E+03 1.601E+03 1.603E+03 1.602E+03 1.603E+03 1.601E+03 1.602E+03 1.900E+03 1.601E+03 W 2.452E+03 2.615E+03 2.657E+03 2.445E+03 2.365E+03 2.088E+03 2.301E+03 3.288E+03 1.975E+03 M 1.858E+03 1.834E+03 1.994E+03 1.860E+03 1.892E+03 1.767E+03 1.833E+03 2.562E+03 1.716E+03 V 1.763E+04 1.833E+04 2.662E+04 2.207E+04 1.953E+04 8.210E+03 1.557E+04 5.267E+04 6.462E+03 F7 B 2.777E+03 2.112E+03 2.334E+03 2.104E+03 2.971E+03 2.202E+03 2.269E+03 7.448E+03 2.103E+03 W 3.541E+06 3.541E+06 7.669E+06 3.541E+06 1.497E+06 2.011E+05 2.449E+05 2.621E+07 4.111E+03 M 7.344E+04 2.477E+04 1.569E+05 4.227E+04 3.757E+05 1.053E+04 1.350E+04 2.926E+06 2.610E+03 V 2.046E+11 7.235E+10 6.043E+11 1.339E+11 1.033E+12 2.370E+08 3.252E+08 6.092E+12 6.713E+04 F8 B 2.254E+03 2.222E+03 2.254E+03 2.229E+03 2.225E+03 2.220E+03 2.221E+03 2.415E+03 2.213E+03 W 3.796E+03 4.052E+03 5.085E+03 4.065E+03 4.544E+03 3.681E+03 4.016E+03 5.117E+03 3.450E+03 M 2.375E+03 2.342E+03 2.465E+03 2.341E+03 2.449E+03 2.366E+03 2.336E+03 3.970E+03 2.305E+03 V 1.076E+04 1.892E+04 7.994E+04 1.807E+04 1.299E+05 1.410E+04 2.766E+04 2.444E+05 4.133E+03 F9 B 2.530E+03 2.500E+03 2.508E+03 2.501E+03 2.501E+03 2.502E+03 2.501E+03 2.790E+03 2.400E+03 W 2.890E+03 2.931E+03 2.919E+03 3.071E+03 3.038E+03 2.851E+03 2.975E+03 3.254E+03 2.784E+03 M 2.773E+03 2.730E+03 2.796E+03 2.774E+03 2.787E+03 2.765E+03 2.796E+03 2.969E+03 2.743E+03 V 2.705E+03 4.136E+03 2.554E+03 5.596E+03 5.747E+03 4.010E+03 7.850E+03 4.251E+03 2.754E+03 F10 B 2.882E+03 2.600E+03 2.657E+03 2.633E+03 2.650E+03 2.654E+03 2.614E+03 3.073E+03 2.600E+03 W 3.356E+03 3.310E+03 4.056E+03 3.300E+03 3.240E+03 3.179E+03 3.056E+03 6.467E+03 3.024E+03 M 2.992E+03 2.956E+03 3.027E+03 2.951E+03 2.972E+03 2.937E+03 2.934E+03 4.307E+03 2.930E+03 V 1.874E+03 2.961E+03 9.400E+03 2.028E+03 3.124E+03 1.649E+03 1.576E+03 2.929E+05 1.178E+03 表 2 算法参数
Table 2 Algorithm parameters
算法 参数 取值 PSO 惯性权重 1 学习因子$ c_1 $和$ c_2 $ 1.5, 1.5 速度范围 [−10, 10] LPSO 惯性权重范围 [0.3, 1.2] 学习因子$ c_1 $和$ c_2 $ 1.5, 1.5 速度范围 [−10, 10] PSO-SA 惯性权重 1 学习因子$ c_1 $和$ c_2 $ 1.5, 1.5 速度范围 [−10, 10] ACVDEPSO 惯性权重范围 [0.3, 1.2] 个体因子范围 [0.1, 1.0] 群体因子范围 [0.1, 1.0] 速度范围 [−10, 10] MSEPSO 惯性权重范围 [0.3, 1.2] 学习因子$ c_1 $和$ c_2 $ 取决于$ w $ 记忆衰减系数$ \mu $ 0.5 速度范围 [−10, 10] 表 3 适应度函数参数
Table 3 Fitness function parameters
参数 取值 $ \omega_1 $ 1 $ \omega_2 $ 0.1 $ \omega_3 $ 10000 $ \omega_4 $ 1000 表 4 不同场景下的实验数据
Table 4 Experimental data in various scenarios
场景 算法 最优解 最劣解 均值 方差 简单山地 PSO 169.646 179.254 173.620 12.406 LPSO 168.709 177.567 174.373 14.606 PSO-SA 168.436 179.876 172.464 12.885 ACVDEPSO 169.797 176.635 173.958 7.560 MSEPSO 164.126 166.190 165.019 0.562 复杂山地 PSO 173.037 194.175 178.897 79.749 LPSO 174.499 185.884 178.400 21.195 PSO-SA 169.102 187.409 179.600 56.882 ACVDEPSO 166.905 192.133 178.073 89.173 MSEPSO 164.785 169.644 166.695 6.522 城市场景1 PSO 185.967 195.121 189.353 12.045 LPSO 324.035 487.195 420.122 5183.551 PSO-SA 183.576 190.903 187.306 7.711 ACVDEPSO 185.522 215.841 194.130 168.304 MSEPSO 182.906 187.127 184.020 3.124 城市场景2 PSO 165.621 175.897 169.139 17.071 LPSO 163.833 173.548 167.518 15.471 PSO-SA 163.906 168.039 165.526 2.675 ACVDEPSO 165.009 177.137 170.999 30.845 MSEPSO 161.070 162.970 162.491 0.640 -
[1] Liu M J, Zhang H X, Yang J, Zhang T Z, Zhang C H, Bo L. A path planning algorithm for three-dimensional collision avoidance based on potential field and B-spline boundary curve. Aerospace Science and Technology, 2024, 144, DOI: 10.1016/j.ast.2023.108763 [2] 陈锦涛, 李鸿一, 任鸿儒, 鲁仁全. 基于RRT森林算法的高层消防多无人机室内协同路径规划. 自动化学报, 2023, 49(12): 2615−2626 doi: 10.16383/j.aas.c210368Chen Jin-Tao, Li Hong-Yi, Ren Hong-Ru, Lu Ren-Quan. Cooperative indoor path planning of multi-UAVs for high-rise fire fighting based on RRT-forest algorithm. Acta Automatica Sinica, 2023, 49(12): 2615−2626 doi: 10.16383/j.aas.c210368 [3] Savkin A V, Huang C, Ni W. Joint Multi-UAV Path Planning and LoS Communication for Mobile-Edge Computing in IoT Networks with RISs. IEEE Internet of Things Journal, 2023, 10(3): 2720−2727 doi: 10.1109/JIOT.2022.3215255 [4] Rückin J, Magistri F, Stachniss C, Popovic M. An Informative Path Planning Framework for Active Learning in UAV-Based Semantic Mapping. IEEE Transactions on Robotics, 2023, 39(6): 4279−4296 doi: 10.1109/TRO.2023.3313811 [5] Liu C, Jiang B, Patton R J, Zhang K. Integrated Fault-Tolerant Control for Close Formation Flight. IEEE Transactions on Aerospace and Electronic Systems, 2020, 56(2): 839−852 doi: 10.1109/TAES.2019.2920221 [6] Ma J, Ma X, Zang S. Multi-destination Path Planning Based on Ant Colony Decision and Rolling Control. IEEE Transactions on Aerospace and Electronic Systems, 2024, 60(6): 8667−8681 doi: 10.1109/TAES.2024.3434777 [7] Chen Y Q, Yu Q Z, Han D, Jiang H. UAV path planning: Integration of grey wolf algorithm and artificial potential field. Concurrency and Computation-practice & Experience, 2024, DOI: 10.1002/cpe.8120 [8] 蒋林, 李峻, 马先重. 一种改进骨架提取的Voronoi路径规划. 机械工程学报, 2020, 56(13): 1388−148 doi: 10.3901/JME.2020.13.138Jiang Lin, Li Jun, Ma Xian-Chong. Voronoi path planning based on improved skeleton extraction. Journal of Mechanical Engineering, 2020, 56(13): 1388−148 doi: 10.3901/JME.2020.13.138 [9] Zhang Y, Su Y, Yang J, Ponce J, Kong H. When Dijkstra Meets Vanishing Point: A Stereo Vision Approach for Road Detection. Journal of Mechanical Engineering, 2018, 27(5): 2176−2188 doi: 10.1109/TIP.2018.2792910 [10] 张凯翔, 毛剑琳, 向凤红, 宣志玮. 基于讨价还价博弈机制的B-IHCA*多机器人路径规划算法. 自动化学报, 2023, 49(7): 1483−1497 doi: 10.16383/j.aas.c220065Zhang Kai-Xiang, Mao Jian-Lin, Xiang Feng-Hong, Xuan Zhi-Wei. B-IHCA*, a bargaining game based multi-agent path finding algorithm. Acta Automatica Sinica, 2023, 49(7): 1483−1497 doi: 10.16383/j.aas.c220065 [11] Huang C, Zhou X B, Ran X J, Wang J M, Chen H Y, Deng W. Adaptive cylinder vector particle swarm optimization with differential evolution for UAV path planning. Engineering Applications of Artificial Intelligence, 2023, 121, DOI: 10.1016/j.engappai.2023.105942 [12] Patle B K, Babu L G, Pandey A. A Review: On Path Planning Strategies for Navigation of Mobile Robot. Defence Technology, 2019, 15(4): 582−606 doi: 10.1016/j.dt.2019.04.011 [13] 朱润泽, 赵静, 蒋国平, 肖敏, 徐丰羽. 基于改进粒子群算法的无人机三维路径规划. 南京邮电大学学报(自然科学版), 2024, 44(6): 120−127 doi: 10.14132/j.cnki.1673-5439.2024.06.012Zhu Run-Ze, Zhao Jing, Jiang Guo-Ping, Xiao Min, Xu Feng-Yu. UAV 3D path planning based on improved particle swarm optimization algorithm. Journal of Nanjing University of Posts and Telecommunications (Natural Science Edition), 2024, 44(6): 120−127 doi: 10.14132/j.cnki.1673-5439.2024.06.012 [14] Tang F F, Li K Y, Xu F, Han L, Zhang H, Yang Z X. Optimal ant colony algorithm for UAV airborne LiDAR route planning in densely vegetated areas. Journal of Applied Remote Sensing, 2023, 17(4), DOI: 10.1117/1.JRS.17.046506 [15] 刘景森, 吉宏远, 李煜. 基于改进蝙蝠算法和三次样条插值的机器人路径规划. 自动化学报, 2021, 47(7): 1710−1719 doi: 10.16383/j.aas.c180855Liu Jin-Seng, Ji Hong-Yuan, Li Yu. Robot path planning based on improved bat algorithm and cubic spline interpolation. Acta Automatica Sinica, 2021, 47(7): 1710−1719 doi: 10.16383/j.aas.c180855 [16] Mirjalili S, Lewis A. The whale optimization algorithm. Advances in Engineering Software, 2016, 95: 51−67 doi: 10.1016/j.advengsoft.2016.01.008 [17] Heidari A A, Mirjalili S, Faris H. Harris hawks optimization: Algorithm and applications. Future generation computer systems, 2019, 97: 849−872 doi: 10.1016/j.future.2019.02.028 [18] Xue J K, Shen B. Dung beetle optimizer: a new meta-heuristic algorithm for global optimization. The Journal of Supercomputing, 2023, 79(7): 7305−7336 doi: 10.1007/s11227-022-04959-6 [19] Zhao S, Zhang T, Ma S. Sea-horse optimizer: a novel nature-inspired meta-heuristic for global optimization problems. Applied Intelligence, 2023, 53(10): 11833−11860 doi: 10.1007/s10489-022-03994-3 [20] Tian S, Li Y, Kang Y, Xia J. Multi-robot path planning in wireless sensor networks based on jump mechanism PSO and safety gap obstacle avoidance. Future Generation Computer Systems, 2021, 118: 37−47 doi: 10.1016/j.future.2020.12.012 [21] Das P K, Behera H S, Das S, Tripathy H K, B.K. Panigrahi, S.K. Pradhan. A hybrid improved PSO-DV algorithm for multi-robot path planning in a clutter environment. Neurocomputing, 2016, 207: 735−753 doi: 10.1016/j.neucom.2016.05.057 [22] Lin A P, Liu D, Li Z Q, Hasanien H M, Shi Y T. Heterogeneous differential evolution particle swarm optimization with local search. Complex and Intelligent Systems, 2023, 9(6): 6905−6925 doi: 10.1007/s40747-023-01082-8 [23] Luo J, Liang Q, Li H. UAV penetration mission path planning based on improved holonic particle swarm optimization. Journal of Systems Engineering and Electronics, 2023, 34(1): 197−213 doi: 10.23919/JSEE.2022.000132 [24] Huang C, Ma X, Zhou H, Deng W. Cooperative Path Planning of Multiple Unmanned Aerial Vehicles Using Cylinder Vector Particle Swarm Optimization With Gene Targeting. IEEE Sensors Journal, 2025, 25(5): 8470−8480 doi: 10.1109/JSEN.2024.3516124 [25] Zhang C, Li Y, Zhou L. Optimal Path and Timetable Planning Method for Multi-Robot Optimal Trajectory. IEEE Robotics and Automation Letters, 2022, 7(3): 8130−8137 doi: 10.1109/LRA.2022.3187529 [26] Haris M, Nam H. Path Planning Optimization of Smart Vehicle With Fast Converging Distance-Dependent PSO Algorithm. IEEE Open Journal of Intelligent Transportation Systems, 2024, 5: 726−739 doi: 10.1109/OJITS.2024.3486155 [27] Gang L, Xinyuan G, Dong H, Kezhong C, Wu L. Multi-Platform Collaborative MRC-PSO Algorithm for Anti-Ship Missile Path Planning. Journal of Systems Engineering and Electronics, 2025, 36(2): 494−509 doi: 10.23919/JSEE.2025.000026 [28] Wang Y, Hu F, Xu H, Zeng J. A Multigroups Cooperative Particle Swarm Algorithm for Optimization of Multivehicle Path Planning in Internet of Vehicles. IEEE Internet of Things Journal, 2024, 11(22): 35839−35851 doi: 10.1109/JIOT.2024.3367328 [29] Yu Z H, Si Z J, Li X B, Wang D, Song H B. A Novel Hybrid Particle Swarm Optimization Algorithm for Path Planning of UAVs. IEEE Internet of Things Journal, 2022, 9(2): 22547−22558 doi: 10.1109/JIOT.2022.3182798 [30] Lin S H, Liu A, Wang J G, Kong X Y. An intelligence-based hybrid PSO-SA for mobile robot path planning in warehouse. Journal of Computational Science, 2023, 67, DOI: 10.1016/j.jocs.2022.101938 [31] Eberhart R, Kennedy J. A new optimizer using particle swarm theory. MHS'95 Proceedings of the Sixth International Symposium on Micro Machine and Human Science, 1995: 39-43, DOI: 10.1109/MHS.1995.494215 [32] Shi Y, EBERHART R. A modified particle swarm optimizer. IEEE.1998 Proceedings of the IEEE International Conference on Evolutionary Computation(CEC), 1998: 69-73, DOI: 10.1109/ICEC.1998.699146 -
计量
- 文章访问数: 13
- HTML全文浏览量: 12
- 被引次数: 0
下载: