移动机器人路径规划蚁群算法及其收敛性分析

刘广瑞，刘 军，孔令云

(1.郑州大学机械工程学院，河南郑州450001;2.黄河科技学院工学院，河南郑州450005)

0 引言

移动机器人的路径规划是指搜索一条从起点到终点的最优或次最优的无碰撞路径使某性能指标最优或次优.路径规划可分为：全局路径规划和局部路径规划.其中，全局路径规划的环境信息是完全已知的，局部路径规划的环境信息是不完整或未知的.

蚁群优化算法的论述和研究较多［1-10］，蚁群算法收敛性分析也有不少［5-6，9］，但是把蚁群优化算法看做马尔科夫过程进行收敛性分析的并不多见.笔者的创新之处在于：将蚁群算法用于移动机器人的路径规划，将蚁群算法的迭代过程视为马尔科夫过程并进行了分析，在此基础上分析该算法的收敛性并提出了改善算法收敛性的途径.

1 路径规划蚁群算法的基本原理

蚁群优化(ACO)是蚁群算法的核心，其思路为：蚂蚁的个体行为非常简单，而它们的群体行为却很复杂;一群蚂蚁容易找到从蚁巢到食物源的最短路径，而单个蚂蚁则难以找到最短路径;蚁群能够适应环境的变化，当在它们的移动路线上突然出现障碍物时，它们能够很快重新找到最短路径.

1.1 环境模型的建立

采用栅格法建立移动机器人的环境模型，建模时首先作如下假设：

(1)机器人的工作空间为一个二维结构化空间，简记为RS;障碍物位置、大小已知且在机器人运动过程中均不发生变化.

(2)机器人的运动空间中分布着有限个已知的、大小不同的障碍物，障碍物可以由栅格描述，忽略障碍物的高度信息.

(3)假定机器人运动在二维平面上的凸多边形有限区域内.

该区域内分布着有限个大小不同的障碍物，在该区域内建立直角坐标系.假设机器人运动的步长为R，并且x轴和y轴均以R为单位来划分栅格.则每行的栅格数为：Nx=xmax/R;每列的栅格数为：Ny=ymax/R.

如果区域为不规则形状，可在边界处加上障碍栅格，补其为正方形或者长方形.补充的障碍物栅格若不满一个，以一个计算.栅格的位置可以用坐标或序列号描述，序列号与坐标是一一对应的，图1表示了栅格坐标与序列号之间的关系.

1.2 栅格标识方法

(1)直角坐标法.建立如图1所示的直角坐标系.x轴水平向右为其正方向，y轴竖直向下为其正方向，坐标原点在栅格阵左上角.用直角坐标(x，y)来表示任意栅格的位置.

(2)序号法.按照由左到右，由上到下的顺序，从栅格阵左上角第一个栅格开始，赋予每一个栅格一个序号n(从0开始计)，则序号n与栅格块一一对应，如图1所示.

图1 栅格坐标与序号的关系Fig.1 Relationship between grid coordinate and serial number

两种表示方法都能唯一地表示一个栅格，一个栅格的直角坐标和序号之间是一一对应的.

2 路径规划蚁群算法的收敛性分析

2.1 蚁群算法的迭代过程是马尔科夫过程

马尔科夫过程是俄国数学家Α.Α.马尔科夫于1907年首次提出的，是一类将来发生的事情与过去发生的事情无关的随机过程［1］.这种在已知“现在”的条件下，“将来”与“过去”独立的特性叫做马尔科夫性.从蚁群算法的概念可知蚁群算法的迭代过程是一个典型的随机过程.设蚁群在t=0，1，2，…，n 时，对应的状态分别为：E0，E1，E2，…，En.

若t=n时系统的状态已知，那么由蚁群算法的迭代过程可知：在t=n时以前的状态对t=n以后的状态没有任何影响，即在“现在状态”已知的情况下，“将来状态”与“过去状态”相互独立，这种过程就是马尔科夫性.

2.2 蚁群算法的收敛性分析

预设A，B两点之间有m条路径AC1B，AC2B，AC3B，…，ACmB，如图2所示.各条路径长度依次设为 d1，d2，d3，…，dm，不失一般性，假设 d1≤d2≤d3≤…≤dm.在算法预定的环境中有n只蚂蚁在A、B之间往返爬行，根据蚁群算法的特性可知，随着时间的推移，大多数蚂蚁应在路径AC1B上，此时我们就认为从出发点A到目标点B之间的最短路径是AC1B，蚁群算法以接近于概率1的趋势寻找最短路径.

以qi，k表示蚂蚁爬行第k趟后留在路径ACiB上的平均信息素，pi，k表示蚂蚁爬行第k趟后选择路径ACiB的平均概率.假设各条路径上的初始信息量相等，均为C.

