基于改进ACS算法的移动机器人路径规划研究

来源:用户上传      作者:马小陆 梅宏 龚瑞 王兵 吴紫恒

　　 摘 要：针对蚁群系统（Ant Colony System，ACS）算法存在收敛速度慢、路径不平滑、易陷入局部最优等缺点，提出了一种基于万有引力搜索策略的ACS算法. 为了解决算法初期由于地图信息匮乏，导致蚁群寻路盲目性较大的问题，提出了简化ACS算法对初始信息素浓度进行更新. 引入万有引力算法搜索策略，提升了算法收敛速度，且有效解决了局部最优问题. 对每次迭代获取到的最优路径进行优化，减少了路径的转折点数量、提升了路径平滑性. 仿真试验表明，改进算法能够有效提升算法的收敛速度、路径平滑性. 将改进算法应用到实际的移动机器人导航试验中，试验结果表明，改进算法能够有效解决移动机器人的路径规划问题，且有效提升移动机器人的导航效率.
　　 关键词：移动机器人;路径搜索;最优路径;蚁群系统算法;万有引力算法
　　 中图分类号：P242.6 文I标志码：A
　　Research on Path Planning of Mobile Robot
　　Based on Improved ACS Algorithm
　　MA Xiaolu1，2?，MEI Hong1，2，GONG Rui1，2，WANG Bing1，2，WU Ziheng1，2
　　（1. School of Electrical and Information Engineering，Anhui University of Technology，Maanshan 243032，China;
　　2. Anhui Province Key Laboratory of Special and Heavy Load Robot，Maanshan 243032，China）
　　 Abstract：Aiming at the shortcomings of slow convergence speed， unsmooth path and easy to fall into local optimum in Ant Colony System（ACS） algorithm， an ACS algorithm based on gravitational search strategy is proposed. Firstly， in order to solve the problem that the lack of map information in the initial stage of the algorithm leads to the great blindness problem of ant colony algorithm， a simplified ant colony algorithm is proposed to update the initial pheromone concentration; secondly， the search strategy of gravity algorithm is introduced to improve the speed of the later algorithm and effectively solve the local optimal problem; finally， the optimal path obtained by each iteration is optimized， which reduces the number of turning points and improves the smoothness of the path. Simulation results show that the improved algorithm can effectively improve the convergence speed and path smoothness of the algorithm. Additionally， the improved algorithm is applied to the actual mobile robot navigation experiment. The experimental results show that the improved algorithm can effectively solve the path planning problem of mobile robot， and effectively improve the efficiency of robot navigation.
　　 Key words：mobile robots; path search; optimal path;Ant Colony System（ACS） algorithm;Gravitational Search Algorithm（GSA）
　　 路径规划问题是移动机器人研究的重点对象之一，是指移动机器人依据现有信息规划出一条从起始位置安全到达目标位置，且满足各项性能指标的完整路径[1]. 近年来，国内外学者对路径规划问题进行了大量的研究，并取得了一定的成果. 传统路径规划算法有Dijkstra算法[2]、A*算法[3]、人工势场法[4]等，随着移动机器人工作空间复杂度的提升，逐渐涌现出一系列的智能仿生算法，如遗传算法[5]、粒子群算法[6]、人工蜂群算法[7]等.
　　 蚂蚁系统（Ant System，AS）是由Dorigo等[8]提出的一种模拟自然界中蚂蚁觅食行为的仿生算法. 虽然AS算法已经能够有效解决移动机器人路径规划问题，但是依旧存在收敛速度慢、易陷入局部最优等问题，因此，Dorigo等[9]于1997年提出了蚁群系统（Ant Colony System，ACS）. ACS算法具有并行性、强鲁棒、易实现等优点，可以有效解决移动机器人路径规划问题，但是ACS算法仍存在寻路速度慢、易陷入局部最优、路径不平滑等问题. 针对上述问题，国内外学者提出了多种优化方法. 文献[10]引入了蚁周模型更新信息素，提高了蚁群搜索效率，降低局部最优概率;文献[11]提出了一种A*算法和ACS算法的融合算法，加快了算法的收敛速度，提高了最优路径的质量;文献[12]引入了信息素阈值，提高了算法的全局搜索能力，增加了最优路径的多样性;文献[13]提出了一种自适应启发函数，提高了蚁群的寻路效率，加快了算法的收敛速度.
转载注明来源:https://www.xzbu.com/4/view-15422064.htm