Computer Engineering and Applications ›› 2022, Vol. 58 ›› Issue (6): 278-286.DOI: 10.3778/j.issn.1002-8331.2109-0106

• Engineering and Applications • Previous Articles     Next Articles

Application of Multi-strategy Ant Colony Algorithm in Robot Path Planning

LIU Shuangshuang, HUANG Yiqing   

  1. 1.Key Laboratory of Advanced Perception and Intelligent Control of High-End Equipment, Ministry of Education, Anhui Polytechnic University, Wuhu, Anhui 241000, China
    2.Anhui Key Laboratory of Electric Drive and Control, Anhui Polytechnic University, Wuhu, Anhui 241000, China
  • Online:2022-03-15 Published:2022-03-15

多策略蚁群算法在机器人路径规划中的应用

刘双双,黄宜庆   

  1. 1.安徽工程大学 高端装备感知与智能控制教育部重点实验室,安徽 芜湖 241000
    2.安徽工程大学 安徽省电气传动与控制重点实验室,安徽 芜湖 241000

Abstract: In a two-dimensional environment, the ant colony algorithm is prone to slow convergence when planning paths, and the paths obtained from the search are sub-optimal paths. To address these problems, a new multi-strategy improved ant colony algorithm is proposed to improve the path finding performance and search efficiency. A non-uniform pheromone distribution is used according to the position of the current grid relative to the starting point, so that the initial pheromone concentration of the dominant grid is higher to avoid blind search by ants. The angle guidance factor is used to increase the guiding effect of the endpoint, the obstacle influence factor is increased to avoid the paths from deadlock as well as to reduce the occurrence rate of zigzag paths. The double-layer elite ant strategy is used to increase the pheromone content of the best path to prevent the algorithm from falling into local optimum and improve the convergence of the algorithm. The experimental results show that, the optimization and convergence ability of the improved algorithm have been greatly improved.

Key words: path planning, ant colony algorithm, non-uniform pheromone, angle guide factor, obstacle influence factor, elite ants

摘要: 在二维环境中,蚁群算法规划路径时易出现收敛慢,搜索得到的路径是次优路径等问题。针对这些问题,提出一种新式多策略改进的蚁群算法以提高路径寻优性能和搜索效率。根据当前栅格相对于起始点的位置采用非均匀信息素的分布方式,使得优势栅格的初始信息素浓度较高,避免蚂蚁盲目搜索;采用定向邻域扩展策略重新定义蚂蚁移动规则,进一步缩短路径并提高搜索效率;利用角度引导因子增加终点的指导作用,增加障碍物影响因子避免路径陷入死锁以及降低曲折路径的出现率;采用双层精英蚁策略加大最佳路径的信息素含量,防止算法陷入局部最优,提升算法收敛性。实验结果表明,经过改进后,算法的寻优性和收敛能力都得到了极大的提升。

关键词: 路径规划, 蚁群算法, 非均匀信息素, 角度引导因子, 障碍物影响因子, 精英蚂蚁