一种基于多出口选择A*算法求解最短路径的人群疏散动态路径规划方法

摘要

本发明提出一种基于多出口选择A*算法求解最短路径的人群疏散动态路径规划方法，从起点和终点进行双向搜索，选择新扩展节点，结合人员疏散流体模型，对扩展节点进行评价，当扩展节点相同时视为规划完成，再对完成规划的路线进行优先级排序；进行排队或拥堵判定，对不拥堵且非最优的线路进行再次分配，完成路径规划；本发明针对现有的算法改良，遵守海事组织相关导则性要求并且考虑群体路径以及疏散环境的复杂性，将不同疏散路线分为不同优先级的分配策略，使得地图节点信息矩阵得以简化，极大程度提高了规划的效率。

说明书

技术领域

本发明属于人群疏散仿真领域，具体地，涉及一种基于多出口选择A*算法求解最短路径的人群疏散动态路径规划方法。

背景技术

随着我国海洋事业的蓬勃发展，海洋平台开发水深越来越深，海洋平台的尺寸也越来越大，这就对海洋平台的安全性提出了更高的要求。海洋平台一旦发生火灾，烟气将迅速蔓延威胁控制室、储油舱室等要害部位，在很短的时间里就会对人员逃生构成威胁。因此，在海洋平台发生火灾时，人员安全有序疏散是减少伤亡的关键环节。

传统海上平台的疏散方式原始，依靠导识板和管理人员进行疏散。疏散人员难以直观了解人员的初始位置与各场景情况，无法获得实时最优撤离路线，疏散效率低。

如何快速规划出安全，合理，通畅的疏散路线成为了当前疏散撤离系统的主要难题，目前人员疏散路径规划方法没有形成统一的行业内标准，尤其是对于多出口的环境下的出口选择问题，如果在出口选择上一开始就是错误的，那么生成的疏散路径一定是不合理的。

发明内容

针对研究现有的船舶环境下的人员疏散路径算法，部分仅将最短路径作为唯一路径评判标准，并且在路径的多样性上有着很少的变化；部分研究依据陆上封闭环境下的人员疏散算法进行改良，综合来说，对船舶环境下的人员疏散路径规划算法研究具有片面性，尚未将海事组织相关导则性要求，为了解决上述问题，本发明考虑多出口封闭空间人员疏散的复杂性，提出一种基于多出口选择A*算法求解最短路径的人群疏散动态路径规划方法。

本发明是通过以下方案实现的：

一种基于多出口选择A*算法求解最短路径的人群疏散动态路径规划方法：

所述方法具体包括以下步骤：

步骤1：从起点进行搜索；从起点开始规划单条路线向着终点扩展；

步骤2：根据已知的地图信息，在从起点开始规划的路线上，通过距离函数选择距起点近的地图节点作为扩展节点；再通过距扩展节点和可选终点之和来选择新扩展节点；

步骤3：结合人员疏散流体模型，通过插值法拟合成分段函数进行状态统计计算，并根据未分配人员的状态进行路况状态统计；

步骤4：在路线状态统计中，判断扩展节点是否可以继续扩展，若不能扩展则返回步骤1；能继续扩展进行步骤5；

步骤5：在搜索过程中，将选择的扩展节点加入评价函数中，并存储扩展节点信息，当产生的某个节点为满足单出口条件的节点时，视为初次搜索结束；之后将另一可选择出口项设置为0，进行传统A*算法搜索，最终得到路线。

步骤6：通过正常通行时间与排队通行时间的差值比率对完成规划的路线进行优先级排序；所述优先级包括最优，次优和次级；

再结合人员疏散流体模型，根据达到时间与排队通行时间的大小对排队或拥堵进行判定，当判定失败时返回步骤2，判定成功时进行步骤7；

步骤7：当人员处于次优或次级路线时，根据人员比率进行再次分配，接入最优或次优路线，判断是否满足约束条件，若不满足则返回步骤6，若满足条件则完成路径规划。

进一步地，

在所述人员疏散流体模型中，通过线性插值法得到计算公式，其中人员在走廊和梯道中的密度D的取值范围为0到3.5，单位为人/m

则走廊中人员规定流量F

走廊中人员流速S的计算公式为：

梯道下行时人员流速S的计算公式为：

梯道上行时人员流速S的计算公式为：

则根据走廊宽度与人员规定流量可计算人员实际流量F

F

其中W

转移节点的流量计算公式为：

∑F

其中，∑F

进一步地，

所述评价函数的计算公式为：

f(n)＝g(n)+h(n) (6)

g(n)为从起始点s到当前节点i的实际距离代价：g(n)＝dis(s，i)；

