基于改进蚁群算法的移动机器人火灾救援路径规划方法

昝新宇，张铁峰, 苑津莎

(华北电力大学电气与电子工程学院，保定 071003)

近年来，中国每年发生数万起火灾事故[1-2]，严重影响着人们正常的生产生活。随着机器人技术的迅速发展，机器人因其智能、高效等优点受到各行各业的青睐，因此移动机器人参与火灾救援已成为未来发展趋势。为此，探究移动机器人在火灾救援中如何快速到达待救援点执行救援任务，具有十分重要的研究意义。

关于火灾救援路径规划的问题，李珊珊等[3]针对多起点、多终点的大型火灾救援路线，设计了一种组合优化路径规划方法，可以计算出安全、快速的救援路径，提高了火灾救援的效率；刘军[4]采用蚁群算法与遗传算法结合方式，改善了超市火灾环境下消防员灭火救援路径；张苏英等[5]提出一种改进蚁群算法，优化了大型综合建筑火灾疏散路径;张丽杰等[6]针对复杂建筑火灾中的人员疏散路径优化策略问题，构建了一种以最短时间、最小风险水平和最大疏散容量为目标的路径优化模型，并结合自适应果蝇算法对模型求解。

在移动机器人路径规划方面，Luo等[7]为解决蚁群算法搜索效率低、收敛速度慢等问题，提出一种优化蚁群算法，并通过实验仿真验证了该算法能够提高移动机器人路径规划效率；王苏彧等[8]提出了一种基于自适应导向的优化蚁群算法，通过优化算法的收敛速度和寻优能力，进而提高了移动机器人自主规划路径的能力；Ranaweera等[9]提出了一种粒子群优化算法来寻找消防救援机器人的最短路径，并通过模拟实验验证了改进算法的效率远高于传统算法；李理等[10]提出了一种多启发因素改进蚁群算法，该算法计算出的路径在路径长度、转弯次数以及坡度平滑性三因素综合性能上具有较大的提高，进而增强了移动机器的环境适应能力。

当前，中外学者针对移动机器人火灾救援路径规划问题的研究较少，而且在已有方法中只考虑了距离因素，没有考虑影响路径选择的其他因素。对此，现考虑多因素针对移动机器人火灾救援路径规划的影响，提出一种基于改进蚁群算法的移动机器人火灾救援路径方法。方法考虑多因素分配各路径上的信息素，指导蚂蚁寻找最优路径。通过动态调整信息素和启发式函数影响因子，以期提升算法的搜索能力与收敛速度。

1 环境描述

环境模型的构建对于移动机器人路径规划至关重要，通过部署在建筑物内的无线传感设备获取环境信息，然后根据栅格法[11]建立环境模型。通过MATLAB仿真，仿真结果如图1所示。

绿色圆点为移动机器人的起始位置，红色圆点为待救援位置；黑色栅格表示障碍物，白色栅格表示自由空间；红色栅格表示火源中心，黄色栅格表示火源周围蔓延区域；绿色深浅表示坡度大小，颜色越深表示坡度越大

针对移动机器人在火灾救援过程中对于安全性方面的要求非常高，规划出的路径尽量远离障碍物、火源以及蔓延区域，即使顶点也要避免触碰。因此规定每个栅格中心为节点，蚂蚁的运动轨迹可以理解为从当前节点到下一节点转移的累积过程。同时为了避免移动机器人在转弯过程中发生碰撞，只有目标栅格和转角处栅格均为自由栅格时，才能向该目标节点转移，如图2所示。

图2 转弯示意图

2 传统蚁群算法

蚁群算法是Dorigo提出的一种模拟蚂蚁种群觅食行为的智能仿生算法[12]。该算法具有并行计算、正反馈、鲁棒性强等优点，因此许多学者将蚁群算法用于路径规划，并取得较好的效果。信息素模型和启发式函数的构建是蚁群算法优劣的关键因素[13]。信息素是蚁群发出的指引信息并随着时间挥发，路径上的信息素浓度越高，越能指导蚂蚁沿该路径前进；启发式函数则相当于蚂蚁根据自身所处环境进行判断的依据。

蚂蚁在搜索过程中根据转移概率选择下一步前进方向，转移概率为

(1)

(2)

每只蚂蚁在使用信息素的同时也会分泌信息素，并且会随着迭代次数的增加，信息素会在路径上积累，同时也会挥发减少。传统蚁群算法的信息素更新模型为

