路径规划是按指定的标准（如距离最短、耗能最低等）规划出一条符合要求的可行路径，其在移动机器人研究领域中占有重要作用^[1]. 传统路径规划算法有A*算法^{[2 - 3]}、Dijkstra算法^[4]、快速搜索随机树法等. 随着移动机器人运行环境复杂性增大以及任务要求更加严格，越来越多的智能优化算法开始出现，如遗传算法^[5]、人工神经网络^[6]、粒子群算法^{[7 - 8]}、蚁群算法^[9]等.

蚁群算法因具有较强的稳健性和适应性^[10]，广泛应用于移动机器人的路径规划，但其存在易陷于局部最优^[11]、收敛速度慢和易陷入死锁等问题. 许多学者从改进搜索策略、改进启发式信息和改进信息素更新策略等几个方面对其进行优化. 许凯波等^[12]提出双层蚁群算法，每次迭代先用外层蚁群算法为内层蚁群算法找到一条可用来构造重新寻优所用的小环境路径，提高算法寻优效果. 张恒等^[13]将蚁群划分为引导层蚁群和普通层蚁群，提高蚁群算法在大规模环境及复杂障碍环境的可行性和稳健性. 史恩秀等^[14]分析蚁群算法的主要参数对规划路径长度和路径规划效率的影响，通过仿真找到最佳匹配参数组使得规划路径不仅长度短，路径规划的效率也得到提升.

移动机器人在实际工作时，转弯频率过高、转角过大都不符合动力学和运动学的要求，不仅导致路径平滑度下降，运行时的能量消耗也会增加. 因此，路径平滑度是衡量规划路径质量的重要因素. 但现有以路径长度最短为目标的研究可能导致算法规划路径的平滑度不高，无法满足移动机器人的实际使用需求. 针对这些问题，本研究提出一种改进多步长蚁群算法，并通过仿真实验验证改进方法的有效性.

1.   环境表示

采用栅格图法对移动机器人运行环境进行建模. 栅格图法将所处环境划分为一个个小的栅格，黑色栅格为运行环境中的障碍物，移动机器人不可通行或停留；白色栅格为可行区域，移动机器人可自由通行或停留. 栅格按从左到右、从上到下的次序进行编号，如图1所示.

图  1  栅格地图

Figure  1.  Grid map

下载: 全尺寸图片 幻灯片

对栅格地图中的障碍物进行一定程度的膨胀，障碍物占满或不占满一个栅格时均按占满整个栅格处理. 为便于研究和开展实验，本研究做出以下假设：

1) 地图是在考虑安全距离的情况下建立的，可将移动机器人视为一个质点，规定其只能从一个栅格中心移动到另一个栅格中心；

2) 在不触碰边界和障碍栅格的情况下，机器人可以自由移动且不考虑自身高度的影响.

2.   蚁群算法原理

蚁群觅食过程中，蚂蚁对路径的选择受到路径上信息素的影响，优先选择信息素浓度高的路径，并在走过的路径上释放信息素，起到正反馈作用，吸引更多的蚂蚁选择该条路径，最终蚂蚁会集中在一条路径上. 随着时间的推移，路径上的信息素会产生挥发.

蚂蚁$k$在$t$时刻位于节点$i$时，选择可选节点$j$为下一步到达节点的概率计算为

式中：$\alpha$为信息素重要程度；$\beta$为启发信息重要程度；${\tau _{ij}}\left( t \right)$为$t$时刻路径$(i,j)$上的信息素；${\eta _{ij}}\left( t \right)$为$t$时刻当前节点$i$到可选节点$j$的启发信息；${\rm{allowed}}$为蚂蚁$k$下一步可选节点的集合；${d_{ij}}$为可选节点$j$到目标节点的距离. 选定下一步移动节点后，将其加入禁忌表，防止到过的节点被再次选中. 所有蚂蚁完成一次路径规划后，对信息素进行更新，公式为

式中：$\rho$为信息素挥发系数；$\Delta {\tau _{ij}}$为蚂蚁在所经过路径$(i,j)$上留下的信息素量，定义为

式中：$Q$为信息素强度，是一个常量；${L_k}\left( t \right)$为蚂蚁$k$走过的路径长度.

3.   改进蚁群算法

3.1   多步长移动方式

传统蚁群算法在栅格地图中采用8方向8邻域搜索方式，即在当前栅格邻接的8个栅格邻域中寻找下一栅格，为单步长移动方式，如图2所示. 该搜索方式使算法规划路径存在多余折线,导致路径较长且转弯次数较多，不能满足移动机器人实际工作需求.

图  2  8方向8邻域搜索方式

Figure  2.  8-direction 8-neighborhood search method

下载: 全尺寸图片 幻灯片

