基于改进蚁群算法的无人矿车路径规划研究

刘 辉，肖 克，王京擘

（青岛大学 自动化学院，青岛 266071）

0 引言

无人采矿技术为智能采矿技术发展的重要领域之一，而矿物运输对于矿区发展起着举足轻重的作用，无人矿车有助于实现安全生产，降低人工成本，提升运行效率，成为在无人采矿技术中的重要组成部分。由于矿区坡度较大、地形复杂，对无人矿车的行驶速度和轨迹都有很大的影响，因此如何根据矿区复杂地形对无人矿车进行安全合理的轨迹规划成为了急需解决的问题。常用的路径规划方法有传统路径规划算法A*算法[1]等和一些智能优化算法，如遗传算法[2]、模拟退火算法[3]、蚁群算法[4～7]等。

蚁群算法具有较强的鲁棒性、优秀的分布式机制[8]，在路径规划领域有着较好的表现。但蚁群算法也存在一些问题，如收敛速度较慢、搜索范围较小容易陷入局部最优路径等。一些研究者通过修改传统蚁群算法状态转移规则中的影响因素来提高算法的性能。文献[9]提出采用等级反馈制度对适应度较强的蚂蚁和较差蚂蚁的信息素分别按照一定比例进行增强和减弱。为了避免陷入局部最优，文献[10]根据目标点信息自适应的调整启发式函数。还有一些研究者将蚁群算法与其它路径规划算法相结合，文献[11]中结合蚁群算法与人工势场法，在迭代初期通过人工势场对信息素进行初始化。文献[12]加入了多策略进化机制并通过A*算法优化初始信息素设置。

本文在矿区复杂环境的基础上，根据传统的路径规划算法，提出了改进的蚁群路径规划算法。通过栅格法建立模型，紧密结合矿区环境，通过坡度-速度模型将矿区环境中矿车的速度引入到状态转移规则中。由于矿区环境复杂，使用常规的蚁群算法容易进入障碍陷阱，因此引入障碍探索机制，对环境进行充分的探索。最后将局部最优路径融合，使每一代蚂蚁能够获得较好的路径。

1 环境建模与蚁群算法介绍

1.1 环境建模

常用的环境建模方法有栅格法[13]、可视图法[14]和拓扑法[15]等。本文采用栅格法对矿区工作环境进行建模，模型如图1所示，黑色栅格表示矿区中的矿堆，矿坑等障碍物。通过M×M个单位栅格的序号i和坐标（x，y）来描述矿车与环境之间的关系，单位栅格的坐标则是每个栅格的中心位置，栅格坐标与序号转换公式如下：

当x为负数时，其值为栅格坐标中的最大横坐标M-0.5，在不碰到障碍物情况下，矿车可以向周围的八个栅格移动。

图1 环境模型示意图

1.2 蚁群算法介绍

蚁群算法是一种用来寻找优化路径的启发式算法，Marco Dorigo通过蚂蚁在寻找食物时的搜寻路径的行为提出了蚁群算法，算法模仿蚂蚁产生信息素，通过蚂蚁间正反馈的方法来引导蚂蚁的行为。传统蚁群算法的状态转移概率公式为：

其中，Pijk（t）为在蚂蚁k在时刻t从节点i到节点j的概率；τij（t）为在时刻t节点i到节点j的信息素浓度；ηij（t）表示在时刻t节点i到节点j之间距离的倒数；Jk（i）为节点i的下一可行节点集合；α和β分别为信息素浓度因子和启发函数因子。

2 改进的蚁群算法

2.1 改进启发函数

蚂蚁在寻路时有时会陷入各种障碍之中，但由于许多障碍对蚂蚁寻找最优路径并不会产生较大影响，因此本文提出一种障碍探索机制，仅对影响蚂蚁寻找最优路径的障碍进行规避。蚂蚁在选择下一栅格时，首先对下一栅格的周围环境进行探索，如果其周围三个距离目标点最近的栅格都包含障碍，则证明其会阻碍蚂蚁寻找最优路径或者陷入死锁，因此会减小此栅格的选择。

障碍探索的几种情况如图2所示，假设红旗位置为蚂蚁所在的当前节点的位置，它的一个可选栅格s为圆点所在栅格，蚂蚁的搜索范围为圆点周围距离目标点最近的三个栅格，即观察栅格i，j，k是否都包含有障碍物，若三个栅格都包含有障碍，则圆点所在栅格的障碍影响因子设为相对较大的值，避免选择此类栅格。若三个栅格不全为障碍，则该栅格的障碍影响因子为零，该栅格为可行栅格。

因此，下一栅格点s的对于蚂蚁搜寻路径的障碍影响因子为：

其中，Dis（s）表示栅格s到目标点的距离，根据栅格位置的不同，动态调整障碍影响因子的大小。G（i）∈{0，1}为栅格i的状态，0表示无障碍、1表示有障碍。i，j，k为s附近的三个离目标点距离最短的栅格且满足：

最后将最优路径影响因子与距离启发信息进行权衡，得出节点s最终的启发函数为：

本节提出一种障碍探索机制，对障碍物进行提前规避，减少了蚂蚁选择一些延长路径的节点和陷阱点的概率，在一定程度上提高了算法的性能，且保障了矿车的安全。

2.2 矿车速度影响因子

由于矿区环境复杂，地形崎岖不平，当矿车在坡度较大区域行驶时会产生大量的能量损耗，也对矿车的安全性有一定影响。因此我们将矿区环境中的坡度等因素考虑入我们建立的环境模型中。我们采用荣健博士论文[16]中的车辆速度与坡度等因素的数学模型：