τi,j(t+1)=(1-ρ)τi,j(t)+ρΔτi,j(t)

(3)

(4)

式中：ρ为信息素挥发度；Δτi,j(t)为第t次迭代中信息素在节点i至节点j上的增量；Q为信息素常数；Lk为第k只蚂蚁从起点至终点走过的路径长度。

3 改进蚁群算法

3.1 多因素启发式函数

传统蚁群算法的启发式信息与当前节点到下一节点的距离成反比，这促使蚂蚁选择距离短的路径。但是，在实际环境中决定路径优劣的因素不止距离一种，还有路径的曲折程度、颠簸程度等因素。移动机器人在火灾救援中多转弯一次可能会浪费大量的宝贵救援时间，颠簸程度较大的路况不仅会影响移动机器人的速度，可能还会损坏机器设备。因此，规划一条综合指标最好的路线对于移动机器人参与火灾救援至关重要。为此，针对影响路径优劣的多因素引入多因素启发式函数，来计算转移概率，并同时引入阻尼系数，加快算法后期的收敛速度，即

(5)

(6)

式中：φ(i,j,q)为距离因素，即当前节点的各个相邻节点至目标节点的欧式距离的倒数；φi,j(t)为曲折程度，即当前转向若与上次转向相同，则其值就较大，反之则较小；υ(i,j)为颠簸程度，即当前节点与下一个节点的高度差的倒数；ζ为阻尼系数；tmax为最大迭代次数。

3.2 改进信息素更新规则

信息素更新主要模拟自然界中蚂蚁信息素随时间的积累和挥发过程。将最大-最小蚁群系统(MMAS)的基本模型与多因素启发式函数相结合，对信息素更新规则进行改进。

每当一只蚂蚁到达终点时，信息素根据式(7)、式(8)进行局部更新。所有蚂蚁完成一次迭代后，所有蚂蚁行走的过程中，会存在综合指标最小的路径，全局信息素只对其更新，从而增加当前综合性最优路径对后续蚁群寻优的影响，如式(9)所示。

(7)

Sk(t)=xLk(t)+yFk(t)+zTk(t)

(8)

(9)

式中：Sk(t)为第k只蚂蚁在第t次迭代中所走路径的综合指标；Smin(t)为第t次迭代中最小的综合指标；Lk(t)为路径长度；Fk(t)为蚂蚁访问过节点的高度均方差；Tk(t)为转弯次数；x、y、z分别为路径长度、颠簸程度以及曲折程度的相对重要性，可以根据实际需要进行调节。为了防止算法停滞，将信息素限制在[τmin,τmax]范围内，如式(10)所示。

(10)

式(10)中：τmin、τmax分别为信息素的最小值和最大值，取值可以根据实际的场景进行设计。

3.3 动态调整信息素和启发式函数影响因子

信息素影响因子反映了信息素在蚁群搜索中的相对重要性[14]，其值过大或过小，都会导致蚁群算法找不到最优解。启发式函数影响因子反映了蚁群寻找最优解过程中先验性的相对重要程度[15]，其值增大，加速算法的收敛，但同时会减小算法的随机性；减小时，则相反。

因此信息素和启发式函数影响因子对于蚁群算法至关重要，为了提升算法收敛速度和搜索能力，提出了一种动态调整信息素和启发式函数影响因子的方法。算法初期，针对信息素分布差别较小，蚂蚁的搜索过程可能混乱，这时启发式函数在蚁群搜索中起主要引导作用，蚂蚁更多地依据自身环境选择前进方向；随着信息素不断地更新，信息素的分布差别变得明显，此时信息素和启发式函数共同引导蚁群寻优过程，蚂蚁在选择下一节点时，需要同时考虑自身环境和前面蚂蚁留下的信息素。如式(11)、式(12)所示。

(11)

(12)

式中：α为信息素影响因子；β为启发式函数影响因子；ζ为一个百分比常数；A、B、C、D、E为正整数，可随环境不同改变取值。

3.4 改进算法流程

步骤1地图障碍物、火源等位置信息以及参数初始化。其中蚂蚁数量m=50，最大迭代次数tmax=100，信息素强度Q=100，其他的参数作为变量根据实验环境进行设置。

步骤2设置起始坐标与终点坐标。