两种搜索方式规划路径如图3所示. 由图可见，通过8方向8邻域单步长搜索方式寻到1号栅格与28号栅格间的最短路径长度为7.24，步数为6；而任意方向任意步长搜索方式寻到的两节点之间的最短路径长度为6.77，步数为 2. 两者相比后者可通过较少的步数，寻找到路径长度更短、平滑度更高的路径，提高算法寻优效率.

图  3  两种搜索方式规划路径

Figure  3.  Two search methods for path planning

下载: 全尺寸图片 幻灯片

移动机器人在实际工作时，转弯频率高、转角大，不仅导致路径平滑度下降，也会增加路径颠簸性和能量消耗，影响移动机器人实际运行. 因此，需要综合考虑路径长度和路径平滑度，如图4所示. 图中，37号栅格为起始节点，36号栅格为目标节点，虚线和实线分别为以距离优先和兼顾路径长度与平滑度得到的路径. 虚线路径虽然为最短路径，但其比实线路径多3次转弯，而实线路径仅比最短路径多2.1%的长度，综合考虑移动机器人的实际工作需求，实线路径为更优路径. 实线路径转弯节点为非障碍物相邻节点，表明可选节点集中包括可直达非障碍物相邻节点时，可寻到路径平滑度更优的路径.

图  4  路径平滑度

Figure  4.  Path smoothness

下载: 全尺寸图片 幻灯片

移动机器人视野域范围内的可直达节点构成移动机器人活动域. 为提高算法寻优效率和解的质量，以移动机器人活动域内的节点作为下一步可选节点，采用多步长移动方式以任意方向任意步长在活动域内寻找下一节点，使得单步搜索范围更大，单步移动距离和移动方向更加灵活，减少了不必要的拐点和路径，可用较少的步数找到路径长度更短、路径平滑度更高的路径，提高算法寻优效果. 可选节点集如图5所示. 灰色栅格为当机器人处在113号节点时其视野域范围内的可直达节点，构成移动机器人当前的活动域.

图  5  可选节点集

Figure  5.  Optional node set

下载: 全尺寸图片 幻灯片

3.2   改进信息素初始分布策略及更新策略

为减少传统蚁群算法初始信息素均匀分布导致算法初期蚁群盲目搜索，在初始化信息素浓度矩阵$T$时，当前节点与各节点之间信息素浓度依各节点与当前节点与目标节点连线距离远近进行分配，公式为

式中：${\tau _{ij}}$为$i$为当前所在节点、$j$为可选节点时，$(i,j)$之间初始信息素浓度；$d$为节点$j$中心到节点$i$中心与目标节点中心连线的距离，距离越小，信息素浓度越高，相反则越低，以达到初始信息素不均匀分布的目的. 以栅格地图左上角为当前所在节点，右下角为目标节点时，当前所在节点与各节点之间初始信息素浓度沿垂直于当前节点与目标节点连线方向逐渐减小，颜色越深代表信息素浓度越高，如图6所示.

图  6  初始信息素不均匀分布

Figure  6.  Uneven distribution of initial pheromone

下载: 全尺寸图片 幻灯片

由于传统蚁群算法只更新最短路径上的信息素，可能使算法过早收敛，陷入局部最优解. 因此，改进信息素更新策略，所有到达目标节点的路径都进行不同程度的信息素奖励更新，公式为

式中：${L_{\rm{m}}}$为到达目标节点的某一路径的长度；${\varsigma _{\rm{m}}}$为该路径长度在所有寻路成功路径长度总和中的占比；${\varsigma _{\rm{z}}}$为最优路径长度在所有寻路成功路径长度总和中的占比；$R$为最优路径信息素更新量，其值根据信息素浓度初始值的设置进行选取. 首先以${\varsigma _{\rm{z}}}$为最优路径信息素更新量；$x$为放大控制因子. 首先以${\varsigma _{\rm{z}}}$为单位，求出各${\varsigma _{\rm{m}}}$相对于${\varsigma _{\rm{z}}}$的倍数，再用信息素更新放大控制因子$x$. 最后，通过（9）式求出该路径需要更新的信息素量. 改进策略可增大优质路径与劣质路径信息素更新量的差距，加快算法收敛速度${\xi _{\rm{m}}}$. 最后，通过（9）式求出该路径需要更新的信息素量， R根据信息素浓度初始值的设置进行取值. 改进策略可增大优质路径与劣质路径信息素更新量的差距，加快算法收敛速度.

3.3   改进启发函数

起始节点与目标节点之间直线最短，选择靠近两点之间连线的路径，可使路径更短. 蚁群算法每步的当前节点可看作新的起始节点. 最短路径比较如图7所示. 1号栅格为起始节点，100号栅格为目标节点，6号栅格为由起始节点出发选中到达的下一个节点. 当移动到6号栅格时，46号栅格和47号栅格均为下一步可选节点，46号栅格为距离起始节点与目标节点连线更近的节点，47号栅格为距离当前节点与目标节点连线更近的节点. 当选用47号栅格作为下一节点时，可使总路径更短. 因此，每次选择可选栅格中距离当前节点和目标节点连线更近的点可有效缩短路径长度.

