基于改进遗传算法的无人机路径规划

doi:10.11772/j.issn.1001-9081.2020060797

计算机应用 ›› 2021, Vol. 41 ›› Issue (2): 390-397.DOI: 10.11772/j.issn.1001-9081.2020060797

所属专题：人工智能

基于改进遗传算法的无人机路径规划

黄书召¹, 田军委², 乔路², 王沁², 苏宇²

1. 西安工业大学电子信息工程学院, 西安 710021;
2. 西安工业大学机电工程学院, 西安 710021

收稿日期:2020-06-05 修回日期:2020-09-07 出版日期:2021-02-10 发布日期:2020-12-17
通讯作者: 黄书召
作者简介:黄书召(1995-),男,陕西安康人,硕士研究生,主要研究方向:无人机路径规划;田军委(1973-),男,陕西渭南人,教授,博士,主要研究方向:视觉检测、测量与控制;乔路(1995-),男,陕西渭南人,硕士,主要研究方向:无人机、无人车路径规划;王沁(1981-),男,陕西西安人,讲师,博士,主要研究方向:机电系统设计、嵌入式系统、特种机器人;苏宇(1982-),男,陕西西安人,讲师,博士,主要研究方向:绳牵引并联机器人、特种机器人、机械电子、环境监测。
基金资助:
陕西省科技统筹创新工程计划项目（2015KTZDGY-02-01）；陕西省重点研发计划项目（2020GY-188，2020NY-148）。

Unmanned aerial vehicle path planning based on improved genetic algorithm

HUANG Shuzhao¹, TIAN Junwei², QIAO Lu², WANG Qin², SU Yu²

1. School of Electronic Information Engineering, Xi'an Technological University, Xi'an Shaanxi 710021, China;
2. School of Mechatronic Engineering, Xi'an Technological University, Xi'an Shaanxi 710021, China

Received:2020-06-05 Revised:2020-09-07 Online:2021-02-10 Published:2020-12-17
Supported by:
This work is partially supported by the Shaanxi Provincial Science and Technology Overall Planning and Innovation Engineering Program (2015KTZDGY-02-01), the Key Research and Development Program of Shaanxi Province (2020GY-188, 2020NY-148).

摘要/Abstract

摘要： 针对传统遗传算法收敛速度慢、容易陷入局部最优、规划路径不够平滑、代价高等问题，提出了一种基于改进遗传算法的无人机（UAV）路径规划方法，该算法对遗传算法的选择算子、交叉算子和变异算子进行改进，从而规划出平滑、可飞的路径。首先，建立适合UAV田间信息获取的环境模型，并考虑UAV的目标函数与约束条件以建立适合本场景的更为复杂、精确的数学模型；然后，提出了混合无重串选择算子、非对称映射交叉算子和启发式多次变异算子，寻找最优路径以及扩大种群搜索范围；最后，采用三次B样条曲线对规划出的路径进行平滑，得到平滑的飞行路径，并且减少了算法的计算时间。实验结果表明，与传统遗传算法相比，所提算法的代价值降低了68%，收敛迭代次数减少了67%；相较蚁群优化（ACO）算法，其代价值降低了55%，收敛迭代次数减少了58%。通过大量对比实验得出，当交叉率的值为（1/染色体长度）时，算法的收敛效果最好。在不同环境下进行算法性能测试，结果表明所提算法具有很好的环境适应性，适合于复杂环境下的路径规划。

关键词: 遗传算法, 无人机, 交叉算子, B样条曲线, 路径规划

Abstract: In order to solve the problems such as slow convergence speed, falling into local optimum easily, unsmooth planning path and high cost of traditional genetic algorithm, an Unmanned Aerial Vehicle (UAV) path planning method based on improved Genetic Algorithm (GA) was proposed. The selection operator, crossover operator and mutation operator of genetic algorithm were improved to planning a smooth and effective flight path. Firstly, an environment model suitable for the field information acquisition of UAV was established, and a more complex and accurate mathematical model suitable for this scene was established by considering the objective function and constraints of UAV. Secondly, the hybrid non-multi-string selection operator, asymmetric mapping crossover operator and heuristic multi-mutation operator were proposed to find the optimal path and expand the search range of the population. Finally, a cubic B-spline curve was used to smooth the planned path to obtain a smooth flight path and reduce the calculation time of the algorithm. Experimental results show that, compared with the traditional GA, the cost value of the proposed algorithm was reduced by 68%, and the number of convergence iterations was reduced by 67%; compared with the Ant Colony Optimization (ACO) algorithm, its cost value was reduced by 55% and the number of convergence iterations was reduced by 58%. Through a large number of comparison experiments, it is concluded that when the value of the crossover rate is the reciprocal of chromosome size, the proposed algorithm has the best convergence effect. After testing the algorithm performance in different environments, it can be seen that the proposed algorithm has good environmental adaptability and is suitable for path planning in complex environments.

