改进A*的高层建筑逃生路径规划算法研究

靳海亮，王赢乐，袁 鸣，陈梦龙

(1. 河南理工大学测绘与国土信息工程学院，河南 焦作 454000； 2. 河南省遥感测绘院，河南 郑州 450003； 3. 河南省测绘工程院，河南 郑州 450003 )

随着经济的发展及科技水平的提高，城市中高层建筑不断涌现，在提高土地利用率、节约市政成本的同时，也带来了一些安全隐患。如在火灾发生时，由于高层建筑内部空间结构和逃生通道的限制，在没有合理疏散引导的情况下，短时间内建筑内部人员将快速向楼梯间移动，从而导致人员疏散速度大幅下降，二次事故发生概率剧增[1]。因此，在火灾发生时结合计算机技术制订合理的逃生路径规划方案尤为必要。

目前，中外学者在这一领域已经开展了研究，取得了一些成果。如文献[2]针对大型建筑或船舶发生火灾时人员疏散问题，通过对火势蔓延、二氧化碳浓度、烟尘浓度等因素的研究，基于蚁群算法提出了火灾场景中的逃生路径规划方法。文献[3]针对危机发生时受灾人员因恐慌、焦虑等因素影响而导致的疏散效率低下的问题，基于代理人基模型对人行为的异质性和人与环境的相互作用进行了研究，在此基础上提出了考虑行人行为和多种路径策略的疏散方案。文献[4]考虑环境因素在A*算法基础上提出了一种优化的建筑火灾逃生算法。文献[5]针对应急疏散中多约束条件下进行合理路径规划问题，基于对Dijkstra算法的改进实现了疏散总时间最短的路径规划优化算法的设计。文献[6]在研究静态路径规划算法的基础上将A*算法引入室内静态路径规划，并实现了基于智能手机平台的APP软件。文献[7]针对传统的基于节点的拓扑模型无法较好解决室内空间“路网”的模糊性问题，提出将基于Delaunay三角剖分导航网格的A*算法应用于室内导航路径规划中。文献[8]针对大型楼宇内部逃生路径规划问题，综合对比了经典路径规划算法的优劣并阐述了其在楼宇内部逃生疏散场景应用的算法思想和主要特征。文献[9]在对传统路径规划算法研究的基础上，对A*算法结构进行了优化，提高了算法的效率。

虽然学者们结合环境因素和人行为因素完善了高层建筑逃生路径规划算法的约束条件，或通过改进算法结构提高了算法效率，但在疏散过程中疏散效率随人员密度增加而降低的问题并没有得到有效解决[10]，拥堵问题仍会出现。因此，本文针对该问题在对A*算法进行改进的基础上提出一种逃生路径规划算法，旨在提高逃生疏散过程中的疏散效率，保证逃生路径的通畅性。

1 A*算法

1.1 基本原理

A*算法是一种在静态路网中求解最短路径的有效的直接搜索方法，它通过估价函数包含的启发信息快速锁定目标方向[11-13]。估价函数的计算方式如下

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

(1)

式中，f(n)代表从起点经过节点n到终点的估计代价；g(n)代表从起点到节点n的真实代价；h(n)为启发函数，代表从节点n到终点的启发式预计代价[8,11]。求解最短路径时，以距离为代价进行估价函数的计算。A*算法在执行过程中，将路径搜索场景以规则格网(本文以正方形格网为例)的形式进行分割，每1个格网代表1个节点。如图1所示，算法开始时首先引入两个集合，即开启列表(用于存储满足估价函数限定条件待遍历的节点，OpenList)和关闭列表(存储已经过遍历并不再进行遍历的点，CloseList)。在路径搜索过程中，以当前节点周围8个方向的邻接节点为扩展对象加入开启列表中，从中选择f(n)最小的格网移出开启列表并加入关闭列表中。以此类推，不断对节点进行扩展，当找到目标节点时完成路径规划。

1.2 算法分析

与Dijkstra算法和Flyod算法的暴力搜索方式不同，A*算法在执行过程中不需要对所有节点进行遍历，因此算法运行效率可有效提高。同时算法增加了约束条件，可针对不同应用环境制定路径规划策略，提高了算法的可扩展性。