图  7  最短路径比较

Figure  7.  Shortest path comparison

下载: 全尺寸图片 幻灯片

启发函数改进为

式中：${d_{j{\rm{z}}}}$为可选节点$j$距离当前节点$i$与目标节点连线的距离；${d_{j{\rm{g}}}}$为可选节点$j$与目标节点之间的距离. 此改进可使选中节点既与当前节点的连线更近，更加趋近于目标节点，提高算法寻优效率.

3.4   最优路径筛选策略

为使改进蚁群算法规划路径在路径长度及路径平滑度方面均表现优异，提出最优路径综合指标F，其计算方法为F，计算方法为

式中：$L$和$S$分别为路径长度和路径转弯次数；$a$和$b$为对应参数的权重系数. 寻路成功的路径中，$F$值最小的路径为最优路径.

4.   改进蚁群算法步骤

1）初始化各项参数，建立二维栅格地图模型，设置起始节点与目标节点.

2）将蚂蚁置于起始节点，并将起始节点加入禁忌表.

3）从当前位置的活动域中选择下一步要到达的节点，并移动到该节点，更新路径长度、局部信息素及禁忌表.

4）判断是否到达目标节点，若达到，则记录蚂蚁所走路径；否则，返回步骤3）.

5）本次迭代所有蚂蚁完成寻路后，更新全局信息素；计算所有到达目标节点的路径F值并记录.

6）判断是否完成所有迭代，若完成，则根据最优路径筛选策略挑选出最优路径并输出；否则，则执行下一次迭代，直到完成所有迭代.

5.   仿真对比实验

为检验改进蚁群算法在移动机器人路径规划时的效果，通过仿真对比实验对其相关性能进行实验分析. 算法运行环境为：操作系统 Windows 10(64位), 处理器 Inter(R) Core(TM) i7-5500U, CPU2.80 GHz,内存4 GB,仿真平台Matlab R2018b.

蚁群算法中不同的参数组合对路径规划效果的作用不同，寻找合理的参数组合成为规划最优路径的重要基础. 目前还没有有效的理论方法能寻到适合各种情况的最优参数组合^[15]，因此，研究将根据经验选取各参数范围，并在参数范围内对各参数设置一组值，得到不同的参数组合. 各参数选取值为$\alpha \in \left\{ {0.5,1,1.5,2,3} \right\}$，$\beta \in \left\{ {1,3,5,7,9} \right\}$，$\rho \in \left\{ {0.1,0.3,0.5,0.7,0.9} \right\}$，$x \in \left\{ {2,3,4,5,6} \right\}$. 在对比各参数取值对算法寻优效果的影响实验中，只改变一个参数的值，其他参数选取默认值，各参数默认值为$\alpha$=1, $\beta$=6, $\rho$=0.5, $x$=3. 为减小实验随机性，对各参数的每个值进行10次仿真实验，并对仿真实验结果求均值进行分析，选出最优参数组合. 各参数值实验结果见表1.

表  1  各参数不同取值实验结果

Table  1.  Experimental results of different values of parameters

参数	参数设定值及实验结果
$\alpha$	0.5	1.0	1.5	2.0	3.0
路径长度均值	29.73	29.68	29.40	30.17	30.76
平均收敛迭代次数	39.3	13.6	4.2	7.9	7.0
$\beta$	1	3	5	7	10
路径长度均值	32.92	32.86	32.90	30.98	33.38
平均收敛迭代次数	8.3	14.9	8.6	6.6	9.8
$\rho$	0.1	0.3	0.5	0.7	0.9
路径长度均值	32.88	32.93	33.07	32.84	33.05
平均收敛迭代次数	21.8	19.4	9.7	8.5	9.8
$x$	2	3	4	5	6
路径长度均值	33.08	32.87	32.71	32.62	33.11
平均收敛迭代次数	12.4	9.7	7.9	6.8	6.3

下载: 导出CSV 

| 显示表格

对实验结果进行分析对比可知，参数$\alpha$、$\beta$、$\rho$、$x$的最优值分别在1.5、7、0.7、5附近，因此，本研究算法各参数设置见表2.

表  2  各参数设置

Table  2.  Parameter settings

参数	参数值
最大迭代次数 Ncmax	100
蚂蚁数量 M	50
信息素重要程度因子$\alpha$	1.5
启发函数重要程度因子$\beta$	7
信息素挥发系数$\rho$	0.7
信息素强度 Q	1
信息素更新放大控制因子$x$	5