h(n)为从当前节点i到可选择出口节点的预估代价：h(n)＝dis(i，t

其中dis()表示距离函数，t

进一步地，所述人员排队判定的计算公式为：

其中，i为人员所在的地图节点，j为判定为需要排队的节点，S

所述人员拥堵判定为：

统计每条路线的所分配的人数p，每条路线的长度L，计算出每条路线单人的行进时间T

当T

每条路线在人数p条件下的行进时间T

T

其中t

进一步地，

所述约束条件为dis(i，k)＜σT

其中i为当前人员所在地图节点，k为优化过程中在路线中选择的接入点，

σ为可选择路径所用时间所占原路线时间的百分比，S

百分比σ的计算公式为：

本发明有益效果

本发明与已有其它方法相比，本发明采用A*算法的计算规则，通过增添多出口，以及路线评级拼接的方式，增添了路径的多样性，加快缩短了规划距离。同时结合船舶人员疏散流体模型，根据时间差值，距离差值来对地图节点进行筛选，使得地图节点信息矩阵得以简化，极大程度提高了规划的效率。

附图说明

图1为本发明实例的多出口A*方法流程图，

图2为本发明实例的路线优化流程图。

具体实施方式

下面将结合本发明实施例中的附图对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例；基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

结合图1和图2，

一种基于多出口选择A*算法求解最短路径的人群疏散动态路径规划方法：

所述方法具体包括以下步骤：

步骤1：从起点进行搜索；从起点开始规划单条路线向着终点扩展；人员起始点对可选择的两个集合站目标点进行搜索

步骤2：根据已知的地图信息，在从起点开始规划的路线上，通过距离函数选择距起点近的地图节点作为扩展节点；再通过距扩展节点和可选终点之和来选择新扩展节点；

步骤3：结合人员疏散流体模型，通过插值法拟合成分段函数进行状态统计计算，并根据未分配人员的状态进行路况状态统计；据人员疏散流体模型，对MSC.1533准则中的表格数据，通过插值法拟合成分段函数进行状态统计计算

步骤4：根据人员疏散模型特点，生成A*算法矩阵，人员搜索考虑多个集合站进行搜索，为路径规划增添了多样性；在路线状态统计中，判断扩展节点是否可以继续扩展，若不能扩展则返回步骤1；能继续扩展进行步骤5；

步骤5：在搜索过程中，将选择的扩展节点加入评价函数中，并存储扩展节点信息，当产生的某个节点为满足单出口条件的节点时，视为初次搜索结束；之后将另一可选择出口项设置为0，进行传统A*算法搜索，最终得到路线，将该人员路径规划信息进行保存，并将其作为从疏散节点扩展出的完整途径，当有其他人员节点扩展节点与该路径重合时，可直接进行调用；

步骤6：通过正常通行时间与排队通行时间的差值比率对完成规划的路线进行优先级排序；所述优先级包括最优，次优和次级；

再结合人员疏散流体模型，根据达到时间与排队通行时间的大小对排队或拥堵进行判定，当判定失败时返回步骤2，判定成功时进行步骤7；

步骤7：当人员处于次优或次级路线时，根据人员比率进行再次分配，接入最优或次优路线，在正常通行时间内可移动的范围限度，进行点的搜索，提高搜索效率；判断是否满足约束条件，若不满足则返回步骤6，若满足条件则完成路径规划。

在所述人员疏散流体模型中，通过线性插值法得到计算公式，其中人员在走廊和梯道中的密度D的取值范围为0到3.5，单位为人/m

MSC.1533准则初始规定流量和初始人员流速作为初始密度的函数

MSC.1533准则规定流量和人员流速

则走廊中人员规定流量F

走廊中人员流速S的计算公式为：

梯道下行时人员流速S的计算公式为：

梯道上行时人员流速S的计算公式为：

则根据走廊宽度与人员规定流量可计算人员实际流量F

F

其中W

转移节点的流量计算公式为：

∑F

其中，∑F

所述评价函数的计算公式为：

f(n)＝g(n)+h(n) (6)

g(n)为从起始点s到当前节点i的实际距离代价：g(n)＝dis(s，i)；

h(n)为从当前节点i到可选择出口节点的预估代价：h(n)＝dis(i，t

其中dis()表示距离函数，t

所述单出口条件判定为：

f(x)为出口选择函数，其物理意义为在两个出口距离选择上，其距离差值与当前最短出口距离的比值。η为出口判定因子，选择范围通常在20％到50％，出口判定因子越大，出口选择条件越粗糙，数据量越小。

同时，在选择该出口节点后，还应判断出口节点的剩余容量是否还存在空缺，可以继续接收人员，所以在确定最近出口距离后还应对出口节点容量进行条件判断，其判断过程如下：

S为当前出口节点面积或撤离设备面积，p为当前节点所规定的最小人均占有面积，N为当前节点或撤离设备的最大人数容量，在未进行设定时，可根据上式计算，

所述人员排队判定的计算公式为：

其中，i为人员所在的地图节点，j为判定为需要排队的节点，S

所述人员拥堵判定为：

统计每条路线的所分配的人数p，每条路线的长度L，计算出每条路线单人的行进时间T

当T

每条路线在人数p条件下的行进时间T

T

其中t

所述约束条件为dis(i，k)＜σT

其中i为当前人员所在地图节点，k为优化过程中在路线中选择的接入点，

σ为可选择路径所用时间所占原路线时间的百分比，S

百分比σ的计算公式为：

以上对本发明所提出的一种基于多出口选择A*算法求解最短路径的人群疏散动态路径规划方法，进行了详细介绍，对本发明的原理及实施方式进行了阐述，以上实施例的说明只是用于帮助理解本发明的方法及其核心思想；同时，对于本领域的一般技术人员，依据本发明的思想，在具体实施方式及应用范围上均会有改变之处，综上所述，本说明书内容不应理解为对本发明的限制。