Journal of Computer Applications ›› 2021, Vol. 41 ›› Issue (2): 390-397.DOI: 10.11772/j.issn.1001-9081.2020060797

Special Issue: 人工智能

• Artificial intelligence • Previous Articles     Next Articles

Unmanned aerial vehicle path planning based on improved genetic algorithm

HUANG Shuzhao1, TIAN Junwei2, QIAO Lu2, WANG Qin2, SU Yu2   

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

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

黄书召1, 田军委2, 乔路2, 王沁2, 苏宇2   

  1. 1. 西安工业大学 电子信息工程学院, 西安 710021;
    2. 西安工业大学 机电工程学院, 西安 710021
  • 通讯作者: 黄书召
  • 作者简介:黄书召(1995-),男,陕西安康人,硕士研究生,主要研究方向:无人机路径规划;田军委(1973-),男,陕西渭南人,教授,博士,主要研究方向:视觉检测、测量与控制;乔路(1995-),男,陕西渭南人,硕士,主要研究方向:无人机、无人车路径规划;王沁(1981-),男,陕西西安人,讲师,博士,主要研究方向:机电系统设计、嵌入式系统、特种机器人;苏宇(1982-),男,陕西西安人,讲师,博士,主要研究方向:绳牵引并联机器人、特种机器人、机械电子、环境监测。
  • 基金资助:
    陕西省科技统筹创新工程计划项目(2015KTZDGY-02-01);陕西省重点研发计划项目(2020GY-188,2020NY-148)。

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

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

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

CLC Number: