煤矿救援机器人路径规划的蚁群优化算法

郭 泰，颜 铤

(重庆应用技术职业学院，重庆 401520)

煤矿作业具有潜在危险性，利用机器人代替人类进入矿井危险区域采集信息，可保障煤矿井下作业安全性，为煤矿救援决策提供有效依据[1]。煤矿井下作业电气设备需为满足严格要求与规定的高防爆设备，煤矿救援机器人安全性需高于煤矿井下设备安全性能[2]。应用于煤矿井下救援的仪器设备应为隔爆型。煤矿救援机器人井下作业时，地理环境复杂，容易由于碰撞破坏其隔爆性能，形成煤尘火花等造成矿井二次垮塌、引爆水、火、障碍物等爆炸等二次灾害。煤矿救援机器人应用于矿井作业中时，应避开水、火、障碍物等危险区域[3]。研究煤矿救援机器人路径规划问题，可令煤矿救援机器人充分发挥其作用。规划煤矿救援机器人行驶路径时，应充分考虑矿井所具有的复杂环境，避开水、火、障碍物等危险区域，寻找无障碍最优路径[4-5]。煤矿救援机器人路径规划问题属于多障碍、高信息量的多约束问题，采用传统寻优算法容易造成求解陷入局部最优，无法获取最优全局规划路径。

目前针对机器人路径规划研究较多，徐梁等[6-8]分别利用改进ACO、粒子群算法以及负反馈机制应用于路径规划中，可有效获取路径规划的全局最优解，但存在计算过于复杂的缺陷，为此提出了煤矿救援机器人路径规划的蚁群优化算法，该算法利用蚁群优化算法获取煤矿救援机器人路径规划的最优解，障碍物分布密集区域仍可保持最优路径规划结果。通过实例分析验证所研究算法具有较高的全局路径规划有效性，矿井的复杂环境下仍具有极高的路径规划能力，可快速获取无障碍物、避开水、火、障碍物等分布的最短路径，规划性能优越。

1 蚁群优化算法

1.1 环境建模与问题描述

用规格为r×r的正方形区域表示煤矿救援机器人尺寸，设救援机器人规划空间为包含众多大小为r×r的栅格组成，编号全部栅格建立栅格化地图模型。标记规划空间中栅格为障碍栅格以及自由栅格[9]，当水、火、障碍物等分布占有栅格部分或全部以及完全不包含水、火、障碍物等分布时，分别用障碍栅格g∈O以及自由栅格表示。设规划空间大小为R×C，ng表示栅格编号，(xg，yg)表示栅格坐标，可得表达式：

(1)

式中，「⎤为取整符号；mod为求余符号。

可得栅格内煤矿救援机器人路径规划问题目标函数：

(2)

(3)

式中，T为目标栅格；N(g)为栅格g的邻域；S为栅格g起点栅格；q为最优路径中栅格数量；dgigi+1为栅格gi与gi+1间的中心距离。

1.2 确定煤矿救援机器人可行驶路径

煤矿救援机器人可行驶路径数量用表示，确定可行驶路径可提升路径搜索速度[10]，避免局部优化问题，机器人可行驶路径：

(4)

式中，stal(i)为起点的聚度；m为移动障碍物数量；r为可绕过移动障碍物的路径数量；al为条路径中障碍物数量。

存在数量为m的障碍物分布于数量为r的道路中时，可得该路径上障碍物数量共m/r个。将起点i的聚度转化为：

(5)

数量为m的障碍物集中于其中一条路径时，可将聚度公式转化为：

(6)

利用式(6)获取最大可能聚度值。

1.3 传统蚁群算法

煤矿救援机器人从i处移动至j处时，做出定义：时间为t时，蚁群在位置i与j处留下的信息浓度用残留信息量ij(t)表示，di，j为2点间距用表示，τ为处于[0，1]的挥发因子。利用以下公式调整蚁群迭代一次后不同路径上信息浓度：

τi，j(t+1)=ρτi，j(t)+Δτi，j

(7)

式中，ρ为信息素保留率；Δτi，j为蚁群经过此条路径时所增加的信息浓度，其计算公式：

(8)

蚂蚁k经过节点i与节点j时，可得公式：

(9)

式中，Q为常数；Lk为蚂蚁k所经过路径总长度。

蚂蚁k由位置i移动至位置j的概率公式为：

(10)

蚂蚁k从i处移动到j处可视程度公式：

(11)

式中，allowed为蚁群可行驶路径集，蚂蚁k行走的全部节点均存储于该集合中时，表示蚂蚁k实现一次迭代，此时煤矿救援机器人完成一次可行路径选取[11]；α为路径的信息浓度；β为启发式因子重要性；η为启发因子。

1.4 蚁群优化算法

1.4.1 改进信息素规则

采用蚁群算法搜索最优路径时，利用调节不同路径信息素聚集蚁群至最优路径附近，通过信息素更新规则改进[12]，同时提升以及降低蚂蚁行驶于最优路径以及最差路径的信息素浓度，令蚁群快速获取最优路径。信息素规则改进公式：

(12)

式中，τnew为信息素挥发系数；ρ为新路径信息素；τold为原路径信息素；δ为调节因子；Dbest为最优解；Dworst为最差解。

通过以上过程改进信息素更新规则，令迭代过程中可较大概率遍历最优路径[13]，缩小煤矿救援机器人路径规划搜索范围，提升蚁群优化算法获取最优解效率。

1.4.2 限制信息素阈值

信息素阈值限制形式：

(13)

式中，τi，j为节点i至j的信息素；τmin为最小信息素；τmax为最大信息素。

