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

姓名：张雪蕾学号：201211131114姓名：崔星宇学号：201211131072姓名：王佳颖学号：201211131054基于元胞自动机的人员疏散仿真研究摘要：本文要仿真模拟学校某层教学楼中的人员疏散[1]，主要方法是建立元胞自动机模型。本文首先规定了学校教室和走廊的规格，并将教室和走廊平面均匀地划分成大小相等且符合实际的正方形网格，每个网格作为一个元胞，可以由教室中的学生或者障碍物占据。模型的建立是先将此楼层的人员疏散过程分成教室和走廊两个部分分别考虑、并分别建立模型。在教室中，根据每一个元胞距离教室门口的位置长短，建立了元胞位置危险度矩阵，然后在此基础上给出教室中书桌所在元胞的位置和教室墙壁所在元胞的位置。我们采用Mooreneighborhood的元胞邻居方式，学生的行走方式取决于其邻居八个元胞及其本身在位置危险度矩阵中所对应的危险度的大小；有多个学生竞争同一元胞时，则采用生成随机数作为前进概率的方法，概率最大的可以成功抢到该目标元胞位置。这样每一次时间步的更新，都会有至多一个人走出本间教室，一间90人的教室需要大约26.25s就可使教室人员全部走出教室。在走廊中，我们考虑走廊只能至多三排学生并行的情况，并规定走廊上的行走规则与教室里的一致。我们采用扩展的Von-Neumannneighborhood的元胞邻居方式，学生的行走方式取决于其邻居五个元胞及其本身在位置危险度矩阵中所对应的值的大小。每一时间步的更新会有至多三个人走出走廊。最终，我们将教室和走廊的情况整合在一起考虑，得到了模拟学校学生在进行疏散时的元胞自动机模型。用此元胞自动机模型对该层教学楼的人员疏散问题进行仿真模拟，若每一时间步为0.25秒，我们得到时间步更新次数为333（即83.25s），四间教室共360人均可全部逃离教学楼，该结果与实际情况十分相符。关键字：人员疏散元胞自动机位置危险度随机数法一、问题重述和分析：某学校教学楼的某层，有一排4间相同的教室，学生们可以沿教室外的走廊一直走到出口，现用元胞自动机模型，模拟学生疏散的过程。由于教室和走廊都是矩形的，我们可以将教室和走廊都划分成二维网格的形式，因而，我们不妨假设教室和走廊的分布如下图：在教室中时，学生在教室中的分布是由座位分布决定，灰色部分为座位区域，黑色部分为墙壁和书桌。如果我们想要得到每个元胞的变化规则，就要制定每个学生的行走规则。我们可以根据生活中的常识，人们一定会走向与出口距离更短的位置；当某元胞被墙壁、书桌和学生占据时，可以认为距离出口的长度为大于整间教室对角线的长度的最小整数，除墙壁、书桌和学生以外的每个元胞上的值表示与门口的距离，得到一张数字表格，此数字表格可以确定每个元胞的位置危险度，危险度越小的元胞越安全。根据Mooreneighborhood[4]的元胞邻居方式，每个学生每一时间步只需考虑周围八个邻居元胞及其本身所在位置的位置危险度。如果该九个元胞的位置危险度存在唯一最小值，学生显然会选择该元胞作为下一个目标（此时存在该元胞的目标为自己的情况，即此元胞的不动）；由于该九个元胞的危险度可能存在多个最小值，此时学生将以相同概率选择这几个元胞之一作为下一个目标，如图1所示。另外由于可能出现多个学生同时竞争一个元胞位置，则令这几个学生下一步走到该元胞的可能性相同，如图2所示。由上述表述，可以得到每一个元胞的变化规则，且每一次时间步的更新表示的是每个人只可能走至多一步，因而每一次模拟至多有一个人走到教室的“门”的位置，即认为其下一步将走出教室到达走廊。研究走廊时，假设只能有3排人行走，学生到达走廊后，仍按照教室里的行走规则行走，即人们一定会走向与出口距离更短的位置。当某元胞被墙壁和学生占据时，可以认为该元胞的位置危险度为大于整个教学楼对角线的长度的最小整数，除墙壁和学生以外的每个元胞上的位置危险度表示为与走廊门口的距离；当学生到达教室门口位置时，受心理因素影响，我们可酌情将教室门口所在位置的位置危险度定义为其左侧元胞的位置危险度，由此仍可得到与教室情况类似的一张元胞位置危险度表，危险度越小的元胞越安全。根据扩展的Von-Neumannneighborhood[4]的元胞邻居方式，每个学生每一步只需考虑周围八个邻居元胞和自己的位置危险度。如果该六个元胞的位置危险度存在唯一最小值，学生显然会选择该元胞作为下一个目标（此时存在该元胞的目标为自己的情况，即此元胞的不动）；由于该六个元胞的危险度可能存在多个最小值，此时学生将以相同概率选择这几个元胞之一作为下一个目标。由于可能出现多个学生同时竞争一个元胞位置，则令这几个学生下一步走到该元胞的可能性相同。由上述表述，可以得到每一个元胞的变化规则，且每一次时间步的更新表示的是每个人只可能走至多一步，因而每一次模拟至多有3个人走到走廊“出口”的位置，即认为其下一步将走出走廊，逃离教学楼。116（人）3.60564.47213.6056116（人）116（人）4.472155.6569目标116（人）116（人）图1图2二、假设：1、教室和走廊均为矩形；2、该楼层有四间教室，且教室布局完全相同，相邻教室共用一面墙壁；3、走廊长度为四间教室内部长度之和加上墙壁的长度；4、教室出口设置在左侧墙壁，走廊出口设置在走廊上方；5、该楼层共有116×26个元胞，每个元胞的大小为0.4×0.4m2；6、走廊内部有3排元胞，即最多只能有3排人行走；7、墙壁只占单排元胞，课桌和人占据单个元胞；三、模型建立与求解：教室部分：一般情况下，教室多为矩形，出口设置在左侧面墙壁，本文采用的教室如图所示，白色为过道区域，灰色为座位区域，黑色为课桌和墙壁，将教室平面划分为二维网格，每个网格相当于一个元胞，大小为0.4×0.4m2，人员只能占据一个元胞，在白色和灰色区域移动。每个格点对应一个位置危险度，人员根据其领域内格点的位置危险度确定下一时刻的运动情况，采用Moore邻居[2]，人员可向8个方向运动或保持静止。每一时步取0.25秒[3]，教室内的人员每个时步更新一次。在整个演化过程中，人员每次更新位置只能移动一个格点。人员运动规则如下:1)计算格点与出口的距离Sxy,设门的位置为(x0,y0)S(x,y)={√(x−x0)2+(y−y0)2（格点为空格）116（格点被人、墙、书桌占据）式中，(x,y)为元胞在系统中的坐标，x0、y0为门在系统中的坐标。2)确定每个格点的位置危险度A(x,y)A(x,y)={0（格点在门口处）116（格点被人、墙、书桌占据）Sxy（格点与出口的距离为Sxy）其中x、y为格点位置，3)比较人员其邻域内各格点的位置危险度，位置危险度最小的格点作为该人员下一时刻的运动目标格点。若运动目标格点位置危险度小于该人员所在格点的位置危险度，人员运动到该格点；大于等于该人员所在格点的位置危险度，则该人员静止不动。4)在人员选择下一目标格点时，如果移动区域内存在多个位置危险度最小值的格点，人员以相同的概率随机选择其中一个格点作为下一步目标格点。5)模型采用并行更新，存在多人同时竞争一个空闲位置的情况，人员之间存在冲突时，系统将以相等概率随机选择一个人占据该格点，被选择的人将移动到该格点，没有被选中的人将留在原地保持位置不变。6)当人员移动到“门”所在的位置时，其下一时间步，具体情况根据走廊人员移动规则确定。教室的情况：N=10N=30N=60N=90N=105算法流程图：矩阵A：给出教室每个元胞的位置危险度矩阵D：给出教室人员的分布矩阵E：给出元胞判定准则的九宫格目标矩阵X选择目标矩阵(x,y)位置的元胞位置P,QP为x坐标Q为y坐标矩阵H：成功抢到(x,y)位置的矩阵NewD：新的教室人员的分布NewD=D+X-H走廊部分：一般情况下，走廊也为矩形，且我们考虑走廊能走3排人的情况，出口设置在上方，如图所示，白色为过道区域。因而我们可以建立一个包含所有教室和走廊的大小为116×26的大矩阵A，其中第1列代表走廊的墙，第2、3、4列代表走廊，第5列表示教室的左侧含门的墙。按照教室划分网格的规则，将走廊平面划分为二维网格，每个网格相当于一个元胞，大小为0.4×0.4m2[2]，人员只能占据一个元胞，在白色区域移动。每个格点对应一个位置危险度，人员根据其领域内格点的位置危险度确定下一时刻的运动情况，采用扩展的Von-Neumann邻居，人员可向5个方向运动或保持静止。每一时步取0.25秒[3]，走廊内人员每个时步更新一次。在整个演化过程中，人员每次更新位置只能移动一个格点。人员运动规则如下:1)计算格点与出口的距离Sxy,设门的位置为(x0,y0)S(x,y)={√(x−x0)2+(y−y0)2（格点为空格）M（格点被人、墙、书桌占据）式中，(x,y)为元胞在系统中的坐标，x0、y0为门在系统中的坐标，M为大于整个楼层对角线长度的最小整数，在本题中为116。2)确定每个格点的位置危险度A(x,y)A(x,y)={0（格点在出口处）M（格点被人、墙占据）Sxy（格点与出口的距离为Sxy）其中x、y为格点位置。同时我们将格点在门口处的位置危险度定义为其左侧格点的位置危险度。3)我们认为当学生到达教室门口位置时，受心理因素影响，我们可酌情将教室门口所在位置的位置危险度定义为其左侧元胞的位置危险度。4)比较人员其邻域内各格点的位置危险度，位置危险度最小的格点作为该人员下一时刻的运动目标格点。若运动目标格点位置危险度小于该人员所在格点的位置危险度，人员运动到该格点；大于等于该人员所在格点的位置危险度，则该人员静止不动。5)在人员选择下一目标格点时，如果移动区域内存在多个位置危险度最小值的格点，人员以相同的概率随机选择其中一个格点作为下一步目标格点。6)模型采用并行更新，存在多人同时竞争一个空闲位置的情况，人员之间存在冲突时，系统将以相等概率随机选择一个人占据该格点，被选择的人将移动到该格点，没有被选中的人将留在原地保持位置不变。7)直到走廊里首次全为0时，所有学生都逃离教学楼。疏散后疏散前运行结果：N=60N=120N=180N=270N=300N=332N=240N=30四、结论：在本题中，用该模型进行人员疏散仿真模拟，运行次数为333（即83.25s）时，四间教室共360人可全部逃离教学楼。该结果与实际情况相符，所以模型的仿真效果良好。五、检验：我们将模型运行30次，得到不同的运行次数，分别为：333,340,334,328,339,322,335,336,333,339,337,331,340,335,332,338,326,334,330,329,334,319,334,329,333,332,331,335,329,344。对此我们求得其均值为333.0333，方差为28.1023，方差所表示的相差的时间约为7.1s,因此模型是比较稳定的。六、参考文献：[1]刘来福，黄海洋，曾文艺．数学模型与数学建模．北京：北京师范大学出版社．2009．[2]薛鹏，周金旺，白克钊，孔令江，刘慕仁．多房间中人员在走廊疏散的元胞自动机模拟研究．广西师范大学物理科学与技术学院，广西桂林541004[3]刘永淇.室内人员疏散的元胞自动机模拟研究.广西师范大学硕士学位论文2011年4月[4]七、附录：Matlab代码附录一，教室情况：function[D]=choic(D)A=zeros(29,22);%生成一个29行22列的零矩阵，并且处理好后的A矩阵将表示每个元胞对门口的渴望程度B=ones(25,22);%生成25行22列的每个位置是1的矩阵，这个是为了处理A(5:29,:)=sqrt((cumsum(B,1)-1).^2+(cumsum(B,2)-1).^2);%运用计算技巧计算好每个元胞距门口的距离C=ones(4,22);%生成4行22列的每个位置是1的矩阵A(1:4,:)=sqrt((cumsum(C,1)-5).^2+(cumsum(C,2)-1).^2);%运用计算技巧计算好每个元胞距门口的距