图2 最短路问题Fig.2 Shortest route problem

定理 1 若 α≥0，β≥0，则 q1，k≥q2，k≥…≥qm，k，p1，k≥p2，k≥…≥pm，k，k=0，1，2，…，n.

证明：当 α≥0，β≥0 时，则

由 d1≤d2≤…≤dm，可得：p1，0≥p2，0≥…≥pm，0;qi，0= ρC+npi，0从而 q1，0≥q2，0≥…≥qm，0;

由上述推导过程可得

式中：ρ为信息素挥发系数.

由上述证明的过程可知：一个循环迭代结束后，路径AC1B上的传递介质浓度最高，因此路径AC1B将会被更多蚂蚁以较大概率选择.

把 pj，k-1与 p1，k-1的表达式代到以上公式：简化得到因 qj，k-1＜ q1，k-1，dj＞ d1，当 α≥1，β≥0 时，式子成立.那么＜0，k=1，2，…n，j=2，3，…，m.

定理 3 若 α≥1，β≥1，则 p1，k＞ p1，k-1，k=1，2，….

证明：由于

证明：根据上述证明过程可得，若α≥1，β≥1 时，那么 p1，k＞ p1，k-1，随机数列 p1，k单调递增，由高等数学极限理论知识易知“单调有界数列必有极限，且收敛到其上界”可得，若k→∝满足的条件下1.

3 改善蚁群算法收敛性的途径

蚁群算法的收敛性与信息素更新机制及参数匹配有很大的联系，可以从下述几方面改善算法的收敛性.

(1)两个指数α、β的选取至关重要，应选在合适的范围内;α≥1，β≥0，选择最优路径的概率才会趋近于1.

(2)由定理1，2的证明过程可知，信息素挥发系数ρ对算法的收敛速度有较大的影响，应重视该参数的选择.ρ愈小，过去信息挥发的愈快，算法收敛愈慢;ρ愈大，挥发的愈慢，算法收敛愈快.ρ应在0和1之间选择.

4 仿真计算

如图2所示，假设 A、B之间有4条路径AC1B，AC2B，AC3B，AC4B，路径长度分别为 1，1.05，1.1，1.15，蚂蚁数目 n=100，信息量 C=30，Q=1，ρ=0.6 .当 α =2，β=2时，算法收敛很快，选择概率的结果如图3所示;当α=0.8，β=1算法运行了200次后还没有收敛，信息素变化规律结果如图4所示.

当α=1.1，β=-0.9时，选择概率的结果如图5所示，虽然收敛，但不一定收敛到最短路径，如图3所示就收敛到路径AC2B中，由上述选择概率的收敛图可以看出：α≥1，β≥0是算法收敛的较好组合.

图5 当 α=1.1，β= －0.9时蚁群算法选择概率变化规律Fig.5 Selection probability varying rules of ant colony algorithm when α =1.1，β = －0.9

5 结论

为了寻找机器人从起点到终点的最优或次最优路径，笔者将蚁群算法应用于移动机器人的路径规划之中，阐述了蚁群算法的基本原理，分析了路径规划蚁群算法的收敛性，概括性地指出了改善蚁群算法收敛性的途径，并以最短路问题为例在设定参数下做了仿真计算.理论分析和仿真计算的结果均表明：指数在α≥1，β≥0的范围内时，算法有较好的收敛性.因此我们认为，指数α、β以及信息挥发系数ρ对算法的收敛性影响较大，应仔细选择.

［1］马良，朱刚，宁爱兵.蚁群优化算法［M］.北京：科学出版社，2008：15-150.

［2］高尚，杨靖宇.群智能算法及其应用［M］.北京：中国水利水电出版社，2006.

［3］高尚.解旅行商问题的混沌蚁群算法［J］.系统工程理论与实践，2005，25(9)：100-104.

［4］段海滨.蚁群算法原理及其应用［M］.北京：科学出版社，2005.

［5］冯远静，冯祖仁，彭勤科.一类自适应蚁群算法及其收敛性分析［J］.控制理论与应用，2005，22(5)：713-717.

［6］高尚，杨靖宇.最短路的蚁群算法收敛性分析［J］.科学技术与工程，2006，6(3)：273-277.

［7］COLORNI A.Heuristics from nature for hard combinatorial optimization problems［J］.Int Trans in Opnl Res，1996，3(1)：1-21.

［8］PIRLOT M.General local search methods［J］.European J of Opnl Res，1996，92(3)：493-511.

［9］赵霞，田恩刚.蚁群系统及其收敛性证明［J］.计算机工程与应用，2007，43(5)：67-70.

［10］KELLER Y，AVERBUCH A.Fast motion estimation using bidirectional gradient methods［J］.IEEE Trans on Image Processing，2004，13(8)：1042-1054.