但是，将A*算法直接运用在高层建筑逃生路径规划中时，仍然会出现以下问题：①逃生路径规划时直接设置逃生终点不利于人员的分流疏散，因此应结合逃生起点与火灾发生位置的距离合理规划逃生终点；②逃生路径规划过程中仅仅注重距离最短是不可取的，短时间内的人员快速聚集会导致疏散效率降低，因此还应综合更多因素为节点扩展提供评估条件，以提高逃生路径的通畅性；③节点扩展过程中如果直接对楼层平面进行格网划分，会造成冗余，降低算法效率，因此应结合楼层平面布局有针对性地进行分割。

2 高层建筑逃生路径规划算法设计与实现

2.1 算法改进

2.1.1 逃生终点优化分配

为了充分利用逃生通道，实现逃生过程中的分流疏散并降低拥堵现象发生概率，本文在进行路径搜索前，首先根据火灾发生的位置信息，按照与火灾位置的楼层距离对高层建筑楼层进行危险等级划分。主要划分成危险、威胁、暂时安全3个等级。针对不同危险等级，确定不同的逃生目标点，实现逃生人员的分流。

本文对楼层危险等级划分做出以下规定：①火灾发生楼层的危险等级设置为危险；②火灾发生楼层上下两层距离内的楼层危险等级设置为威胁；③在危险、威胁区域以外的楼层危险等级设置为暂时安全。算法执行时，首先根据起火位置对楼层进行危险等级划分，然后判断逃生起点的危险等级信息，针对不同危险等级设置对应的逃生终点，实现分流疏散。

2.1.2 节点扩展优化

为了提高逃生路径规划算法运行效率，本文对节点扩展过程进行了优化。根据高层建筑楼层平面布局，借鉴拓扑结构思想对房间、走廊、楼梯间等进行抽象，忽略形状大小的影响，用节点表示房间、楼梯间、走廊等关键点，用线段表示逃生路径，构造高层建筑内部路网拓扑结构。在保证高层建筑内部路网基本特征的前提下减少对非必要节点的遍历，降低节点扩展时邻接点的数量，提高算法运算效率。改进后的节点扩展如图2所示。

算法通过该方式进行节点扩展时，首先排除已经存在于CloseList和OpenList中的节点及障碍节点，然后对邻接节点进行遍历并寻求满足权值的节点加入OpenList中。算法执行过程中不再从8个方向获取邻接节点信息，只对具备拓扑邻接关系的节点进行遍历，有效提高了节点扩展效率，同时节点扩展也实现了在三维空间中的延伸(如图2(a)、(b)所示)。

2.1.3 权值优化

影响高层建筑逃生的因素主要分为以下3个方面：①火灾发生的状态，包括火灾发生位置、火灾蔓延速度、烟气浓度等；②高层建筑内人员状态，包括人员数量、人员分布、人员移动速度、人员密度等；③高层建筑内部特征，包括走廊宽度、疏散关键点分布等[13]。本文主要依据影响疏散效率的相关因素选用以下5个方面内容作为路径规划的权重并记录在属性表中。

(1) 火灾位置。火灾位置是影响逃生路径规划的主要因素之一，它直接影响逃生策略的制定。火灾位置在算法中以路网节点属性进行存储，包括空间坐标及楼层信息。本文主要通过火灾位置实现高层建筑内楼层危险等级的划分。

(2) 人员数量与分布。作为逃生的主体，人员数量与分布直接影响逃生路径的走向，同时也是权值计算的主要内容。人员数量是指火灾发生时楼内各个路网节点对应人员数量；人员分布主要记录各个楼层人数及位置分布。在算法中人员数量及其分布主要通过路网节点对应人数属性进行存储，通过路网节点对应空间坐标实现人员分布控制。

(3) 走廊面积。走廊面积由走廊长度和宽度决定，一般情况下，走廊面积与逃生过程中疏散效率成正比，走廊面积越大，逃生过程中疏散效率就会越高；反之，疏散效率越低。本文主要通过记录走廊长度和宽度实现走廊面积计算，在算法中计算走廊面积对应的长宽均由固定值表示。

(4) 人员密度。人员密度是逃生路径规划的关键影响因素，本文采用单位面积内人员的数量表示人员密度。算法中人员密度由路网节点对应人员密度属性存储，通过人员数量与走廊面积之比进行表示，用于节点扩展过程中估价函数h(n)的计算。

(5) 路网节点分布信息。路网节点分布信息用于描述各楼层房间分布信息及楼层与楼层之间逃生出口信息，它为火灾发生时人员的疏散引导提供指南。本文以空间坐标和节点类型的方式记录各路网节点的相关信息。