Key words: genetic algorithm, Unmanned Aerial Vehicle (UAV), crossover operator, B-spline curve, path planning

中图分类号:

TP181
TP13

黄书召, 田军委, 乔路, 王沁, 苏宇. 基于改进遗传算法的无人机路径规划[J]. 计算机应用, 2021, 41(2): 390-397.

HUANG Shuzhao, TIAN Junwei, QIAO Lu, WANG Qin, SU Yu. Unmanned aerial vehicle path planning based on improved genetic algorithm[J]. Journal of Computer Applications, 2021, 41(2): 390-397.

参考文献

[1] 杨陆强, 果霖, 朱加繁, 等. 我国农用无人机发展概况与展望[J]. 农机化研究,2017,39(8):6-11.(YANG L Q,GUO L, ZHU J F, et al. The development situation and prospect of agricultural UAV in China[J]. Journal of Agricultural Mechanization Research,2017,39(8):6-11.)
[2] 祁玄玄, 黄家骏, 曹建安. 基于改进A^*算法的无人车路径规划[J/OL]. 计算机应用[2020-06-11]. http://kns.cnki.net/kcms/detail/51.1307.TP.20200521.1551.006.html. (QI X X, HUANG J J,CAO J A. Autonomous vehicle path planning based on improved A^* algorithm[J/OL]. Journal of Computer Applications[2020-06-11]. http://kns.cnki.net/kcms/detail/51.1307.TP.20200521.1551.006.html.)
[3] MAINI P,YU K,SUJIT P B,et al. Persistent monitoring with refueling on a terrain using a team of aerial and ground robots[C]//Proceedings of the 2018 IEEE/RSJ International Conference on Intelligent Robots and Systems. Piscataway:IEEE,2018:8493-8498.
[4] 刘生伟, 马钺, 孟树峰, 等. 改进A*算法的AGV路径规划[J]. 计算机应用,2019,39(S2):41-44.(LIU S W,MA Y,MENG S F, et al. Improved A* algorithm for path planning of AGV[J]. Journal of Computer Applications,2019,39(S2):41-44.)
[5] 薄宁, 李相民, 代进进, 等. 基于变步长稀疏A*搜索和MPC的多无人机层次化协同航迹规划[J]. 指挥控制与仿真,2018,40(2):65-71. (BO N,LI X M,DAI J J,et al. A hierarchical optimization strategy of trajectory planning based on variable step size SAS and MPC for UAVs[J]. Command Control and Simulation,2018,40(2):65-71.)
[6] 成怡, 王赟, 修春波. 一种改进RRT算法在路径规划中的应用研究[J]. 控制工程,2020,27(3):567-571.(CHENG Y,WANG Y,XIU C B. Application research of an improved RRT algorithm in path planning[J]. Control Engineering of China,2020,27(3):567-571.)
[7] 谭建豪, 肖友伦, 刘力铭, 等. 改进PRM算法的无人机航迹规划[J]. 传感器与微系统,2020,39(1):38-41.(TAN J H,XIAO Y L,LIU L M,et al. UAV trajectory planning with improved PRM algorithm[J]. Sensors and Microsystems,2020,39(1):38-41.)
[8] KALISIAK M,VAN DE PANNE M. RRT-blossom:RRT with a local flood-fill behavior[C]//Proceedings of the 2006 IEEE International Conference on Robotics and Automation. Piscataway:IEEE,2006:1237-1242.
[9] JIMÉNEZ-FRANCO L D, KLETTING P, BEER A J, et al. Treatment planning algorithm for PRRT considering multiple tumor lesions and organs at risk[J]. Medical Physics,2018,45(8):3516-3523.
[10] 宋彦, 张羊阳, 姚琦, 等. 基于启发式动态规划的履带机器人路径跟随控制方法[J]. 农业机械学报,2019,50(11):24-33. (SONG Y,ZHANG Y Y,YAO Q,et al. Path following control method of tracked mobile robot based on heuristic dynamic programming[J]. Transactions of the Chinese Society of Agricultural Machinery,2019,50(11):24-33.)
[11] BABAIE O, NASR ESFAHANY M. Optimization and heat integration of hybrid R-HIDiC and pervaporation by combining GA and PSO algorithm in TAME synthesis[J]. Separation and Purification Technology,2020,236:No. 116288.
[12] BURCHARDT H,SALOMON R. Implementation of path planning using genetic algorithms on mobile robots[C]//Proceedings of the 2006 IEEE Congress on Evolutionary Computation. Piscataway:IEEE,2006:1831-1836.
[13] 宋宇, 王志明. 基于改进遗传算法的移动机器人路径规划[J]. 现代电子技术,2019,42(24):172-175.(SONG Y,WANG Z M. Path planning of mobile robot based on improved genetic algorithm[J]. Modern Electronics Technique,2019,42(24):172-175.)
[14] BESADA-PORTAS E,DE LA TORRE L,DE LA CRUZ J M,et al. Evolutionary trajectory planner for multiple UAVs in realistic scenarios[J]. IEEE Transactions on Robotics,2010,26(4):619-634.
[15] VOLKAN PEHLIVANOGLU Y. A new vibrational genetic algorithm enhanced with a Voronoi diagram for path planning of autonomous UAV[J]. Aerospace Science and Technology,2012, 16(1):47-55.
[16] VOLKAN PEHLIVANOGLU Y,BAYSAL O,HACIOGLU A. Path planning for autonomous UAV via vibrational genetic algorithm[J]. Aircraft Engineering and Aerospace Technology, 2007,79(4):352-359.
[17] YANG Q,YOO S J. Optimal UAV path planning:sensing data acquisition over IoT sensor networks using multi-objective bioinspired algorithms[J]. IEEE Access,2018,6:13671-13684.
[18] BEHROOZ K. A crossover operator for improving the efficiency of permutation-based genetic algorithms[J]. Expert Systems with Applications,2020,151:113381.
[19] QI Z,SHAO Z,PING Y S,et al. An improved heuristic algorithm for UAV path planning in 3D environment[C]//Proceedings of the 2nd Intelligent Human-Machine Systems and Cybernetics. Piscataway:IEEE,2010:258-261.
[20] 于洋, 周佳伟, 冯迎宾, 等. 基于三次B样条曲线的无人车轨迹优化方法研究[J]. 沈阳理工大学学报,2019,38(5):71-75. (YU Y,ZHOU J W,FENG Y B,et al. Research on trajectory optimization of unmanned vehicle based on cubic B-spline interpolation[J]. Journal of Shenyang Ligong University,2019,38(5):71-75.)
[21] 邱柳钦. 改进遗传算法在MF-TDMA资源规划中的研究[J]. 通信技术,2013,46(4):117-120.(QIU L Q. Improved genetic algorithm in MF-TDMA resource allocation[J]. Communications Technology,2013,46(4):117-120.)

