复杂多陷阱环境下机器人导航路径的蚁群规划策略

李 婧，李艳萍

（1.山西职业技术学院，山西太原 030006；2.太原理工大学信息与计算机工程学院，山西太原 030024）

1 引言

移动机器人的工作路径极大地影响其安全性、工作效率、行驶耗能和机械磨损，好的工作路径在保证机器人安全的基础上，能够极大提高机器人工作效率，并减少行驶耗能［1］。智能算法在路径规划中存在多种缺陷，诸如易陷入局部最优、收敛速度慢、算法复杂度高等问题［2］。对智能算法进行优化，提高智能算法的收敛速度和求解质量，对提高路径规划效率和路径规划质量具有重要意义。

机器人路径规划的研究主要分为两个方面：（1）环境建模；（2）路径搜索算法。环境建模的常用方法包括可视图法、自由空间法、栅格法等。路径搜索算法包括传统搜索算法和智能仿生算法，传统搜索算法包括人工势场法、模糊逻辑法、模拟退火法等，人工势场法［3］优点是路径平滑性好，缺点是多障碍物环境下易陷入局部最优；模糊逻辑法［4］优点是无需被控对象模型，缺点是模糊规则表难以确定；模拟退火法［5］优点是建模简单，缺点是算法收敛速度慢、参数难以设定。智能仿生算法包括遗传算法、蚁群算法、粒子群算法等。蚁群算法［6］模拟蚁群觅食过程，常应用于路径规划，但是算法前期收敛较慢且易得到次优解。遗传算法［7］主要模拟交叉变异、适者生存两种自然现象提出的算法，算法应用于路径规划时运行效率低于蚁群算法。粒子群算法［8］是模拟鸟群觅食过程提出的，首先将路径规划问题转化为连续变量优化问题，才能使用粒子群算法进行路径规划，粒子群算法最大缺陷是随着迭代的进行，所有粒子聚集在最优粒子附近，粒子的单一性使算法失去进化能力，从而影响路径规划质量。

这里研究了复杂多陷阱环境下的行驶机器人路径规划问题，建立了机器人工作环境的栅格模型，将安全启发因素和智能蚂蚁策略融入到蚁群算法中，在栅格环境下进行路径规划，实现了提高路径规划质量和路径规划效率的目的。

2 栅格模型与算法分析

2.1 栅格模型

栅格法是简单高效的环境建模方法，在机器人路径规划中得到了广泛应用。使用固定大小的栅格将机器人工作环境进行划分，并根据栅格内有无障碍物定义栅格属性即可得到栅格模型［9］。当栅格内存在障碍物时将栅格属性定义为“1”，当栅格内不存在障碍物时将栅格属性定义为“0”，以图1所示栅格环境为例，其0−1矩阵模型为：

图1 栅格环境模型Fig.1 Grid Environment Model

从以下3个方面对栅格模型进行说明：

（1）栅格编码包括顺序编码和坐标编码2种方法，2种方法之间可以相互转化。这里顺序编码方法为：从左至右，由上到下依次编码。栅格规模记为N，则第i个栅格的坐标编码为：

（2）栅格之间的距离使用欧式距离计算方法。

（3）使用蚁群算法进行路径规划时，蚂蚁可选栅格为当前栅格紧邻的8个栅格中的非障碍物栅格，以图1为例，蚂蚁的转移图结构，如图2所示。图中箭头方向为蚂蚁的可转移方向。

图2 蚂蚁转移图结构Fig.2 Ant Transferring Figure Structure

2.2 蚁群算法介绍

蚂蚁群寻找食物过程中，主要依靠食物源的启发作用和信息素的沟通作用而实现的，模拟蚂蚁群这一觅食过程而提出了蚁群算法。算法在第t次迭代时，蚂蚁k由当前节点i转移至节点j的概率(t)为［10］：

