《武汉工程大学学报》 2009年05期
76-79
出版日期：2009-05-28
ISSN:1674-2869
CN:42-1779/TQ
一种新的基于MMAS的机器人路径规划方法
0引言1991年，意大利学者Dorigo［1］等人通过模拟蚂蚁觅食行为提出了蚁群算法，该算法具有响应快和环境鲁棒性强等特点［2］.蚂蚁算法在求解TSP问题、二次分配问题、以及job2 shop问题上取得了很大成功.后来，人们提出了一些改进算法，如：最大最小蚂蚁算法，蚁群系统等，其中，最大最小蚂蚁算法具有最优性能.本文在介绍这种算法的同时，阐述该算法在机器人路径规划方面的应用.1蚁群算法1.1基本蚁群算法蚁群算法的基本思想就是模仿蚂蚁的信息素进行通信而显示出的社会行动.仿效自然界的蚁群行为，蚁群算法的描述如下［2］：蚂蚁个体之间通过一种称之为信息素的物质进行信息传递，蚂蚁在运动过程中能够感知到这种物质的存在及其强度，倾向于朝着该物质强度高的方向移动.因此，某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大［3］，蚂蚁之间就是通过这个信息的交流达到搜索食物的目的.为了便于理解，通常以蚁群系统求解平面上n个城市的TSP问题为例来说明蚁群算法模型［4］.假设有n个城市，TSP问题的目标是寻找一个路径最短的最优旅行路线，旅行商经过所有城市并回到原出发城市，除出发城市外，每个城市只允许经过一次，TSP问题的可行解即为除出发城市外所有城市的一个无重复序列.假设将m只蚂蚁放入到给定的n个城市中，那么每一只蚂蚁每一步的行动将符合下列规律：（1） 根据路径上的信息素浓度，以相应的概率来选取下一个城市.（2） 不再选取自己本次循环已经经过的城市为下一个城市.（3） 当完成一步从一个城市到达另外一个城市或者一个循环完成对所有n个城市的访问后，更新所有路径上的残留信息浓度.蚂蚁在选择下一个城市的依据主要是两点：（1）τij（t）为t时刻连接城市i和j的路径上残留信息的浓度，则在t+1时刻此路径上的信息素浓度为 τij（t+1）=ρτij（t）+∑mk-1Δτkij（1）
式（1）中，ρ为一个取值在0-1之间的常数，1-ρ表示信息素的挥发，Δτkij是第k只蚂蚁在时刻t-t+1之间的路径（i，j）上的增加的信息素浓度. Δτkij=Qdij，Q是（固定）常量值.dij是节点i和节点j之间的路径长度.（2）ηij（t）为由城市i转移到城市j的启发信息，该启发信息是由要解决的问题给出的，由一定的算法实现.那么，t时刻位于城市i的蚂蚁k选择城市j为目标城市的概率为
Pkij（t）=［τij（t）］α·［ηij］β∑［τij（t）］α·［ηij］β，j∈ALLOWEDk
0，otherwise（2）
式（2）中，α为信息启发式因子，β为期望启发式因子，α、β的最佳组合由实验而确定.ALLOWEDk表示蚂蚁k下一步允许选择的城市.Pkij（t）为t时刻蚂蚁k由城市i转移到城市j的概率.也即，蚂蚁选中某一个城市的可能性是问题本身所提供的启发信息与从蚂蚁目前所在城市到目标城市路径上残留信息量的函数.1.2最大最小蚂蚁系统最大最小蚂蚁系统，简称MMAS，是到目前为止求解TSP和QAP等问题最好的蚁群算法模型［4］.MMAS算法直接来源于基本蚂蚁算法（AS），主要作了如下的改进.
1.2.1信息素更新一次循环中只有最短路径的蚂蚁才进行信息素修改增加，其更新规则为：τij（t+1）=ρτij（t）+∑mk-1Δτbestij（3）
其中
Δτbestij=Qf（Sbest）（4）
式（4）中，f（Sbest）表示本次周游最优蚂蚁或全局最优蚂蚁值.利用公式（1）、（2）、（3）对各路径上的信息素做出调整.
1.2.2信息素限定为了避免算法过早收敛到非全局最优解，MMAS将各路径的信息素浓度限制在［τmin，τmax］之间，超出这个范围的值被强制设为τmin或者τmax.τmax的设置是一个渐进的过程，在算法启动时将所有支路上的信息素浓度初始化为最大值，每次迭代后，ρ按挥发系数降低痕迹浓度，只有最佳路径上的支路才允许增加其浓度，并保持在高水平上.τmin的值可以根据经验选取.MMAS可以有效地避免某条路径上的信息量远大于其余路径，使得所有的蚂蚁都集中到同一条路径上，从而使算法不再扩散.
第5期张彦铎，等：一种新的基于MMAS的机器人路径规划方法
武汉工程大学学报第31卷
1.2.3信息素初始化为了更加充分地进行寻优，各路径信息素初始化为一个很大的值（通常大于τmax），由于信息素范围的限制，在第一次迭代后设为最大值τmax，这样可以在一开始迭代时增大搜索的范围.将信息素初始化为τmax，是让可行解的各元素间信息素浓度差别不会过大，这样可以使算法遍历搜索空间，不致早熟.从实验结果看，MMAS算法在防止算法过早停滞及有效性方面对AS算法有较大的改进，明显优于AS.2基于MMAS的机器人路径规划
方法机器人规划就是在复杂的结构空间中，找到一条由起始点到目标点避障的可行路径［56］.根据一定的采样精度，将机器人的结构空间离散化为一系列网格点.可以采用均匀采样方法，也可以采用非均匀采样方法，如在窄过道的困难区域提高采样精度.起始点和目标点都位于网格点上［7］，障碍物位于两者之间.机器人每次只能移动一个网格，有两种移动方式：四邻域和八邻域.一般采用八邻域的精度要好于四邻域.在MMAS算法的基础上，提出了机器人路径规划改进算法的迭代计算过程，根据以下步骤：机器人在移动过程中，根据所收集的周围环境的信息，会产生多条由起点到终点的可行路径；假设每条路径代表一只蚂蚁的爬行踪迹；对每条路径计算其长度，然后将计算出的路径长度与目前记录的最短路径进行比较，如果计算出的当前路径长度比所记录的最短路径值更小，将其替换到最短路径的记录中.如果经反复计算后的值达到终止条件（即多数蚂蚁最终选择的路径，在一定时刻范围内没有更好的解），则此时路径为可行的最优路径.若提高机器人结构空间的采样精度，会得到一条更光滑的路径，但算法所需蚂蚁数和计算时间要成倍增加.若采样精度低，虽然计算时间会减少，但通常得到的路径不够平滑，有时甚至得不到优化的路径.在机器人规划的问题中，若假设路径包括n步，则该问题可以认为相当于n个城市的TSP.因此，机器人规划问题的蚂蚁数也可确定出来.在计算时先假设由起始点到目标点的路径长度，再除以机器人步长，可估计出蚂蚁数.启发函数的权重β的取值范围设为［1，5］.信息素强度的最大值τmax取1.信息素强度最小值τmin越小，则两者之间的差别越大，这样有利于产生新的解.3仿真该仿真算法的基本步骤如下：（1） 变量初始化.令时间t和循环次数N=0，设置蚂蚁数量m=100和最大循环次数100，初始化环境信息，并将所有蚂蚁都置于起点H.（2） 启动蚁群.m只蚂蚁按概率函数选择下一路径点，第k只蚂蚁到达终点，保留此局部解.（3） 重复步骤（2），直到蚁群到达终点，得到局部解.（4） 搜索蚁群的路径并记录周游最优蚂蚁和全局最优蚂蚁的路径信息，一次循环搜索完毕之后，要对最佳路径上的信息素进行更新，令t=t+1，N=N+1.（5） 记录当前最优解，对每一条可行路径进行重点搜索，得到局部最优解.（6） 对局部最优解采取随机搜索与重点搜索相结合的方式进行搜索，得到全局最优解.（7） 若蚁群全部收敛到一条路径或达到最大循环次数，则循环结束，输出最佳路径，否则转到步骤（2）.（8） 完成整个搜索过程，输出最终结果.实验中在平面中定义起始点和目的点，并加入若干障碍物.图1给出了运行时实验环境.H为起始点，F为目的点.图2给出了实验结果，通过MMAS得出的最佳路径.表1给出了算法仿真实验结果.图1实验模拟图
Fig.1The figure of simulation experiment图2实验结果图
Fig.2The figure of experiment result如表1所示，在第50次至100次最短路径的值就几乎没有改变过，则认为MMAS可以较快的找到一条近似最优路径.在计算70次后，发现最优路径长度值已经没有波动，说明已经找到一条路径.由仿真结果可以看出MMAS算法类似于概率算法，单个蚂蚁的简单控制不能代表整个系统的设计，必须将多蚂蚁的高层次复杂运动应用于系统运动中.
表1仿真结果
Table 1Simulation result
路径规划计算次数基于MMAS算法最短路径50216.560214.870213.580213.590213.5100213.54结语以上给出了基于最大最小蚂蚁系统的机器人路径规划的一种方法.该算法具有很好的寻优功能，当MMAS达到较好的求解性能时，只要没有找到新的最短路径，局部信息更新就会逐渐减少已穿越路径上的信息量，最终收敛到全局最优路径.