张原艺，章 政，王 泉

(武汉科技大学 信息科学与工程学院，湖北 武汉 430081)

0 引 言

传统的移动机器人路径规划方法有栅格法、人工势场法[1,2]、A*算法[3]等。随着移动机器人技术的发展以及对机器人智能化的要求逐渐提高，许多智能优化算法已经逐渐应用到移动机器人研究领域中，如遗传算法[4]、粒子群算法[5,6]以及蚁群算法[7-9]等。其中，蚁群算法因其具有良好的寻优能力、强鲁棒性等优点，广泛应用于移动机器人路径规划问题中。

近些年来，针对蚁群算法存在收敛速度慢、易陷入局部最优等问题，学者们展开了一系列研究工作[10-13]。通过分析现有的用于机器人路径规划的改进蚁群算法，还存在一些问题有待进一步研究，如：①采用单步长的搜索方式难以规划出最简化的路径；②基于直线引导搜索策略的多步长蚁群算法因其搜索视野范围受限而难以搜索到最优多步长路径；③规划出的最优路径距离障碍物太近从而难以保证移动机器人安全到达目标点。针对上述问题，本文设计了一种改进多步长蚁群算法用于移动机器人路径规划。首先，设计了一种路径引导搜索策略来确定机器人下一步移动的候选栅格。一方面扩大了算法的搜索范围，另一方面提高了算法的搜索效率；然后，设计了一种多策略栅格选择方法，根据选择概率因子从不同的候选栅格集合中选择出下一步移动的栅格，从而提高了算法的全局搜索能力。在搜索多步长的候选路径时加入安全距离判断策略以提高最优路径的安全性。最后，将本文算法应用于移动机器人路径规划中并进行仿真实验以验证本文算法的有效性。

1 改进多步长蚁群算法描述

本文的改进多步长蚁群算法主要分为3个部分：①通过路径引导的方式得到多步长候选栅格。②采用一种多策略栅格选择机制来选择蚂蚁下一步移动的栅格。③通过改进的信息素更新策略对信息素进行更新。

1.1 环境建模

假设机器人在某个二维空间内移动，且该区域内存在有限个静态障碍物，采用栅格法对机器人的运动环境建模。将机器人的运动区域的横向和纵向以相等的间隔划分为m和n等分，则该区域可表述为m×n个栅格构成的栅格图，栅格的大小由移动机器人的尺寸而定，栅格的大小能保证容纳移动机器人并且移动机器人与栅格的边界保持适当的距离。栅格中无障碍物的栅格为可行栅格，有障碍物的栅格则为不可行栅格。通常有障碍物的栅格用黑色方格表示，为方便研究，当障碍物小于一个栅格时按一个栅格处理，可行栅格用白色方格表示。移动机器人在栅格之间的移动可看作一个质点，并且假设移动机器人每次都停留在栅格的中心位置。

以横向为坐标系X轴，纵向为坐标系的Y轴，设X、Y方向的最大值分别为xmax和ymax。假设机器人移动的步长为λ(通常λ=1)，以λ为单位将X和Y轴分别进行划分，则每行栅格数为Nx=xmax/λ,每列的栅格数为Ny=ymax/λ。地图中左上角为1号栅格，栅格序号从左至右依次加1，序号从上至下依次加Ny。每个栅格的中心坐标与栅格的序号相对应，栅格i的中心坐标可表示为

(1)

式中：xi和yi分别为i号栅格中心点的横坐标和纵坐标,且1≤i≤Nx·Ny。

基于上述描述本文定义的30×30环境模型如图1所示。

图1 30×30栅格环境模型

1.2 搜索候选栅格

传统蚁群算法路径规划采用单步长方式进行搜索，即将当前位置相邻的栅格作为下一步移动栅格，这种搜索方式不仅会使算法收敛速度慢而且容易产生多余的拐角。多步长搜索方式是采用一些策略从地图中所有的自由栅格中筛选出下一步移动的候选栅格，采用多步长路径搜索方式可有效减小路径的长度、提高搜索效率、简化移动路径。但是采用多步长路径搜索方式时需要考虑如何筛选多步长候选栅格，若将所有的自由栅格都作为候选栅格会大大降低算法的搜索效率，若采用直线引导的方式难以保证搜索到最优的候选栅格。因此本文设计了一种路径引导的路径搜索方式，将蚁群每次迭代搜索出的全局最优路径作为引导路径，将当前位置与引导路径中连线不经过障碍物且距离目标点最近的栅格作为多步长候选栅格。路径引导搜索方法具体如下：

