基于改进蚁群算法的消防救援机器人路径规划方法

丁金虎

摘  要：该文介绍蚁群算法的基本原理与实现步骤，利用BIM技术构建火灾建筑室内环境模型，结合火场情况对蚁群算法进行改进，逐一阐述优化信息素提取更新过程、改进启发函数、躲避特定障碍物、选择逃生路径的具体方法，分析全局路径规划中改进蚁群算法的实现方式，最后展开规划路径仿真实验。通过与2种不同改进算法的路径规划能力进行对比，得出该文所提出改进蚁群算法的优越性，同时还通过算法性能分析发现，此算法的最佳性能、时间性能、鲁棒性均优于其他算法，得出消防救援机器人路径规划过程中改进蚁群算法具有应用可行性与优越性的结论。

关键词：蚁群算法；算法改进；消防救援机器人；路径规划；BIM技术

中图分类号：TU998.1      文献标志码：A          文章编号：2095-2945（2024）14-0133-04

Abstract： In this chapter， the basic principle and implementation steps of ant colony algorithm are introduced， the indoor environment model of fire building is constructed by using BIM technology， and the ant colony algorithm is improved according to the situation of fire scene. The specific methods of optimizing pheromone extraction and updating process， improving heuristic function， avoiding specific obstacles and choosing escape path are expounded one by one， and the implementation of improved ant colony algorithm in global path planning is analyzed. Finally， the path planning simulation experiment is carried out， and by comparing with the path planning ability of two different improved algorithms， the superiority of the improved ant colony algorithm proposed in this paper is obtained. At the same time， through the performance analysis of the algorithm， it is found that this algorithm has better performance， time performance and robustness than other algorithms. It is concluded that the improved ant colony algorithm has application feasibility and superiority in the process of fire and rescue robot path planning.

Keywords： ant colony algorithm; algorithm improvement; fire and rescue robot; path planning; BIM technology

发生火灾的建筑室内环境往往较为复杂，烟气会影响普通激光雷达的运行效果，无法获取准确的室内布局图，因而救援路径规划难度较大。为此，本文提出了利用BIM技术获取建筑物基础信息，再基于改进蚁群算法规划消防救援机器人的救援路径。此种方式能够精准获得建筑室内信息并绘制出准确的室内地图，有效收集障碍物实体信息，且能弥补传统蚁群算法路径规划效率低、性能不佳的弊端。

1  蚁群算法的原理及实现步骤

蚁群算法是模拟蚂蚁寻食行动所构建的算法，蚂蚁之间可通过释放信息素传递信息，从而不受环境限制快速找出到达食物地点的通往路径。路径构建、信息素更新是蚁群算法的两大核心，算法初始阶段会给出固定信息素浓度，迭代一次蚂蚁便完成一次寻食，并计算探寻路径，之后再更新信息素浓度[1]。由于短距离线路较长距离线路残留信息素浓度更高，因而其是路径算法的最优解。蚁群算法共有3种模型，分别是蚂蚁数量系统、蚂蚁密度系统、蚂蚁圈系统，根据旅行商问题（TSP）解决中3种模型的应用效果对比发现，蚂蚁圈系統表现最为优势，因而本文的算法信息素更新机制选用此算法。蚁群算法的实现需经过8个步骤：一是初始化算法参数，二是更新迭代次数，三是设置蚂蚁放置位置，四是基于动态转移概率选择前往位置，五是在禁忌表中加入走过位置，六是循环结束后更新全局信息素求得路径解，七是判断循环完成情况并对比路径解找出循环可行解，八是判断循环（迭代）次数的最大值达成情况并对比各次循环可行解，找出最优解。

2  基于改进蚁群算法的消防救援机器人路径规划方法

2.1  利用BIM技术构建室内环境模型

为缩短救援时间，需基于建筑BIM图中的建筑材料信息、楼层出口位置信息展开火灾仿真，可为消防救援机器人提供火场全局地图，通过局部避障、采用远程控制方式，远程操控机器人快速实施救援。BIM模型数据库涵盖多个数据库引擎，可为BIM数据读写提供支持。因此，可将BIM模型视作建筑数据源，可在模型读写基础上，运用路径规划算法完成室内路径规划任务。本文利用分类提取法提取BIM建筑信息。采用过滤器归类BIM中各个几何元素，收集信道参数预测需应用的建筑构件元素集，再判断各元素类型，提取并存储元素属性中的绝对位置、几何尺寸等信息，以保存文件为基础，构建环境信息数组矩阵，之后采用栅格法创建栅格地图。

2.2  结合火场情况改进蚁群算法

2.2.1  提取更新信息素过程优化

为平衡算法的收敛速度及随机性，应对信息素初始获取及更新过程进行调整，利用栅格间距离计算方法得到节点权值及障碍物分布情况，再预处理障碍物，根据起点及目标点间射线与障碍物是否接触选择需要预处理的障碍物，并标记预处理障碍物在下栅格图中的边界点，以之作为障碍物的起点或末点，注意相交障碍物交点不可作为边界点[2]。再将邻近障碍物距离射线最近的边界点相连，便可绘制出多线段构建的初始路径R，此路径上的信息素可按式（1）初始化

