考虑液氧泄漏的改进A*算法及其应用*

张学锋， 贾梦成， 汤亚玲， 储岳中

(安徽工业大学 计算机科学与技术学院,安徽 马鞍山 243000)

0 引 言

当前国内工厂意外事故时有发生，其中不乏由于职工应急处置错误而造成的重大后果。由于在现实中演练成本太高，所以为更好地应对工厂突发事件，国内外公司企业不断地研发应急演练平台，通过让职工操作PC端演练平台以达到对其培训的目的。例如为应对电力系统由于设备的危险性和操作的高要求无法经常实地开展，王欢等[1]设计出一套模拟危险设备操作的应急演练系统。但该系统的任务是由指挥小组手动发布而非一套标准化任务流程，同时企业会因工作需要时常改变环境布局，因此该系统无法满足调整场景需求。国内许多大学在人员疏散仿真模拟方面一直有深入研究。在文献[2]中，张润莲等提出了基于距离与坡度的改进A*寻路算法模型，该模型的提出优化了搜索路径，降低了搜索时间；张学锋等[3]提出了基于多智能体技术的人员感知疏散模型。以上的算法改进虽提高了算法效率但未考虑路径的安全性。在危险发生时保证路径的安全性是首当其冲的,在获取寻路路径时应结合寻路算法与风险评估两种模型考虑[4]，同时将演练平台和人员疏散系统结合可以更好地应用于实际中。

针对上述问题，提出了集演练平台和人员疏散于一体的应急演练系统，在此基础之上研发了一套场景配置平台，该平台使得用户可根据自身需要对场景进行修改。传统A*算法并未考虑场景的复杂性和安全性，在应急演练系统中运用寻路算法时应考虑线路中每个路点与灾难点是否保持安全距离，同时应考虑距离与方向对启发函数的影响。为使得寻路算法更好地应用于液氧泄漏实际问题中,提出了将液氧泄漏风险模型与修改启发函数的改进A*算法相结合的方法。

1 系统架构及设计流程

该应急演练系统以Unity作为开发平台，以3DsMax作为建模软件对工厂进行建模。通过多人协同完成配置好的任务流程以达到模拟现实灾难发生后做出正确处理以使损失降到最低的目的，同时系统将改进后的A*算法应用其中，以实现规划模拟逃生路径，达到让用户掌握灾难应急处理和了解更安全逃生路线的目的。

系统通过构建多个模块与子系统来完成预案流程，达到处理灾难点的目的(图1)。该系统分为系统服务端、客户端。服务分为云数据服务和数据服务。数据服务的主要功能是解析角色登录信息，从数据库中获取预案信息、装备信息、题目信息等发送给客户端以回应客户端的请求，以及同步各角色的位置，记录每次演练的效果及成绩等。该演练系统的客户端通过多个模块的设计让系统中的角色完成已设定好的任务，从而模拟发生液氧泄漏时应做出的紧急处理，达到演练的效果。此外该应急演练系统还具备场景配置功能，用户可根据自身需求在场景配置端进行修改，修改后的场景信息以xml文件保存在服务器中，重新打开演练平台时系统自动读取该信息并覆盖原演练场景。图2为系统界面。

图1 系统框架

图2 系统界面

2 标准A*算法

20世纪60年代末，Hart和Nilsson将最为经典的A*算法提出，虽然半个世纪的时间已经过去，各项技术和科学已有了质的飞跃，但A*算法依然是最有效果的静态路网寻求最短路径的直接搜索算法，同时也是许多现实生活的科技产品中较为常用的启发式算法之一。

A*算法的原理可以用一个估价函数如式(1)所示：

f(n)=g(n)+h(n)

(1)

g(n)代表着当前所在位置与起始点之间的距离，h(n)代表的是当前所在位置与终点之间的距离，f(n)代表了对当前节点n的估价。以当前点n为中心分别计算该节点附近8个点的代价并从中选出最小代价的点，以该选中点为中心继续以上操作直至到达终点。由此操作规划出的路径即为起点与终点间的最优路径。其中距离通常采用曼哈顿距离如式(2)所示，欧式距离如式(3)所示或切比雪夫距离[5-6]如式(4)所示：

DM=|x1-xgoal|+|y1-ygoal|

(2)

(3)

DC=max{ |x1-xgoal|,|y1-ygoal| }

(4)

步骤：首先建立表并将地形信息以坐标的形式存入表中,建立close表和open表，分别存储当前节点周围已遍历的8个子节点及其估计值和已走过的节点；先将起始点存于open表中，对open表中最新加入元素的周围8个子节点遍历，并计算出每个子节点的估价值，对比close表，若该表中无加入的子节点，则将其存于close表中，如果有该点，则更新该子节点的信息；再对close表中所有元素排序，取出估价值最小的节点存于open表中。重复以上操作直至到达终点，即获得了最优路径。

3 A*算法的改进

传统的A*寻路算法仅考虑了最小网格映射中路径长度来生成最小路径，并未考虑场景的复杂性和安全性，难以应用于实际问题中，为更好地解决实际问题，需要对标准A*算法进行改进。

3.1 改进原理

在传统A*算法启发函数中，g(n)为从起始点开始沿着已计算出的最佳路径移动到点n的实际代价。对于每个点而言，沿着已计算出的路径移动，该代价函数的值是固定不变的，唯一影响候选点值的是h(n)，该函数表示的是候选点n到目标点的估计代价，当该函数越接近实际代价,路径越接近最佳路径。针对液氧泄漏的问题,不仅要考虑路径的长短而且需要考虑路径的安全性，所以对A*算法改进的思路主要有3点：第一点是该算法必须在远离泄漏点的安全区域内进行搜索；第二点是针对工厂复杂的地形，对A*算法的启发函数进行修改；第三点是为了使得启发函数中h(n)估计代价更接近于实际代价，应对启发函数进行修改。