创建引导路径集合guidepath,将目标点G放入引导路径集合中，即guidepath=G。判断当前点与目标点的连线经过的栅格是否存在障碍物，若无障碍物则当前点和目标点是连通路径，否则为不连通路径。若当前点和目标点是连通路径，则可将目标栅格作为下一步移动栅格，若不是连通路径，则将当前点到目标点连线上离目标点最近且与当前点连通的栅格作为下一步移动的候选栅格。将所有蚂蚁第一次搜索结束后得到的全局最短路径包含的所有栅格加入到guidepath中，则guidepath=S,p1,p2,……,pn-1,pn,G。进行第二次搜索时则以新的guidepath集合作为引导路径。从目标点G开始依次判断当前栅格到guidepath中各个元素的连线是否是连通路径，将guidepath集合中与当前点S连通且距离目标点G最近的栅格作为候选栅格。

图2所示为采用路径引导搜索策略搜索路径方法示意图。图中S为当前点，G为目标点，虚线为引导路径guidepath=S,p1,p2,p3,p4,G，图中S点到G点、S点到p4点都不是连通路径，而S点到p1点、S点到p2点、S点到p3点都是连通路径，其中p3点距离G点最近，因此可将p3作为候选栅格。

图2 路径引导搜索策略

在每次迭代后，将本次迭代中的最短路径与引导路径进行比较，若本次迭代的最短路径长度更短，则将新的路径替代原来的引导路径。采用上述路径引导的搜索方法可以迅速找到距离目标点最近且与当前点连通的多步长候选栅格，从而有效提高路径搜索的效率。

1.3 多步长路径选择策略

为了增加搜索路径的多样性，提高算法的全局搜索能力，在选择下一步移动栅格时引入多策略路径选择机制。假设在t时刻，蚂蚁k位于栅格i，设q1和q2是(0,1)内服从均匀分布的随机变量，设置选择概率因子q0，将q0与q1和q2进行比较。当q1≤q0时，将当前点周围的栅格和路径引导策略选出的栅格作为候选栅格，即多步长候选栅格。当q1>q0且q2≤q0时，直接将路径引导策略选择出的栅格作为下一步移动栅格。当q1>q0且q2>q0时，将当前点周围的栅格作为下一步移动栅格，即单步长候选栅格。每次选择下一个移动栅格X的公式可表示为

(2)

式中：V和V′分别表示多步长候选栅格集合和单步长候选栅格集合。pn是通过路径引导搜索策略选择的下一移动栅格，j和j′是根据式(3)选择出的下一移动栅格

(3)

式中：τij(t)为t时刻从栅格i到栅格j的信息素浓度；ηij(t)为t时刻从栅格i到栅格j的启发值，其表达式为ηij(t)=1/djG，即栅格j到目标栅格G的欧式距离的倒数；α为信息素浓度启发因子，α的值越大，表明蚂蚁更有可能选择多数蚂蚁走过的路径；β为能见度启发因子，β的值越大，表明蚂蚁更有可能选择离终点更近的栅格。

1.4 信息素更新

采用多步长蚁群算法进行路径规划时，搜索出的路径通常含有单步长路径和多步长路径，单步长路径信息素的更新方式是只更新栅格i到栅格j的信息素，而多步长路径还包含栅格i到栅格j中心点的连线所经过的栅格。若使用单步长的信息素更新方式来对多步长路径进行更新，会降低信息素的连续性，减少了路径搜索的多样性，因此需要采用多步长信息素更新方式。多步长信息素更新方式可表示为

(4)

式中：ρ为信息素浓度衰减系数；∂为多步长路径连线经过的栅格信息素增量的权值，且0<∂<1； Δτij(t,t+1)为信息素增量，其计算方式如下