下载: 导出CSV 

| 显示表格

5.1   20 × 20仿真环境对比实验

设置规模为20 × 20，障碍栅格占比为20%的栅格地图，并设置槽型、多齿型复杂障碍物，提高栅格地图复杂度，以检验改进算法防死锁及在复杂环境下的寻路能力. 同时为检验算法稳定性及降低实验的随机性，两种算法各进行10次连续仿真实验. 实验时设置栅格地图左上角栅格为起始节点，右下角栅格为目标节点. 实验结果如图8所示. 仿真数据见表3.

图  8  20 × 20地图模型仿真结果

Figure  8.  20 × 20 map model simulation results

下载: 全尺寸图片 幻灯片

表  3  20 × 20栅格地图仿真数据

Table  3.  20 × 20 grid map simulation data

算法	路径平均长度	平均收敛迭代次数	路径平均转弯次数	最优路径长度	最优路径转弯次数	最优路径迭代次数
传统蚁群算法	35.25	57.6	16.8	34.04	15	64
本研究改进算法	28.40	5.2	3.7	27.96	5	6

下载: 导出CSV 

| 显示表格

由仿真结果可知，改进算法在路径长度、迭代收敛次数及转弯次数方面，均比标准蚁群算法性能更好，路径平均长度缩短19.4%，平均收敛迭代次数减少91.0%，平均转弯次数减少78.0%. 改进算法各数据总体表现更加稳定，改进算法稳定性更强.

两算法10次仿真中的最优路径规划图及其收敛曲线图如图9所示. 分析可知，算法最优路径长度为27.96，比传统蚁群算法最优路径长度34.04缩短17.9%；算法最优路径转弯次数为5次，比传统蚁群算法转弯次数15次减少66.7%；算法最优路径收敛迭代次数为6次，比传统蚁群算法收敛迭代次数64次减少90.6%，算法收敛速度得到提升. 改进算法迭代初期收敛曲线波动幅度较小，各代最优路径长度与最终规划路径长度相近，表明初始信息素不均匀分布策略起到有效作用. 从两种算法路径规划图中可以看到，改进蚁群算法避免了传统蚁群算法中出现的路径多余、引导方向错误的现象. 以上表明，改进算法规划出的路径相比传统蚁群算法单步移动距离更长、路径长度更短、路径平滑度更高，实用性更强.

图  9  最优路径仿真结果对比

Figure  9.  Comparison of optimal path simulation results

下载: 全尺寸图片 幻灯片

5.2   30 × 30仿真环境对比实验

在规模为30 × 30的仿真环境下，采用文献[16]中的栅格地图进行仿真实验. 设置栅格地图左上角栅格为起始节点，右下角栅格为目标节点，比较本研究改进算法、文献[16]算法、传统蚁群算法路径规划效果，如图10所示. 相关实验结果见表4.

图  10  30 × 30地图模型仿真结果

Figure  10.  30 × 30 map model simulation results

下载: 全尺寸图片 幻灯片

表  4  30 × 30栅格地图仿真数据

Table  4.  30 × 30 grid map simulation data

算法	最优路径长度	路径转弯次数	收敛迭代次数
传统蚁群算法	47.11	19	68
文献[16]算法	44.53	12	9
本研究改进蚁群算法	42.20	4	6

下载: 导出CSV 

| 显示表格

分析实验结果可知，改进蚁群算法较传统蚁群算法，在路径长度、路径转弯次数、收敛迭代次数方面均表现更优，尤其在路径转弯次数、收敛迭代次数方面提升较大，分别减少78.9%和77.9%，在路径长度方面同样缩短10.4%，优化效果明显；同时，相比文献[16]算法，路径长度、路径转弯次数、收敛迭代次数分别减少5.2%、66.7%和33.3%，路径转弯角度均小于90°，路径平滑度更高. 实验结果表明，改进蚁群算法综合表现最优，有较强的寻优能力和收敛性，在地图增大时，依然可以规划出兼顾路径长度与平滑度的路径，更符合移动机器人的实际使用需求.

6.   结　语

研究提出一种改进多步长蚁群算法用于移动机器人路径规划. 通过多步长移动方式，使单步搜索范围更广，单步移动距离和移动方向更加灵活，提高了算法寻优效率；各节点之间初始信息素浓度采取不均匀分布，提高了算法初期蚁群搜索的指导性；通过路径长度增大优质路径与劣质路径的信息素更新差距，使优质路径的信息素更强，改进启发函数，提高了算法收敛速度. 同时，加入最优路径筛选策略，使规划路径兼顾路径长度与路径平滑度. Matlab仿真结果表明，改进蚁群算法规划路径在长度、平滑度方面均表现优异，规划路径具有长度短、平滑度高、步数少的优点，更符合移动机器人的实际工作需求.