其中，v2为上坡Δt时间段后车辆的速度，v1为Δt之前的速度，Δt为经过的时间步长。P表示车辆功率质量比，δ与KF表示车辆的惯性阻力系数与风阻系数，i，f为坡度与摩擦阻力，g表示重力加速度，G表示车辆的空载质量与实际载重。

为了简化模型，本文中在起始栅格设置初始速度，将上一栅格到达当前栅格的速度和当前栅格i到达下一栅格j的速度Vij(t)近似代替式(6)中的v1，v2。环境坡度随着y坐标的减小逐渐增大。将速度预测模型加入栅格状态转移模型中，使得在路程较短的情况下更多的选择坡度较小栅格，以减少能量损耗、更短的时间完成任务。

2.3 改进信息素策略

在传统的蚁群算法中，在一代蚂蚁寻找路径后更新全部信息素，因此会导致出现收敛速度较慢，收敛到局部最优等问题。为了使每代蚂蚁寻找完路径之后能探索距离与时间综合最优的路径，使下一代蚂蚁在此较优路径的基础上探寻更优的路径，因此在每代蚂蚁寻找完路径之后采用局部距离时间综合最优路径融合的方法。

图3 路径融合示意图

首先根据式(7)挑选出每代蚂蚁中距离与时间综合最优的几只优秀蚂蚁，对它们局部的距离时间综合最优的路径进行融合，重新组成一条可能更优的路径。距离与时间权衡公式如下：

其中D为路径长度；T为走过该路径消耗的时间，根据栅格之间的速度与距离得出；ξ代表时间的重要程度。图中为第n代蚂蚁中前三条最优的路径，ai表示蚂蚁i所走过的节点。若路径之间存在相同节点，则对比蚂蚁的相同节点之间的距离与时间，根据式(7)取出两节点之间的最优路径。图中阴影栅格表示了融合后的最优路径，融合公式如下：

其中Flir（t）为第t代优秀蚂蚁r从节点l到节点j的距离与时间综合评价指标，Lljr（t）为第t代优秀蚂蚁r从节点l到节点j的路径，L12（t）表示优秀蚂蚁1和优秀蚂蚁2的融合路径。k，m与g，n代表蚂蚁经过的相同的节点中两个最近的节点。另外加入了历史最优蚂蚁路径同融合路径进行对比选择更优路径，使算法在前期能够通过融合路径更好地探索最优路径，而在后期会较多选择历史最优路径，加大对最优路径的利用，公式如下：

则新的信息素更新公式如下：

2.4 改进算法流程图

改进算法步骤如图4所示，首先对地图进行处理和参数初始化，蚂蚁在选择每个可选节点时先对其周围探索区域进行探索，在信息素、启发式信息、速度的共同作用下选择节点。当蚂蚁到达目标点时记录路径，挑选出优秀蚂蚁进行路径融合，增强融合路径和历史最短路径中较优路径的信息素。当到达最大迭代次数后，输出最优路径。

图4 改进蚁群算法流程图

3 仿真实验

为验证本文改进的蚁群算法的有效性，在MATLAB 2014a软件环境进行仿真实验，并与传统蚁群算法进行比较。栅格环境大小为20×20，每个栅格大小表示100m×100m，即矿区环境大小为2km×2km，并且栅格颜色的加深，表示矿区坡度不断变大，根据栅格之间的速度和距离求解出完成路径规划所需的时间。实验设置每代蚂蚁的个数M=50，最大迭代次数为50次，信息素影响因子α=1，信息素蒸发系数ρ=0.5，启发式影响因子β=7，距离启发信息影响因子σ=1，最优路径影响因子比例δ=2，速度影响因子γ=1。

3.1 仿真实验结果

图5和图6为两种障碍物复杂度不同的仿真环境，可以看出由于改进的蚁群算法由于加入了障碍探索机制，对于一些阻碍蚂蚁寻找最优路径的点和陷阱点，算法对其提前进行了屏蔽，避免了如图5中传统蚁群算法陷入了一些障碍中。在图6环境中，虽然两种算法都找到了最短路径，但改进的算法有着较快的收敛速度，如图7所示，改进算法在16代左右就收敛到了最优路径，相比传统蚁群算法在29代左右收敛有了明显的提升，另外在相同路长情况下，改进的算法较多的选择坡度较小的栅格，以21.07min到达目标点，比传统蚁群算法21.19min完成用时更短。

图5 仿真环境1及仿真结果

图6 仿真环境2及仿真结果

图7 仿真环境2收敛曲线

最后选取了30×30栅格的新环境并进行了多次实验，结果取其平均值，最终结果如表1所示，可以看出改进的蚁群算法在两种环境中所用路长和时长较为稳定，且都优于传统蚁群算法。

表1 改进蚁群算法与传统蚁群算法性能对比

4 结语

本文针对矿区环境下的矿车路径规划问题，提出了一种改进的蚁群路径规划算法。首先考虑到矿区环境的复杂性，提出一种障碍探索机制，对于一些会阻碍蚂蚁寻找最优路径的节点和陷阱点进行规避，避免蚂蚁增加其路径长度和陷入死锁，对矿车的安全性也带来一定提升。结合矿区部分区域坡度较大问题，将坡度-速度模型加入状态转移概率公式中，在路径较短的前提下，尽可能的选择坡度较小的区域，以加快运输时间。最后采用优秀蚂蚁路径融合的方法，提高了路径探索率，一定程度上避免收敛到局部最优路径。经仿真验证，改进的蚁群算法在复杂的矿区环境下能够规划出一条距离和时间较短、安全性较高的路径。