(5)

(6)

其中，Lk为蚂蚁k在本次循环中所走的路径长度，Q为信息素强度，通常是一个常量。

2 安全距离判断策略

为了提高路径的安全性，在选择下一步移动的候选栅格时加入安全距离判断策略，使规划出的路径与障碍物的距离大于安全距离。图3为一段多步长路径。设当前位置s为1号栅格，终点e为15号栅格。从图中可以看出该路径为连通路径，但是在某些情况下连通的路径不能保证机器人能完全避开障碍物。因此本文设计了一种安全距离判断策略以提高路径的安全性。安全距离判断策略方法如下所示。

图3 加入安全距离判断策略

首先确定判断的主方向。计算多步长路径的斜率kpath，若0

然后判断路径的安全距离。设图3中1号栅格中心坐标为x1,y1，多步长路径与2号栅格的交点分别为a和b。路径的直线方程可表示为

y=kpathx-x1+y1

(7)

设直线x=x1+0.5与直线y=y1-0.5的交点为d，线段de为点d到路径ab的距离，线段de可表示为路径到6号栅格的安全距离。de的长度lde表示安全距离的大小。lde的计算方式如式(8)所示

lde=ladcosθ

(8)

最后比较li(i=1,2,…,n)与δ的大小判断路径是否满足安全距离。若路径中所有的li都大于δ，则说明该路径满足安全距离条件，路径对应的栅格可作为下一步移动的候选栅格。若路径中有一处li小于δ，则该路径不满足安全距离条件。该路径不可行。

3 算法流程

本文算法流程如下：

步骤1 采用栅格法进行地图构建，将机器人初始位置设为起始点，设置目标点，各项参数初始化。

步骤2 将M只蚂蚁放在起点，将起点加入禁忌表中。

步骤3 根据路径引导搜索策略搜索多步长候选路径同时判断候选路径是否满足安全距离，将满足条件的多步长候选栅格与当前位置周围的栅格一起作为机器人下一步可移动的候选栅格集合，根据式(2)从候选栅格集合中选择下一步移动栅格并将当前栅格加入到禁忌表中。

步骤4 重复步骤3直至本次迭代中除“迷失”蚂蚁外所有蚂蚁到达终点栅格，保存蚂蚁所走的路径及路径长度。

步骤5 找出本次迭代中除“迷失”蚂蚁外所有蚂蚁所走路径长度最短的路径。将最短路径经过的栅格集合作为引导路径。

步骤6 根据式(4)进行多步长信息素更新。

步骤7 判断是否满足停止条件。如果达到停止条件则结束，否则令迭代次数加1并重复步骤2～步骤6。最终保存的最短路径作为规划出的最优路径。

本文算法流程如图4所示。

图4 本文算法流程

4 仿真实验及结果分析

为验证本文算法的可行性和有效性，将蚁群算法、基于直线引导的多步长蚁群算法以及本文算法用于机器人路径规划并进行仿真分析。

4.1 仿真结果分析

在图1环境下，对蚁群算法、直线引导多步长蚁群算法以及本文算法规划出的路径结果进行比较分析。算法各项参数设置为最大迭代次数Nmax=70，蚁群数量M=30，α=1，β=7，Q=50，q0=0.5。图5为上述3种算法迭代次数与搜索出的路径长度关系，从图中可以看出多步长蚁群算法比单步长蚁群算法收敛速度快，得到的最优路径长度更短。本文算法相比于直线引导的多步长蚁群算法提高了算法的收敛速度，且减小了路径长度。

图5 路径长度与迭代次数的关系

图6为在图1环境下分别采用上述3种算法路径规划出的路径结果。从图中可以看出多步长的路径搜索方式能够搜索出比单步长的路径搜索方式更简化且路径长度更短的路径。相比于直线引导多步长蚁群算法，采用本文算法规划出的路径长度更短且拐点更少，路径更平滑。其中直线引导多步长蚁群算法是当前点到目标点的连线经过的自由栅格中进行搜索，因此算法的搜索范围较小，从图6(b)的路径可以看出有些路径时可以直接一步到达，但是受到算法的搜索范围的限制而无法搜索到。本文基于路径引导的搜索方式扩大了多步长路径的搜索范围，因此相比于直线引导的搜索方式，本文算法能够搜索到可以直接一步到达的路径，所以规划出的路径更为简化，路径长度更短。