式中：τij(t)—蚂蚁k由当前栅格i转移至栅格j的信息素浓度；α—信息素因子；ηij(t)—蚂蚁k由当前栅格i转移至栅格j的启发函数；β—启发函数因子；allowk—蚂蚁k的可转移栅格集合。在路径规划中，启发函数一般使用栅格间的距离定义，即ηij(t) = 1dij，dij—栅格i和栅格j之间的距离。

但是由于栅格环境的特殊性，栅格间距离只有1和 2 两种情况，因此传统启发函数定义方法的启发效果极小。为了解决这一问题，这里使用下一栅格与目标栅格的距离构造启发函数，即：

式中：djG—待选栅格j与目标栅格G间的距离。

路径上信息素更新包括两个方面：（1）信息素的挥发；（2）蚂蚁在走过路径上的信息素残留。考虑以上两个方面，得到信息素更新方法为：

式中：ρ—信息素挥发系数；

Δτij(t)—路径ij上信息素增量；

m—蚁群规模；

Q—信息素强度；

Lk—蚂蚁k的路径长度。

2.3 多陷阱环境下蚁群算法缺陷分析

栅格环境下，陷阱一般定义为U 型障碍物和V 型障碍物，如图3 所示。蚁群算法执行过程为：初始时刻将所有蚂蚁放置在起点，蚂蚁按照式（2）进行路径规划，所有蚂蚁到达终点后，蚁群算法完成一次迭代。但是在多陷阱环境下，蚂蚁极易陷入死区而无法到达终点，影响算法的路径规划质量，甚至使算法无法循环。

图3 多陷阱环境Fig.3 Multiple Traps Environment

当前常用的陷阱处理方法包括蚂蚁夭折策略和蚂蚁回退策略。蚂蚁夭折策略是指当蚂蚁陷入死区时，蚂蚁提前死亡不再进行后续的路径规划，且夭折蚂蚁经过的路径不再留下此蚂蚁的信息素。此方法能够保证不因个别蚂蚁而影响算法效率，但是在多陷阱环境下过多蚂蚁夭折必然影响算法对路径的规划质量。

蚂蚁回退策略是指蚂蚁进入死区后，反复采取回退、判断的方法，直到蚂蚁逃出死区，而后进行后续的路径规划。这种方法能够保证蚂蚁绝大多数或者全部到达终点，因而可以保证较高的路径规划质量。但是当死区较深时，蚂蚁回退策略会耗时较大，从而拖慢整个算法的运行。

综上所述，在多陷阱环境下传统蚁群算法存在陷入陷阱而规划失败的问题，而蚂蚁夭折策略和蚂蚁回退策略均存在一定缺陷，因此有必要研究高效的躲避陷阱策略。

3 多因素启发蚁群算法

为了提高多陷阱环境下蚁群算法的路径规划效率和规划质量，这里从两个角度提出改进方法。（1）引入新的启发因素，命名为安全启发因素，新启发因素的引入使蚂蚁避开障碍物密集区域；（2）引入智能蚂蚁策略，为蚂蚁赋予一定智能性，当蚂蚁所在陷阱过深时则蚂蚁夭折，当蚂蚁所在陷阱不深时则蚂蚁跳跃出陷阱，保证算法的高效性。

3.1 安全启发因素

式中：ε—避障系数；safetyj—安全启发因素；Aj—栅格j的紧邻栅格数；Oj—栅格j的紧邻栅格中的障碍物栅格数；Lj—栅格j的紧邻栅格中被禁忌表限制不能通过的栅格数量。

另外，这里提出了迭代次数自适应的伪随机转移策略，为：

式中：q0—自适应迭代次数；Nmax—最大迭代次数；Nm—当前迭代次数。分析式（6）可知，当迭代次数较小时，q0较大，算法主要按照(t)更新栅格，使算法随机性较大，提高路径规划的多样性；当迭代次数较大时，q0较小，算法主要按照更新栅格，使算法主要选择较优栅格，使算法快速收敛于最优路径。

3.2 智能蚂蚁策略

