基于改进蚁群算法的移动机器人全局路径规划

任红格，胡鸿长，史涛

(1.天津城建大学 控制与机械工程学院，天津 300384；2.华北理工大学 电气工程学院，河北 唐山 063210)

移动机器人路径规划是机器人学研究领域中的一个重要组成部分，其任务是在具有障碍物的环境内，按照一定的评价标准(工作代价最小、行进路线最短等)寻找一条从起始状态(包括位置和姿态)到目标状态(包括位置和姿态)、与障碍物无碰的路径[1]。根据环境信息的已知程度不同，移动机器人路径规划又可分为环境已知的全局路径规划及环境未知的局部路径规划。全局路径规划主要分为2个问题，即环境构建与搜索算法。目前，可视图法、栅格法等在环境构建中应用较多，对于搜寻路径最优的算法，比较流行的是A*算法[2-5]、遗传算法、蚁群算法等[6-9]。

蚁群算法最早成功应用于解决著名的TSP(Travelling salesman problem )，该算法采用了分布式并行计算机制，易于和其他方法结合，而且具有较强的鲁棒性,因此，也常常将蚁群算法应用到许多实际问题上。金飞虎等[10]将蚁群算法应用于自由飞行空间机器人的路径规划中，文献[11]则将蚁群算法应用于图像分类中。该项目则提出一种改进蚁群算法，采用修改算法路径搜索策略、启发函数以及信息素挥发系数，改进算法与传统算法相比，不仅具有更快的收敛速度，而且搜索到的路径也更优。

1改进蚁群算法

1.1 环境建模

本文采用栅格法对已知的环境信息进行建模，通过将序号以及二维直角坐标相结合的方式对栅格进行标记。为了确保机器人与障碍物无碰撞，障碍物采用膨化的方式，以机器人的半径大小进行膨化，由此在栅格图中将机器人视为一个点，建好的栅格图如图1所示。

图1 栅格图

设栅格图列数为c，则序号n与坐标(x，y)的对应关系由式(1)给出：

(1)

式中mod为取余运算，floor为向负无穷方向取整。

1.2 路径搜索策略的改进

当路径上存在类似于U型障碍物的特殊形状障碍物时，传统蚁群算法缺乏逃出此类特殊环境的手段，因此该算法在这类环境中不仅搜索效率低下，而且还有可能陷入停滞。U型障碍物如图2所示。

图2 U型障碍物

刘徐迅等[12]提出一种蚂蚁回退策略，既在蚂蚁陷入U型障碍物时，蚂蚁通过反复回退，跳出障碍物，增加了计算量。康冰等[13]则在其基础上，提出一种禁忌栅格优化法，通过改进蚂蚁跳出U型障碍物的手段，在一定程度上减少了计算量。以上算法追求的都是在蚂蚁陷入U型陷阱后，通过提高蚂蚁的逃出速度来降低算法计算量。该研究不局限于跨越U型陷阱这个点，而是修改算法路径搜索策略，既在蚂蚁陷入U型障碍物时，蚂蚁无需回退，而是直接放弃此次搜索过程，进行下一次搜索。当蚂蚁搜索陷入U型障碍物时，即使蚂蚁最终跳出陷阱，找到目标点，此次路径也不会是最优的，放弃这条路径，不仅能减少计算量，还能避免劣质路径对蚂蚁搜索的干扰。

1.3 基于方向性原则的启发函数

在传统蚁群算法中，启发函数ηij(t)是相邻栅格之间距离的倒数，因此蚂蚁在相邻栅格中的启发权值差异并不明显，这使得启发函数在蚂蚁转移决策中并没有起到很明显的作用，使得算法的搜索效率比较低。蚂蚁一次转移的可能性如图3所示。

图3 蚂蚁可能的选择方向

由图3可以看出，蚂蚁在一次节点转移中，它的启发函数值仅有2种可能性，且比值仅为1：√2。在起点终点位置已知，方向明确的情况下，按照基本蚁群算法的启发函数公式计算状态转移概率，启发函数既没有利用上路径起点终点的方向信息，又不能很明确地反映出相邻节点的差异，这导致蚂蚁在相邻节点转移时会做许多无用功，既增加了搜索时间，又延长了搜索的路径。

基于方向性原则的启发函数则是取下一个可行节点与终点距离的倒数的平方，表达式如式(2)所示。

ηjd=1/[(xj-xd)2+(yj-yd)2]

(2)

式中，(xj,yj)是下一个可行节点的坐标，(xd,yd)是目标节点的坐标。

1.4 基于时空信息交互的信息素更新策略

在基本蚁群算法中，蚂蚁种群在完成一次迭代之后，所有蚂蚁都要进行信息素更新。在蚂蚁种群进行反复迭代更新之后，路径各节点之间的信息素会出现很大差异，信息素高的节点经过的蚂蚁越多，而经过的蚂蚁就越多，节点的信息素就越高，这是一个正反馈过程。然而，在迭代次数不高的时候，种群中的蚂蚁搜寻到的大部分都不是最优解，即在算法搜索前期，信息素的更新更容易受到劣质解的干扰，劣质解不仅会使蚁群算法寻优搜索时间增长，降低其效率，而且在劣质解大量存在的时候，算法易陷入局部最优解。文献[14]给出了一种自适应调整挥发系数的信息更新策略，调整方案为：

ρ(t)=max[γρ(t-1),ρmin]

(3)

式中，ρmin为挥发系数最小值。

在张煜东等[14]的基础上，进一步提出一种基于时间空间的信息素更新策略。基于时间空间的信息素更新策略是将路径信息与迭代次数同时应用在信息挥发系数ρ上，动态调整ρ，使信息素满足蚁群在不同时刻，不同区域的取值需求。信息素更新策略如式(4)～式(6)：

