Computer Engineering and Applications ›› 2022, Vol. 58 ›› Issue (1): 282-291.DOI: 10.3778/j.issn.1002-8331.2107-0369

• Engineering and Applications • Previous Articles     Next Articles

Research on Improved Ant Colony Algorithm for Robot Global Path Planning

ZHANG Tianrui, WU Baoku, ZHOU Fuqiang   

  1. School of Mechanical Engineering, Shenyang University, Shenyang 110044, China
  • Online:2022-01-01 Published:2022-01-06

面向机器人全局路径规划的改进蚁群算法研究

张天瑞,吴宝库,周福强   

  1. 沈阳大学 机械工程学院,沈阳 110044

Abstract: The problems of basic ant colony algorithm are solved including too large turning angle, easy to fall into local minimum and slow convergence speed of basic ant colony algorithm in the process of robot path planning. Based on the analysis of robot path planning environment modeling method, firstly, the corner heuristic function is introduced into the node selection probability formula to enhance the directivity of path selection and improve the search speed of the algorithm. Furthermore, the heuristic function is improved by introducing the quadratic sum of the distance between the current node and the next node, the distance between the next node and the target node, which makes the search process more targeted and reduces the probability of falling into local minimum. In addition, the pheromone volatilization factor adaptive update strategy is proposed to expand the search range and improve the convergence speed. Secondly, the crossover operation of genetic algorithm is used to optimize the mobile path twice to enhance the optimization ability of the algorithm. Then the path smoothing operation is introduced based on Floyd algorithm to reduce the number of nodes in the mobile path. Finally, the grid method is used to model the environment. Finally, compared with other algorithms by solving multiple unimodal test functions and multi-modal test functions in MATLAB, and the simulation comparison experiment of robot global path planning in grid environment modeling, so as to verify that the improved algorithm has more advantages in path optimization speed and quality. The simulation results show that the improved ant colony algorithm is feasible and effective.

Key words: path planning, improved ant colony algorithm, environmental modeling, grid method, genetic algorithm

摘要: 针对基本蚁群算法在机器人路径规划过程中路径转弯角度过大、易陷入局部极小值、收敛速度慢等问题,对其进行改进。在分析机器人路径规划环境建模方法基础上,将转角启发函数引入至节点选择概率公式,以增强路径选择指向性,提高算法搜索速度;通过引入当前节点与下一节点之间的距离和下一节点与目标节点距离之和的二次方对启发函数进行改进,使得算法搜索过程更有针对性,并降低陷入局部极小值概率;提出信息素挥发因子自适应更新策略,扩大算法搜索范围,提高收敛速度;利用遗传算法的交叉操作对移动路径进行二次优化,以增强算法的寻优能力,进而以Floyd算法为基础引入路径平滑操作,减少移动路径节点。在MATLAB中与其他算法通过求解多个单模测试函数与多模测试函数进行对比,并在栅格法环境建模中进行机器人全局路径规划仿真对比实验,以验证改进算法在路径寻优速度和质量上更具优越性。仿真结果表明,改进后的蚁群算法具有一定的可行性和有效性。

关键词: 路径规划, 改进蚁群算法, 环境建模, 栅格法, 遗传算法