2.2 算法数据结构设计

根据前述路径规划权值的内容，算法的数据结构设计如下：

Struct NodeNet

{

private string nodeName; ∥记录节点名称

private string nodeType; ∥记录节点类型，主要分为房间节点、走廊节点、楼梯节点、电梯节点

private Point fatherNode;∥记录节点的父节点

private Point neibor;∥记录节点邻接节点

private int dangerousLevel;∥节点对应危险等级，危险为2，威胁为1，暂时安全为0

private int floor;∥记录节点对应楼层信息

private int X;∥记录节点位置信息

private int Y;

private int Z;

private int count;∥记录节点对应人数信息

private double G;∥从上一节点到当前节点的真实代价

private double H;∥启发函数计算值

private double F;∥估价函数计算值

private double density;∥记录节点对应人员密度

}

2.3 算法步骤

改进后的算法步骤如下：

(1) 输入路网数据G、起火点位置信息F、楼内总人数集合C及逃生起点S。

(2) 根据起火点F划分各楼层危险等级，判断起点S所在楼层的危险等级，如果为危险，转至步骤(3)；如果为威胁，转至步骤(4)；如果为暂时安全，转至步骤(5)。

(3) 设置起点S对应路径搜索目标点E1为最近安全楼层消防电梯节点。

(4) 设置起点S对应路径搜索目标点E2为危险楼层人员疏散完毕后消防电梯节点。

(5) 设置起点S对应路径搜索目标点E3为大楼出口节点。

(6) 将起点S加入开启列表中，设置S为当前节点，根据拓扑关系获得当前节点对应邻接节点，并加入开启列表中，设置父节点为当前节点。

(7) 将当前节点从开启列表中移出，加入关闭列表中。

(8) 遍历开启列表，进行如下判断：判断该点是否为障碍点，若该点是障碍点，则跳过该点；若该点不是障碍点，选择f(n)值最小的点S1，h(n)值最小的点S2。对S1和S2作如下判断：若S1对应h(n)值小于S2对应的h(n)值，则将S1加入开启列表中，并设置S1为当前节点；若S1对应h(n)值大于S2对应的h(n)值，则将S2加入开启列表中，并设置S2为当前节点。

(9) 重复步骤(6)—(8)，当路径搜索目标点存在于开启列表时，根据节点对应父节点返回路径信息，输出路径节点并绘制在计算机屏幕上。

高层建筑逃生路径规划算法流程如图3所示。

3 算法复杂度分析

假设路网中有n个节点，每个节点有k个邻接节点。完成路径求解需要以下几个过程：首先对n个节点的危险等级进行划分，对应时间复杂度为O(n)；其次确定当前节点危险等级，对应时间复杂度为O(1)；然后对邻接节点进行遍历向逃生终点靠近，考虑最坏的情况，需要遍历的邻接节点个数是4个(A*算法则需要遍历8个邻接节点)，对应时间复杂度为O(k2)(k≤4)；最后返回路径规划结果，对应时间复杂度为O(n)。因此改进后算法的时间复杂度为O(n+k2)，虽然与A*算法的时间复杂度一致，但降低了邻接点遍历次数，因此算法运行效率明显提高。

4 试验验证

本文选取某高层建筑为试验对象，对该建筑进行路网数据收集，其路网数据如图4所示。基于Visual Studio 2010开发环境使用C#编程语言结合EV-Globe SDK二次开发包实现了高层建筑逃生路径规划算法，并与A*算法进行了对比。算法效果如图5所示，其中图5(a)为算法改进前的路径规划效果，图5(b)为算法改进后的逃生路径规划效果。

通过算法的实现效果可以看出，改进后的算法根据不同区域的危险等级进行了有针对性的路径规划，同时考虑了人员密度、人员数量等因素，在逃生路径规划过程中不再一味追求距离最短，而更多地考虑了路径的通畅性。

5 结 语

本文针对高层建筑内部结构复杂、没有疏散引导的情况，以及逃生过程中疏散效率降低的问题，对A*算法进行改进，提出了适用于高层建筑的逃生路径规划算法。该算法通过对终点的优化分配、节点扩展的优化及权值优化3个方面的改进，实现了高层建筑内部的分流疏散，保证了逃生路径的通畅性。