3.2 风险模型

由于液氧的沸点为-183 ℃，所以液氧泄漏最直接的危害是人体碰触会发生冻伤；其次当液氧接触到静电火花时易发生爆炸；当空气中氧气浓度高于23.5%时，为富氧状态，此时易产生火灾，当氧气浓度高于40%时，人体吸入后引发氧中毒的可能性较大[7]。所以在灾难发生时，通过寻路算法找寻最佳逃生路径时应避开这些区域。爆破能力E计算公式如式(5)所示：

Ew=[(H1-H2)-(S1-S2)T1]W

(5)

它可计算泄漏发生爆炸时产生的能量。其中Ew表示以kJ为单位的饱和水的爆破能量；H1和H2分别表示爆炸前液化液体的焓以及大气压下饱和液体的焓，其单位都是kJ/kg；液氧的H1与H2分别为 -79.84 kJ/kg和-133.69 kJ/kg；S1与S2表示的是爆炸前液化液体的熵以及大气压下饱和液体的熵,单位是kJ/(kg·K)；液氧的S1和S2分别为3.44 kJ/(kg·K)与2.94 kJ/(kg·K)[8];T1表示的是介质在大气压下的沸点，单位为K；W是饱和液体质量，单位为kg。得出Ew的值后，即可得出TNT当量q(kg)，如式(6)所示：

q=E/qTNT

(6)

液氧槽产生爆炸时的效果与TNT当量q的关系如式(7)所示：

R=r/q1/3

(7)

其中，R表示冲击波大小(ΔP),表1列出了冲击波大小对人体的伤害程度。据此，计算该厂区密度为1.14×103kg/m2的液氧储槽发生泄漏产生爆炸时的安全距离。通过查阅相关资料可知，对于液氧储槽发生泄漏后氧气浓度高于40%的区域为30 m内的地方[10]。

表1 冲击波对人体伤害程度

3.3 改进算法启发函数

灾难发生时,绝对安全区域是一个范围而非一个定点，所以最终人物移动到设定的目标点附近即可，因此对于不同路段与时间段人物移动的目的性有细微差别。在人物远离绝对安全区域前寻路的最主要目的是准确朝着目标点的方向移动，而在离目标点较近时寻路的主要目的是迅速移动到绝对安全点附近。由此对传统的A*寻路算法进行修改，在其中加入权重因子W，从而公式变为

f(n)=g(n)+W*h(n)

加入矢量因子的目的在于可以根据离绝对安全区域的距离来自行增加或减少向目标节点收敛的速度[11-12]。W=0时，该方法变为Dijkstra算法，Dijkstra算法为宽度优先的盲目搜索算法，并不适用于场景较大的系统；W<1时，估计值h(n)与实际值相差太远，所以采用的W≥1，增大当前所在位置与终点之间的距离对f(n)的影响。

传统A*算法主要针对的是简单场景的寻路，在3D复杂场景中需要对启发函数进行修改，加入方向因素同时权衡距离与方向的影响，该改动会使得相邻的几个节点估计代价相同的几率更小，对减少非必要的回溯有明显效果，从而提高搜索的精度也加快了搜索进程。修改后的公式如式(8)所示：

h(n)=W1*α(ni,nj)+W2*d(nj,ngoal)

(8)

α(ni,nj)表示的是当前点与周围候选点的连线L1与起始点和目标点的连线L2之间的夹角值；d(nj,ngoal)表示的是候选点与目标点的距离值；W1与W2分别为角度与距离的权重，W1取值范围为[0.35，0.45)，W2的取值范围是(0.55，0.65][13]。在复杂地形中引入权重系数的优势在于权衡距离信息与方向信息, 加快搜索进程。

综上，修改后的A*启发函数如式(9)所示：

f(n)=g(n)+W(W1*α(ni,nj)+

(1-W1)*d(nj,ngoal))

(9)

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

4 实验结果对比

在该应急演练系统中，利用Unity3D自身所携带的坐标系统并设Y坐标为0，将整个地形信息以及障碍物信息以点坐标的形式存入数组中，再根据A*算法和A*改进算法的启发函数进行实验。其中障碍物被白色方框围起来以方便观察，火焰地方即为泄漏点。

根据以上所写内容，进行对比实验。实验分别为根据实际环境标出障碍物条件下的标准A*算法的寻路路线(图4)；同样具备障碍物条件下不考虑风险模型A*改进算法的寻路路线(图5)和考虑风险模型的A*改进算法的寻路路线(图6)。

图3 改进A*算法流程

图4 标准A*算法寻路路径

图5 不考虑风险模型的A*改进算法寻路路径

图6 考虑风险模型的A*改进算法寻路路径

由实验结果表明：标准A*算法获得的逃生路径(图4)距离灾难发生点的最近距离为18.9 m，逃生路径节点中处于爆炸冲击波和液氧伤害危险的伤害范围的节点为79个(表2)。修改A*算法的启发函数后获得的寻路路径相较于标准A*算法所获得的路径在节点数上有所减少，但路径中仍有较多路点处于危险区内。从实验结果可以看出，改进A*算法获得的寻路路线(图6)完美避开危险区域，逃生路径中没有处于危险区域内的节点，且距离泄漏点最近的距离为32.3 m(表2)。

表2 处于液氧泄漏危险范围内的节点个数

当灾难发生时为了保护场内员工的生命安全，应对标准寻路算法做出如上改进，使得可以规划出更合理更安全的路线以便员工迅速安全的到达指定地点。同时，对A*启发函数的修改后获得的路径相对于仅考虑风险模型的A*算法获得的路径回溯更快。