通过以上过程限制，信息素位于[τmin，τmax]，可保障所获取的信息素变化于合理范围内，避免信息素无穷大或无穷小[14]，限制最优路径以及最差路径中信息素浓度差异。

1.4.3 改进转移概率

改进蚁群算法中的启发因子，提升算法获取最优解概率[15]，定义优化后启发因子公式：

(14)

式中，djEnd为栅格节点j至终点间距，其公式：

(15)

式中，(xj，yj)为节点坐标值；(xEnd，yEnd)为终点坐标值。

优化所获取启发因子ηjEnd越小，表示被选中该栅格节点j概率越高。

将随机选择参数r0加入算法中，利用多样性的解提升算法全局寻优能力。r∈(0，1)与r0∈(0，1)分别为随机数以及随机选择参数，当r

(16)

(17)

式中，t为时间变量；s为可行走栅格节点。

2 实例分析

选取某煤矿规格为80 m×4 m的巷道进行实验。矿井下部分区域分布有水、火、障碍物等，巷道下所分布水、火、障碍物等均低于5%，未存在超标情况。为保障煤矿救援机器人安全行驶，设置煤矿内水、火、障碍物等高于3%的区域为机器人行驶危险区域。充分考虑煤矿巷道内的水、火等分布以及巨石、土堆等障碍物，建立实验区域巷道环境模型如图1所示。

从图1实验结果可以看出，本文算法可有效依据煤矿的矿井巷道环境建立环境模型。所建立环境模型有效考虑水、火、障碍物等分布情况，并将巨石、土堆等障碍物均建立于模型环境中，提升煤矿救援机器人路径规划的行驶安全性。

实验设置机器人起点与终点坐标分别为(5，0.5)、(80，10)。选取ACO算法(参考文献[6])、粒子群算法(参考文献[7])以及负反馈算法(参考文献[8])作为对比算法，不同算法搜寻机器人行驶最优路径时收敛曲线如图2所示。由图2实验结果可以看出，采用本文算法规划煤矿救援机器人行驶最优路径，仅需20次左右即可快速获取最优解，算法步入平稳趋势；ACO算法、粒子群算法以及负反馈算法搜寻机器人最优行驶路径时，均需要80次以上收敛曲线趋于稳定。对比结果说明，本文算法采用蚁群优化算法具有较高的收敛性能，可快速搜寻煤矿救援机器人最优行驶路径。

图2 收敛曲线对比

采用4种算法规划煤矿救援机器人最优行驶路径结果如图3所示。

由图3实验结果可以看出，采用不同算法均可有效获取煤矿救援机器人最优行驶路径。本文算法所获取机器人最优行驶路径可有效避免水、火等分布以及巨石、土堆等障碍物；ACO算法、粒子群算法以及负反馈算法虽同样可以获取机器人最优行驶路径，但仅可躲避巨石等障碍物，未考虑水、火、障碍物等分布情况。煤矿救援机器人行驶于矿井巷道中，容易由于碰撞火花与水、火、障碍物等接触出现二次爆炸等严重情况，本文算法所获取机器人最优行驶路径有效躲避水、火、障碍物等分布区域，提升煤矿救援机器人行驶安全性。

统计采用本文算法规划煤矿救援机器人行驶路径的最优路径长度、最优转角数量以及最优危险度，统计结果如图4—图6所示。

图4 最优路径长度

由图4—图6实验结果可以看出，相比于其他算法，本文算法具有较强的收敛速度以及全局寻优能力，本文算法采用蚁群优化算法规划煤矿救援机器人具有较高有效性。本文算法可快速获取具有最优综合性能的可行驶路径，规划效果优越。本文算法应用于煤矿救援机器人路径规划时，充分考虑煤矿巷道工作区域的复杂性以及危险性，所获取路径规划结果长度最短，最优转角数量最少，最优危险度最低，验证采用本文算法所获取最优解具有较高质量。

图6 最优危险度

为验证本文算法采用蚁群优化算法的准确性，在上述实验参数和环境的基础上，进行对比实验，不同方法的鲁棒性和运算效率对比结果如图7、图8所示。

图7 不同方法的鲁棒性对比

图8 不同方法的运算效率对比

由图7和图8可知，相比其他方法，本文算法采用蚁群优化算法规划煤矿救援机器人具有较高的鲁棒性和运算效率。本文算法可准确获取可行驶路径，规划效果优越。验证采用本文算法所获取最优解具有较高准确性。

测试不同方法进行煤矿救援机器人路径规划的参数对比如图9所示。分析图9得知，本文方法降低了疏散时间，提高了救援机器人的可靠性抵达能力。

图9 参数性能对比

3 结语

通过机器人路径规划获取无障碍物影响，且行驶长度最短的路径即机器人行驶的最优路径。蚁群算法应用于机器人路径规划时具有易陷入局部最优、运算过于复杂的缺陷。煤矿救援机器人应用过程中具有较高复杂性，煤矿救援机器人运行于矿井时，不仅需要考虑路径最短问题，最优路径规划时还需躲避水、火、障碍物等区域。将蚁群优化算法应用于煤矿救援机器人路径规划中，通过信息素更新规则等部分优化算法，令蚁群算法信息素浓度处于合理范围，提升蚁群优化算法寻找最优路径的运算效率，提升算法全局寻优性能。通过实验验证，采用该算法可有效获取煤矿救援机器人的最优路径规划结果，快速获取最优可行解，所获取机器人路径规划结果有效避开水、火、障碍物等部位，在复杂矿井环境下仍具有较高的寻优能力，可应用于环境复杂的煤矿救援机器人路径规划中。