基于节点安全预测的火场撤离路径规划

安亚娟，李德敏，许晓天，张谦益

（东华大学 信息科学与技术学院，上海 201620）

基于节点安全预测的火场撤离路径规划

安亚娟，李德敏，许晓天，张谦益

（东华大学 信息科学与技术学院，上海 201620）

火场烟雾弥漫、能见度低，消防队员很难准确定位并找寻到合适的撤离路径。文中使用人机协作在火场中建立动态三角网基础上，以网络节点为参考点为消防员规划撤离路线。该方案使用基于相似函数的证据理论对火场中各节点采集的烟雾浓度、温度、氧气浓度进行数据融合，并确定节点位置的安全等级；引入预测机制，可以预测短时间内前进路径中节点位置的安全等级的变化。根据安全等级变化，剔除网络中危险节点，使用基于路程换算的A⋆算法计算实时最短的安全路径。通过数据分析表明，该方案能更好的适应火场环境多变的特点。

动态三角网；撤离路径规划；信息预测；规避危险节点

随着建筑物的规模越来越大，内部结构越来越复杂，消防员面临的救援形势也越来越危险。当消防员深入火灾现场完成搜救抢险任务后，火势通常会恶化，由于火场烟雾弥漫，能见度低，消防队员很难准确定位并找寻到合适的撤离路径。为了解决这一问题，我们提出了一种基于机器人节点安全预测算法，动态选择安全路径，最后进行计算分析性能，可以看出该算法在动态路径的优越性。

为了给消防员选择最安全的撤离路径，Marina Yusoff[1]对近年来有关紧急撤离的数学算法和模型进行了评价总结。其中最经典的是使用Dijkstra进行最短路径撤离，但是在未知环境里面此法有一定的缺陷。文献[2]将蚁群优化算法应用到紧急撤离的最短路径选择中。文献[3]结合Dijkstra算法进行路径选择建立了消防疏散系统。有学者提出了一种改进的遗传算法[4]，用来解决路径规划问题。文献[5-6]提出基于多目标优化模型的城市疏散计划然而， 上述方法多数只采取路径长度最短作为衡量最优路径的单一指标。Zhang[7]考虑了节点的安全性，但是未考虑火场动态性，未对节点安全进行动态预测，在撤离时高危节点可能会被规划在所选路线中，消防员就会进入危险节点，不仅会威胁消防员的安全，还会增加了救援时间。

本文的创新之处主要在于根据火场实时信息对对未来短时内路径的安全性进行预测，并运用采集的实时数据和路径，预测消防员的撤离路径。这样保证了预测的实时性和有效性。路径安全性预测可提前排除不安全的撤离路径，使得消防员撤离更有效率。对采集的火场信息进行融合和预测路径安全，可保证每个周期内计算所得安全路径的正确性。从而选择出安全有效的最短路径。

1 基于节点安全预测路径规划

1.1 动态三角网

大型仓库、超市在火灾发生时，部分通信设备可能会失效，消防员不能及时的了解现场信息，尤其是获取危险区域的信息，Ulf Witkowski构建了由机器人组建的动态三角网络模型，该方法的主要目的是最大的覆盖方式部署机器人从而为火场中的救援机器人及消防员提供了稳固的通信。假设某时刻机器人组建的部分救援网络在平面建筑中的分布如图1所示。

图1 救援网络模型Fig. 1 Rescue network model

Zhang规定消防员在撤离过程中必须是往出口方向移动的，忽略了包围式火势情况下消防员无法前进的情况。本文使用基于路程换算的A*算法对有效节点进行最短路径选择，避免了单纯使用最短路径情况下消防员进入危险节点。

1.2 节点安全度的评价和数据融合

选取温度，烟雾浓度和氧气浓度3个较能体现火场状态的参量作为火场安全度的评价因素。依据专家系统得到的各参量在不同范围内的环境安全状况。运用基于相似函数的证据理论的方式融合温度、烟雾浓度、氧气浓度3类不同的传感器信息。依据融合结果和在3种参数的各种浓度下人类所能承受的极限，把节点的安全等级划分为I、II、III 3个等级，分别代表环境安全、中度危险、高风险3个状态。

