一种改进栅格蚁群算法的机器人路径规划

梁玉清，李 妍，何静涛

(蚌埠学院计算机科学与技术系，安徽蚌埠 233030)

机器人路径规划是机器人在已知的环境中，自主寻找一条优化路径.多种算法都被应用于这一领域，实践中发现，单一的算法，往往存在着效率不高、搜索空间过大等缺点.而将几种算法结合在一起，利用各自的优点，可以使规划的路径相对最优.栅格法能确保稳定地找到优化路径，但栅格密度的大小会影响到算法的效率.蚁群算法模拟了蚂蚁寻找食物的路径行为，常用于解决机器人的路径规划问题，但也存在着收敛慢及容易出现停滞等不足之处［1－4］.

由于蚁群算法易于与其它算法结合，很多研究者提出了一些改进的蚁群算法.如文献［5］提出多级路径优化的路径规划策略，加强蚁群算法搜索的正反馈、高效收敛的优势，避免算法过早或过晚结束而影响划分算法的整体性能，使得信息栅格节点调度能依据任务量和路径性能进行有效分配.但在复杂结构的真实信息栅格环境下的节点调度效率还不是很高，在路径陷阱和可行路径的平滑性上仍需进一步解决.文献［6］在蚁群算法中融入了遗传算法的交叉、变异操作以加快算法收敛.改进后基于蚁群算法的路径搜索更简单，但如果遇到结构复杂、障碍物多的环境时，因为复杂度的提高，算法的性能会受到一定的影响.

本文提出的改进算法是，在栅格法对环境建模的基础上，通过调整距离启发信息等改进蚁群算法，提高复杂环境下最优路径搜索效率，仿真实验结果表明这种复合的算法在复杂环境下得到的路径最短，程序运行效率高.

图1 环境建模示意图Fig.1 Schematic diagram of environmental modeling

1 问题定义及建模

如图1所示，机器人起始位置为S(xs，ys)，目标位置为G(xg，yg)，以S点为坐标原点，SG为X'轴，垂直于SG的直线为Y'轴，将线段SG划分为m等分，再将每一等分线m等分，将规划范围分为m×m栅格.栅格点在新坐标系与原坐标系的关系如下，其中为α新坐标系旋转的角度.

机器人的位置坐标也用栅格坐标表示，机器人在某位置坐标p(x，y)与栅格坐标g(x，y)的对应关系为:

2 蚁群算法

栅格法建模中，将一个栅格的大小等效为一个实际机器人的大小;从一个栅格到另一个栅格的移动就相当于机器人实际从一个点移动到另外一个点;栅格模型中起始点到目标点的路径规划完成了，说明实际中机器人找到了一个起始点到目的点的路径.

以机器人在栅格内自由运动的最长距离Ra为步长，SG在X方向的最大值为Xmax，在Y方向的最大值为Ymax.每行的栅格数Nx=Xmax/Ra，每列的栅格数为Ny=Ymax/Ra.

任意栅格g的坐标g(x，y)，x=row，y=col，row是行号，col是列号，坐标值与序号i的对应关系根据式(2)确定:

蚁群算法中，信息素是引导蚂蚁运动的重要物质.蚂蚁选择信息素浓度较高的路移动，信息素浓度越高，选择的可能性越大，这是蚁群算法的正反馈特点［7－8］.

蚂蚁的转移有一定的规则，栅格i的蚂蚁k如何选择下一个栅格节点j，应按照公式(4)或者公式(5)列出规则执行，j∈allowedk且 j∉tabuk.allowedk是可行区域，tabuk是禁忌表［9］.

其中:q是在［0，1］区间均匀分布的随机数，q0是一个参数.当q＞q0时，须先计算可行节点的转移概率值，然后运用轮盘赌规则选择节点 j，以获得S值.τij是信息素轨迹强度，ηjg是能见度，一般将 ηjg的值设置为1/d(j，g)，d(j，g)表示距离.积累信息和启发信息的相对重要性用α、β表示.ρlocal是局部信息素挥发参数，且 0＜ρlocal≤1.

当一条完整的路径建立后，公式(6)将更新路径信息.Q是总信息量;己走过的路程用L表示.

在算法中，全局最优的蚂蚁才可以释放信息素，当所有蚂蚁完成路径后，式(7)将更新建立的路径.

ρglobal为全局信息素挥发系数，0＜ρglobal≤1.Lbest表示目前为止找出的全局最优路径长度.蚂蚁从栅格gi移动到栅格gj后，会及时更新局部信息素，目的是减少对后面的蚂蚁的吸引力，从而增加蚂蚁选路的多样性［10－11］.

3 改进蚁群算法

3.1 信息素的存储处理

信息素存储一般采用M×M节点模式.如一个20×20的栅格，信息素存储空间为400.但在蚁群算法路径规划中，只会用到很少的一部分，即每个节点邻域为8，因此只要建立周围8个节点的信息素关联，而且两节点间信息存储的无方向，所以每节点只需4个信息素关联，信息素存储空间大大降低.

3.2 调整距离启发信息

距离启发信息η一般设为η=1/Lij或η=1/Ljg.Lij是相邻两点的距离.Ljg是j到g的距离.第一条路径建立时，需要距离启发信息引导，往往会选择最短路径点.当η值为1/Lij时，蚂蚁倾向于走直线;当η的值为1/Ljg时，蚂蚁总倾向于走斜线而非直线，为了均衡两者的影响我们将η改进定义为下式所示的形式:

3.3 蚂蚁回退策略

遇到陷阱，一般的处理方法就是消除陷阱.即:在初始环境时，将障碍物作给予一定的设定，使环境中障碍物变成非凹形，因而凹形障碍造成的陷阱将不复存在.如图3所示.

