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

林海涛　徐高晶　徐韬　俞学宏

摘要：该文将蚁群算法运用到机器人全局路径规划上，主要针对蚂蚁算法在搜索路径过程中落入障碍物陷阱而造成算法停滞的现象，提出了改进策略，同时基于对机器人所处环境的表示方法及算法中对应问题的描述和定义的研究，对相关参数进行了改进探讨。通过对算法的改进，增强了机器人的蚁群算法在复杂环境路径规划下的适应能力。

关键词：机器人；路径规划；蚁群算法

中图分类号：TP18 文献标识码：A 文章编号：1009-3044（2015）01-0130-03

1 环境描述

机器人在路径规划前必须建立其所处的环境模型，假设机器人所处环境中存在有限数量的静止障碍，并且障碍物大小位置已知，并且当机器人处于动态情况下，障碍的方位和形状都是恒定的。利用机器人的传感器获取环境的相关信息后，提取相关环境信息数据，完成环境数据搜集后，将搜集到的图像按照栅格来划分，并且栅格内部有障碍物与无障碍物栅格分别用阴影实体与空白表示，处理之后可以得到障碍物分布在各个栅格内，对未布满整个栅格的按照一个栅格来计算。

2 蚁群算法及相关问题描述

2.1 算法原理

研究发现：在寻找食物的过程中，蚂蚁自身会释放一种信息素，该元素可以被其他个体所感知，并且会倾向于朝着信息素浓度高的方向移动，所以，在蚂蚁寻找食物的过程中，群体的行为会呈现出一种趋势：如果某一个目标路径的距离越短，则该路径上蚂蚁的通过率越高，在该路径上信息素的释放量也是越多，而后来的蚁群都会感知信息素浓度大小，并会倾向于选择距离最短的那条路径，蚂蚁个体之间这种搜寻食物的过程也是蚁群算法的最初基础，蚁群算法实际就是模拟蚂蚁群体寻找食物过程的优化算法。

通过对N个城市的TSP问题求解可得到蚁群算法的基本模型。城市的TSP问题就是要寻找求解出从出发城市到终点城市距离最近的路径，其中的条件就是该过程需要通过每一个城市，且只能通过一次。设m表示蚂蚁数量，[dij（i，j=1，2，???，m）]表示城市i和城市j之间的距离，[τij（t）]表示t时刻i，j连线上的信息量，设[τij（0）=C]为常数。任一蚂蚁k（k=1，2，...，m），它的移动方向是由路径上信息量的含量决定的，在t时刻蚂蚁由i向j移动的概率[pkij（t）]可由下式表示：

[pkij（t）=[τij（t）]α?[ηij（t）]βs∈allowedk[τij（t）]??[τij（t）]β，j∈allowedk0， 否则]

上式中，[τij]表示t时刻i、j连线上的信息素量；[ηij]表示t时刻蚂蚁从i移动到j的期望程度；[allowedk]表示蚂蚁下一次移动可以选择的城市，[allowedk]={1，2，...，n}-[tabuk]；α，β分别代表某一路段上的[τij]和[ηij]的重要程度；[tabuk]表示蚂蚁已走过城市的集合，当[tabuk]将所有城市包含时，表示蚂蚁已完成了一次路径选择，并且该选择路径成为最优路径问题的备选解。

2.2 相关问题的描述与定义

对于机器人路径规划问题，可以设起始点为[gbegin]，终结点为[gaim]，具体描述如下：

1） City={1，2，...，n}表示划分区域的集合；Ant={1，2，...，m}表示蚂蚁的集合；G={[g1，g2，???，gN?N]}，G为所有栅格节点[gi]的集合。

2） 蚂蚁经过路段上留下的信息素会随着时间的积累逐渐挥发消散，有下式：

[τij（t+h）=（1-ρ）τij（t）+Δτij（t）]

上式表示蚂蚁t时刻在分割区[pi，pj]连线上所剩的信息素，[τij（t）∈[τmin，τmax]]，其中[ρ]为信息素挥发系数，[Δτij（t）=k=1m]为该次运动过程中路径i，j上的信息增量：

[Δτij（t）=k=1mΔτkij]

