基于虚拟节点的远洋客船人员应急疏散路径规划算法

1.本发明涉及一种基于虚拟节点的远洋客船人员应急疏散路径规划算法，属于安全科学领域。


背景技术：

2.客船由于乘客密度大且类型复杂等原因，发生事故后的人员死亡率高于其他船舶。同时由于客船相对独立封闭的特殊工作环境，导致事故发生时往往很难及时得到外界的救援，即使在有外来船只前来参与救援的情况下，水上进行救援工作也比陆地上的救援工作更加困难。因此，在船舶遭遇事故之初时，让所有乘客快速集合并登上救生艇，对于提高船上人员的生存率具有重要的作用。路径规划技术作为运动规划领域的重要技术之一，在很多领域都有广泛的应用。将路径规划技术应用于船舶疏散领域，可以在面对突发的状况时，快速生成疏散路径，引导乘客进行快速的疏散，保证乘客的安全，能够对救援疏散过程中的人员疏散提供指引，提高乘客疏散效率。
3.现有路径规划可分为传统算法如a*算法、d*算法、人工势场法、随机搜索树算法等和群体智能优化算法如蚁群算法、人工蜂群算法、粒子群算法、遗传算法、萤火虫算法等，但在行人导航领域，现有算法主要适用于室外空旷场景的路径规划，当应用于船舶疏散场景时，传统算法虽然规划速度快，但无法适应疏散场景中动态的环境和人员特征；而群体智能优化算法虽然能在一定程度上反应场景中的动态因素，但算法的复杂度较高，在全局的最优路径输出质量上较差。因此，在疏散问题中，综合考虑全局与局部的算法仍待进一步研究。
4.通过对现有规划算法和客船环境的分析，本发明基于客船对称式多出口的环境结构，提出了一种基于虚拟节点的远洋客船人员应急疏散路径规划算法，在原本的地图节点网络的基础上引入虚拟节点，将该节点与各出口进行连接，以虚拟节点为目标节点，各出口为中间节点，展开算法搜索，从而避免算法对出口的多次展开，提高算法效率。在此基础上针对人员分布不均的问题，对虚拟节点进行动态更新，均衡分配人员到各出口减缓出口拥挤情况。最后构建了基于引导路径的社会力模型，模拟人群的疏散过程，动态的反应人员疏散的轨迹，有效地对疏散进行指导。


技术实现要素：

