基于改进鲸鱼算法的无人机三维路径规划

doi:10.11896/jsjkx.201000021

计算机科学 ›› 2021, Vol. 48 ›› Issue (12): 304-311.doi: 10.11896/jsjkx.201000021

基于改进鲸鱼算法的无人机三维路径规划

郭启程^1,2, 杜晓玉^1,3, 张延宇^1,2, 周毅^1,2

1 河南大学计算机与信息工程学院河南开封475004
2 河南省车联网协同技术国际联合实验室河南开封475004
3 河南省大数据分析与处理重点实验室河南开封475004

收稿日期:2020-10-05 修回日期:2021-04-07 出版日期:2021-12-15 发布日期:2021-11-26
通讯作者: 杜晓玉(dxy@henu.edu.cn)
作者简介:104753180684@vip.henu.edu.cn
基金资助:
国家自然科学基金(61701170);河南省科技厅科技发展计划项目(202102210327)

Three-dimensional Path Planning of UAV Based on Improved Whale Optimization Algorithm

GUO Qi-cheng^1,2, DU Xiao-yu^1,3, ZHANG Yan-yu^1,2, ZHOU Yi^1,2

1 School of Computer and Information Engineering,Henan University,Kaifeng,Henan 475004,China
2 International Joint Research Laboratory for Cooperative Vehicular Networks of Henan,Kaifeng,Henan 475004,China
3 Henan Key Laboratory of Big Data Analysis and Processing,Kaifeng,Henan 475004,China

Received:2020-10-05 Revised:2021-04-07 Online:2021-12-15 Published:2021-11-26
About author:GUO Qi-cheng,born in 1995,master's degree.His main research interests include collaborative technology of internet of vehicles.
DU Xiao-yu,born in 1979,Ph.D,asso-ciate professor,master supervisor.Her main research interests include wireless sensor network positioning and cove-rage technology.
Supported by:
National Natural Science Foundation of China(61701170) and Programs for Science and Technology Development of Henan Province(202102210327).

摘要/Abstract

摘要： 无人机三维路径规划是一个比较复杂的全局优化问题,其目标是在考虑威胁和约束的条件下,获得最优或接近最优的飞行路径。针对鲸鱼算法在进行无人机三维航迹规划时,存在容易陷入局部最优、收敛速度较慢、收敛精度不够高等问题,提出了一种基于莱维飞行(Lévy flight)的鲸鱼优化算法(Levy Flight Based on Whale Optimization Algorithm,LWOA),用于解决无人机三维路径规划问题。该算法在迭代过程中加入了Levy飞行对最优解进行随机扰动;引入了信息交流机制,通过当前全局最优解和个体记忆最优解以及邻域最优解来更新个体的位置,能够更好地权衡局部收敛和全局开发。仿真结果表明,所提路径规划算法可以有效避开威胁区,收敛速度更快,收敛精度更高,且更不易陷入局部最优解。当迭代次数为300次、种群个数为50时,LWOA算法求得的成本函数值是PSO算法的91.1%,是GWO算法的92.1%,是WOA算法的95.9%,航迹代价更小。

关键词: 鲸鱼算法, 莱维飞行, 启发式算法, 三维路径规划, 信息交流机制

Abstract: The three-dimensional path planning of UAVs is a relatively complex global optimization problem.Its goal is to obtain the optimal or close to optimal flight path considering threats and constraints.Aiming at the problems of whale algorithm in the three-dimensional trajectory planning of UAVs,it is easy to fall into the local optimum,and the convergence speed is slow,and the convergence accuracy is not high enough.A whale optimization algorithm based on Lévy flight is proposed to solve the pro-blem of UAV three-dimensional path planning.In the iterative process of the algorithm,Levy flight is added to randomly disturb the optimal solution;an information exchange mechanism is introduced to update the individual's position through the current global optimal solution,the individual memory optimal solution and the neighborhood optimal solution;better trade-offs local convergence and global development.The simulation results show that the path planning algorithm proposed in this paper can effectively avoid the threat zone,the convergence speed is faster,the convergence accuracy is higher,and it is less likely to fall into the local optimal solution.When the number of iterations is 300 and the number of populations is 50,the cost function value obtained by the LWOA algorithm is 91.1% of the PSO algorithm,92.1% of the GWO algorithm,95.9% of the WOA algorithm,and the track cost is smaller.

Key words: Heuristic algorithm, Information exchange mechanism, Lévy flight, Three-dimensional path planning, Whale optimization algorithm

中图分类号:

TP301