？子（R）=kC，  （1）

式中：k表示不小于零的常数，C表示其他节点信息素初始化值。得到的可行解能够绕过多数障碍物展开搜索，可降低蚂蚁寻径盲目性。之后，应以节点对最优路径的贡献为基础，更改信息素更新规则，即

式中：Lmin、Lkmin分別表示上次迭代及当前迭代次数的最短路径，Lbmin是迭径次数中的最低值，？琢为调节系数，pathmin表示当前迭代次数中蚂蚁路径为最短路径，path指当前迭代次数中其他蚂蚁的有效路径。利用此规则可确保当前迭代次数下，最短路径节点间具有最高的信息素浓度，可使法算收敛速度有所提升。为防止全局搜索时信息素挥发因子为固定常数导致搜索效率下降，需对此因子做出改进，即

式中：GD表示拐点参数平均值，T表示迭代次数。在第T次迭代的拐点参数平均值比第T-1代迭代更高时，增大信息素挥发因子可使算法全局搜索能力得到有效提升，由于消防救援机器人行走路径中的直角优化为钝角，因而机器人可快速获取到最优路径。

2.2.2  改进启发函数

为降低下个最佳节点选择难度，应在具有可访问性且存在多个出口指向目标的节点中筛选下一节点，而节点附近障碍物数量是节点能否正确获取的影响因素，二者成反比关系。为此，应添加概率因子Pij，概率因子的计算公式为

式中：C（8，N）表示节点j附近障碍物所有可能分布的情况个数，C（8-N-1，1）则为节点j出口分布情况个数，根据此公式可以得到新启发函数定义公式

式中：djs表示j点与s点（终点）间的距离，这一距离会对启发函数产生影响，且目标点对路径吸引力更大。概率因子的添加，使节点障碍物个数成为了节点选择的重要影响因素，即节点j附近障碍物数量越少，概率因子Pij值越大，获得的启发函数也越大，此节点的被选择概率将会大幅提升[3]。由此规划出的路径可有效避让障碍物较多区域，可为机器人救援安全性及高效性提供保障。

2.2.3  躲避特定障碍物

为避免利用蚁群算法求解时出现蚂蚁被困在半封闭障碍物中，导致有效循环参与蚂蚁数量不足引发算法运算效率降低问题，致使机器人救援时间延长而增大被困人员安全隐患。需要设定蚂蚁进入半封闭式障碍空间的条件限制，达到特定条件下，便自动解除蚂蚁循环。寻找路径蚂蚁位置坐标及目标点坐标分别为（i，j）与（S，E）时，蚂蚁跳出循环的必要条件有4个，一是i与j分别不大于S与E，（i+1，j）=0、（i，j+1）=0；二是i不大于S、j不小于E，（i+1，j）=0、（i，j-1）=0；三是i与j分别不小于S与E，（i-1，j）=0、（i，j-1）=0；四是i不小于S、j不大于E，（i-1，j）=0、（i，j+1）=0。满足这4个条件之一时，说明蚂蚁进入了半封闭障碍物中，此时应使蚂蚁跳出循环，并将蚂蚁当前所在位置的节点权值调整为0[4]。

2.2.4  选择逃生路径

由于被困人员存在个体差异，年龄、性别、性格不同的个性，对应急疏散行为的反应并不一致。男性逃生者比女性逃生者更愿意寻找火源灭火，可向此类被困者提供火源及灭火装置位置信息，引导其控制火势或降低逃生路径危险节点温度。而幼龄及老龄被困人员疏散能力弱于中青年被困者，可利用救援机器人对其实施救援。除此之外，理智型性格被困人员较情绪型、混合型性格被困人员更易于通过权衡利弊筛选逃生路径。为此，消防救援时需要规划长短不一的2种逃生路径：一是短距离逃生路径，在不超出人体耐受度的情况下，通过穿越危险点逃生；二是远距离逃生路径，避让危险点选择其他出路逃生。老人、儿童则停留在安全地带，危险区内的特殊人员，可按规划路径转移至安全位置，再等待救援。

2.3  改进蚁群算法在全局路径规划中的实现

消防救援机器人利用改进蚁群算法实施救援时，可先利用BIM图分析建筑室内布局、建筑材料，基于传感器感知获取火源位置信息，根据材料成分信息提前预测或约束火灾建筑可能出现垮塌的区域，并规划出不经过垮塌区的机器人救援路径，从而使局部路径规划难度降低，以此节约救援时间[5]。全局路径规划中，改进蚁群算法的实现要经过以下步骤：一是构建环境模型；二是提取FDS仿真数据，获取危险区一氧化碳含量及温度值；三是预处理障碍物以获得较优路径，以增大路径信息素初始值；四是初始化蚁群算法参数；五是将蚂蚁设置于起点准备实施搜索；六是选择下一节点并向禁忌表添加节点，并于路径探索后更新信息素，此步骤循环多次；七是将蚂蚁位置重新设置为起点并将禁忌表清空；八是判断迭代次数是否达到预设值，根据判断结果选择结束迭代循环或继续循环；九是基于FDS仿真数据，判断不同被困人员逃生速度与路径的适合度，路径合格应完成输出，否则应重新选择逃生节点并从障碍物预处理环节开始寻径。