3.1 节通过在蚁群算法中引入安全启发因素使算法尽量避开障碍物密集区域，但是无法完全避开陷阱的死区。为了使蚂蚁在陷入死区后能够兼顾规划效率和规划质量，提出了智能蚂蚁策略，分为陷阱死区确认、蚂蚁复位和蚂蚁跳跃等3个方面。

（1）陷阱死区确认。当蚂蚁的可选栅格只有一个时，对蚂蚁所在栅格进行标记并计数，当这种情况连续出现且最终无栅格可选时说明蚂蚁陷入了死区。陷阱深度通过计数得到，记为H；

（2）蚂蚁复位：设置一个陷阱深度阈值，记为Hth。当H≥Hth表示陷阱较深，蚂蚁在陷阱中耽误时间较长，为了防止此蚂蚁拖慢算法，此时蚂蚁不再进行路径规划，将其复位到起点，等待下次循环；

（3）蚂蚁跳跃：当H

预想故障集的选择，实用中一般采用N-1的安全准则，主要考虑交流线路N-1故障、主变N-1故障及母线N-1故障，以及VSC-HVDC接入后，所带来的直流线路N-1故障、换流变N-1故障以及换流阀的N-1故障。

3.3 算法流程

根据3.1节安全启发因素和3.2节智能蚂蚁策略的构造方法，结合蚁群算法基本流程，得到多因素启发蚁群算法流程为：

（1）设置算法参数，包括蚁群规模m、信息素因子α、启发函数因子β、避障系数ε、最大迭代次数Nmax、陷阱深度阈值Hth；

（2）将所有蚂蚁均放置在起点位置，蚂蚁按照式（6）选择下一栅格；

（3）判断蚂蚁是否进入陷阱死区，若是则使用智能蚂蚁策略逃出陷阱；

（4）当复位蚂蚁和到达终点蚂蚁数之和为m时，表示一次迭代完毕，Nm=Nm+ 1；判断Nm是否达到最大迭代次数Nmax，若否则转至（2）；若是则输出最优路径，算法结束。

4 实验验证

本节通过3个仿真实验对2个改进措施进行验证：（1）验证改进算法可否有效避开障碍物密集区域；（2）验证在多U型障碍物环境下的规划质量；（3）验证复杂多障碍物环境下改进算法的规划效果。

4.1 对躲避障碍物密集区域的验证

3.1 节引入的安全启发因素可以使算法躲避环境中的障碍物密集区域，本节对这一改进措施进行验证。为了进行比较，同时使用蚁群算法和多因素启发蚁群算法进行路径规划，为了保证公平，算法参数设置为相同值。算法参数设置为：蚁群规模m= 30、信息素因子α= 1、启发函数因子β= 6、避障系数ε= 1、最大迭代次数Nmax= 100、陷阱深度阈值Hth= 4。

同时使用蚁群算法和多因素启发蚁群算法在图4所示环境中进行路径规划，所得结果，如图4所示。图中“S”为起点栅格，“G”为目标栅格，实线为多因素启发蚁群算法的规划路径，虚线为蚁群算法的规划路径。

图4 环境1的路径规划结果Fig.4 Path Planning Result Under Environment 1

分析图4可知，路径过程中不存在U型障碍物，因此规划过程中未使用智能蚂蚁策略，只有安全启发因素这一改进措施发挥作用，实现了对单一改进措施的验证。从路径长度看，传统蚁群算法和多因素启发蚁群算法规划的路径长度均为13.8995，即路径长度一致。但是传统蚁群算法规划路径中存在一段“危险路径”，即红色虚圆圈出部分，此部分路径在障碍物之间穿过，安全裕度较小；而多因素启发蚁群算法由于加入了安全启发因素，能够有效避开障碍物密集区域，提高了路径安全裕度。

4.2 多U型障碍物环境下仿真

前文提出的智能蚂蚁策略可以在蚂蚁掉入陷阱时进行复位或者跳出，为了验证这一改进措施的有效性，这里在多U型障碍物环境下进行仿真测试。为了进行比较，同时使用传统蚁群算法和多因素启发蚁群算法进行路径规划。为了使传统蚁群算法可以应对多U 型障碍物环境，将蚂蚁夭折策略融入传统算法中。算法参数设置同4.1节一致，仿真环境及规划结果，如图5所示。图中虚线为传统蚁群算法规划结果，实线为多因素启发蚁群算法规划结果。