且：

[Δτkij=QLk，第k只蚂蚁在h时间内走过路径p（i，j）0， 否则]

其中，Q为常数，[Lk]为第k只蚂蚁选择路径的总长度。

3） 任意分割区间的距离是指两分割区间中心点的连线长度，即[d（pl，pm），l，m∈G]，则可以计算：

[d（pl，pm）=（xl-xm）2+（yl-ym）2]

2.3 算法改进策略

机器人处在实际环境中搜索路径时可能会遇到可陷入的障碍，这样会造成蚂蚁无法选择下一分割区，如表1所示，蚂蚁k在众多可选择爬行路径中，假设选取的是从[g7]处到[g12]，再到[g17]，此时蚂蚁将无后续结点可以选择，即落入陷阱，此时，该蚂蚁就会停滞不前，最终导致算法提前停滞，对于这种问题，通常采取的方法是，在初始化环境过程中，假定环境中存在的这类障碍都为凸状而不是凹状，以排除由凹状障碍引起的算法停滞问题。表1的栅格环境进行凸处理后得到的结果示意如表2所示。

在蚂蚁前进过程中，如果出现没有后续分割区供选择的情况时，我们就判定此时的蚂蚁已经陷入障碍，需要退回到上一个分割区，然后开始再一次的判定，判定依据和执行过程都相同，直到蚂蚁不再陷入障碍为止。蚂蚁在退回时，需要将未退回时的当前栅格加入蚂蚁的禁忌表，以保证该蚂蚁不会落入一个障碍两次，最终蚂蚁完成整个路径的搜索。

2.3.1 蚂蚁算法参数的改进

1） 信息量[τij（t）]和期望度[ηij（t）]分析。[τij（t）]是表示過去的信息素，而[ηij（t）]则是表示未来信息的载体，他们会对蚁群算法的求解范围和效率产生很大的影响。该文中的各个路径段上的[τij（t）]的更新要从全局和局部展开，[ηij（t）]为相关路段长度的倒数。

2） [τij]启发式因子α和[ηij]启发式因子β的选取。其中α的值越大，蚂蚁选择过去路径的可能性越大，选择的随机性也随之减少；如果其值过小，则会增加路径选择的随机性，只能局部性选择，而不能实现全局规划。β的值越大，则蚂蚁选择路径时选择局部最短路径的可能性较大，这样就会容易陷入局部最优。该文两个参数取值在0-5之间。

3） 挥发系数[ρ]分析。[ρ]的取值过大时，之前被搜寻的路径很有可能被再次选中，这样就会降低算法的全局规划能力和随机性，如果取值过小，会降低算法的收敛速度，影响搜索效率。所以，信息素挥发系数的选择，必须要同时考虑到算法的全局规划能力和搜寻速度，[ρ]可以取0.9。

2.3 改进蚁群算法的实现

改进的算法流程图如图3所示。

3 结论

本文首先利用栅格法对机器人的移动环境进行建模，在此基础上，主要针对在复杂地形环境中，蚁群算法容易导致蚂蚁陷入“陷阱”而造成的算法停滞的现象，对蚁群算法进行了改进，最后得到改进蚁群算法的相关流程与步骤，使得蚁群算法的鲁棒性和适应性得到提高，增强了蚁群算法在复杂环境下的适应能力，使其能够有效解决复杂环境中的机器人路径规划问题。

参考文献：

[1] 蔡自兴.机器人学[M].北京：清华大学出版社，2009：256-261.

[2] 乔茹.基于改进蚁群算法的移动机器人全局路径规划[J].安徽工业大学学报，2009，26（1）：77-80.

[3] 朱庆保.复杂环境下的机器人路径规划蚂蚁算法[J].自动化学报，2006，32（4）：287-293

[4] 任春明，张建勋.基于优化蚁群算法的机器人路径规划[J].计算机工程，2008，34（15）：1-3，35.

[5] LIU Shi-rong，MAO lin-bo.Path Planning Based on Ant Colony Algorithm and Distributed Local Navigation for Multi-Robot-Systems[C]//2006 IEEE International Conference on Mechatronics and Automation，2006：1733-1738.