郭启程, 杜晓玉, 张延宇, 周毅. 基于改进鲸鱼算法的无人机三维路径规划[J]. 计算机科学, 2021, 48(12): 304-311. https://doi.org/10.11896/jsjkx.201000021

GUO Qi-cheng, DU Xiao-yu, ZHANG Yan-yu, ZHOU Yi. Three-dimensional Path Planning of UAV Based on Improved Whale Optimization Algorithm[J]. Computer Science, 2021, 48(12): 304-311. https://doi.org/10.11896/jsjkx.201000021

参考文献

[1]CHENG H H,YANG S,QI X H.Online Obstacle Avoidance Path Planning Method for Quadrotor UAVs in Urban Environment[J].Computer Science,2019,46(4):241-246.
[2]YOU W J,DONG C,WU Q H.Survey of Layered Architecture in Large-scale FANETs[J].Computer Science,2020,47(9):226-231.
[3]ZENG Y,ZHANG R.Energy-Efficient UAV Communication with Trajectory Optimization[J].IEEE Transactions on Wireless Communications,2017,16(6):3747-3760.
[4]WANG H B,YIN P H,ZHENG W,et al.Mobile Robot Path Planning Based on Improved A* Algorithm and Dynamic Window Method[J].Robots,2020,42(3):346-353.
[5]WANG S J,HU L K,WANG Y F.Path Planning of Indoor Mobile Robot based on Improved D^* Algorithm[J].Computer Engineering and Design,2020,41(4):1118-1124.
[6]TAN J H,XIAO Y L,LIU L M,et al.Improved PRM algorithm for path planning of UAV[J].Sensors and Microsystems,2020,39(1):38-41.
[7]GUO Y C,LIU X X,ZHANG W G,et al.UAV 3D path planning method based on improved potential field method[J].Journal of Northwest Polytechnic University,2020,38(5):977-986.
[8]YU M,LUO J J,WANG M M,et al.A Coordinated Path Planning by Integrating Improved RRT^* and Quartic Spline[J].Chinese Journal of Mechanics,2020,52(4):1024-1034.
[9]JIANG C K,LI Z,PAN S B,et al.Collision-free Path Planning of AGVs Based on Improved Dijkstra Algorithm[J].Computer Science,2020,47(8):272-277.
[10]LV Q,SUN X K,XIONG Y J.UAV path planning based on Improved Genetic Algorithm[J].Journal of Navigation and Positioning,2020,8(5):42-48.
[11]WANG Y H,WANG S M.UAV path planning based on improved particle swarm optimization[J].Computer Engineering and Science,2020,42(9):1690-1696.
[12]CAO Y,WEI W,BAI Y,et al.Multi-base multi-UAV cooperative reconnaissance path planning with genetic algorithm[J].Cluster Computing,2019,22:5175-5184.
[13]WEI J,WANG J J,WANG J,et al.3D Path Planning Based on Improved Ant Colony Algorithm[J].Computer Engineering and Applications,2020,56(17):217-223.
[14]PAN J,LIU N,CHU S.A Hybrid Differential Evolution Algorithm and Its Application in Unmanned Combat Aerial Vehicle Path Planning[J].IEEE Access,2020,8:17691-17712.
[15]ZHOU J,CHEN P,LIU H,et al.Improved Path Planning for Mobile Robot Based on Firefly Algorithm[C]//2019 IEEE International Conference on Robotics and Biomimetics(ROBIO).IEEE,2019:2885-2889.
[16]PANDEY P,SHUKLA A,TIWARI R.Three-dimensional path planning for unmanned aerial vehicles using glowworm swarm optimization algorithm[J].International Journal of System Assurance Engineering and Management,2018,9(4):836-852.
[17]QU C,GAI W,ZHANG J,et al.A novel hybrid grey wolf optimizer algorithm for unmanned aerial vehicle(UAV) path planning[J].Knowledge-Based Systems,2020,194:105530.
[18]LIN N,TANG J,LI X,et al.A Novel Improved Bat Algorithm in UAV Path Planning[J].Computers,Materials and Continua,2019,61(1):323-344.
[19]WU K,TAN S C.UAV route planning based on improved whale optimization algorithm[J].Journal of Aeronautics,2020,41(S2):107-114.
[20]MIRJALILI S,LEWIS A.The Whale Optimization Algorithm[J].Advances in Engineering Software,2016,95:51-67.
[21]PAVLYUKEVICH I.Lévy flights,non-local search and simulated annealing[J].Journal of Computational Physics,2007,226(2):1830-1844.

相关文章 15

