机器人全局路径规划的混合蚁群系统算法  

Hybrid ACS algorithm for robot global path planning

作　　者：吕金秋[1] 游晓明[1] 刘升[2] 

机构地区：[1]上海工程技术大学电子电气工程学院,上海201620 [2]上海工程技术大学管理学院,上海201620

出　　处：《计算机工程与应用》2016年第11期38-43,共6页Computer Engineering and Applications

基　　金：国家自然科学基金(No.61075115);上海市教委科研创新重点项目基金(No.12ZZ185);上海市学科专业建设项目(No.XKCZ1212)

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

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

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]