表1 参数概率赋值表Tab.1 Asignment table of parameter probability

假设在某一特定时间，传感器收集到的信息是：烟雾浓度1 200 ppm，温度400 ℃，氧气浓度10%。Si代表不同类型的传感器，E(i)代表不同级别的环境状况，各概率分布如下表1所示,我们运用基于相似函数的证据理论的方式融合3类不同的传感器信息。

我们对E(1), E(2) , E(3)3个分配函数进行融合计算:

结果如表2所示：

表2 特定时间的概率分布Tab.2 Probability distribution of specif i c time

根据表3最终融合结果H2显示，环境安全，不确定，高风险的概率分别为0.146 2、0.020 9、0.832 9。

表3 信息融合结果Tab.3 Result of the information fusion

基于相似函数的证据理论的最大可信度原则，取max{E(1)，E(2)，E(3)} ，可判定环境态势等级为III，为高风险节点，可确定该节点是危险节点，消防员必须避开此节点。通过信息融合，确定各目的节点的安全等级，从而为路径选择做好准备。

2 撤离路径节点位置安全预测算法

在火场环境中，高温、浓烟、缺氧等因素均会威胁到消防员的安全。在危险环境下消防员的前进速度会有很大限制，Pender等人据经验丰富的消防员粗略测算出爬行速度为每分钟12 m[8]。因此，必须考虑火场信息的实时性获取，并对所获信息进行分析，从而预测出消防员到达相应节点时此节点的安全情况。

首先以温度为例，计算出消防员到达某一节点i时温度。首先对已选路径的每个节点的过去5分钟温度进行分析（采样周期Δt=5 s），文献[9]中温度的变化具有连续性，而传感器所得数据是离散的，故预测消防员沿某一路径起点， 到达时刻的节点温度的具体计算方法如下：

对烟雾浓度和氧气浓度的预测也是采用此方法。

3 撤离路径预测算法的结果比较

对于图1中,若火源在障碍物1与障碍物2附近，则附近节点便是危险区域，若使用最短路径规划，则选择c→g→j→o→s 。节点Ri可以用(Xi, Yi)坐标定义，对图1中网络节点传感器数据进行数据融合，计算得到节点d,e,f,i,j,m,n处于危险区域，依据安全等级，消防员必须避开这些节点，上述最短路径c→g→j→o→s失效。

本文撤离路径的选择算法流程图如图2所示。

图2 撤离路径规划策略流程图Fig. 2 Flow chart of evacuation path planning strategy

A*算法在搜索过程中与Dijkstra算法相比，增加了启发函数H(x)部分，大大缩短了寻找时间。此处使用基于路程换算的A*算法快速的计算出最短路径，启发函数F(x)=G(x)+H(x)，其中G(x)表示已经经过的路径长度，H(x)为评估值即下一可选结点到终点的笛卡尔距离。

G0表示当前经过的路径长度, G'表示下一路段的长度， v'为消防员标准理想速度0.5 m/s，v为消防员在节点间实际速度，相当于同比放大了G'，在算法计算时认为通行速度越慢等于距离越长。使用Java计算仿真，其中节点的颜色越深节点危险系数越大，此时求得路径❶如图3。

图3 初始选择路径Fig. 3 Initial selection path

此时预测在消防员到达节点g时将处于危险区域，必须重新选择路径，讲节点g从有效网络节点中删除，再次运行A*算法，得到路径❷：c→1→2→k→p →t →w→z。

根据上述策略描述，火势是实时变化的，路径规划必须动态规划才能保证消防员快速安全的撤离。因此消防员在前进3个节点后重新选择路径得到最终的路径如图4。

图4 本文算法最终选择路径Fig. 4 Final selection path of proposed algorithm

图5 矩阵迭代算法选择路径Fig. 5 Selection path of matrix iteration algorithm

