疏散问题元胞自动机仿真方法

《疏散问题元胞自动机仿真方法》由会员分享，可在线阅读，更多相关《疏散问题元胞自动机仿真方法（21页珍藏版）》请在金锄头文库上搜索。

1、姓名：张雪蕾学号：201211131114姓名：崔星宇学号：201211131072姓名：王佳颖学号：201211131054基于元胞自动机的人员疏散仿真研究摘要：本文要仿真模拟学校某层教学楼中的人员疏散 1 ，主要方法是建立元胞自 动机模型。本文首先规定了学校教室和走廊的规格， 并将教室和走廊平面均匀地划分成 大小相等且符合实际的正方形网格， 每个网格作为一个元胞， 可以由教室中的学 生或者障碍物占据。 模型的建立是先将此楼层的人员疏散过程分成教室和走廊两 个部分分别考虑、并分别建立模型。在教室中， 根据每一个元胞距离教室门口的位置长短， 建立了元胞位置危险 度矩阵，然后在此基础上给出教室中

2、书桌所在元胞的位置和教室墙壁所在元胞的 位置。我们采用 Moore neighborhood 的元胞邻居方式，学生的行走方式取决于 其邻居八个元胞及其本身在位置危险度矩阵中所对应的危险度的大小； 有多个学 生竞争同一元胞时， 则采用生成随机数作为前进概率的方法， 概率最大的可以成 功抢到该目标元胞位置。 这样每一次时间步的更新， 都会有至多一个人走出本间 教室，一间 90 人的教室需要大约 26.25s 就可使教室人员全部走出教室。在走廊中， 我们考虑走廊只能至多三排学生并行的情况， 并规定走廊上的行 走规则与教室里的一致。我们采用扩展的 Von-Neumann neighborhood 的元

3、胞邻 居方式，学生的行走方式取决于其邻居五个元胞及其本身在位置危险度矩阵中所 对应的值的大小。每一时间步的更新会有至多三个人走出走廊。最终，我们将教室和走廊的情况整合在一起考虑， 得到了模拟学校学生在进 行疏散时的元胞自动机模型。 用此元胞自动机模型对该层教学楼的人员疏散问题 进行仿真模拟，若每一时间步为 0.25 秒，我们得到时间步更新次数为 333（即 83.25s ），四间教室共 360人均可全部逃离教学楼， 该结果与实际情况十分相符。 关键字：人员疏散 元胞自动机 位置危险度 随机数法一、问题重述和分析：某学校教学楼的某层，有一排4间相同的教室，学生们可以沿教室外的走廊 一直走到出口，

4、现用元胞自动机模型，模拟学生疏散的过程。由于教室和走廊都是矩形的，我们可以将教室和走廊都划分成二维网格的形 式，因而，我们不妨假设教室和走廊的分布如下图：在教室中时，学生在教室中的分布是由座位分布决定，灰色部分为座位区域， 黑色部分为墙壁和书桌。如果我们想要得到每个元胞的变化规则，就要制定每个 学生的行走规则。我们可以根据生活中的常识，人们一定会走向与出口距离更短的位置；当某元胞被墙壁、书桌和学生占据时，可以认为距离出口的长度为大于整间教室对角 线的长度的最小整数，除墙壁、书桌和学生以外的每个元胞上的值表示与门口的 距离，得到一张数字表格，此数字表格可以确定每个元胞的位置危险度， 危险度 越小

5、的元胞越安全。根据Moore neighborhood 的元胞邻居方式，每个学生每一时间步只需考虑周围八个邻居元胞及其本身所在位置的位置危险度。如果该九个元胞的位置危 险度存在唯一最小值，学生显然会选择该元胞作为下一个目标 （此时存在该元胞 的目标为自己的情况，即此元胞的不动）；由于该九个元胞的危险度可能存在多 个最小值，此时学生将以相同概率选择这几个元胞之一作为下一个目标，如图1所示。另外由于可能出现多个学生同时竞争一个元胞位置，则令这几个学生下一步走到该元胞的可能性相同，如图 2所示。由上述表述，可以得到每一个元胞的变化规则，且每一次时间步的更新表示 的是每个人只可能走至多一步，因而每一次

6、模拟至多有一个人走到教室的“门” 的位置，即认为其下一步将走出教室到达走廊。116（人）3.60564.47213.6056116，（人）116（人）4.472155.6569目标116l（人）116（人）图1图2研究走廊时，假设只能有3排人行走，学生到达走廊后，仍按照教室里的行 走规则行走，即人们一定会走向与出口距离更短的位置。当某元胞被墙壁和学生占据时，可以认为该元胞的位置危险度为大于整个教 学楼对角线的长度的最小整数，除墙壁和学生以外的每个元胞上的位置危险度表 示为与走廊门口的距离；当学生到达教室门口位置时，受心理因素影响，我们可 酌情将教室门口所在位置的位置危险度定义为其左侧元胞的位置

7、危险度，由此仍可得到与教室情况类似的一张元胞位置危险度表，危险度越小的元胞越安全。根据扩展的Von-Neumannneighborhood的元胞邻居方式，每个学生每一步只需考虑周围八个邻居元胞和自己的位置危险度。 如果该六个元胞的位置危险 度存在唯一最小值，学生显然会选择该元胞作为下一个目标 （此时存在该元胞的 目标为自己的情况，即此元胞的不动）；由于该六个元胞的危险度可能存在多个 最小值，此时学生将以相同概率选择这几个元胞之一作为下一个目标。由于可能出现多个学生同时竞争一个元胞位置，则令这几个学生下一步走到该元胞的可能 性相同。由上述表述，可以得到每一个元胞的变化规则，且每一次时间步的更新表