步骤3禁忌表初始化。

步骤4确定信息素和启发式函数影响因子。根据式(11)和式(12)分别计算信息素和启发式函数影响因子。

步骤5路径选择。由式(3)和式(5)分别计算信息素与多因素启发式函数，然后由式(1)计算蚂蚁每个前进方向的概率，最后利用轮盘赌决定蚂蚁下一个转移节点。

步骤6更新禁忌表。

步骤7判断当前蚂蚁是否到达终点坐标位置，若是，继续执行算法；否则，返回步骤5。

步骤8由式(8)计算蚂蚁走过路径的综合指标，由式(7)进行信息素局部更新。

步骤9判断是否所有蚂蚁完成搜索，若是，继续执行算法；否则，增加蚂蚁数量，即m=m+1，然后返回步骤3。

步骤10更新全局信息素。需要找到本次迭代中综合指标最佳的路径，并根据式(9)进行全局信息素更新。

步骤11判断迭代次数是否达到最大迭代次数，若是，比较各迭代次数中综合指标最佳的路径，输出最优路径，结束算法；否则，增加迭代次数，即t=t+1,m=1，然后返回步骤3。

改进的算法流程如图3所示。

图3 改进算法流程

4 实验仿真与分析

使用MATLAB R2019a仿真软件对算法进行仿真，模拟移动机器人在火灾救援中规避障碍物和火源及蔓延区域的路径规划过程。设定30 m×30 m的区域内均匀分布传感设备，时刻监视火源及蔓延区域情况；移动机器人的起始坐标为(0.5,0.5)m，待救援位置即终点坐标为(29.5,29.5)m。初始环境如图1所示。根据经验和实验仿真对比进行参数取值，算法的参数配置如表1所示。

表1 改进蚁群算法的参数配置

将改进蚁群算法、文献[10]算法和传统蚁群算法在相同的环境模型中进行实验仿真。3种不同算法计算出最佳救援路线如图4所示。

蓝色实线为传统蚁群算法的规划路线；黑色虚线为文献[10]算法计算出的最佳路径；红色实线为本文算法规划的最佳路径

为了验证改进算法的优越性，进行了多次实验仿真，如图5和表2所示。通过比较3个算法的实验结果，在路径长度、路径高度均方差以及转弯次数3个指标上本文算法均小于传统蚁群算法和文献[10]算法，比较3个算法的综合指标可以看出，本文算法计算出的路径在多因素上明显优于文献[10]算法和传统蚁群算法。并且本文算法较大地提高了算法的收敛速度，降低了稳定迭代次数，提升了算法的搜索能力，使蚂蚁初始寻路就能找到综合指标较好的路径。在算法稳定性方面，本文算法多次实验计算出的最优路径中的各项指标波动较小，明显优于文献[10]算法和传统蚁群算法。

表2 本文算法、文献[10]算法及传统蚁群算法的结果对比

连续10次实验中不同算法平均运行时间如表3所示，虽然本文算法运行时间稍长于传统算法，但迭代稳定时间明显小于传统蚁群算法和文献[10]算法。由此可见，本文算法的执行效率显然优于传统蚁群算法和文献[10]算法，可以帮助移动机器人快速找到一条多因素综合性最优的路径。

表3 连续10次实验中不同算法平均运行时间

可见，本文算法在多因素综合性能上有了较大提升，并且具有较好的全局搜索能力和收敛速度。因此，该方法可以使移动机器人有效避开障碍物和火源区域，找到一条安全、快速的救援路线，大大提高了火灾救援的效率。

5 结论

针对移动机器人在火灾救援中路径规划的多种影响因素，提出了一种基于改进蚁群算法的路径规划方法。

(1)改进蚁群算法通过引入多启发式函数和改进全局信息素更新策略，更好地引导蚁群向综合性最优的路径靠近。

(2)通过对信息素和启发式函数影响因子动态调整，提升了算法的搜索能力和收敛速度。

(3)通过实验仿真验证和3种方法的对比分析，验证了本文算法能够满足移动机器人救援路径规划快速决策的需要，较好地提高了火灾救援的效率。

改进算法在传统蚁群算法基础上针对启发式函数和信息素更新方式等方面进行了优化，没有考虑初始信息素差别分布，在今后的研究中，可以利用神经网络对其进行优化，使路径规划方法更加高效、智能。