3  基于改进蚁群算法的消防救援机器人路径规划仿真实验

3.1  路径规划仿真

将改进蚁群算法的参数设置为蚂蚁数目50个、迭代100次、信息素因子及启发函数因子分别为1个与5个、信息素初始值及初始挥发因子分别为1个与0.5个。路径规划仿真时，选取其他研究专家的改进蚁群算法与本文提出的改进蚁群算法进行对比，图1（a）是基于改进势场蚁群算法的机器人最优路径（虚线）及本文所提出算法的规划路径（实线）的对比图，二者最优路径长度分别是31.56 m与30.97 m，平均路径分别是31.97 m与31.43 m，而迭代次数分别是8次与9次，仿真10次达到最优路径的次数分别为9次与8次。由此可见，障碍物相同时，本文所提出的改进蚁群算法虽比迭代次数多出一个，但最短路径及平均路径更短。

圖1（b）是利用修改期望值并采用挥发系数自适应方法的改进蚁群算法规划的路径（虚线）及本文提出算法路径（实线）的对比，这2种算法的最优路径长度均为28.04 m，平均路径长度分别是30.87 m与29.73 m，迭代次数分别是19次与8次。说明复杂程度、障碍物相同条件下，本文提出的改进蚁群算法平均路径长度更短，迭代次数更少。而2种算法仿真10次达到最优路径的次数分别为2次与8次，意味着本文提出的改进蚁群算法稳定性更佳。而后继续在20 m×20 m、30 m×30 m 2种栅格环境下展开仿真，发现本文提出的攻进蚁群算法均可在较少迭代次数、良好收敛性的基础上快速找到最优路径，说明此算法在复杂环境中也较为适用。

3.2  算法性能对比

立足全局路径规划下将本文提出的改进蚁群算法，分别与传统蚁群算法及改进势场蚁群算法进行对比。在已知搭建障碍物信息的情况下，利用栅格法构建环境模型，将环境规模设定为20 m×20 m，栅格边长设定为1 m，改进蚁群算法的其他参数均与上文相同，在图2所示的3种不同栅格障碍物设置情况下进行仿真。

分析发现，在复杂度均为20 m×20 m、障碍物也一致的情况下，3种算法结果对比（详见表１），１＃栅格障碍情况下，本文改进蚁群算法的最优路径长度与改进势场蚁群算法相同，而平均路径长度、迭代次数均优于传统蚁群算法及改进势场蚁群算法。

由于最佳性能分析当中，最佳性能指标决定着算法的优化性能[6]，本文改进蚁群算法、改进势场蚁群算法与被困者位置处的优化距离均有所变短，但根据最佳性能指标分析得知，最佳性能指标数值最小，算法优越性越好，因而，本文提出的改进蚁群算法的优化性能最佳（见表2）。按照同样方法对不同栅格障碍情况下对3种算法的时间性能、鲁棒性能进行分析发现，本文所提出的改进蚁群算法的收敛速度更快、鲁棒性也更强。通过3大性能指标对比结果分析，可以得出本文提出的改进蚁群算法具有良好的优势性能，在消防救援机器人路径规划方面更为适用。

4  结束语

本文提出的改进蚁群算法，采用分类提取方式从BIM图中提取建筑空间布局及材料信息，生成机器人可识别的栅格图，并规划出最佳救援路径。通过仿真分析发现，本文提出的改进蚁群算法在最优路径寻找时具有迭代次数少、收敛性能佳的优势，且适用于复杂环境，并且最佳性能、时间性能、鲁棒性均较为优越，此算法在消防救援机器人救援路径规划方面具有较高应用价值。

参考文献：

[1] 王俊彭，宋屹峰，赵娟平，等.基于蚁群算法的人员疏散机器人路径规划方法[J].工业仪表与自动化装置，2023（4）：77-83，88.

[2] 乔佳，史艳霞，王浩陈.基于改进蚁群算法的森林火灾救援机器人三维路径规划[J].消防科学与技术，2023，42（7）：989-994.

[3] 王宏北，黄民，黄小龙，等.基于改进蚁群算法的消防机器人路径规划[J].北京信息科技大学学报（自然科学版），2021，36（4）：82-87.

[4] 王钾.基于BIM和优化蚁群算法的建筑消防疏散路径规划[D].西安：西安建筑科技大学，2020.

[5] 周鹏.基于BIM和自适应蚁群算法的建筑消防疏散研究[D].西安：西安建筑科技大学，2019.

[6] 郑家风，田思庆.基于改进蚁群算法的煤矿救援机器人全局路径规划研究[J].电脑知识与技术，2018，14（24）：171-172，184.