此时针对同一火场情况，消防员从相同起点就Zhang[7]所提出基于安全的矩阵迭代法与本文方法进行比较如表4，图5表示基于矩阵迭代法选择路径，图4表示基于本文方法选择路径。

表4 不同撤离方法对比Tab.4 Different evacuation method comparison

从以上结果可以看出，矩阵迭代法同样可以选择安全路径，但是缺乏预测功能导致消防员进入危险节点，不但会威胁到消防员人身安全，且需要不断的从危险节点转移到安全节点，从而增加了撤离时间降低了效率。而本文算法则在选择最短路径的同时考虑火场变换动态预测安全路径，使消防员以最短时间撤离。

4 结束语

文中提出了一种基于动态三角网的消防员撤离路径规划的优化方法。此处机器人携带有传感器，具有从消防员难以达到的未知区域获取实时信息的优势。假设在构架动态三角网的火场中只有一个出口，需要进一步研究的有多出口的火场撤离路径规划，同时此模型中的机器人是假设固定的，现实情况中机器人有可能跟随消防员移动从而获得实时数据，因此下一步研究方向为基于移动的机器人的消防员火场撤离路径规划。

[1] Yusoff M, Optimization Approaches for Ma-croscopic Emergency Evacuation Planning[J]. A Survey, Information Technology,2010(3):1-7.

[2] YAO Kun, CHEN Qing-quan. Applying the Ant Colony Algorithm to the Optimization of Emerbency Response Search Paths[C].CICTP,2012.

[3] ZONG Xin-lu ,Multi-objective Ant Colony Optimization Model for Emergency Evacuation[C]//International Conference on Natural Computation, 2010.

[4] WANG Tian-YU, I. The Application of the Shortest Path Algorithm in the Evacuation System[C]//International Conference of Information Technology, Computer Engineering and Management Sciences,2011.

[5] LI Qiu-ping.Multi-objective Ev-acuation Route Assignment Model Based on Genetic Algorithm[C]//Geoinformatics,18th International Conference, 2010.

[6] Joao Coutinho-Rodrigues,Lino Tralhao,Luís Alaada- Almeida,Solving a location-routing problem with a multi-objective approach:the design of urban evacuation plans[J]. Journal of Transport Geography,2012(22): 206-218.

[7] ZHANG Qian-yi.AN.Evacuat-ion Path Selection for Firefighters Based on Dynamic Triangular Network Model [J].International Journal of Advanced Research in Artificial Intelligence, 2012,1(7):1-6.

[8] PENDERS. A Robot swarm assisting a human fire-fighter[J]. Advanced Robotics,2011, 25(1-2):93-117.

[9] Joshi V.Analyzing electrical effects of RTA-driven local anneal temperature variation[C]//Proceedings of the 2010 Asia and South Pacific Design Automation Conference,2010.

An evacuation path planning based on dynamic triangular network model

AN Ya-juan, LI De-min, XU Xiao-tian, ZHANG Qian-yi
（College of Information Science and Technology, Donghua University, Shanghai 201620, China）

It’s difficult for the firefighters to position accurately when find the right evacuation path cause the smoke,low visibility. Dynamic triangulation network is generated by Robot and firefighter and used to help compute evacuation routed. Evidence theory based on similarity function is used to determine the node security levels after fusing the firedata such as smoke concentration, temperature, oxygen concentration. Prediction mechanism is introduced in order to predict the changes of the security level of node position in the forward path in a short period of time, then risk nodes in network are processed dynamically A* algorithm based on distance conversion is used periodically to calculation the shortest and safest path in real time. By computing and data analyzing, It can adapt to the characteristics of the fire environment changes more flexible.

dynamic triangulation network; evacuated route planning; Information prediction; avoiding dangerous node

TN913

A

1674-6236(2014)03-0059-03

2013–06–20 稿件编号：201306126

国家自然科学基金(71171045)

安亚娟(1988—)，女，河南濮阳人，硕士研究生。研究方向：无线自组网及其应用。