Computer Engineering and Applications ›› 2021, Vol. 57 ›› Issue (15): 279-285.DOI: 10.3778/j.issn.1002-8331.2103-0071

Previous Articles     Next Articles

Three-Dimensional Terrain Path Planning Based on Sight Range and Genetic Algorithm

HE Jiao, TAN Dailun   

  1. School of Mathematics and Information, China West Normal University, Nanchong, Sichuan 637000, China
  • Online:2021-08-01 Published:2021-07-26

基于视野范围和遗传算法的三维地形路径规划

贺娇,谭代伦   

  1. 西华师范大学 数学与信息学院,四川 南充 637000

Abstract:

For 3D terrain path planning, in order to overcome the uncertainty of terrain and learn from the working mechanism of biological vision system in nature, the concept of sight range in path planning is proposed. With the help of spatial geometric projection method, the construction of sight range is realized, and the detection algorithm of sight range is established, which is integrated into the population initialization and mutation strategy of genetic algorithm. So that the individual population of genetic algorithm(walking path) is always in the sight range, so as to avoid the terrain obstacles naturally, ensure the feasibility of the path, do not need to design repair operator, reduce the complexity of the algorithm. The simulation results show that the optimal path length obtained by the former can be reduced by 18.7% on average, and the solution performance and efficiency are higher. This provides some new ideas and methods for the combination of bionics and modern swarm intelligence algorithm.

Key words: three-dimensional terrain, path planning, geometric projection, sight range, genetic algorithm

摘要:

对三维地形路径规划,为克服地形的不确定性,借鉴自然界生物视觉系统的工作机制,提出了路径规划中的视野范围概念,借助空间几何投影方法实现了视野范围的构建,建立了视野范围的检测算法,并融合到遗传算法的种群初始化和变异策略中,使得遗传算法的种群个体(行走路径)总在视野范围内,从而自然避开地形障碍,确保了路径的可行性,不必再设计修复算子,降低了算法复杂度。仿真实验以融合视野范围的遗传算法和蚁群算法分别求解,结果表明前者求得的最优路径长度平均能降低18.7%,且求解性能和效率更高。这为仿生学与现代群智能算法的结合提供了一些新的思路和方法。

关键词: 三维地形, 路径规划, 几何投影, 视野范围, 遗传算法