蚁群算法在多障碍场所疏散路径规划中的应用

张嘉琪 张言

摘要：文章将栅格蚁群算法应用于多障碍场所的人员动态疏散中，对该算法提出了一些改进方法，使其搜索效率得到了一定的提高，针对所研究对象具有多障碍物、难疏散的特点，根据火灾发生时场所环境的变化特点，对场所环境进行动态分析，规划出在最大限度保证人员安全的前提下的最短路径，使人员在紧急情况下安全快速地所找到出口，避免紧急情况下找不到出路盲目逃生，大大提高了疏散效率，减少人员伤亡。仿真模拟结果显示，该算法是解决动态疏散路径规划问题的有效方法。

关键词：安全；蚁群算法；多障碍场所；路径规划

随着建筑行业的发展，建筑物种类和结构越来越多样化，然而建筑火灾也随之发生地越来越频繁，由于火灾造成的人员伤亡和经济损失极为严重。尤其是多障碍物的公共场所，由于场所障碍物较多，人员对场所的环境也不熟悉，所以一旦发生火灾，逃生极为困难。当发生火灾的时候人员的恐慌和从众心理使得群众盲目逃生，传统疏散指示图达不到预期的疏散效果，而且火灾发生时火焰和烟气态势的发展变化，造成路径通行能力的动态变化，而目前建筑物中普遍使用的大多为固定方向式指示标志，存在着当安全出口附近发生火灾时会将人员引向危险区域的隐患。蚁群算法是受到自然界中蚂蚁觅食行为启发而提出的一种仿生进化算法。研究发现，当发生火灾时，人员逃生特性和蚁群觅食有一定的相似性，因此，根据蚁群算法对建筑空间进行网格模型划分，定义和描述建筑空间各网格的静态属性和动态属性；根据火灾报警系统提供的火警信息搜索人员疏散的最优路径，利用软件程序控制技术，实现路径优化算法和消防探测控制系统的数据传递，通过控制程序把最优路径快速规划出来，这样人们可以很直观地看到当前最优逃生路径，避免在障碍物较多的场所找不到出口，减少了盲目逃生带来的恐慌。

一、环境模型的建立

将要规划路径的区域划分成大小相同的栅格，将原本有障碍物的栅格标记为不可行区域，剩下的栅格就是正常情况下的可行区域。在可行区域定点安装温度和烟气传感器，火灾发生时，如果某区域内的温度和烟气传感器数值有任何一个超过了安全阈值，则该区域内的栅格被自动定义为障碍栅格，路径只能在可行区域内规划。

影响动态疏散的因素有现场温度、烟气浓度以及人群拥挤状况等，对这些因素加以权重分析得出每个栅格的风险值，根据风险最小的原则来规划路径。用下面的函数来确定由栅格i转移到栅格j的风险值大小

式中T、C、ρ分别表示各栅格对应的温度、危险气体浓度和人流密度，a、b、c为相应的权重系数， 表示从栅格i到栅格j的路线长度。最优疏散路径 即从当前点到出口累计风险值最小的一条路径

二、栅格蚁群算法的原理及改进

1.传统蚁群算法的原理

设要规划路径的起点为S点，目标为O点。蚂蚁从起点S出发寻找路径，只能从其所在栅格的相邻栅格中选择一个前行。第k只蚂蚁在t时刻从栅格i选择栅格j行走的概率为：

表示第k只蚂蚁在时段（t，t+1）留在路径（i，j）上的信息素，列迭代之后，蚂蚁最佳的路径上，从而使算法收敛。

2.蚁群算法的改进

对于路径规划问题，栅格蚁群算法存在可优化空间。

因为在火灾逃生中蚂蚁搜索的目标是已知的，所以可以使用目标函数启发法提高蚂蚁搜索效率，引入启发函数h（x）如下：

其中，启发因子c是一个大于0的常数，决定了蚂蚁受目标启发的程度，c越大蚂蚁受到的启发强度越大。引入该启发函数后，蚂蚁的状态转移概率变为：

改进之后在进行动态路径规划时可以减少循环次数，从而快速得到较好的路径规划结果。

三、蚁群算法的流程

设表示启发因子和信息挥发率。

第一步：初始化m、x、α、β、c、ρ、x、y等参数；

第二步：判斷本次规划是不是首次规划，如果是，将信息素初始化为常数；否则将信息素设定为上次规划保存的信息素值；

第三步：当x小于y时进入循环，否则转到第八步；

第四步：对每一只蚂蚁从起点开始按照式（7）选择下一个栅格搜索路径直到找到目标。如果没有找到目标则让其回到起点重新搜索并且失败次数加一。若失败次数累计达到最大允许失败次数z则程序结束并返回未找到路径；

第五步：对每只蚂蚁找到的路径与全局最佳路径比较，如果比全局最佳路径更好则将该路径更新全局最佳路径；

第六步：对全局最佳的路径按照式（8）更新信息素；

第七步：循环计数x加一，转到第三步；

第八步：保存本次规划时蚂蚁产生的信息素；

第九步：程序结束，将全局最佳路径作为结果输出。

四、仿真实验

为了验证栅格蚁群算法在多障碍区域的路径规划效果，选取某超市作为试验样本，

在LabVIEW2015开发环境下将实验模型的建筑平面图转换为在该环境下可用的简易地图。并在LabView2015开发环境下将算法程序按照前文所述的方法和流程编写出来。

运行该程序，在前面板添加两个标识点S和O，分别代表起点和出口，该程序规划结果如图中L1，即为从起点S到出口O的最短路径，用时60毫秒。如果在这条路径上选择一点A设置为障碍点，并重新规划路径，则该程序规划结果如图中L2，即为在避开该障碍点A的前提下，从起点S到出口O的最短路径，用时71毫秒。

五、实验结论

该仿真实验结果表明，在多障碍场所利用改进后的栅格蚁群算法规划逃生路径是安全可行的，该算法既能保证避开障碍物，也可以实时动态避开危险区域，并且在此前提下迅速规划出最短的逃生路线。

参考文献：

陈庆全.基于蚁群算法的动态人员疏散模拟[J].软件时空，2012，（10）：424-426.

段鹏飞.面向大型场馆疏散的改进多蚁群算法[J].计算机应用研究，2013，（02）：357-359.

赵容齐.基于人工势场法的机器人路径规划研究[D].山东：山东大学，2008.

王树西，吴政学.改进的Dijkstra最短路径算法及其应用研究[J].计算机科学，2012，（05）：223-228.

王荣，江东，韩惠.基于Floyd方法的最短路径算法优化算法[J].甘肃科学学报，2012，（04）：110-114.

石铁峰.改进遗传算法在移动机器人路径规划中的应用[J].计算机仿真，2011，（04）：193-195.

邱莉莉.基于改进蚁群算法的机器人路径规划[D].上海：东华大学，2015.