一种面向三维船舶场景的可扩展性实时快速应急路径规划方法，包括以下步骤：根据船舶室内结构构建三维导航网络；先在三维导航网络的路标节点处布设无线传感器，构造无线传感器网络，再利用无线传感器采集相邻路标节点之间的路段延迟信息以及危险到达路段的时间间隔信息，然后根据路标节点和路段延迟信息，采用有向图建立应急导航模型；根据应急导航策略的目标，利用舍入和缩放算法，为每个船载人员规划最优导航路径；根据船舶疏散环境的动态变化，利用无线传感器网络采集到的信息，实时更新应急导航模型参数，最后利用舍入和缩放算法实时计算船载人员的最优导航路径。本设计不仅可扩展性好，而且疏散效率高、用户安全性强。
1.一种面向三维船舶场景的可扩展性实时快速应急路径规划方法，其特征在于，该方法包括以下步骤：S1、根据船舶室内结构构建三维导航网络；
S2、先在三维导航网络的路标节点处布设无线传感器，构造无线传感器网络，再利用无线传感器采集相邻路标节点之间的路段延迟信息以及危险到达路段的时间间隔信息，然后根据路标节点和路段延迟信息，采用有向图建立应急导航模型；
S3、根据应急导航策略的目标，利用舍入和缩放算法，为每个船载人员规划最优导航路径；
所述应急导航策略的目标是指为每个船载人员规划一条远离危险区域的路径，经过该路径，在所有情况下船载人员都能在硬截止时间内到达出口路标，同时经历从用户初始路标到达出口路标的最小典型延迟；
S31、定义路标vi对应的相邻安全路标集合υi以及路标vi到达出口路标ve的安全路径集合s
(1)对于路标vi对应的相邻安全路标集合υi的定义如下：对于路标vi的相邻路标vj，若从路标vj到达出口路标ve的路径集合中存在一条路径pje，对于其中任意不等于路标vj的路标vn，若满足以下不等式，则路标vj为路标vi的相邻安全路s标，所有相邻安全路标构成集合υi；
式中， 为从路标vi到路标vj的路段的最坏情况延迟， 为从路标vj到达路标vn的路径pjn的最坏情况延迟； 为危险到达路段 的最短时间间隔，其中，路标vm位于路径pje上并且路段 为路标vn的相邻路段；
对于路径Pie，当且仅当每个位于路径Pie的路标vi，满足 将Pie定义为路标vi到出口路标ve的安全路径；其中，vj∈pie， 路标vi到出口路标ve的所有安全路径构成集合*
S32、定义路标vi到达出口路标ve的最小典型延迟 以及其对应的最优路径p(Γ)；
式中， 为路标vi到路标vj的典型延迟， 为路标vj到出口路标ve的典型延迟，tj为危险到达路标的硬截止时间；
将最小典型延迟 对应的最优相邻路标定义为πi，安全路径 定义为*
最优路径p(Γ)，当且仅当每个包含于安全路径pue的路标，满足vj＝πi；
S33、利用舍入和缩放算法，在多项式时间内计算最优路径p(Γ)与最优典型延迟(1)利用释放算法计算最小最坏情况延迟：式中，gj(dT)为典型延迟不超过dT的u‑j路径上的最小最坏情况延迟，gj(dT‑1)为典型延迟不超过dT‑1的u‑j路径上的最小最坏情况延迟， 为典型延迟不超过的u‑k路径上的最小最坏情况延迟， 为路段 的典型延迟， 为路段的最坏情况延迟；
(3)执行舍入和缩放算法，计算最优路径p(Γ)与最优典型延迟S4、根据船舶疏散环境的动态变化，利用无线传感器网络采集到的信息，实时更新应急导航模型参数，最后利用舍入和缩放算法实时计算船载人员的最优导航路径。
2.根据权利要求1所述的一种面向三维船舶场景的可扩展性实时快速应急路径规划方法，其特征在于：步骤S1中，采用基于泰森多边形的导航网络构建方法，具体包括以下步骤：S11、初始化赋值，VD单元格集合R1＝f，当前曲面细分等级TL＝1；
S12、导航场景中门节点、凹角节点和楼梯节点投影对应于约束形核点集合N，对于待测VD单元格集合M中的每个VD单元格Rk，计算约束形核点连线 的二等分线bl，再计算二等分线bl与VD单元格Rk的交点集合L；
S13、若交点集合L中的元素个数大于2，则创建边(j，k)，并将其插入多边形f的细分曲面中；将包含约束形核点Nj的VD单元格Rk添加到集合R中；对于边(j，k)相交的边，将其相邻的VD单元格Rk添加到待测VD单元格集合M中；
S14、删除约束形核点Nj新生成的VD单元格边界内的边；
S15、对于多边形f的细分曲面中的每条边e，若边e的长度超过边长阈值T1，或者边e受两个约束形核点限制，或者边e的端点位于不共线约束边上时，计算边e的二等分点bp，并将二等分点bp添加到集合N中；
S16、对细分等级赋值TL＝TL+1，重复步骤S12、S13、S14、S15，直到完成最大细分等级TLmax的计算。
3.根据权利要求1所述的一种面向三维船舶场景的可扩展性实时快速应急路径规划方法，其特征在于：步骤S2具体包括以下步骤：S21、采用有向图对无线传感器网络进行建模，得到图模型为：式中，v为路标集合，ε为两个路标之间路段构成的集合；
S22、估计不同路段对应的典型延迟 和最坏情况延迟S23、将图模型 中每个路标v设置为三元组：式中，ID为部署无线传感器时分配的路标标识符，LC为路标在导航网络中的位置坐标，为最短危险到达时间集合；
为危险从初始位置扩展到路标vj的相邻路段 的最短时间间隔，定义为：式中， 为危险从初始位置扩展到路标vj所有相邻路段的最短时间间隔集合，为路标vj的相邻路标集合；
式中，Tc(t0)为疏散截止时间，ve为出口路标。
4.根据权利要求3所述的一种面向三维船舶场景的可扩展性实时快速应急路径规划方法，其特征在于：步骤S22中，将动态危险情况下船载人员的典型速度与图模型中各路段长度相结合，计算出该路段对应的典型延迟对于因水密舱壁而不受浸水影响的路段，其最坏情况速度SW为：式中， 为倾斜角为30度时步行速度的衰减系数；
对于受浸水影响的路段，其最坏情况速度SW为：式中， 为水深0.8m时步行速度的衰减系数；
将船载人员通过各路段的最坏情况速度与图模型中各路段长度相结合，计算出该路段对应的最坏情况延迟
5.根据权利要求3所述的一种面向三维船舶场景的可扩展性实时快速应急路径规划方法，其特征在于：步骤S33中，上界U的计算方法包括以下步骤：(1)基于未插入危险区域时的图模型 计算上界U的初始值对应于从用户初始路标到U达出口路标的最小最坏情况延迟，对应路径为p；
(3)对于路径p中的各个路段 判断图模型插入第i个危险区域后， 是否安全U路段，如果不属于，则基于插入第i个危险区域后的图模型 更新路径p；
(4)重复步骤(2)、(3)，直到完成插入nh个危险区域，得到的最小最坏情况延迟即路径p(Γ)的上界U。
6.根据权利要求5所述的一种面向三维船舶场景的可扩展性实时快速应急路径规划方法，其特征在于：步骤S33中，下界L的计算方法为：i
对不同的路段典型延迟 进行排序，取典型延迟最大值 定义ε(t)为典型延迟不超过 的路段集合，表达式如下：l l
由于图模型 中一定包含一条Tc(t)内的路径p，并且路径p中所有路段都包含于集合j j因此存在唯一索引值j，使得图模型 中包含一条Tc(t)内的路径p且路径p中所有路段都包含于集合 中，并且满足在图模型 中，从初始路标到出口路标的所有j‑1 *路径p ，其最坏情况延迟都超过Tc(t)，得到最优路径p(Γ)的下界L表达式如下：j
式中， 为Tc(t)内的路径p中路段的典型延迟最大值， 为最优路径的典型延迟。
7.根据权利要求6所述的一种面向三维船舶场景的可扩展性实时快速应急路径规划方*法，其特征在于：步骤S33中，最优路径p(Γ)与最优典型延迟 的计算方法如下：(1)对于图模型 中的每一条路段 的典型延迟 按照公式进行舍入操作，其中，n为图模型中路标数量，∈为近似因子；
(2)对最优路径上界U，按照公式 进行舍入操作，保证(3)对路径的最小最坏情况延迟初始化，令gj(0)＝+∞，(4)调用舍入和缩放中的释放算法，计算典型延迟不超过 的u‑j路径的最小最坏情况延迟令 依次计算，直到首次满足最小最坏情况延迟 小于疏散截止时间Tc(t)，即满足 时，则取 为最优典型延迟 其对应的路径为最优路径。
8.根据权利要求7所述的一种面向三维船舶场景的可扩展性实时快速应急路径规划方法，其特征在于：步骤S4中，导航路径pue由用户路标vu到达出口路标ve的路标序列构成，表达式如下：式中，pue(Γ)为随着典型延迟改变动态更新的路标序列，Γ为路标序列pue(Γ)的累积时间；
路径p(Γ)的典型延迟 和最坏情况延迟 定义为：根据Top‑level算法获取躲避危险的无折返导航路径，具体包括以下步骤：(1)调用舍入和缩放算法得到最优路径 计算出从vu到ve的Tc(t)内的路径，其典型延迟不超过(2)将变量test1设置为FALSE，表明在危险入侵之前，所有路段均可通行；
(3)将变量test2设置为FALSE，表明典型延迟未发生变化；
(4)构造一个集合εtest，其中元素为危险入侵之前，原计划路径中用户无法通行的路段；
(5)判断已经包含在最优路径 中的路段是否应该纳入集合εtest；对于最优路径中的每条路段，判断各路段 的最坏延迟时间 是否超过危险传播时间若超过了，则表明在危险入侵之前，该路段无法通行，将路段 加入集合εtest中；
(6)对于图模型 中的路段集合ε，删除包含于集合εtest中的元素，以重新建立导航网络连接；
(7)基于当前的图模型 调用舍入和缩放算法获取最优路径 并选择路径中的相邻路标 作为用户的下一路标；在下一次迭代中， 将作为新的用户路标；
(8)再次检查典型延迟是否改变，若发生改变，将test2设置为TRUE；
(9)判断test2的状态，若test2为TURE，表明典型延迟发生改变，则将test2设置为FALSE，回到步骤(5)，根据变化后的典型延迟重新计算当前用户路标到达出口路标的路径其中，tnew为到达当前路标的时间戳；若test2为FALSE，表明典型延迟未发生改变，则用户移动到路径 中当前用户路标的相邻路标，其中，tN‑1为离开前一路标的时间戳。
面向三维船舶场景的可扩展性实时快速应急路径规划方法
技术领域
[0001] 本发明涉及智能交通的船载人员应急疏散领域，尤其涉及一种面向三维船舶场景的可扩展性实时快速应急路径规划方法。
背景技术
[0002] 邮轮事故往往会造成大量的人员伤亡，无效的应急疏散方法被认为是造成人员伤亡的主要原因之一，可靠且高效的应急疏散对于邮轮乘客的安全至关重要。
[0003] 目前有许多先进的基于无线传感器网络的应急疏散方法，利用无线传感器与动态环境进行交互，实时获取信息，为用户提供实时的导航服务。但是这些疏散方法主要应用于陆地上的建筑，没有考虑到船载环境复杂的内部结构、有限的生存时间以及船体运动，因此无法直接将其应用于船舶疏散。首先，大部分方法仅用于处理二维传感场景，没有考虑到实际的导航环境；这些方法会在运行阶段探索环境中的障碍物并且构建路线图，由于邮轮内部结构极度复杂，疏散过程中存在动态危险，这些导航方法无法为船载乘客提供实时且可靠的导航方案。其次，船舶人员应急疏散需要考虑船体倾覆的硬截止时间，具体来说，部分疏散方法考虑了危险变化的影响，旨在引导用户在远离危险的同时无振荡地逃生，但忽视了导航效率，导致乘客长时间处于危险中，从而错过了船舶的逃生时间。最后，船载人员的运动会受到船舶倾斜角与受损情况的影响，疏散人员速度变化会引起相同路段上逃生时间的改变，因此在船体倾覆之前，传统的疏散方法可能无法完成乘客安全疏散。
[0004] 由于船舶室内环境结构复杂，目前先进的应急疏散方法主要适用于结构简单的陆地建筑物。对于存在动态危险及疏散硬截止时间的船载环境，基于无线传感器网络的应急疏散策略存在算法可扩展性差、疏散效率低、用户安全性差的问题。
发明内容
[0005] 本发明的目的是克服现有技术中存在的可扩展性差、疏散效率低、用户安全性差的缺陷与问题，提供一种可扩展性好、疏散效率高、用户安全性强的面向三维船舶场景的可扩展性实时快速应急路径规划方法。
[0006] 为实现以上目的，本发明的技术解决方案是：一种面向三维船舶场景的可扩展性实时快速应急路径规划方法，该方法包括以下步骤：
[0007] S1、根据船舶室内结构构建三维导航网络；
[0008] S2、先在三维导航网络的路标节点处布设无线传感器，构造无线传感器网络，再利用无线传感器采集相邻路标节点之间的路段延迟信息以及危险到达路段的时间间隔信息，然后根据路标节点和路段延迟信息，采用有向图建立应急导航模型；
[0009] S3、根据应急导航策略的目标，利用舍入和缩放算法，为每个船载人员规划最优导航路径；
[0010] S4、根据船舶疏散环境的动态变化，利用无线传感器网络采集到的信息，实时更新应急导航模型参数，最后利用舍入和缩放算法实时计算船载人员的最优导航路径。
[0011] 步骤S1中，采用基于泰森多边形的导航网络构建方法，具体包括以下步骤：
[0012] S11、初始化赋值，VD单元格集合R1＝f，当前曲面细分等级TL＝1；
[0013] S12、导航场景中门节点、凹角节点和楼梯节点投影对应于约束形核点集合N，对于待测VD单元格集合M中的每个VD单元格Rk，计算约束形核点连线 的二等分线bl，再计算二等分线bl与VD单元格Rk的交点集合L；
[0014] S13、若交点集合L中的元素个数大于2，则创建边(j，k)，并将其插入多边形f的细分曲面中；将包含约束形核点Nj的VD单元格Rk添加到集合R中；对于边(j，k)相交的边，将其相邻的VD单元格Rk添加到待测VD单元格集合M中；
[0015] S14、删除约束形核点Nj新生成的VD单元格边界内的边；
[0016] S15、对于多边形f的细分曲面中的每条边e，若边e的长度超过边长阈值T1，或者边e受两个约束形核点限制，或者边e的端点位于不共线约束边上时，计算边e的二等分点bp，并将二等分点bp添加到集合N中；
[0017] S16、对细分等级赋值TL＝TL+1，重复步骤S12、S13、S14、S15，直到完成最大细分等级TLmax的计算。
[0018] 步骤S2具体包括以下步骤：
[0019] S21、采用有向图对无线传感器网络进行建模，得到图模型为：
[0020]
[0021] 式中，υ为路标集合，ε为两个路标之间路段构成的集合；
[0022] S22、估计不同路段对应的典型延迟 和最坏情况延迟
[0023] S23、将图模型 中每个路标v设置为三元组：
[0024]
[0025] 式中，ID为部署无线传感器时分配的路标标识符，LC为路标在导航网络中的位置坐标， 为最短危险到达时间集合；
[0026] 为危险从初始位置扩展到路标vj的相邻路段 的最短时间间隔，定义为：
[0027]
[0028] 式中， 为危险从初始位置扩展到路标vj所有相邻路段的最短时间间隔集合， 为路标vj的相邻路标集合；
[0029]
[0030]
[0031] 式中，Tc(t0)为疏散截止时间，ve为出口路标。
[0032] 步骤S22中，将动态危险情况下船载人员的典型速度与图模型中各路段长度相结合，计算出该路段对应的典型延迟
[0033] 对于因水密舱壁而不受浸水影响的路段，其最坏情况速度SW为：
[0034]
[0035] 式中， 为倾斜角为30度时步行速度的衰减系数；
[0036] 对于受浸水影响的路段，其最坏情况速度SW为：
[0037]
[0038] 式中， 为水深0.8m时步行速度的衰减系数；
[0039] 将船载人员通过各路段的最坏情况速度与图模型中各路段长度相结合，计算出该路段对应的最坏情况延迟
[0040] 所述应急导航策略的目标是指为每个船载人员规划一条远离危险区域的路径，经过该路径，在所有情况下船载人员都能在硬截止时间内到达出口路标，同时经历从用户初始路标到达出口路标的最小典型延迟。
[0041] 步骤S3具体包括以下步骤：
[0042] S31、定义路标vi对应的相邻安全路标集合υis以及路标vi到达出口路标ve的安全路径集合
[0043] (1)对于路标vi对应的相邻安全路标集合υis的定义如下：
[0044] 对于路标vi的相邻路标vj，若从路标vj到达出口路标ve的路径集合中存在一条路径pje，对于其中任意不等于路标vj的路标vn，若满足以下不等式，则路标vj为路标vi的相邻s安全路标，所有相邻安全路标构成集合υi；
[0045]
[0046] 式中， 为从路标vi到路标vj的路段的最坏情况延迟， 为从路标vj到达路标vn的路径pjn的最坏情况延迟； 为危险到达路段 的最短时间间隔，其中，路标vm位于路径pje上并且路段 为路标vn的相邻路段；
[0047] (2)对于安全路径集合 的定义如下：
[0048] 对于路径Pie，当且仅当每个位于路径Pie的路标vi，满足 将Pie定义为路标vi到出口路标ve的安全路径；其中，vj∈pie， 路标vi到出口路标ve的所有安全路径构成集合
[0049] S32、定义路标vi到达出口路标ve的最小典型延迟 以及其对应的最优路*
径p(Γ)；
[0050] 最小典型延迟 为：
[0051]
[0052] 式中， 为路标vi到路标vj的典型延迟， 为路标vj到出口路标ve的典型延迟，tj为危险到达路标的硬截止时间；
[0053] 将最小典型延迟 对应的最优相邻路标定义为πi，安全路径*
定义为最优路径p(Γ)，当且仅当每个包含于安全路径pue的路标，满足vj＝πi；
[0054] S33、利用舍入和缩放算法，在多项式时间内计算最优路径p*(Γ)与最优典型延迟[0055] (1)利用释放算法计算最小最坏情况延迟：
[0056]
[0057] 式中，gj(dT)为典型延迟不超过dT的u‑j路径上的最小最坏情况延迟，gj(dT‑1)为典型延迟不超过dT‑1的u‑j路径上的最小最坏情况延迟， 为典型延迟不超过的u‑k路径上的最小最坏情况延迟， 为路段 的典型延迟， 为路
段 的最坏情况延迟；
[0058] (2)分别计算最优路径p*(Γ)的上界U与下界L；
[0059] (3)执行舍入和缩放算法，计算最优路径p*(Γ)与最优典型延迟
[0060] 步骤S33中，上界U的计算方法包括以下步骤：
[0061] (1)基于未插入危险区域时的图模型 计算上界U的初始值对应于从用户初始路U标到达出口路标的最小最坏情况延迟，对应路径为p；
[0062] (2)在图模型中逐个插入nh个危险区域；U
[0063] (3)对于路径p中的各个路段 判断图模型插入第i个危险区域后， 是否U
安全路段，如果不属于，则基于插入第i个危险区域后的图模型 更新路径p ；
[0064] (4)重复步骤(2)、(3)，直到完成插入nh个危险区域，得到的最小最坏情况延迟即*路径p(Γ)的上界U。
[0065] 步骤S33中，下界L的计算方法为：
[0066] 对不同的路段典型延迟 进行排序，取典型延迟最大值 定义εi(t)为典型延迟不超过 的路段集合，表达式如下：
[0067]
[0068] 由于图模型 中一定包含一条Tc(t)内的路径pl，并且路径pl中所有路段都包含j于集合 因此存在唯一索引值j，使得图模型 中包含一条Tc(t)内的路径p且路
j
径p 中所有路段都包含于集合 中，并且满足在图模型 中，从初始路标到出口
j‑1 *
路标的所有路径p ，其最坏情况延迟都超过Tc(t)，得到最优路径p (Γ)的下界L表达式如下：
[0069]j
[0070] 式中， 为Tc(t)内的路径p中路段的典型延迟最大值， 为最优路径的典型延迟。
[0071] 步骤S33中，最优路径p*(Γ)与最优典型延迟 的计算方法如下：
[0072] (1)对于图模型 中的每一条路段 的典型延迟 按照公式进行舍入操作，其中，n为图模型中路标数量，∈为近似因子；
[0073] (2)对最优路径上界U，按照公式 进行舍入操作，保证
[0074] (3)对路径的最小最坏情况延迟初始化，令gj(0)＝+∞，
[0075] (4)调用舍入和缩放中的释放算法，计算典型延迟不超过 的u‑j路径的最小最坏情况延迟
[0076] 令 依次计算，直到首次满足最小最坏情况延迟 小于疏散截止时间Tc(t)，即满足 时，则取 为最优典型延迟 其对应
的路径 为最优路径。
[0077] 步骤S4中，导航路径pue由用户路标vu到达出口路标ve的路标序列构成，表达式如下：
[0078]
[0079] 式中，pue(Γ)为随着典型延迟改变动态更新的路标序列，Γ为路标序列pue(Γ)的累积时间；
[0080] 路径p(Γ)的典型延迟 和最坏情况延迟 定义为：
[0081]
[0082] 根据Top‑level算法获取躲避危险的无折返导航路径，具体包括以下步骤：
[0083] (1)调用舍入和缩放算法得到最优路径 计算出从vu到ve的Tc(t)内的路径，其典型延迟不超过
[0084] (2)将变量test1设置为FALSE，表明在危险入侵之前，所有路段均可通行；
[0085] (3)将变量test2设置为FALSE，表明典型延迟未发生变化；
[0086] (4)构造一个集合εtest，其中元素为危险入侵之前，原计划路径中用户无法通行的路段；
[0087] (5)判断已经包含在最优路径 中的路段是否应该纳入集合εtest；对于最优路径中的每条路段，判断各路段 的最坏延迟时间 是否超过危险传播时间若超过了，则表明在危险入侵之前，该路段无法通行，将路段 加入集合εtest
中；
[0088] (6)对于图模型 中的路段集合ε，删除包含于集合εtest中的元素，以重新建立导航网络连接；
[0089] (7)基于当前的图模型 调用舍入和缩放算法获取最优路径 并选择路径中的相邻路标 作为用户的下一路标；在下一次迭代中， 将作为新的用户路标；
[0090] (8)再次检查典型延迟是否改变，若发生改变，将test2设置为TRUE；
[0091] (9)判断test2的状态，若test2为TURE，表明典型延迟发生改变，则将test2设置为FALSE，回到步骤(5)，根据变化后的典型延迟重新计算当前用户路标到达出口路标的路径其中，tnew为到达当前路标的时间戳；若test2为FALSE，表明典型延迟未发生改变，则用户移动到路径 中当前用户路标的相邻路标，其中，tN‑1为离开前一路标的时间戳。
[0092] 与现有技术相比，本发明的有益效果为：
[0093] 本发明一种面向三维船舶场景的可扩展性实时快速应急路径规划方法中，提出的导航方法能够实时地根据船载人员行走速度及当前环境选择最优的导航路径，将路径规划问题转化为双约束最短路径问题，利用近似算法选取最优路径，该路径上的最坏情况延迟不超过规定的截止时间，且总动态典型延迟较小，能保证用户能在硬截止时间内，避开危险到达出口位置。因此，本发明不仅保证了疏散过程中用户的安全性、路径规划的高效性，而且提高了算法的可扩展性。
附图说明
[0094] 图1是本发明一种面向三维船舶场景的可扩展性实时快速应急路径规划方法的流程图。
[0095] 图2是本发明的实施例中的客船二层平面图。
[0096] 图3是本发明的实施例中的第一次细分迭代后生成的导航网络。
[0097] 图4是本发明的实施例中的第二次细分迭代后生成的导航网络。
[0098] 图5是本发明的实施例中的t1时刻应急导航场景。
[0099] 图6是本发明的实施例中的t1时刻应急导航模型。
[0100] 图7是本发明的实施例中的t2时刻应急导航场景。
[0101] 图8是本发明的实施例中的t2时刻应急导航模型。
[0102] 图9是本发明的实施例中的∈＝1情况下本发明方法和OPEN方法在图3所示导航网络中的平均疏散时间对比图。
[0103] 图10是本发明的实施例中的∈＝0.5情况下本发明方法和OPEN方法在图3所示导航网络中的平均疏散时间对比图。
[0104] 图11是本发明的实施例中的∈＝0.25情况下本发明方法和OPEN方法在图3所示导航网络中的平均疏散时间对比图。
[0105] 图12是本发明的实施例中的∈＝0.5时本发明方法和OPEN方法在不同用户数量及导航场景下的平均疏散时间对比图。
[0106] 图13是本发明的实施例中的∈＝1情况下本发明方法和OPEN方法在图3所示导航网络中的导航成功率对比图。
[0107] 图14是本发明的实施例中的∈＝0.5情况下本发明方法和OPEN方法在图3所示导航网络中的导航成功率对比图。
[0108] 图15是本发明的实施例中的∈＝0.25情况下本发明方法和OPEN方法在图3所示导航网络中的导航成功率对比图。
[0109] 图16是本发明的实施例中的∈＝0.5时本发明方法和OPEN方法在图3所示导航网络中距离危险区域最短距离对比图。
具体实施方式
[0110] 以下结合附图说明和具体实施方式对本发明作进一步详细的说明。
[0111] 参见图1，一种面向三维船舶场景的可扩展性实时快速应急路径规划方法，该方法包括以下步骤：
[0112] S1、根据船舶室内结构构建三维导航网络；
[0113] 采用基于泰森多边形的导航网络构建方法，具体包括以下步骤：
[0114] S11、初始化赋值，VD单元格集合R1＝f，当前曲面细分等级TL＝1；
[0115] S12、导航场景中门节点、凹角节点和楼梯节点投影对应于约束形核点集合N，对于待测VD单元格集合M中的每个VD单元格Rk，计算约束形核点连线 的二等分线bl，再计算二等分线bl与VD单元格Rk的交点集合L；
[0116] S13、若交点集合L中的元素个数大于2，则创建边(j，k)，并将其插入多边形f的细分曲面中；将包含约束形核点Nj的VD单元格Rk添加到集合R中；对于边(j，k)相交的边，将其相邻的VD单元格Rk添加到待测VD单元格集合M中；
[0117] S14、删除约束形核点Nj新生成的VD单元格边界内的边；
[0118] S15、对于多边形f的细分曲面中的每条边e，若边e的长度超过边长阈值T1，或者边e受两个约束形核点限制，或者边e的端点位于不共线约束边上时，计算边e的二等分点bp，并将二等分点bp添加到集合N中；
[0119] S16、对细分等级赋值TL＝TL+1，重复步骤S12、S13、S14、S15，直到完成最大细分等级TLmax的计算；
[0120] 以黄金7号客船为例，根据真实船舶拓扑结构构建三维导航网络。为了验证算法的可扩展性，通过改变细分曲面的迭代次数，生成具有不同数量路标的导航网络。基于客船二层平面图，如图2所示，采用不同的迭代次数，我们定义了两个不同的导航网络：如图3所示，第一次细分迭代后生成的导航网络，包含98个节点；如图4所示，第二次细分迭代后生成的导航网络，包含196个节点。
[0121] S2、先在三维导航网络的路标节点处布设无线传感器，构造无线传感器网络，再利用无线传感器采集相邻路标节点之间的路段延迟信息以及危险到达路段的时间间隔信息，然后根据路标节点和路段延迟信息，采用有向图建立应急导航模型；具体包括以下步骤：
[0122] S21、采用有向图对无线传感器网络进行建模，得到图模型为：
[0123]
[0124] 式中，υ为路标集合，ε为两个路标之间路段构成的集合；
[0125] 如图5‑图8所示，图模型包含了路标以及两个路标之间的路段，每个路标对应一个无线传感器节点，路标分为两类：危险路标和普通路标，危险路标子集的凸包构成危险区域。船载人员当前到达的路标定义为用户路标(vu∈υ)，距离集合站点最近的路标视作出口路标(ve∈υ)；
[0126] S22、估计不同路段对应的典型延迟 和最坏情况延迟
[0127] 将动态危险情况下船载人员的典型速度与图模型中各路段长度相结合，计算出该路段对应的典型延迟
[0128] 对于因水密舱壁而不受浸水影响的路段，其最坏情况速度SW为：
[0129]
[0130] 式中， 为倾斜角为30度时步行速度的衰减系数；
[0131] 对于受浸水影响的路段，其最坏情况速度SW为：
[0132]
[0133] 式中， 为水深0.8m时步行速度的衰减系数；
[0134] 将船载人员通过各路段的最坏情况速度与图模型中各路段长度相结合，计算出该路段对应的最坏情况延迟
[0135] S23、将图模型 中每个路标v设置为三元组：
[0136]
[0137] 式中，ID为部署无线传感器时分配的路标标识符，LC为路标在导航网络中的位置坐标， 为最短危险到达时间集合；
[0138] 为危险从初始位置扩展到路标vj的相邻路段 的最短时间间隔，定义为：
[0139]
[0140] 式中， 为危险从初始位置扩展到路标vj所有相邻路段的最短时间间隔集合， 为路标vj的相邻路标集合；
[0141]
[0142]
[0143] 式中，Tc(t0)为疏散截止时间，ve为出口路标；
[0144] 如果 表示危险接近，否则表明危险不会影响该路段；考虑船舶倾斜角度动态变化特性，利用无线传感器周期性探头捕获危险路标到达路段的时间间隔，进而获得最短危险达到时间集合 当路标vj探测到危险路标vh时，根据图模型
以及危险扩散方向与速度决定是否更新元素 中的值；
[0145] S3、根据应急导航策略的目标，利用舍入和缩放算法，为每个船载人员规划最优导航路径；
[0146] 基于应急导航模型描述船载人员应急导航问题，定义应急导航策略的目标，所述应急导航策略的目标是指为每个船载人员规划一条远离危险区域的路径，经过该路径，在所有情况下船载人员都能在硬截止时间内到达出口路标，同时经历从用户初始路标到达出口路标的最小典型延迟；
[0147] 具体包括以下步骤：
[0148] S31、定义路标vi对应的相邻安全路标集合υis以及路标vi到达出口路标ve的安全路径集合
[0149] (1)对于路标vi对应的相邻安全路标集合υis的定义如下：
[0150] 对于路标vi的相邻路标vj，若从路标vj到达出口路标ve的路径集合中存在一条路径pje，对于其中任意不等于路标vj的路标vn，若满足以下不等式，则路标vj为路标vi的相邻s安全路标，所有相邻安全路标构成集合υi；
[0151]
[0152] 式中， 为从路标vi到路标vj的路段的最坏情况延迟， 为从路标vj到达路标vn的路径pjn的最坏情况延迟； 为危险到达路段 的最短时间间隔，其中，路标vm位于路径pje上并且路段 为路标vn的相邻路段；
[0153] (2)对于安全路径集合 的定义如下：
[0154] 对于路径Pie，当且仅当每个位于路径Pie的路标vi，满足 将Pie定义为路标vi到出口路标ve的安全路径；其中，vj∈pie， 路标vi到出口路标ve的所有安全路径构成集合
[0155] S32、定义路标vi到达出口路标ve的最小典型延迟 以及其对应的最优路*
径p(Γ)；
[0156] 最小典型延迟 为：
[0157]
[0158] 式中， 为路标vi到路标vj的典型延迟， 为路标vj到出口路标ve的典型延迟，tj为危险到达路标的硬截止时间；以保证从路标vi到出口路标ve的整体典型延迟最小，同时保证用户在疏散过程中能够躲避动态危险并且疏散时间不超过危险到达路标的硬截止时间tj；
[0159] 将最小典型延迟 对应的最优相邻路标定义为πi，安全路径 定*
义为最优路径p(Γ)，当且仅当每个包含于安全路径pue的路标，满足vj＝πi；
[0160] S33、利用舍入和缩放算法，在多项式时间内计算最优路径p*(Γ)与最优典型延迟使该路径上的最坏情况延迟不超过硬截止时间，且总动态典型延迟较小；
[0161] (1)利用释放算法计算最小最坏情况延迟：
[0162]
[0163] 式中，gj(dT)为典型延迟不超过dT的u‑j路径上的最小最坏情况延迟，gj(dT‑1)为典型延迟不超过dT‑1的u‑j路径上的最小最坏情况延迟， 为典型延迟不超过的u‑k路径上的最小最坏情况延迟， 为路段 的典型延迟， 为路
段 的最坏情况延迟；
[0164] 路径的最小最坏情况延迟一开始是未知的，对应用户路标vu到路标vj的u‑j路径，首先令dT＝1，vj＝vu+1，...，ve，计算gj(dT)的值，然后对dT＝2，vj＝vu+1，...，ve，计算gj(dT)的值，以此类推 直到出现dT的值首次满足gj(dT)≤Tc(t0)，那么 为此时dT的值；
[0165] (2)分别计算最优路径p*(Γ)的上界U与下界L；
[0166] 上界U的计算方法包括以下步骤：
[0167] ①基于未插入危险区域时的图模型 计算上界U的初始值对应于从用户初始路U标到达出口路标的最小最坏情况延迟，对应路径为p；
[0168] ②在图模型中逐个插入nh个危险区域；
[0169] ③对于路径pU中的各个路段 判断图模型插入第i个危险区域后， 是否U
安全路段，如果不属于，则基于插入第i个危险区域后的图模型 更新路径p ；
[0170] ④重复步骤(2)、(3)，直到完成插入nh个危险区域，得到的最小最坏情况延迟即路*径p(Γ)的上界U；
[0171] 下界L的计算方法为：
[0172] 对不同的路段典型延迟 进行排序 其中，li
≤|ε|＝m，取典型延迟最大值 定义ε(t)为典型延迟不超过 的路段集合，表达
式如下：
[0173]
[0174] 令 那么 由于图模型 中一定包含一条Tc(t)内的路径l l
p ，并且路径p中所有路段都包含于集合 因此存在唯一索引值j，使得图模型
j j
中包含一条Tc(t)内的路径p且路径p中所有路段都包含于集合 中，并且满足在图
j‑1
模型 中，从初始路标到出口路标的所有路径p ，其最坏情况延迟都超过Tc(t)，得到最*
优路径p(Γ)的下界L表达式如下：
[0175]
[0176] 式中， 为Tc(t)内的路径pj中路段的典型延迟最大值， 为最优路径的典型延迟；
[0177] (3)执行舍入和缩放算法，计算最优路径p*(Γ)与最优典型延迟*
[0178] 最优路径p (Γ)与最优典型延迟 的计算方法如下：
[0179] ①对于图模型 中的每一条路段 的典型延迟 按照公式进行舍入操作，保证 其中，n为图模型中路标数量，∈
(0＜∈＜1)为近似因子；
[0180] ②对最优路径上界U，按照公式 进行舍入操作，保证
[0181] ③对路径的最小最坏情况延迟初始化，令gj(0)＝+∞，
[0182] ④调用舍入和缩放中的释放算法，计算典型延迟不超过 的u‑j路径的最小最坏情况延迟
[0183] 由于 令 依次计算，直到首次满足最小最坏情况延迟 小于疏散截止时间Tc(t)，即满足
时，则取 为最优典型延迟 其对应的路径 为最优路径；
[0184] S4、根据船舶疏散环境的动态变化，利用无线传感器网络采集到的信息，实时更新应急导航模型参数，最后利用舍入和缩放算法实时计算船载人员的最优导航路径；
[0185] 导航路径pue由用户路标vu到达出口路标ve的路标序列构成，表达式如下：
[0186]
[0187] 式中，pue(Γ)为随着典型延迟改变动态更新的路标序列，该序列存储在用户路标与出口路标之间的每个路标中；Γ为路标序列pue(Γ)的累积时间；
[0188] 路径p(Γ)的典型延迟 和最坏情况延迟 定义为：
[0189]
[0190] 考虑船舶倾斜带来的动态危险，路段可能会被阻塞，典型延迟和最坏情况延迟的变化会导致船载人员错过船舶疏散的硬截止时间；根据Top‑level算法获取躲避危险的无折返导航路径，具体包括以下步骤：
[0191] (1)调用舍入和缩放算法得到最优路径 计算出从vu到ve的Tc(t)内的路径，其典型延迟不超过
[0192] (2)将变量test1设置为FALSE，表明在危险入侵之前，所有路段均可通行；
[0193] (3)将变量test2设置为FALSE，表明典型延迟未发生变化；
[0194] (4)构造一个集合εtest，其中元素为危险入侵之前，原计划路径中用户无法通行的路段；
[0195] (5)判断已经包含在最优路径 中的路段是否应该纳入集合εtest；对于最优路径中的每条路段，判断各路段 的最坏延迟时间 是否超过危险传播时间若超过了，则表明在危险入侵之前，该路段无法通行，将路段 加入集合εtest
中；
[0196] (6)对于图模型 中的路段集合ε，删除包含于集合εtest中的元素，以重新建立导航网络连接；
[0197] (7)基于当前的图模型 调用舍入和缩放算法获取最优路径 并选择路径中的相邻路标 作为用户的下一路标；在下一次迭代中， 将作为新的用户路标；
[0198] (8)再次检查典型延迟是否改变，若发生改变，将test2设置为TRUE；
[0199] (9)判断test2的状态，若test2为TURE，表明典型延迟发生改变，则将test2设置为FALSE，回到步骤(5)，根据变化后的典型延迟重新计算当前用户路标到达出口路标的路径其中，tnew为到达当前路标的时间戳；若test2为FALSE，表明典型延迟未发生改变，则用户移动到路径 中当前用户路标的相邻路标，其中，tN‑1为离开前一路标的时间戳。
[0200] 将本发明设计的应急导航方法(WEND)与先进的应急导航方法OPEN(基于预期折返次数(ENO)的无折返导航方法)进行比较。参见图9‑图11，首先对于不同∈值，本方法(WEND)的平均疏散时间90％低于OPEN，这是由于OPEN方法的目标是生成一条无折返的导航路径，没有考虑到每个路段的典型延迟，从而可能产生较大的弯路，导致疏散时间过长用户错过船舶疏散硬截止时间；在某些特殊结果点处，本方法(WEND)的平均疏散时间高于OPEN方法，这是因为本方法设计的导航路径不仅考虑了各路段的典型延迟，同时考虑了各路段的最坏情况延迟，因此设计的导航路段不是理论上的最快安全路径。进一步比较两种方法的可扩展性，在不同的导航场景中进行模拟，得到仿真结果如图12所示，随着导航网络复杂度的增加，两种方法的疏散时间均增加了，这是因为导航网络越复杂，包含的导航节点越多，基于距离的延时测量结果越精确。在两种导航场景中，本发明设计的方法(WEND)均优于OPEN方法，用户疏散时间更短。其次考虑船舶疏散的硬截止时间，对比两种方法的导航成功率。图13‑图15展示了两种方法在硬截止时间内到达可能性的累积分布函数，从图中可以看出采用本方法(WEND)，超过70％、80％、85％的用户可以在硬截止时间内到达出口，而OPEN方法能保证60％的用户成功导航。最后验证两种导航方法的路径安全性，如图16所示对比了不同用户数量下两种导航方法到达危险区域的最短距离，本方法(WEND)的距离约为4米，OPEN方法的距离大于5米。在疏散过程中无需寻找安全距离最大的导航路径，因为这样的导航决策过于保守，增加用户在导航环境中花费的时间，降低了用户的整体安全性。相比之下，本发明设计的算法大大减少了用户在危险环境中的停留时间，提高了用户在硬截止时间内到达出口的机会。通过对比，验证了本发明设计的动态危险船舶室内环境应急疏散策略在疏散效率、用户安全性以及算法效率方面均有提高。
[0201] 本设计方法主要解决了以下四方面的问题：1)船舶室内环境中的应急疏散问题。船舶室内环境拓扑结构较为复杂，在预处理阶段构建船舶的三维拓扑模型，提取出包括走廊、楼梯和电梯在内的所有可通行路径。2)动态危险信息获取。通过布设无线传感器网络，及时获取危险发生位置以及危险到达时间，更新图模型中的路标属性以及最短危险到达时间信息；在模型中引入两个延迟参数：典型延迟 和最坏情况延迟 来表征导航
路径中的路段信息，它们分别表示通过路段 所需的典型延迟以及最大延迟的保证上界。3)船舶倾斜与受损情况对于船载人员疏散的影响。与陆地建筑物的室内疏散问题相比，船载室内环境的应急疏散需要考虑船体倾覆以及船舱破损后船舱内液体流动对行人运动的影响等，并且船载环境中乘客疏散时间是有限的，制定的导航路径必须在硬截止时间之内；结合船舶倾斜角度变化以及水密舱壁对船舱内液体流动的影响，分别估计船载人员典型速度以及最坏情况速度，实时更新各路段对应的典型延迟 和最坏情况延迟
利用无线传感器周期性探头捕获危险路标到达各路段的时间间隔，及时更新最短危险到达时间集合 4)算法可扩展性问题。随着导航网络包含的节点数量增加、网络复杂度提高，路径延时测量结果会更精确，但是会导致疏散时间增加；根据船舶疏散环境的动态变化以及应急导航策略的目标，实时更新模型参数，利用受约束最短路径问题的近似算法为每个船载人员规划最优的逃生路径。本设计考虑了船载环境应急疏散过程中存在的动态危险，结合船舶受损情况以及倾斜角变化对于船载人员运动速度的影响，基于无线传感器网络，提出了一种面向三维船舶场景的可扩展性实时快速应急路径规划方法，该疏散方法能够实时地为每一位船载人员提供安全高效的导航路径。