图6 路径比较结果

表1 算法仿真结果对比

4.2 路径多样性分析

为验证多策略路径选择机制中选择概率因子q0对算法全局搜索能力的影响，将q0取不同的值来观察路径多样性的变化。路径多样性函数的计算公式如下

(9)

式中：m表示蚁群的个数，Lk(n)表示蚂蚁k在第n次迭代搜索的路径长度，avg(L(n))表示第n次迭代所有蚂蚁搜索的路径的平均长度。DIV(n)函数反映了不同蚂蚁个体之间搜索出的路径差异的大小，若路径差异较大则说明算法的全局搜索能力较强。

图7为q0在0.2、0.5和0.8这3种取值下得到的路径多样性曲线。从图中可以看出，DIV(n)的取值随着q0的增大而增大，这说明q0越大路径的多样性越强。随着迭代次数的增大，DIV(n)的值逐渐减小，这是由于经过数次迭代后搜索出的路径逐渐收敛。当q0=0.2时虽然路径的多样性较强，但算法的收敛速度相对较慢，当q0=0.8时，虽然收敛速度较快但是路径的多样性相对较差，容易产生局部最优解，因此q0的取值在0.5左右比较合适。

图7 不同q0条件下解的多样性曲线

4.3 加入安全距离的多步长蚁群算法路径规划

为了提高路径的安全性，在搜索多步长候选栅格时加入安全距离判断策略。图8为δ=0.3时采用路径引导多步长蚁群算法搜索到的路径。比较图8与图6(c)的路径可以看出加入安全距离判断策略后规划出的路径与障碍物的距离始终大于安全距离，从而保证移动机器人能够安全无碰撞到达目标点。

图8 加入安全距离判断策略后的路径

本文算法加入安全距离判断条件前后的路径参数对比见表2。从表中可以看出加入安全距离判断策略后规划出的路径长度有少量增加，这是因为未加入安全距离判断策略进行路径搜索时，只需搜索出路径长度最短的自由栅格作为候选栅格。而加入安全距离判断后使得原来的短的路径可能会离障碍物太近而无法保证移动机器人能够安全无碰撞地通过，因此需要规划出即满足安全距离又使得移动距离最短的路径。未加入安全距离判断策略搜索出的路径在障碍物附近走的是直线，加入安全距离后，之前部分走直线的地方变成了拐角，从而减小了路径的平滑度，增加了拐点个数。

表2 加入安全距离判断策略前后对比

5 结束语

本文提出了一种基于路径引导的多步长蚁群算法。首先设计了一种路径引导搜索策略来选择多步长候选栅格，将引导路径中与当前位置的连线不存在障碍物且与目标点最近的栅格作为候选栅格。在每次迭代后搜索出的最优路径与引导路径长度进行比较，若新的最优路径长度小于引导路径的长度，则将本次迭代搜索到的最优路径作为新的引导路径。采用路径引导搜索方式有效改善了多步长蚁群算法搜索范围受限制的问题，从而提高了算法的搜索效率。在采用路径引导搜索策略搜索多步长候选栅格的过程中加入安全距离判断策略，使规划出的路径与障碍物的距离始终大于安全距离。然后设计了一种多策略的栅格选择方式从候选栅格集合中选择下一步移动栅格以提高算法的全局搜索能力，并分析了选择概率因子q0在不同取值情况下对算法全局搜索能力的影响。最后将本文提出的改进多步长蚁群算法与传统蚁群算法和直线引导多步长蚁群算法进行仿真对比实验。实验结果表明，本文改进的算法有效减少路径的长度和拐弯次数，提高了算法的收敛速度。比较加入安全距离判断策略前后规划出的路径可以看出，加入安全距离判断策略后规划出的路径虽然路径的长度有所增加、平滑度降低，但是保证了路径的安全性。