Abstract: To solve the contradictory between the convergence speed and the local optimum, a hybrid ACS algorithm for robot global path planning problem is presented. The algorithm consists of a combination of Dijkstra algorithm for finding a sub-optimal free path and an improved ACS algorithm for optimizing the sub-optimal path. Then, it defines a new heuristic information function which increases the population diversity and a modified crossover operator for avoiding getting trapped in the local optimum and improving the solution quality. The results of simulation experiments confirm that the proposed algorithm is effective and has better performance in solution quality and search efficiency as compared with the path planning method in the literature. It is observed that the hybrid ACS algorithm can find better target traversal paths and spend less time with faster convergence speed for multi-target path planning problems in the complex environment.

Key words: global path planning, ant colony system, Dijkstra algorithm, heuristic information function, multi-target

摘要： 针对蚁群算法易陷入局部最优的缺点以及收敛速度与局部最优的矛盾，提出一种求解移动机器人全局路径规划的改进混合蚁群系统算法。该算法由两部分组成：Dijkstra算法用于规划出一条次优路径;进一步用改进的蚁群系统算法优化次优路径以获得最优路径。在改进的蚁群系统算法中，首先定义了一种新的启发信息函数来增加种群多样性;然后给出改进的交叉算子避免算法陷入局部最优，并进一步提高解的质量。仿真结果表明：所提出的算法与参考文献中的算法相比搜索效率更高，解的质量更好，性能更优。即使在障碍物复杂的环境中，对于多目标点问题，该算法仍能规划出较好的目标遍历路径，且用时时间较少。

关键词: 全局路径规划, 蚁群系统算法, Dijkstra算法, 启发信息函数, 多目标点