(4)

ρ(t)=max[μρ(t-1),ρmin]

(5)

τij(t+Δt)=[1-ρ(l)-ρ(t)]·τij(t)+Δτij(t)

(6)

式中，dmid是蚁群在一次迭代过程中路径长度的平均值；dbest是迭代过程中的最短路径，δ为常数，用来调整ρ(l)的值，使ρ(l)∈(0,1)；μ是衰减系数，ρmin是挥发系数最小值。

由式(4)～式(5)可以看出，ρ(l)包含的是关于路径的空间信息，主要由最短路径与平均路径长度构成。在一次迭代过程中，若最短路径与平均路径长度相差过大，则意味着迭代过程中包含了太多的劣质解，此时应该增大信息素挥发系数，加快信息素的挥发，避免算法受劣质解干扰。ρ(t)将挥发系数与时间联系起来，让系数随着时间的积累而逐渐减小，直至取到最小值。即在蚁群搜索前期，信息素挥发系数较大，蚁群之间协作性较弱，搜索随机性较强，搜索范围增大，而在后期，系数减小，蚁群之间协作性增强，搜索范围逐渐向最优解区域收缩，加快了算法后期的收敛性。

2改进蚁群算法的算法流程

在蚁群算法中引入了新的路径搜索策略以及改进的信息素跟新策略后，算法流程图如图4所示，具体步骤如下：

图4 改进蚁群算法的算法流程图

步骤1：利用栅格法对地图环境进行建模，设置起点，终点以及障碍栅格。

步骤2：算法流程及各参数初始化。设置时间t=0，循环次数NC=0，取最大循环次数NCmax，设定好ρ、β、μ等各参数值。

步骤3：循环次数NC=NC+1，k=1。

步骤4：蚂蚁数目k=k+1。

步骤5：每只蚂蚁都从初始节点出发开始搜索遍历，蚂蚁个体根据状态转移概率公式计算的概率,使用轮盘赌法，选择下一步可行点并前进。

步骤6：修改禁忌表指针，选择好可行点之后将蚂蚁移动到新的栅格，并把该点加入到此蚂蚁个体的禁忌表中。

步骤7：按改进的蚂蚁搜索策略进行路径搜索，如果蚂蚁搜索到终点，则计算该蚂蚁搜索到的路径长度，返回步骤4；如果没有，则返回步骤5；如果蚂蚁陷入U型障碍物则放弃此次搜索，并对该陷阱进行标记，返回步骤3。

步骤8：如果k>m(m为蚂蚁数目，即一次迭代过程中搜索的次数)，按信息素更新策略更新路径信息素并返回步骤3。

步骤9：如果NC>NCmax，输出算法计算结果，算法结束。

3算法仿真及结果分析

为了验证改进后的ACO的性能，使用MATLAB编写仿真程序，算法的仿真参数设置如如表1所示。

表1 仿真参数值

本文分别从3个方面对算法进行仿真分析：(1)比较2个算法最终规划出的最优路径；(2)比较算法在运行过程中，所有蚂蚁的运动轨迹；(3)比较2个算法的收敛曲线。

3.1 算法最优路径仿真实验

将传统蚁群算法与改进蚁群算法在相同的环境下进行对比，图5和图6分别为2种算法规划出的最优路径，图7和图8分别为一次路径规划中传统和改进蚁群算法所有蚂蚁寻优路径图。

图5 传统蚁群算法的寻优路径

图6 改进蚁群算法的寻优路径

图7 传统蚁群算法的所有蚂蚁寻优路径图

图8 改进蚁群算法的所有蚂蚁寻优路径图

由图5，图6对比可看出，改进蚁群算法不仅能准确地搜索到最优路径，相对于传统蚁群算法，其路径拐点也更少，路径更为平滑。

由图7，图8对比可看出，传统蚁群算法在寻优路径的过程中，相当于是遍历整个栅格图，反映了传统蚁群算法在前期存在的盲目性搜索以及后期收敛速度慢的问题，而在改进蚁群算法中蚂蚁的寻优路径则更集中于起点与终点之间的重要区域，且更加集中，蚂蚁基本没有探索过地图的边缘位置，反映了改进蚁群算法的路径搜索更具有目标性，搜索效率更高。

3.2 算法收敛仿真实验

图9、图10是2种算法的收敛曲线图，反应了2种算法的收敛速度，同时亦比较了2种算法规划出的最优路径的长短。

图9 传统蚁群算法的收敛曲线 图10 改进蚁群算法是收敛曲线

由图9、图10对比可以看出，改进蚁群算法相对于传统蚁群算法的收敛速度更快，而且搜索到的路径长度也更短。

表2提取了图9和图10中的收敛曲线相关数据，分别比较了蚂蚁在整个路径搜索过程中所走过的最长、最短路径，算法的迭代次数以及搜索时间。

表2 改进算法与传统算法的性能比较

从表2中可以看出，改进的ACO在路径规划方面比传统ACO具有更多优势。 就搜索路径长度而言，在整个路径规划过程中，改进的ACO搜索的最长路径比传统ACO的搜索最短路径短，改进的算法迭代次数更少，搜索时间更短。

4结论

针对传统ACO在移动机器人路径规划中出现的搜索结果不理想，有时无法搜索到最优路径等的不足，提出一种时空信息交互蚁群算法，通过修改蚁群算法路径搜索策略，并在蚂蚁搜索过程中，加强蚂蚁对搜索时间与地图环境空间的感知，相对于原算法，蚂蚁的搜索效率提高了37%，路径长度缩短了41%，并且路径质量也得到了改善，为路径规划寻优问题提供了新的思路和方法。