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

• 人工智能 • 上一篇    下一篇

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

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

  1. 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-cheng1,2, DU Xiao-yu1,3, ZHANG Yan-yu1,2, ZHOU Yi1,2   

  1. 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).

摘要: 无人机三维路径规划是一个比较复杂的全局优化问题,其目标是在考虑威胁和约束的条件下,获得最优或接近最优的飞行路径。针对鲸鱼算法在进行无人机三维航迹规划时,存在容易陷入局部最优、收敛速度较慢、收敛精度不够高等问题,提出了一种基于莱维飞行(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: Three-dimensional path planning, Heuristic algorithm, Whale optimization algorithm, Information exchange mechanism, Lévy flight

中图分类号: 

  • TP301
[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.
[1] 章菊, 李学鋆. 基于莱维萤火虫算法的智能生产线调度问题研究[J]. 计算机科学, 2021, 48(6A): 668-672.
[2] 刘忠慧, 赵琦, 邹璐, 闵帆. 三元概念的启发式构建及其在社会化推荐中的应用[J]. 计算机科学, 2021, 48(6): 234-240.
[3] 郑洁锋, 占红武, 黄巍, 张恒, 吴周鑫. Lévy Flight的发展和智能优化算法中的应用综述[J]. 计算机科学, 2021, 48(2): 190-206.
[4] 郭飞雁, 唐兵. 基于用户延迟感知的移动边缘服务器放置方法[J]. 计算机科学, 2021, 48(1): 103-110.
[5] 李阳, 李维刚, 赵云涛, 刘翱. 基于莱维飞行和随机游动策略的灰狼算法[J]. 计算机科学, 2020, 47(8): 291-296.
[6] 张严, 秦亮曦. 基于Levy飞行策略的改进樽海鞘群算法[J]. 计算机科学, 2020, 47(7): 154-160.
[7] 张旭, 王莉莉, 杨博韬. 带有一刀切约束的二维非规则装箱算法[J]. 计算机科学, 2020, 47(5): 212-216.
[8] 杨婷, 罗飞, 丁炜超, 卢海峰. 一种自适应优化松弛量的装箱算法[J]. 计算机科学, 2020, 47(4): 211-216.
[9] 罗飞, 任强, 丁炜超, 卢海峰. 基于最小松弛量的启发式一维装箱算法[J]. 计算机科学, 2019, 46(9): 315-320.
[10] 张澍裕, 宫达, 谢兵, 刘开贵. 基于实时GPS的公交短时动态调度算法[J]. 计算机科学, 2019, 46(6A): 497-501.
[11] 史雯隽,武继刚,罗裕春. 针对移动云计算任务迁移的快速高效调度算法[J]. 计算机科学, 2018, 45(4): 94-99.
[12] 单天羽, 管煜旸. 基于种群多样性的可变种群缩减差分进化算法[J]. 计算机科学, 2018, 45(11A): 160-166.
[13] 李美争,李磊军,米据生,解滨. 概念格中基于粗糙熵的属性约简方法[J]. 计算机科学, 2018, 45(1): 84-89.
[14] 李荣雨,戴睿闻. 自适应步长布谷鸟搜索算法[J]. 计算机科学, 2017, 44(5): 235-240.
[15] 殷晓波,罗恩. 一种松弛的优化均衡流式图划分算法研究[J]. 计算机科学, 2016, 43(4): 231-234.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] 邹华福,谢承旺,周杨萍,王立平. 应用反向学习和差分进化的群搜索优化算法[J]. 计算机科学, 2018, 45(6A): 124 -129 .
[2] 曲佳博, 秦勃. 基于ST-CNN的交通标志实时检测识别算法[J]. 计算机科学, 2019, 46(11A): 309 -314 .
[3] 周凯, 任怡, 汪哲, 管剑波, 张芳, 赵言亢. 基于主题模型的Ubuntu操作系统缺陷报告的分类及分析[J]. 计算机科学, 2020, 47(12): 35 -41 .
[4] 潘孝勤, 芦天亮, 杜彦辉, 仝鑫. 基于深度学习的语音合成与转换技术综述[J]. 计算机科学, 2021, 48(8): 200 -208 .
[5] 王俊, 王修来, 庞威, 赵鸿飞. 面向科技前瞻预测的大数据治理研究[J]. 计算机科学, 2021, 48(9): 36 -42 .
[6] 余力, 杜启翰, 岳博妍, 向君瑶, 徐冠宇, 冷友方. 基于强化学习的推荐研究综述[J]. 计算机科学, 2021, 48(10): 1 -18 .
[7] 王梓强, 胡晓光, 李晓筱, 杜卓群. 移动机器人全局路径规划算法综述[J]. 计算机科学, 2021, 48(10): 19 -29 .
[8] 高洪皓, 郑子彬, 殷昱煜, 丁勇. 区块链技术专题序言[J]. 计算机科学, 2021, 48(11): 1 -3 .
[9] 毛瀚宇, 聂铁铮, 申德荣, 于戈, 徐石成, 何光宇. 区块链即服务平台关键技术及发展综述[J]. 计算机科学, 2021, 48(11): 4 -11 .
[10] 陈源毅, 冯文龙, 黄梦醒, 冯思玲. 基于知识图谱的行为路径协同过滤推荐算法[J]. 计算机科学, 2021, 48(11): 176 -183 .