图5 环境2的路径规划结果Fig.5 Path Planning Result Under Environment 2

从图5中可以直观看出，传统蚁群算法在多U型障碍物环境下规划的路径充满曲折路段，不仅严重增加了路径长度，而且增加了路径转折点，增加了机器人行驶过程中的磨损。统计两种算法规划的路径长度、未完成路径规划的蚂蚁数量，如表1所示。

表1 多U型障碍物环境下结果统计Tab.1 Result Statistics Under Multiple U-Shaped Barriers Environment

表中“未完成路径规划的蚂蚁”是指传统蚁群算法中的夭折蚂蚁和改进算法中的复位蚂蚁，算法迭代次数为50次，表中未完成路径规划的蚂蚁数量为50次迭代的均值。

结合图5和表1可知，传统算法中夭折蚂蚁数量均值为14，改进算法中复位蚂蚁数量为5，由于传统蚁群算法中夭折蚂蚁数量较大，因此了路径规划质量，最终规划的路径长度为34.968，且路径充满曲折路段。而改进算法复位蚂蚁数量均值仅为5，远小于夭折蚂蚁数量，说明智能蚂蚁策略能够较好地保持种群规模、提高路径规划质量，最终规划路径长度为33.312，比传统蚁群算法路径长度减少了4.74%，且路径平滑，易于机器人行驶。

4.3 复杂多障碍物环境下仿真

为了进一步验证多因素启发蚁群算法的性能，在复杂多障碍物环境下进行仿真，同时使用传统蚁群算法和改进蚁群算法进行路径规划，算法参数设置同4.1 节一致。为了验证算法性能的稳定性，进行20次仿真。仿真环境及最优规划路径，如图6所示。图中虚线为传统蚁群算法规划结果，实线为多因素启发蚁群算法规划结果。

图6 环境3的路径规划结果Fig.6 Path Planning Result Under Environment 3

统计20次规划的最优路径均值、最优路径最优值、算法迭代次数均值、算法迭代次数最小值、路径拐点均值结果，如表2所示。

表2 复杂多障碍物环境下结果统计Tab.2 Result Statistics under Complex Multiple Barriers Environment

由表中数据可知，传统蚁群算法规划的路径最优值为34.141，改进算法规划的最优路径长度为27.042，减小了20.79%；从算法迭代次数看，传统算法最少迭代次数为22，改进算法最少迭代次数为13，两者相差约1倍。从路径拐点数量看，传统蚁群算法拐点数量为35，而改进算法拐点数量为9，相差约4倍。从路径最优值和均值差值看，改进蚁群算法的性能稳定性明显优于传统蚁群算法。

以上数据说明，多因素启发蚁群算法规划的路径长度、拐点数量均优于传统蚁群算法；且算法迭代次数较少，规划效率明显高于传统蚁群算法。以上3个实验充分验证了多因素启发蚁群算法在复杂多障碍物环境下路径规划的有效性，其规划性能明显高于传统蚁群算法。

5 结论

这里研究了复杂多障碍物环境下的机器人导航路径规划问题，建立了工作环境的栅格模型，提出了多因素启发的蚁群算法，经验证得出以下结论：

（1）经前文验证可知，多因素启发蚁群算法由于加入了安全启发因素，能够有效避开障碍物密集区域，提高了路径安全裕度，从主动选择的角度减少陷入陷阱的可能性；

（2）经前文验证可知，在多U型障碍物环境下，传统蚁群算法夭折数量大，且路径较长，而改进蚁群算法的夭折数量小，且路径平均长度较小；

（3）由前文验证可知，多因素启发蚁群算法规划的路径长度、拐点数量均优于传统蚁群算法，且算法迭代次数较少，规划效率明显高于传统蚁群算法。