基于元胞自动机的人员疏散仿真研究

1、孟俊仙，周淑秋，饶敏：基于元胞自动机的人员疏散仿真研究2009,30(1 241 0引言人员聚集的大型场所如影剧院、体育馆、商场、超市等具有人群密度高、流动性大的特点，而且其建筑结构也比较复杂，一旦火灾发生，如果疏散不及时将造成严重的生命财产损失。因此，对人员疏散过程进行计算机仿真研究，可对建筑的安全疏散性能给出合理的评估，为建筑的设计者和使用者提供一个合理的安全疏散方案。目前人员疏散的计算机仿真模型主要分为两种类型1-4：第一类仅仅考虑建筑物及其各部分的疏散能力，这类模型通常叫做宏观仿真模型，它以人群整体运动作为分析目标，其对空间的构造通常以节点和连接为单位，特点是计算速度快，但无法描述疏散

2、过程中人的行为细节，计算结果有较大的偏差。第二类模型不仅考虑建筑物空间的物理特性，而且考虑每个个体对火灾的响应，通常叫做微观仿真模型，它以人员在人群中的个体特性作为分析对象，依照一定算法来驱动人员向出口行走，人的行为受到周围环境、建筑物结构等各种相互作用因素的影响。此类模型仿真度高，但计算量大，计算结果受驱动算法的影响大。1元胞自动机理论描述元胞自动机(cellular automata ，CA 模型是最具代表性的微观离散模型，最早由Von Neumann 和Ulam 提出。元胞自动机作为一个时间、空间、状态都离散的数学模型框架，通过单元间的相互作用来构造动态演化系统，具有较强模拟各种物理系统

3、和自然现象的能力。这是元胞自动机广泛应用于社会、经济、环境、地学、生物等领域的原因。目前，人们已经将元胞自动机应用到在交通流和行人流模型中，再现了真实交通流中各种现象的发展规律过程。元胞自动机最基本的组成包括元胞(Cell ，元胞空间(Lattice ，邻域(Neighbor ，规则(Rule 。元胞自动机可以视为由一个元胞空间和定义在该空间的变换函数所组成，可以用一个四元组表示5-9(1式(1 代表一个元胞自动机系统；是元胞的有限的离散的状态集合；=(2,ÊÇÁÚÓòÄÚÔª°

4、51;µÄ¸öÊý£»ÊôÓÚ=(1,2, ,ÊDZ仯¹æÔò£¬Îª½«ÉϵÄÒ»¸ö¾Ö²¿ 作者简介：孟俊仙(1979 ，女，山西太原人，硕士，研究方向为计算机仿真与虚拟现实；周淑秋(19

5、67 ，女，教授，硕士生导师，研究方向为计算机仿真技术；饶敏(1961 ，女，副教授，研究方向为计算机教学。基于元胞自动机的人员疏散仿真研究孟俊仙1，周淑秋2，饶敏3(1. 首钢工学院计算机系，北京100041；2. 中国劳动关系学院，北京100037；3. 首都师范大学，北京100037摘要：在人员聚集的大型场所，如果紧急事件发生则极有可能造成人员的大量伤亡，因此对人员疏散行为进行深入研究，具有极大的现实意义。通过分析已有的理论基础，利用元胞自动机原理建立了人员疏散数学模型。模型采用二维元胞自动机技术，确定了元胞空间和元胞状态，建立了人员疏散行为规则并着重探讨了从众行为和建筑结构不同对疏散时

6、间的影响。试验结果表明，该疏散仿真模型更具真实性和合理性。关键词：元胞自动机; 人群疏散; 疏散仿真; 仿真模型; 行为规则中图法分类号：TP391文献标识码：A文章编号：1000-7024(2009 01-0241-03Study on occupant evacuation simulation based on cellular automataMENG Jun-xian 1,ZHOU Shu-qiu 2,RAO Min 3(1. Shougang Institute of Technology, Beijing 100041, China; 2. China Institute of

7、Industrial Relations, Beijing 100037, China; 3. Capital Normal University, Beijing 100037, China Abstract ：When accidents occur in a large building of many people, it is very likely to cause injury or death. This makes the study of evacuation dynamics very necessary. Basic principle and structure of

8、 cellular automata (CA is analyzed, and occupant evacuation simulation model in big building is established by using CA rule. Based on math structure model, adopting the two-dimensional CA technology, the cellular space and cellular states are established, and the rule for person behavior is made. T

9、he influence of the following movement and different structures on the occupant behavior and evacuation time in several cases is mainly discussed. The results show that the evacuation simulation model is more real and reasonable.Key words ：CA; crowd evacuation; evacuation simulation; simulation mode

10、l; behavior rule计算机工程与设计Computer Engineering and Design2422009,30(1 计算机工程与设计Computer Engineering and Design转换函数。所有的元胞位于来确定。本文在已有模型理论的基础上，将进一步模拟同一疏散场所中不同人员可以根据自身情况采取不同的疏散行为模式，并着重探讨了不同建筑结构以及从众心理对疏散产生的影响，从而使该模型更具合理性，模拟能力更强，为大型建筑的疏散方案提出合理的评估意见。2人员疏散模型的建立人员疏散模型的建立需要考虑众多因素，如疏散空间的虚拟化，疏散路径的选择，疏散过程中人员行为的研究以及

11、各种影响因素的仿真，其中对人员行为进行研究是疏散仿真研究的重点也是难点。2.1疏散空间火灾发生在一定的区域，把疏散区域设定在一个二维的 在元胞空间中，每个元胞可以有以下几种状态：一被建筑或障碍物占据，二被人员占据，三为空。另外给元胞设定一个特殊的属性来描述火灾场景的蔓延情况。如果该元胞的烟雾达到一定浓度仍有人员处于其中则会对人的生命造成一定的 威胁。所有元胞(除被建筑物占据 的状态都在不断的发生变化，t+1时刻的元胞状态与t 时刻的状态以及其周围相邻元胞的状态相关。可以采用Von Neumann 或Moore 两种状态10，如图1所示，其中黑色的元胞为中心元胞，灰色元胞为其邻居。 2.2人员模

12、型的基本假定 (1 人员初始位置：人员处于元胞自动机的某个单元格中，可以随机产生或根据实际情况预先设定。(2 移动方向：每个人员可以移动到周围4个或8个元胞 中，如果某个元胞被建筑物或人员占据，则不能移入。当某个元胞的烟雾达到一定密度时，如果移入则有生命危险。 (3 冲突检测：当出现多个人员都选择同一个单元格时则需要进行冲突检测。在此引入个体竞争能力C来解决冲突问题。表示疏散人员的个体特性，当疏散人员为青壮年时，其 表示人员距该目 标点的方向值，一般认为目标点处于人员的前后左右时其值大于处于4个对角线的方向距离值。如果竞争力相同，则随机产生一个顺序进行疏散。2.3人员疏散的基本行为规则火灾发生

13、后人员在疏散过程中的行为模拟包括如何避免碰撞、绕行、排队、折返等各种复杂现象，对这些现象的模拟是疏散仿真研究的难点问题之一。本文从人员在虚拟平面内位置变化出发，提出了人员疏散遵循的基本规则，并在此基础上模拟疏散过程中的复杂现象。首先，所有人员将根据其所处网格的状态和邻域内所有网格的状态来选择领域网格吸引力概率最大的一个网格作为下一时间步的目标网格，其次在疏散时人员总是以寻找距离自己最近的出口为目标，这是最基本的行为模式；在考虑到火灾发生时，疏散过程中人员从众心理的影响，趋向于选择和别人相同的路线进行逃离; 当遇到火灾时，人员选择绕行。图2为人员下一步可能的移动方向和概率。在此引入几个概念参数作

14、为个体选择疏散路线的主要依据。(1网格位置吸引力概率, ,(3式中：,网格,距离出口最大的网格距离值，min ,距离出口最小的网格距离值。距离疏散出口越近的网格，其位置吸引力概率越大，反之距离疏散出口越远，其位置吸引力概率越小。(2 网格方向吸引力概率：人员模拟过程中，个体每一步移动都要先根据其视野范围内的所有人员的运动方向来做出决策，选择一个最优路径。(4式中：一定范围内=(0, ,8 9个单元格人员移动数量总和，0当前人员所在位置。(3 火灾场景排斥力：火灾发生时人员尽量选择远离火源的路径疏散，如果烟雾达到一定浓度，将对人员的生命造成威胁。1,×ʱ¿

15、;ÌÍø¸ñ,1,11,1,+1+1孟俊仙，周淑秋，饶敏：基于元胞自动机的人员疏散仿真研究2009,30(1 243 实验中主要从以下几种情形进行对比分析：一是建筑内结构不同情况下人员的疏散状况；二是在考虑出口吸引力和位置吸引力时，从众行为的权重设定对疏散时间的影响。表1为相同时间步长结构不同时已疏散人数对照表。图5为结构1和结构2两种建筑结构下人员疏散的过程图。表1和图5的实验数据表明，在疏散初期，两种建筑结构下同一时间疏散人数相当，到了疏散后期在结构2中部分人员由于紧张慌乱迷失了方向，导致疏散时间延长。可见，建筑物内的结构特征对疏散效率有一

16、定的影响作用，建议在大型建筑物内设置隔段或摆放大型物品货架时其位置最好与出口位置相对，当火灾或紧急事件发生时人员能够快速对出口位置做出判断。如果无法重新设置建筑物内结构，可以增加引导措施，便于人员找到出口位置。表2为从众行为权重设定不同情况下所用疏散时间步长对照表。表2的实验数据表明，s2=0.0时，只考虑出口吸引力单一因素其疏散过程所用时间较长，通过增加从众行为权重s2所占比值，疏散时间减小，疏散效率提高，当s2=0.9时，由于大多数人员的盲目从众，导致疏散效率下降，疏散所用时间变长。试验结果表明从众行为在疏散过程中具有一定的影响作用，是人员疏散行为研究必须考虑的一个主要因素，在从众行为权重

17、设置得当情况下可真实再现人员疏散的全过程。4结束语本文提出的基于元胞自动机技术的大型建筑内人员疏散行为模型，利用CA 在模拟复杂物理现象方面的优势，引入方向吸引力和火灾场景排斥力等因素，使得模型在模拟紧急情况下人员疏散路径的选择上更具合理性和真实性，但紧急状况下的人员疏散仍是一个非常复杂的过程，会受到周围环境、人员心理和生理等多方面因素的影响，本文不可能全部涉及，许多相关问题需要更深层次的探讨和完善。参考文献:1张培红, 陈宝智. 火灾时人员疏散行为规律J . 东北大学学报, 2001,22(1 :54-56.2Helbing D.A fluid dynamic model for the m

18、ovement of pedes-trians J .Complex Systems, 1992(6 :391-415.(下转第246页图3人员疏散仿真流程结束疏散结果分析与反馈显示疏散所用时间人员是否疏散完毕建筑物内疏散人员移动到新的位置Time+对于建筑物内的每个人员选择下一步疏散位置人员是否疏散完毕YN N是否有火源Time=0输入火源位置坐标输入人员位置和属性参数初始化建筑空间位置开始按照火势蔓延趋势计算下一步扩散位置初始化火源位置信息YYN90725334175疏散结束图5两种建筑结构下人员疏散过程(a t=0人数=90(b t=30人数=67(c t=70人数=26(d t=0人数

19、=90(e t=30人数=65(f t=70人数=36表2从众行为权重设定不同所用疏散时间步长对照出口吸引力权重(s1从众行为权重(s2疏散结束所用时间步长S1=1.0S1=0.5S1=0.3S1=0.2S1=0.1S2=0.0S2=0.5S2=0.7S2=0.8S2=0.92462009,30(1 计算机工程与设计Computer Engineering and Design足P2P-IPTV 的应用需求。对P2P-IPTV 体系结构进行了研究分析后，采用的搜索技术是基于Small World 理论的非结构化搜索算法和DHT 的结构化搜索算法。小世界重叠网协议(SWOP 旨在有效地寻找任何网

20、络中的对象，特别是在严重的网络负载的情况下，它可以采取高效率的方式进入动态的对象中。SWOP 是构建在P2P 网络结构的最顶层，它并没有影响P2P 网络层所提供的功能，反而改善了查找对象的性能。现有的网络采用基于DHT 的结构化的搜索算法，但因其体系结构呈现出高内聚性，故可以把这些网络分为一个个的小世界网络，再通过超级节点把这些网络资源联接起来了。在整个网络中查找资源，每条文件索引都被表示成一个(K,V 对，K 称为关键字，可以是文件名(或文件的其它描述信息 的哈希值，V 是实际存储文件的节点的IP 地址(或节点的其它描述信息 和该信息来自相对应的网络(是本地的，还是外部的小世界网络 。而在超

21、级节点上还是采用了P2P 网络，把这些超级节点连接形成一个环状。在SWOP 网络中8，用一个圆环作为合乎逻辑的代表，而它正是P2P 结构化网络中的一个代表模型，并且通过SWOP 有利于揭示小世界(small world 对P2P 网络的影响。定义SWOP 的一些参数如下：簇大小G ：簇中数最多节点数；簇距离d ：一个簇中相邻节点间最大的Hash 间距离；在群集中k 距离连接的数量。SWOP 网络中有两种类型的节点(头节点和内节点 和两种类型的链接(长链接和簇链接 。长链接连接两个不同簇中的不同节点，簇链接连接同一簇中两个不同的节点。每个簇中只有一个头节点，至少k 条长链接和簇链接连接簇中的所有

22、节点。在簇中，一个内节点有一个连接头节点的链接和一些连接簇中的其它节点的簇链接。在以上的设置中，一个内节点i 能与目标节点j 通信指在簇中簇链接(假设i 和j 是连通的 和节点i 都能发送消息给它的头节点，并且头节点通过簇链接转发该信息给节点j 。为了在不同的簇中的目标节点能够互相的通信，节点i 首先发送消息给头节点，然后头节点通过长链接(比较靠近目标节点j 发送消息给节点j 。节点j 也是采用这种方式通信的。这个处理过程一直反复，直到消息被转发到同一簇中和节点j 相同的节点。小世界网络具有高度聚集的特性，即每个节点的大部分的连接都连向附近的节点。基于小世界模型的对等网络也具备了该特性。因此，

23、如果能够使逻辑环上邻近的节点在网络拓扑空间也是邻近的，就可以保证大量应用层链路限制在底层网络的局部区域内，实现对等网络的拓扑意识。3结束语本文提出的基于P2P 的DHT 算法和基于Small World 理论的非结构化搜索算法相结合的一种P2P-IPTV 体系结构的模型，该模型继承了DHT 和Small World 的固有优点，同时，可扩展性好且易于实现管理，适合于面向Internet 上的文件共享、协同工作、电视点播的IPTV 的应用。将P2P 技术和Small World 融入到IPTV 的机顶盒中，使用户可以同时共享同一资源，可以用更低的成本提供更高质量、更大容量的流媒体业务，大大降低了

24、投资风险。理论分析表明了P2P-IPTV 模型的应用层链路的平均延时可以得到明显的减少，而且链接遍历的平均数也要低于传统的DHT 。参考文献:1Bu T,Towsley D. On distinguishing between Internet power law topology generators J . Kermani P . Proc of INFOCOM. New York,USA:IEEE Computer Society Press,2002:638-647.2Faloutsos M, Faloutsos P , Faloutsos C. On power-law relati

25、on-ships of the Internet topology C .Chapin L,Sterbenz J P G,Parul-kar G,et al.Proc of SIGCOMM. Cambridge,Massachusetts,USA:ACM Press,1999:251-262. 3Newman M E J.The structure and function of complex networks J .SIAM Review,2003,45(2 :167-256.4邓肯瓦茨. 小小世界:有序与无序之间的网络动力学M . 北京:中国人民大学出版社,2006:4-16.5Watt

26、s D J,Strogatz S H.Collective dynamics of small-world net-works J . Nature,1998,393:440-442.6Manku G S, Bawa M, Raghavan P. Symphony:Distributed Hashing in a small world C . Proc of the 4th USENIX Sympo-sium on Internet Technologies and Systems.Seattle,WA,USA:USENIX,2003:127-140.7Ken Y K Hui,John C S Lui. Small world overlay P2P networks J .Computer Networks,2006,50:15.3Matslshita,Olazaki.A study of simulation model far away fin-ding behavior by experiments in mazes J .