8、示 的是每个人只可能走至多一步，因而每一次模拟至多有 3个人走到走廊“出口” 的位置，即认为其下一步将走出走廊，逃离教学楼。二、假设：1、教室和走廊均为矩形；2、该楼层有四间教室，且教室布局完全相同，相邻教室共用一面墙壁；3、走廊长度为四间教室内部长度之和加上墙壁的长度；4、教室出口设置在左侧墙壁，走廊出口设置在走廊上方；5、该楼层共有116 X26个元胞，每个元胞的大小为0.4 X0.4m2 ；6、走廊内部有3排元胞，即最多只能有3排人行走；7、墙壁只占单排元胞，课桌和人占据单个元胞；三、模型建立与求解：教室部分：一般情况下，教室多为矩形，出口设置在左侧面墙壁，本文采用的教室如图 所示，白色

9、为过道区域，灰色为座位区域，黑色为课桌和墙壁，将教室平面划分 为二维网格，每个网格相当于一个元胞，大小为 0.4 X0.4m2 ，人员只能占据 一个元胞，在白色和灰色区域移动。每个格点对应一个位置危险度，人员根据其领域内格点的位置危险度确定下 一时刻的运动情况，采用Moore邻居2，人员可向8个方向运动或保持静止。每 一时步取0.25秒，教室内的人员每个时步更新一次。在整个演化过程中，人 员每次更新位置只能移动一个格点。人员运动规则如下：1）计算格点与出口的距离Sxy，设门的位置为（X,y）v（x- X0）2 + （y - y。）2（格点为空格）S（ x, y） = 116（格点被人、墙、书桌

10、占据）式中，（x,y）为元胞在系统中的坐标，x0、y0为门在系统中的坐标2）确定每个格点的位置危险度A（x,y）0（格点在门口处）A（x,y） = 116（格点被人、墙、书桌占据）Sxy（格点与出口的距离为Sxy ）其中x、y为格点位置,3）比较人员其邻域内各格点的位置危险度，位置危险度最小的格点作 为该人员下一时刻的运动目标格点。 若运动目标格点位置危险度小于该人员 所在格点的位置危险度，人员运动到该格点；大于等于该人员所在格点的位 置危险度，则该人员静止不动。4）在人员选择下一目标格点时，如果移动区域内存在多个位置危险度 最小值的格点，人员以相同的概率随机选择其中一个格点作为下一步目标格

11、点。5）模型采用并行更新，存在多人同时竞争一个空闲位置的情况，人员 之间存在冲突时，系统将以相等概率随机选择一个人占据该格点，被选择的 人将移动到该格点，没有被选中的人将留在原地保持位置不变。6）当人员移动到“门”所在的位置时，其下一时间步，具体情况根据 走廊人员移动规则确定。教室的情况:算法流程图:目标矩阵XNew D：新的教室人 员的分布New D选择目标矩阵(x,y) 位置的元胞位置P,QP为x坐标Q为y坐标矩阵H：成功抢 到(x,y)位置的 矩阵走廊部分:一般情况下，走廊也为矩形，且我们考虑走廊能走3排人的情况，出口设置 在上方，如图所示，白色为过道区域。因而我们可以建立一个包含所有教

12、室和走 廊的大小为116 X 26的大矩阵A,其中第1列代表走廊的墙，第2、3、4列代表 走廊，第5列表示教室的左侧含门的墙。按照教室划分网格的规则，将走廊平面 划分为二维网格，每个网格相当于一个元胞，大小为0.4 X0.4m22，人员只能占据一个元胞，在白色区域移动。每个格点对应一个位置危险度，人员根据其领域内格点的位置危险度确定下 一时刻的运动情况，采用扩展的Von-Neumanr邻居，人员可向5个方向运动或保 持静止。每一时步取0.25秒3，走廊内人员每个时步更新一次。 在整个演化过 程中，人员每次更新位置只能移动一个格点。人员运动规则如下：1）计算格点与出口的距离Sxy,设门的位置为（

13、Xo,yo）v（x- Xo）2 + （y- yo）2（格点为空格）S（x, y） = M（格点被人、墙、书桌占据）式中，（x,y）为元胞在系统中的坐标，X0、y为门在系统中的坐标，M为大于 整个楼层对角线长度的最小整数，在本题中为116。2）确定每个格点的位置危险度A（x,y）0（格点在出口处）A（x,y） = M（格点被人、墙占据）Sxy（格点与出口的距离为Sxy ）其中x、y为格点位置。同时我们将格点在门口处的位置危险度定义为其左 侧格点的位置危险度。3）我们认为当学生到达教室门口位置时，受心理因素影响，我们可酌情将教室门口所在位置的位置危险度定义为其左侧元胞的位置危险度。4）比较人员其邻

14、域内各格点的位置危险度，位置危险度最小的格点作为该人员下一时刻的运动目标格点。 若运动目标格点位置危险度小于该人员 所在格点的位置危险度，人员运动到该格点；大于等于该人员所在格点的位 置危险度，则该人员静止不动。5）在人员选择下一目标格点时，如果移动区域内存在多个位置危险度 最小值的格点，人员以相同的概率随机选择其中一个格点作为下一步目标格 点。6）模型采用并行更新，存在多人同时竞争一个空闲位置的情况，人员 之间存在冲突时，系统将以相等概率随机选择一个人占据该格点，被选择的 人将移动到该格点，没有被选中的人将留在原地保持位置不变。7）直到走廊里首次全为0时，所有学生都逃离教学楼。III iiii iiii iiii疏散后疏散前运行结果:N=180= = = = -= = -=三=N=332N=120N=30N=60= = =-=二三二三= -= =1N=270N=240N=300四、结论：在本题中，用该模型进行人员疏散仿真模拟，运行次数为333(即 83.25s )时，四间教室共 360 人可全部逃离教学楼。 该结果与实际情况相符，