蚁群算法在机器人路径规划中研究及发展趋势

付 宁，张东霞，国海涛

(1.潍坊工程职业学院，山东青州 262500;2.鲁东大学，山东烟台 264025)

蚁群算法在机器人路径规划中研究及发展趋势

付 宁1，张东霞1，国海涛2

(1.潍坊工程职业学院，山东青州 262500;2.鲁东大学，山东烟台 264025)

移动机器人研究中的一个重要领域是机器人路径规划方法。本文对蚁群算法在机器人路径规划方法的研究现状进行了概括与总结，指出了各种改进方法的优点及不足，最后对其发展方向进行了展望。

移动机器人;蚁群算法;动态路径规划

1 蚁群算法基本原理

20世纪90年代，意大利学者 M·Dorigo、V· Maniezzao、A·Colorni等人从生物进化的机理中受到启发，通过模拟自然界蚂蚁寻食的行为，提出了一种全新的模拟进化算法：蚁群优化算法［1］(Ant Colony Optimization Algorithm简称ACOA)。其算法基本原理是：经过大量的研究发现，蚂蚁个体之间是通过一种称之为外激素的物质进行信息传递，从而能相互协作，完成复杂的任务。同时，蚂蚁在运动过程中，能够在它所经过的路径上留下一种物质，而且能够感知这种物质的存在及其强度，并以此指导自己的运动方向，蚂蚁倾向于朝着该物质强度高的方向移动。这种物质在蚁群算法中称为信息素。因此，由大量蚂蚁组成的蚁群的集体行为便表现出一种信息正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。蚂蚁个体之间就是通过这种信息的交流选择出最佳路线，达到搜索食物的目的。

2 蚁群算法在机器人路径规划中的应用现状

移动机器人路径规划［2］是指在有障碍物的工作环境中，寻找一条从给定起始点到终止点的较优的运动路径，使机器人在运动过程中能安全、无碰撞地绕过所有障碍物，且所走路径较短。移动机器人路径规划是机器人学中非常重要的研究分支，是研究机器人控制系统的重要基础问题，因而受到了广大研究者的关注并成为经久不衰的研究热点，在这一领域取得了很多重要成果，诸如传统的人工势场法［3］、A*算法［4］等。但传统的优化方法在机器人路径规划这类复杂非线性优化问题中缺乏自适应性，计算太复杂，优化过程缺乏鲁棒性［5］，近年来，随着智能方法的广泛应用，机器人路径规划方法也有了长足的进展，许多研究者把目光放在了基于智能方法的路径规划研究上。其中蚁群算法成为研究热点。

樊小平［6］等人首先将基本蚁群算法引入到机器人路径规划研究领域，并尝试在蚁群算法中通过调整避障系数，得到不同的优化轨迹。但由于传统的蚁群算法存在一定的不足，如算法收敛速度慢，不能解决复杂环境下尤其是具有凹型障碍环境的路径规划问题，所以随后很多学者对其进行了改进。文献［7］首次将蚁群算法与栅格法环境建模相结合用于机器人路径规划中，并提出了双蚂蚁思想，但该算法没有考虑机器人路径规划中的死锁问题。文献［8］中的算法提出了蚂蚁死亡的概念，即当蚂蚁无路可选时，蚂蚁死亡，重新初始化一只蚂蚁，这样避免了死锁。此文中也是采用双向蚂蚁相向搜索，但是两组蚂蚁采用的搜索策略不同。澳大利亚学者Russell设计了一种用于移动机器人的气味传感器导航机制［9］，并深入分析了蚁群算法在该领域应用的鲁棒性。瑞士学者Michael等将蚁群算法的程序编入微型机器人中，使众多微型机器人象蚂蚁一样协同工作，完成复杂任务。这项研究成果已被国际著名刊物《Nature》报道［10］。

文献［11］提出使用伪随机比例状态转移规则选择下一个节点，仅让每一代中最好的个体所走过的路径上的信息素进行更新，以加快收敛速度。由于强化了最优信息的反馈，会导致早熟、停滞现象。文献［12］提出最大 -最小蚂蚁系统(Max-Min Ant System，MMAS)，对路径上的信息素进行限制，虽然在一定程度上避免了早熟、停滞现象，但在解的分布较分散时收敛速度较慢。