更为复杂的是，该处理方法可以避免单个障碍物陷阱，但障碍物与障碍物之间、障碍物与环境边界之间的陷阱，如针对1→6→11→16或5→10→15→20的情形，没有有效的办法.为解决上述的问题，本文提出一种蚂蚁回退策略，步骤如下:

步骤2:蚂蚁从13回到8，N(k)=N(k)+1，tabu(N(k))=8.

步骤4:蚂蚁从8回到3，N(k)=N(k)+1，tabu(N(k))=3.

图2 落入陷阱Fig.2 Fall into the trap

图3 陷阱障碍物初始处理Fig.3 Traps obstades initial treatment

即使蚂蚁通过回退策略逃离了陷阱，但也会留下信息素，使得该陷阱周围的信息素有所增强，而下一代蚂蚁很容易再次选择此路径.如果这样的话，找到最短路径的时间会大幅度增加，甚至找不到最优化路径.因而，采用惩罚函数，使蚂蚁尽可能不重复陷阱周围的路径.遇到陷阱时，用惩罚函数代替原局部信息素更新公式，以减少陷阱周围路径上信息素，以提高搜索效率.惩罚函数定义如下:

3.4 改进蚁群算法的路径规划

步骤1:若干蚂蚁位于起始点，设信息素浓度初始值为l，最大循环次数Nc.

步骤2:蚂蚁周围有可转移节点吗?如果有，则计算τij，依据公式(4)、(5)选择下一个节点;如果没有，表明蚂蚁落入陷阱，应返回.

步骤3:蚂蚁是否到达目标点?到达，转步骤4;未到，转步骤2.

步骤4:所有蚂蚁都从起点到终点后，选出其中的最优路径和最差路径，利用公式(6)更新信息素.

步骤5:从路径中选出全局最优和最差，利用公式(7)进行信息素更新，Nc=Nc+1.

步骤6:是否达到最大循环次数Nc?已经达到，则进入步骤7，否则，返回步骤2.

步骤7:输出最优路径.

4 结果与分析

实验采用“博创科技”的自主移动机器人作为实验平台，该平台采用高负载能力和高运动精度的直流伺服控制，控制计算机为嵌入式控制器，配备多种传感器和机械手等执行器.

实验场地为6 m×6 m，划分栅格编号N为:0～399，机器人的起点(0，0)，栅格号N=0，终点为(0，19)，栅格号 N=19.障碍物设定为4个矩形，大小为20 cm×10 cm、15 cm×20 cm、40 cm×20 cm、10 cm×10 cm，在路径规划中机器人可以选择自由栅格作为它的路径点.

通过实验比较基本蚁群算法与改进蚁群算法，基本算法和改进算法各进行10次实验，对结果取平均值.设定最大循环次数为100次(外循环20次，内循环5次).实验结果见表1.

实验结果表明，对信息素更新规则进行修改后，路径长度有所缩短，转弯次数减少，路径的平滑度有一定优化.结果还显示，改进蚁群算法的平均迭代次数较之基本蚁群算法大幅减少，收敛性有了较好改善，但因为增加了对局部循环信息素的更新，使得运行时间有所增加.

改进蚁群算法每次实验的数据见表2.数据显示，每次实验都能找到最优路径，且平均路径长度与最优路径长度相同，说明该算法有较高的稳定性.实验迭代次数除其中有2次较高外，其它均小于18次，说明该算法能够很快地收敛.显然，改进算法的性能优于基本算法.

表1 基本算法与改进算法对照表Tab.1 Comparison table of the basic algorithm and improved algorithm

表2 迭代次数与最优路径长度Tab.2 Number of iterations and optimal path length

5 结论

在机器人的路径规划中，改进蚁群算法动态地调整ρ值，并将ρ值限制在［τmin，τmax］之间，并在算法步骤中，增添了选出局部最优值和局部最差值的步骤，在每轮循环结束后，增强最优，减弱最差，优化了路径长度和路径平滑度.但算法中增加了局部循环信息素的更新，运行时间比基本蚁群算法要长.

［1］张捍东，郑睿，岑豫皖.移动机器人路径规划技术的现状与展望［J］.系统仿真学报，2005，17(2):439－443.

［2］蔡自兴，贺汉根，陈虹.未知环境中移动机器人导航控制研究的若干问题［J］.控制与决策，2002，17(4):385－390.

［3］王志文，郭戈.移动机器人导航技术现状与展望［J］.机器人，2003，25(5):470－474.

［4］朱大奇，颜明重.移动机器人路径规划综述［J］.控制与决策，2010，25(7):961－967.

［5］吴沉寒，罗玉臣，陈炜.改进蚁群自适应多级栅格路径优化策略［J］.计算机工程，2009，35(9):185－186.

［6］范佳，钱徽，朱淼良，等.优化路径分配的多作业机器人任务规划［J］.计算机工程，2010，36(23):142－145.

［7］周兰凤，徐芳.一种考虑不确定性的机器人路径规划方法［J］.微电子学与计算机，2010，27(7):86－93.

［8］朱庆保.复杂环境下的机器人路径规划蚂蚁算法［J］.自动化学报，2006，32(4):287－293.

［9］Stuezle T，Dorigo M.A short convergence proof for a class of ant colony optimization algorithms［J］.IEEE Transactions on Evolutionary Computation，2002，6(4):358－365.

［10］Meng C，Wang T M.A global optimal path planning algorithm for mobile robot［J］.Robot，2008，30(3):217－222.

［11］Zhu Q B，Zhang Y L.An Ant Colony Algorithm Based on Grid Method for Mobile Robot Path Planning［J］.Robot，2005，27(2):132－135.