[1]	陈俊, 何庆, 李守玉. 基于自适应反馈调节因子的阿基米德优化算法 Archimedes Optimization Algorithm Based on Adaptive Feedback Adjustment Factor 计算机科学, 2022, 49(8): 237-246. https://doi.org/10.11896/jsjkx.210700150
[2]	范星泽, 禹梅. 改进灰狼算法的无线传感器网络覆盖优化 Coverage Optimization of WSN Based on Improved Grey Wolf Optimizer 计算机科学, 2022, 49(6A): 628-631. https://doi.org/10.11896/jsjkx.210500037
[3]	耿海军, 王威, 尹霞. 基于混合软件定义网络的单节点故障保护方法 Single Node Failure Routing Protection Algorithm Based on Hybrid Software Defined Networks 计算机科学, 2022, 49(2): 329-335. https://doi.org/10.11896/jsjkx.210100051
[4]	章菊, 李学鋆. 基于莱维萤火虫算法的智能生产线调度问题研究 Research on Intelligent Production Line Scheduling Problem Based on LGSO Algorithm 计算机科学, 2021, 48(6A): 668-672. https://doi.org/10.11896/jsjkx.210300118
[5]	刘忠慧, 赵琦, 邹璐, 闵帆. 三元概念的启发式构建及其在社会化推荐中的应用 Heuristic Construction of Triadic Concept and Its Application in Social Recommendation 计算机科学, 2021, 48(6): 234-240. https://doi.org/10.11896/jsjkx.200500136
[6]	郑洁锋, 占红武, 黄巍, 张恒, 吴周鑫. Lévy Flight的发展和智能优化算法中的应用综述 Development of Lévy Flight and Its Application in Intelligent Optimization Algorithm 计算机科学, 2021, 48(2): 190-206. https://doi.org/10.11896/jsjkx.200500142
[7]	郭飞雁, 唐兵. 基于用户延迟感知的移动边缘服务器放置方法 Mobile Edge Server Placement Method Based on User Latency-aware 计算机科学, 2021, 48(1): 103-110. https://doi.org/10.11896/jsjkx.200900146
[8]	李阳, 李维刚, 赵云涛, 刘翱. 基于莱维飞行和随机游动策略的灰狼算法 Grey Wolf Algorithm Based on Levy Flight and Random Walk Strategy 计算机科学, 2020, 47(8): 291-296. https://doi.org/10.11896/jsjkx.190600107
[9]	张严, 秦亮曦. 基于Levy飞行策略的改进樽海鞘群算法 Improved Salp Swarm Algorithm Based on Levy Flight Strategy 计算机科学, 2020, 47(7): 154-160. https://doi.org/10.11896/jsjkx.190600068
[10]	张旭, 王莉莉, 杨博韬. 带有一刀切约束的二维非规则装箱算法 Heuristic Algorithms for Two-dimensional Irregular Bin Packing Problem with GuillotineConstraints 计算机科学, 2020, 47(5): 212-216. https://doi.org/10.11896/jsjkx.190400078
[11]	杨婷, 罗飞, 丁炜超, 卢海峰. 一种自适应优化松弛量的装箱算法 Bin Packing Algorithm Based on Adaptive Optimization of Slack 计算机科学, 2020, 47(4): 211-216. https://doi.org/10.11896/jsjkx.190500132
[12]	罗飞, 任强, 丁炜超, 卢海峰. 基于最小松弛量的启发式一维装箱算法 Heuristic One-dimensional Bin Packing Algorithm Based on Minimum Slack 计算机科学, 2019, 46(9): 315-320. https://doi.org/10.11896/j.issn.1002-137X.2019.09.048
[13]	张澍裕, 宫达, 谢兵, 刘开贵. 基于实时GPS的公交短时动态调度算法 Bus Short-term Dynamic Dispatch Algorithm Based on Real-time GPS 计算机科学, 2019, 46(6A): 497-501.
[14]	史雯隽,武继刚,罗裕春. 针对移动云计算任务迁移的快速高效调度算法 Fast and Efficient Scheduling Algorithms for Mobile Cloud Offloading 计算机科学, 2018, 45(4): 94-99. https://doi.org/10.11896/j.issn.1002-137X.2018.04.014
[15]	单天羽, 管煜旸. 基于种群多样性的可变种群缩减差分进化算法 Differential Evolution Algorithm with Adaptive Population Size Reduction Based on Population Diversity 计算机科学, 2018, 45(11A): 160-166.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

基于改进鲸鱼算法的无人机三维路径规划

Three-dimensional Path Planning of UAV Based on Improved Whale Optimization Algorithm

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

Metrics

本文评价

推荐阅读 0