传统的蚁群算法一方面存在算法初期信息素匮乏导致搜索时间过长，难以满足实时规划或导航的要求等缺陷;另一方面不能扩大解的搜索范围导致解空间的探索不够、搜索容易陷入局部最优导致搜索易于停滞，难以保证每次都能找到全局最优或者较优路径。虽然有的改进方法较好地避免了搜索的局部停滞，但是由于只更新最优路径上的信息素，因此也会导致路径的搜索陷入停滞。

3 蚁群算法在机器人路径规划中的研究趋势

目前蚁群算法用于机器人路径规划时所建立的模型与方案不是很成熟，仍具有很大的研究空间。虽然学者们提出了各种各样的改进蚁群算法，但所有的改进都是基于原始模型的，仍然有不少关键理论和技术问题急需解决。就目前改进的蚁群算法而言仍有共同问题存在：由于其信息素加强正反馈的同时造成了早收敛，无法对解空间进一步搜索，而不能发现全局最优路径。信息素的更新不是很合理使最优路径、次优路径、不可行路径之间的信息素差距不是很大，限制了搜索的多样性，容易陷入局部循环当中，以至于早熟，而不能发现全局最优。因此如何解决容易早熟、停滞和收敛速度之间的矛盾，如何在加大搜索空间的同时又能跳离局部最优解，是该领域当前急需解决的问题。

［1］Dorigo M，Maniezzo V，Colorni A.Ant system：optimization by a colony of coopera——ting agents［J］.IEEE Transactions on SMC，1996，26(1)：29-41.

［2］蒋新松.机器人学导论［M］.沈阳：辽宁科学技术出版社，1994.

［3］Min Gyu Park，Min Cheol Lee.Artificial Potential Field Based Path Planning for Mobile Robots Using a Virtual Obstacle Concept.IEEE/ASME International Conference on Advanced Intelligent Mechatronics，Kobe，Japan，2003：735-740.

［4］A.Yahja，S.Singb，A.Stenz.An Efficient On-line Path Planner for Outdoor Mobile Robots［J］.Robotics and Autonomous Systems，2000，32(2-3)：129-143.

［5］谢宏斌.动态环境中移动机器人路径规划的研究［D］.无锡：江南大学硕士学位论文，2003.

［6］Xiaoping Fan，Xiong Luo，Sheng Yi，Shengyue Yang，Heng Zhang.Optimal Path Planning for Mobile Robots Based on Intensified Ant Colony Optimization Algorithm［C］.Proceedings of the 2003 IEEE Intemational Conferenceon Robotics，Intelligent Systemsand Signal Processing，2003，(1)：131-136.

［7］朱庆保，张玉兰.基于栅格法的机器人路径规划蚁群算法机器人［J］.机器人，2005，27(2)：132-136.

［8］Mohd M.Mohamad，Matthew W.Dunnigan，Nicholas K.Taylor.Ant Colony Robot Motion Planning［C］.EUROCON 2005 IEEE：213-216.

［9］Russell R A.Ant t rails-An example for robots to follow［C］∥Proc of the 1999 IEEE Int Conf on Robotics and Automation.Detroit，1999，2698-2703.

［10］Michael J B K，Jean-Bernard B，Laurent K.Ant-like task and recruitment in coop- -erative robots［J］.Nature，2000，406 (31)：992-995.

［11］Mohd M.Mohamad，Matthew W.Dunnigan，Nicholas K.Taylor.Ant Colony Robot Motion Planning［C］.EUROCON 2005 IEEE：213-216.

［12］Stutzle T，Hoos H H.Max-min ant system［J］.Future Generation Computer System，2000，16(8)：889-914.

2011-08-24

付宁(1981-)，男，山东青州人，潍坊工程职业学院讲师。

TP242 文献标志码：A 文章编号：1009-2080(2011)05-0081-02

(责任编辑：潘 敏)