基于改进遗传算法的无人机路径规划

Unmanned aerial vehicle path planning based on improved genetic algorithm

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	李开荣, 刘爽, 胡倩倩, 唐亦媛. 基于转角约束的改进蚁群优化算法路径规划[J]. 计算机应用, 2021, 41(9): 2560-2568.
[2]	张闻强, 邢征, 杨卫东. 基于多区域采样策略的混合粒子群优化求解多目标柔性作业车间调度问题[J]. 计算机应用, 2021, 41(8): 2249-2257.
[3]	张盟, 郭健全. 需求和回收不确定的闭环供应链渠道结构选择[J]. 计算机应用, 2021, 41(7): 2100-2107.
[4]	杨震, 马健霄, 王宝杰. 设置待行区条件下双环相位信号配时优化模型[J]. 计算机应用, 2021, 41(7): 2108-2112.
[5]	李进, 王凤, 杨沈宇. 换电模式下电动车货运路径优化模型与算法[J]. 计算机应用, 2021, 41(6): 1792-1798.
[6]	马子玉, 何明, 刘祖均, 顾凌枫, 刘锦涛. 无人机协同控制研究综述[J]. 计算机应用, 2021, 41(5): 1477-1483.
[7]	李舒仪, 韩晓龙. 海铁联运港口混合作业模式下轨道吊与集卡协同调度[J]. 计算机应用, 2021, 41(5): 1506-1513.
[8]	周美玲, 陈淮莉. 基于负荷平衡的电动汽车模糊多目标充电调度算法[J]. 计算机应用, 2021, 41(4): 1192-1198.
[9]	马晓梅, 何非. 基于改进遗传算法的标签印刷生产调度技术[J]. 计算机应用, 2021, 41(3): 860-866.
[10]	王彬溶, 谭代伦, 郑伯川. 基于旅行商问题转化和遗传算法求解汽配件喷涂顺序[J]. 计算机应用, 2021, 41(3): 881-886.
[11]	钟莎, 黄玉清. 基于孪生区域候选网络的无人机指定目标跟踪[J]. 计算机应用, 2021, 41(2): 523-529.
[12]	王家亮, 李树华, 张海涛. 基于贝叶斯估计与区域划分遍历的四轴飞行器避障路径规划算法[J]. 计算机应用, 2021, 41(2): 384-389.
[13]	焦海林, 郭玉英, 朱正为. 基于加速度补偿的无人机吊挂飞行抗摆控制[J]. 计算机应用, 2021, 41(2): 604-610.
[14]	魏博, 杨茸, 舒思豪, 万勇, 苗建国. 基于离子运动-人工蜂群算法的移动机器人路径规划[J]. 计算机应用, 2021, 41(2): 379-383.
[15]	张驰, 李铸洪, 刘舟, 沈未名. 基于场景图划分的无人机影像定位算法[J]. 计算机应用, 2021, 41(10): 3004-3009.