计算机工程与应用 ›› 2018, Vol. 54 ›› Issue (19): 129-134.DOI: 10.3778/j.issn.1002-8331.1706-0080

• 模式识别与人工智能 • 上一篇    下一篇

基于改进蚁群算法的机器人路径规划问题研究

朱  艳1,游晓明1,刘  升2,袁汪凰1   

  1. 1.上海工程技术大学 电子电气工程学院,上海 201620
    2.上海工程技术大学 管理学院,上海 201620
  • 出版日期:2018-10-01 发布日期:2018-10-19

Research for robot path planning problem based on improved Ant Colony System(ACS) algorithm

ZHU Yan1, YOU Xiaoming1, LIU Sheng2, YUAN Wanghuang1   

  1. 1.College of Electronic and Electrical Engineering, Shanghai University of Engineering Science, Shanghai 201620, China
    2.School of Management, Shanghai University of Engineering Science, Shanghai 201620, China
  • Online:2018-10-01 Published:2018-10-19

摘要: 针对蚁群算法收敛速度慢,容易陷入局部最优的问题,结合A*算法和蚁群算法提出了一种解决机器人路径规划问题的改进蚁群算法。自适应调整启发函数,在路径的后程借鉴启发式A*算法的估价函数,在ACS算法的启发函数中引入方向信息,提高算法的搜索效率,同时动态调整权重系数改变目标点的方向信息在蚂蚁移动过程中的影响,以平衡ACS算法解的多样性和收敛速度慢之间的关系。仿真实验表明,该算法不但可以提高收敛速度,而且在改善解的质量方面也取得了较好的效果。

关键词: 蚁群算法, A*算法, 路径规划, 启发函数, ACS算法

Abstract: In view of the problem that the ant colony algorithm has a slow convergence speed and easily falls into the local optimal, an improved ant colony algorithm is proposed to solve the problem of robot path planning by combining the A star algorithm and ant colony algorithm. Adaptive adjustment of the heuristic function, in the later stage, using the evaluation function of the A star algorithm to extract the direction information in the heuristic function of the Ant Colony System(ACS) algorithm, and the search efficiency of the algorithm is improved. The direction information of the target is dynamic changed in the process of the ants moving to balance the relationship of the ACS algorithm between the diversity and the slow convergence rate. Simulation results show that the proposed algorithm not only improves the convergence rate, but also achieves good results in improving the quality of the solution.

Key words: ant colony algorithm, A star algorithm, path planning, heuristic information function, Ant Colony System(ACS) algorithm