5.本发明提供了一种基于虚拟节点的远洋客船人员应急疏散路径规划算法，主要解决客船疏散过程中多个出口情况下的人员出口均衡分配以及有序疏散过程的模拟问题。通过疏散规划算法合理将客船人员合理分配到各出口，将算法规划出的路径输入疏散模型中对模拟人员疏散过程，从而完成对疏散过程的指导。
6.本发明的目的是这样实现的：步骤如下：
7.步骤一：获取疏散连通图：采集客船相关数据构建客船结构地图，对船舶结构地图进行简化处理，提取结构图中的各房间中心位置、出口位置、走廊转角、逃离出口的位置以
及部分可行空间内的可行区域节点，构建连通图；
8.步骤二：构建加入等距虚拟目标节点的疏散网络拓扑图：以连通图为基础，通过各出口的位置计算得出虚拟节点位置，将虚拟节点加入到连通网络中，建立船舶的疏散网络拓扑图；
9.步骤三：初始化乘客位置，将乘客位置接入疏散网络拓扑图；
10.步骤四：在疏散网络拓扑图的基础上，以乘客初始位置为起始点，虚拟目标节点作为规划终点，采用基于虚拟节点网络的a*算法进行路径搜索，获取当前乘客的疏散路径；
11.步骤五：判断全体乘客是否完成规划，若存在尚未规划的乘客，则根据当前乘客选择的出口位置，动态地更新虚拟节点位置，开始下一个乘客的规划过程，重复步骤三-五，直到完成所有乘客的规划任务，输出所有乘客的疏散路径；
12.步骤六：构建基于路径引导的社会力模型，将规划算法输出的所有疏散路径输入到社会力模型中，以规划算法输出的路径中的各个点作为模型中疏散个体的驱动点运行模型，输出最终的动态疏散路径。
13.本发明还包括这样一些结构特征：
14.1.(1)虚拟节点网络构建
15.在存在多个出口时，若对每个出口都进行一次出口展开会造成规划效率的低下，故设计一个等距虚拟节点将多出口问题转化为对虚拟节点的搜索过程。构建加入等距虚拟目标节点的疏散网络拓扑图：
16.虚拟节点是一种模拟的空间节点，所计算出来的位置与实际空间的空间特性无直接关系，是为了减少算法的多次展开而存在设计的。为了不影响实际规划路径的最终结果，该节点需存在如下特性：该节点只与最终的疏散出口连通，与其余的节点均不存在连通关系；该节点虽然参与路径搜索的过程，但不在最终的路径节点中进行输出；该节点到各个出口的初始代价成本是一致的。
17.针对疏散出口位置分布较为平均，其初始虚拟节点的计算方法可用如下公式计算：
[0018][0019]
其中，[x,y]表示虚拟节点的位置，goal表示出口节点位置，n表示出口总数。
[0020]
(2)疏散搜索算法展开
[0021]
初始化乘客位置，将乘客位置接入连通网络，在疏散网络拓扑图的基础上，以乘客初始位置为起始点，虚拟目标节点作为规划终点，采用a*算法以进行路径搜索，直到所有乘客规划结束。
[0022]
在该过程中采用原始a*算法的代价值进行节点扩展，会造成无用节点的过度搜索，故当以虚拟节点作为目标进行节点扩展时，需要对目标节点的搜索采用负激励，采用扩展节点到虚拟节点距离的负数作为节点扩展的代价值，代价值的计算公式如下所示：
[0023]
hv(n)＝l-h(n)
[0024]
其中，h(n)表示中间节点到虚拟节点的直线距离，l为一个相对合适的正值避免代价值为负数。
[0025]
2.步骤五中的动态更新方式具体包括：
[0026]
当乘客数量增多且各个区域乘客密度不相等的情况下，会造成个别出口的拥堵情况，针对各区域乘客密度不相同的情况引入均衡调整权重，当乘客到达一个出口时，调整该出口的一个权重，同时更新虚拟节点的位置，从而改变虚拟节点到各个出口的代价，使乘客在同等距离代价的情况下选择人员数量较少的出口，从而达到均衡人员分配的情况。
[0027]
初始位置虚拟节点到各个出口的距离代价均相等，当有人员从出口逃离时，虚拟节点将以靠近该出口的方式进行位置更新，从而增大到虚拟节点的代价值。为保证虚拟节点更新过后对其它出口的规划过程的影响尽可能小，采用虚拟节点与出口连线的反向延长线进行位置的更新，虚拟节点的位置更新方程为：
[0028][0029]
其中：l表示正向延长的距离，该距离由地图大小与人员数量共同决定，k表示连线之间的斜率，(x0,y0)表示原本的虚拟节点位置，(x
goal
,y
goal
)表示上一次规划所选择出口的位置。
[0030]
3.步骤六中的社会力模型构建具体包括：
[0031]
(1)基础模型构建
[0032]
社会力模型将个体在疏散过程中的决策行为通过力的方式来表达，将个体的心理活动采用数学建模进行定量描述，模型方程如下：
[0033][0034]
其中，表示个体自身驱动力，表示人与环境之间的互相作用力，表示人与人之间的互相作用力。
[0035][0036]
其中，τi表示个体i的步长反应时间，即行人的运动状态发生改变的所花费的时间。表示个体i在t时刻的实际运动速度大小和方向。表示个体在无外界干扰的情况下向目标点前进的期望速度。表示个体i在t时刻在期望方向的单位矢量。
[0037][0038][0039]
其中，aiexp[(r
ij-d
ij
)/bi]n
ij
表示个体与周围其他个体保持一段距离的心理作用力，ai表示作用强度系数，bi表示斥力范围系数，均为常量；
[0040]
k1g(r
ij-d
ij
)n
ij
表示个体与个体之间的挤压力，k1表示挤压系数，r
ij
表示个体i和个体j之间的距离，n
ij
表示由个体i到个体j的标准化矢量，与t
ij
垂直，t
ij
表示切线方向与n
ij
垂直，d
ij
表示两个个体之间的圆心距离；表示个体与个体之间的滑动摩擦
力，k2表示摩擦系数。
[0041][0042]
其中，d
iw
表示个体i与障碍物w之间的最短距离；n
iw
表示由障碍物w到行人i质心的单位向量；t
iw
为行人与障碍物接触时的摩擦方向的单位向量。
[0043]
(2)加入规划引导
[0044]
1)地图架构
[0045]
路径规划采用的是实际地图提取出来的路径网络作为规划的基础，而疏散模型采用的是实际的连续地图作为显示的基础。所以需要将地图抽象为两个层次：
[0046]
第一层为路径规划地图层，表示为map1(x,y)。该层是由可行路径构成的拓扑网络，包括各类关键节点和和节点之间的可通行路径段，主要用于路径规划过程中路径搜索的数据基础，不在可视化图层中进行显示。
[0047]
第二层为疏散模型演示层，表示为map2(x,y)。该层为一个连续的地图，主要记录实际疏散场景的环境信息如环境的空间结构、事故发生地点、出口位置和人员的位置信息等，主要用于显示人员疏散的实际位置和疏散场景的环境信息。
[0048]
2)节点转换
[0049]
原本的模型采取的是单对单的关键节点的引导，人员在引导过程中所选取的节点是唯一的，而路径规划输出的路径一般存在多个节点，传统模型在多个中间节点的引导转换时，容易出现速度的剧烈变化，需要对个体路径引导方式进行改进，在路径节点之间加入转换，使其平滑过渡每个中间节点。该过程分为以下两个部分：
[0050]
加入引导点转换判断：当人员从当前位置移动到引导点时，若当前位置与当前引导点的距离小于某一阈值，则转换到下一个引导点，持续该过程直到当前节点为最后的路径引导节点，当前节点为最后的路径节点时，跳过转换判断，达到目标节点时结束判断。
[0051]
引导方程改进：当引导点变为多个时，若采用原本的驱动方程会在各个引导点转换时出现速度突变等情况，通过加入多个中间引导点减缓速度突变的方法极大的提高了算法和模型的复杂度。故本发明采用对引导方程进行修改的方式来减缓这种速度的突变，在接近引导点转换阈值时，提前进行转换来减缓速度突变的趋势，修正过后的引导方程如下所示：
[0052][0053][0054]
其中：f
now
表示当前引导点的吸引力，f
next
表示下一引导点的吸引力，ω1、ω2为权重系数，r表示人员到当前驱动点的距离，r表示转换半径。
[0055]
与现有技术相比，本发明的有益效果是：本发明主要解决客船疏散过程中多个出口情况下的人员出口均衡分配以及有序疏散过程的模拟问题。由于客船存在多个对称式的出口，采用直线距离进行直线判断的效率低，且容易造成路径质量低的问题。本发明基于节点网络地图，在原本的地图节点网络的基础上引入虚拟节点，将该节点与各出口进行连接，以虚拟节点为目标节点，各出口为中间节点，展开算法搜索，减少了算法的搜索时间，在此
基础上基于人员分布不均的问题，对虚拟节点进行动态更新，进一步解决了多出口人员分配不均的问题。最后构建了基于引导路径的社会力模型，模拟人群的疏散过程，动态的反应人员疏散的轨迹，有效地对疏散进行指导。
附图说明
[0056]
图1是本发明流程示意图；
[0057]
图2(a)是客船实际结构图；
[0058]
图2(b)是客船简化结构图；
[0059]
图3是疏散网络图；
[0060]
图4是人员位置分布图；
[0061]
图5(a)是第10s人员疏散过程图；
[0062]
图5(b)是第20s人员疏散过程图；
[0063]
图5(c)是第30s人员疏散过程图；
[0064]
图6(a)是平均且分散人员位置分布图；
[0065]
图6(b)是平均且密集人员位置分布图；
[0066]
图6(c)是不均且密集人员位置分布图。
具体实施方式
[0067]
下面结合附图与具体实施方式对本发明作进一步详细描述。
[0068]
本发明是一种基于虚拟节点的远洋客船人员应急疏散路径规划算法。针对多出口的对称式客船环境，在疏散网络的节点中加入虚拟节点，减少算法展开次数，同时对虚拟节点位置进行动态更新实现人员的均衡分配，最后将规划出的路径与社会力模型进行结合，得到动态的疏散过程，对疏散过程进行指导。
[0069]
下面结合附图对本发明进一步说明：
[0070]
本发明是一种基于虚拟节点的远洋客船人员应急疏散路径规划算法，图1是本发明的流程图，具体步骤包括：
[0071]
(1)采集疏散环境信息，构建简化的结构网络；
[0072]
(2)构建虚拟节点并加入疏散网络；
[0073]
(3)将人员所在节点接入网络，采用a*算法展开搜索，节点展开过程采用出口节点作为中间节点，虚拟节点作为目标节点，同时采用初始点到中间节点的距离代价与中间节点到虚拟节点的负相关距离代价之和作为节点展开的总代价函数。
[0074]
(4)为进一步均衡各个出口的人员数量，采用动态更新的方式对虚拟节点位置进行计算；
[0075]
(5)构建社会力模型，将疏散过程中人与人和人与环境的互相作用通过力学公式以人员速度的方式表示出来；
[0076]
(6)将疏散网络与社会力模型进行结合构建，通过坐标对应的方式将疏散网络与疏散结构图进行人员位置坐标的对应，通过转换判断以及方程实现疏散过程中节点转换的平滑性；
[0077]
(7)将节点网络中规划出的疏散路径结果输入到模型中，得到最终的规划结果。
[0078]
本发明实施例用来解释本发明，而不是对本发明进行限制，在发明的精神和权利要求的保护范围内，对本发明做出的任何修改和改变，都落入本发明的保护范围。
[0079]
采用matlab仿真软件进行仿真实验，来验证所设计的规划方法的可靠性，下面结合实例进行仿真分析。以某一客船甲板中的客舱层的样段为例，长度为40m，宽度为55m。构建的结构图如图2所示，白色代表可行空间，黑色代表墙壁；构建的疏散网络如图3所示，红色线段表示疏散网络；采用人员位置分布如图4所示，红色表示人员所在位置。
[0080]
模拟灾害发生事故后的，人员疏散过程，疏散过程如图所示，图5(a)为在事故发生第10s时的人员位置分布图，图5(b)在事故发生第20s时的人员位置分布图，图5(c)在事故发生第30s时的人员位置分布图，可知，所有模拟人员均能够分配到一条通向出口的最近路径，表明所设计的算法能够在规则场景下为所有人员规划处一条合理的疏散路径，同时模型能够较为准确的模拟疏散过程中的拥挤、向出口移动等疏散现象。
[0081]
进一步对规划算法时间和模型按照规划路径进行疏散的时间进行对比，通过图6(a)人员分布平均且分散、图6(b)人员分布平均且密集和图6(c)人员分布不均且密集三种人员分布的情况，采用直接进行直线距离判断法、虚拟节点法和虚拟权重节点法进行疏散规划，如表1所示，其中，直接采用直线距离进行多出口判断所需花费的时间最多，采用虚拟节点进行多出口规划的时间最短，在虚拟节点的基础上加入均衡权重对于规划时间的影响不大，基本与虚拟节点的规划时间相同，验证了本发明所设计疏散规划算法在时间层面上存在一定的改进。
[0082]
表1算法规划时间对比
[0083][0084]
将三种算法规划出的路径输入到引导模型中进行模拟验证，通过模型模拟人员疏散过程的时间对算法规划出的引导路径进行评估分析。
[0085]
人员疏散时间对比如表2所示，人员位置分布比较平均时如图6(a)与图6(b)，人员按照各算法规划出的引导路径进行疏散所用的时间相差不大，当人员位置分布不平均且存在人员聚集时如图6(c)，传统多出口与仅加入虚拟节点的引导疏散时间相差不大，但加入了均衡权重后，由于人员路径节点选择不再单纯的由距离因素决定，同时与各出口的人员数量有关，能够更加平均的分配人员到各个出口，此时人员按照引导路径进行疏散时间更少，故采用均衡分配算法进行多出口人员路径规划能够更加合理的分配人员，从而达到减少疏散时间的目的。
[0086]
表2模型疏散时间对比
[0087][0088]
结合表1与表2可知，对比传统多出口的分配算法，加入虚拟节点后在算法的规划时间上有一定的改进，均衡分配算法在人员分布不平均的场景在群体疏散路径质量提升上有一定的改进。
[0089]
综上，对于客船等出口分布较为规则的场景中，本发明所设计的结合疏散网络与社会力模型的疏散方法，规划效率高，路径输出质量高，且能够进一步对疏散过程进行动态的模拟。