一种面向人群疏散的高效分组方法
|
摘要
在人群疏散的过程中,个体会依据关系的亲密度产生分组现象,因此人群分组行为是人群疏散仿真中不可忽略的因素。家人、朋友、同事等会根据亲密度形成分组,在疏散过程中同组人群会聚集成簇。聚类分组时常用的k-mediods聚类算法对噪声敏感,容易陷入局部最优,只能发现球状簇,且对初始聚类中心点的选择敏感,在聚类准确度上不尽人意。而DBSCAN算法具有抗噪声能力强、可发现任意形状的簇、无须指定初始聚类中心等优点,但只能识别密度相近的簇。对此,文中提出了折半DBSCAN聚类算法。该算法首先对关系数据进行二分划分,将有关系的数据划分到一个网格中,然后根据每个网格的人群密度决定聚类半径ε,最后对每个网格进行DBSCAN聚类,因此该算法可识别密度不同的簇。人群聚类分组后,在加入同组内个体吸引力的社会力模型中驱动个体运动,并模拟关系密切程度对聚集程度的影响。实验结果表明,在考虑了现实生活中有关系的人群空间分布状况下,所提方法具有较高的聚类精度,可真实地再现现实场景中的人群疏散情况,可作为紧急情况下预测人群疏散时间和疏散状况的重要工具。
In the crowd evacuation process,individuals usually produce the grouping phenomenon according to the intimacy of the relationship.Therefore,the grouping behavior is a factor that can not be neglected in the evacuation simulation of the crowd.The family,friends and colleagues usually form a group according to the degree of intimacy and gather together to a cluster in the evacuation process.The commonly used k-mediods clustering algorithm is sensitive to noise and easy to fall into the local optimum.It can only find the spherical cluster and is sensitive to the selection of the initial clustering center point,which is unsatisfactory in the accuracy of clustering.The DBSCAN algorithm has the advantages of strong ability to deal with noise and can find clusters of arbitrary shape and without specifying the initial clustering center,etc.But it can only identify clusters of similar density.Therefore,this paper proposed a binary DBSCAN clustering algorithm.This algorithm firstly divides the relational data to a grid,then it determines the cluster radius ε according to the density of population of the grid,and finally it executes the DBSCAN clustering algorithm for each grid,so these clusters with different densities can be identified.After clustering,the individual movement is driven in the social force modelwhich adds the individual attraction in the same group.And the influence of the intimacy degree on the aggregation degree is simulated.The experimental results show that,considering the spatial distribution of connected pedestrians in real life,this method has higher clustering accuracy.It can reappear the evacuation situation in the real scene and can be used as an important tool to predict evacuation time and evacuation situation.
In the crowd evacuation process,individuals usually produce the grouping phenomenon according to the intimacy of the relationship.Therefore,the grouping behavior is a factor that can not be neglected in the evacuation simulation of the crowd.The family,friends and colleagues usually form a group according to the degree of intimacy and gather together to a cluster in the evacuation process.The commonly used k-mediods clustering algorithm is sensitive to noise and easy to fall into the local optimum.It can only find the spherical cluster and is sensitive to the selection of the initial clustering center point,which is unsatisfactory in the accuracy of clustering.The DBSCAN algorithm has the advantages of strong ability to deal with noise and can find clusters of arbitrary shape and without specifying the initial clustering center,etc.But it can only identify clusters of similar density.Therefore,this paper proposed a binary DBSCAN clustering algorithm.This algorithm firstly divides the relational data to a grid,then it determines the cluster radius ε according to the density of population of the grid,and finally it executes the DBSCAN clustering algorithm for each grid,so these clusters with different densities can be identified.After clustering,the individual movement is driven in the social force modelwhich adds the individual attraction in the same group.And the influence of the intimacy degree on the aggregation degree is simulated.The experimental results show that,considering the spatial distribution of connected pedestrians in real life,this method has higher clustering accuracy.It can reappear the evacuation situation in the real scene and can be used as an important tool to predict evacuation time and evacuation situation.
引文
[1] LIU G P,LIU H,LV L,et al.Relationship-integrated crowds simulation[J].Journal of Chinese Mini-Micro Computer Systems,2016,37(8):1735-1740.(in Chinese)柳广鹏,刘弘,吕蕾,等.融入关系分组的人群运动仿真[J].小型微型计算机系统,2016,37(8):1735-1740.
[2] FESTINGER L.A theory of social comparison processes[J].Human Relations,1954,7(7):117-140.
[3] TSAI J,FRIDMAN N,BOWRING E,et al.ESCAPES- Evacuation Simulation with Children,Authorities,Parents,Emotions,and Social comparison[J].Copyright,2013,50(6):563-564.
[4] LI Y,LIU H,LIU G P,ET A L.A grouping method based on grid density and relationship for crowd evacuation simulation[J].Physica A Statistical Mechanics & Its Applications,2017,473(1):319-336.
[5] TAN Y,HU R F,YIN G F.Adapted DBSCAN with multi- threshold[J].Journal of Computer Applications,2008,28(3):745-748.(in Chinese)谭颖,胡瑞飞,殷国富.多密度阈值的 DBSCAN 改进算法[J].计算机应用,2008,28(3):745-748.
[6] XIA L N.SA-DBSCAN:A self-adaptive density-based clustering algorithm[J].Journal of the Graduate School of the Chinese Academy of Sciences,2009,26(4):530-538.
[7] KUMAR K M,REDDY A R M.A fast DBSCAN clustering algorithm by accelerating neighbor searching using Groups method[J].Pattern Recognition,2016,58:39-48.
[8] HE X X,GUAN J Y,YE X Z,et al.A density-based and grid-based cluster centers determination clustering algorithm[J].Control and Decision,2017,32(5):913-919.(in Chinese)何熊熊,管俊轶,叶宣佐,等.一种基于密度和网格的簇心可确定聚类算法[J].控制与决策,2017,32(5):913-919.
[9] PATWARY M M A,PALSETIA D,AGRAWAL A,et al.A new scalable parallel DBSCAN algorithm using the disjoint-set data structure[C]//High Performance Computing,Networking,Storage and Analysis.IEEE,2013:1-11.
[10] HE Y,TAN H,LUO W,et al.MR-DBSCAN:a scalable MapReduce-based DBSCAN algorithm for heavily skewed data[J].Frontiers of Computer Science,2014,8(1):83-99.
[11] LAKOBA T I,KAUP D J,FINKELSTEIN N M.Modifications of the Helbing-Molnar-Farkas-Vicsek social force model for pedestrian evolution[J].Simulation,2005,81 (5):339-352.
[12] OSARAGI T.Modeling of pedestrian behavior and its applications to spatial evaluation[C]//Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems-Volume 2.IEEE Computer Society,2004:836-843.
[13] MOUSSA?D M,HELBING D,THERAULAZ G.How simple rules determine pedestrian behavior and crowd disasters[J].Proceedings of the National Academy of Sciences,2011,108(17):6884-6888.
[14] HUGHES R L.A continuum theory for the flow of pedestrians[J].Transportation Research Part B:Methodological,2002,36(6):507-535.
[15] HOOGENDOORN S,BOVY P.Gas-kinetic modeling and simulation of pedestrian flows [J].Transportarion Research Record:Journal of the Transportation Research Board,2000,1710(1):28-36.
[16] HELBING D,JOHANSSON A,AL-ABIDEEN H Z.Dynamics of crowd disasters:An empirical study[J].Physical Review E,2007,75(4):046109.
[17] STEFFEN B.A modification of the social force model by foresight[M]//Pedestrian and Evacuation Dynamics 2008.Berlin:Springer,2010:677-682.
[18] CAO M X,ZHANG G J,HUANG L J,et al.Crowd Animation Generation Method Based on Personalized Emotional Contagion[J].Computer Science,2017,44(6):306-311.(in Chinese)曹梦晓,张桂娟,黄丽君,等.基于个性化情绪感染的人群动画生成方法[J].计算机科学,2017,44(6):306-311.
[19] PARISI D R,GILMAN M,MOLDOVAN H.A modification of the Social Force Model can reproduce experimental data of pedestrian flows in normal conditions[J].Physica A Statistical Mechanics and Its Applications,2012,388(17):3600-3608.
[20] JI Q G,HE H,WANG F C.Social Force Model for Crowd Simulation Using Density Field[J].Computer Science,2015,42(6):12-17.(in Chinese)纪庆革,何浩,王福川.密度场下的短程社会力模型[J].计算机科学,2015,42(6):12-17.
[21] MUSSE S R,THALMANN D.A model of human crowd beha- vior:Group inter-relationship and collision detection analysis[J].Computer Animation and Simulation,1997,97(9):39-51.
[22] VIZZARI G,MANENTI L,CROCIANI L.Adaptive pedestrian behaviour for the preservation of group cohesion[J].Complex Adaptive Systems Modeling,2013,1(1):1-29.
[23] QIU F,HU X.Modeling group structures in pedestrian crowd simulation[J].Simulation Modelling Practice and Theory,2010,18(2):190-205.
[24] FU Y W,LIANG J H,LIU Q P,et al.Crowd Simulation for Evacuation Behaviors Based on Multi-agent System and Cellular Automaton[C]//International Conference on Virtual Reality and Visualization.IEEE,2015:103-109.
[25] QIU F,HU X.A Framework for Modeling Social Groups in Agent-Based Pedestrian Crowd Simulations[J].International Journal of Agent Technologies and Systems,2012,4(1):39-58.
[26] QIN X,LIU H,ZHANG H,et al.A collective motion model based on two-layer relationship mechanism for bi-direction pedestrian flow simulation[J].Simulation Modelling Practice and Theory,2018,84:268-285.
[27] ZHANG H,LIU H,QIN X,et al.Modified two-layer social force model for emergency earthquake evacuation[J].Physica A Statistical Mechanics and Its Applications,2018,492:1107-1119.
[28] LIU B,LIU H,ZHANG H,et al.A social force evacuation model driven by video data[J].Simulation Modelling Practice and Theo-ry,2018,84:190-203.
[29] XU X,ZHANG L,SOTIRIADIS S,et al.CLOTHO:A Large-Scale Internet of Things based Crowd Evacuation Planning System for Disaster Management[J].IEEE Internet of Things Journal,2018,99:1-1.
[30] LIU H,XU B,LU D,et al.A Path Planning Approach for Crowd Evacuation in Buildings Based on Improved Artificial Bee Colony Algorithm[J].Applied Soft Computing,2018,68:360-376.
[31] MOUSSA?D M,PEROZO N,GARNIER S,et al.The walking behaviour of pedestrian social groups and its impact on crowd dynamics[J].Plos One,2010,5(4):e10047.
[32] RODRIGUEZ A,LAIO A.Clustering by fast search and find of density peaks[J].Science,2014,344(6191):1492-1496.
[33] FRIDMAN N,KAMINKA G A.Comparing human and synthetic group behaviors:A model based on social psychology[C]//International Conference on Cognitive Modeling(ICCM-09).2009.
[34] FRIDMAN N,KAMINKA G A.Towards a cognitive model of crowd behavior based on social comparison theory[C]//National Conference on Artificial Intelligence.AAAI Press,2007:731-737.
[35] WANG L,CAI Y,XU Q.Modifications to Social Force Model [J].Journal of Nanjing University of Science and Technology(Natural Science),2011,35(1):144-149.(in Chinese)汪蕾,蔡云,徐青.社会力模型的改进研究[J].南京理工大学学报,2011,35(1):144-149.
[2] FESTINGER L.A theory of social comparison processes[J].Human Relations,1954,7(7):117-140.
[3] TSAI J,FRIDMAN N,BOWRING E,et al.ESCAPES- Evacuation Simulation with Children,Authorities,Parents,Emotions,and Social comparison[J].Copyright,2013,50(6):563-564.
[4] LI Y,LIU H,LIU G P,ET A L.A grouping method based on grid density and relationship for crowd evacuation simulation[J].Physica A Statistical Mechanics & Its Applications,2017,473(1):319-336.
[5] TAN Y,HU R F,YIN G F.Adapted DBSCAN with multi- threshold[J].Journal of Computer Applications,2008,28(3):745-748.(in Chinese)谭颖,胡瑞飞,殷国富.多密度阈值的 DBSCAN 改进算法[J].计算机应用,2008,28(3):745-748.
[6] XIA L N.SA-DBSCAN:A self-adaptive density-based clustering algorithm[J].Journal of the Graduate School of the Chinese Academy of Sciences,2009,26(4):530-538.
[7] KUMAR K M,REDDY A R M.A fast DBSCAN clustering algorithm by accelerating neighbor searching using Groups method[J].Pattern Recognition,2016,58:39-48.
[8] HE X X,GUAN J Y,YE X Z,et al.A density-based and grid-based cluster centers determination clustering algorithm[J].Control and Decision,2017,32(5):913-919.(in Chinese)何熊熊,管俊轶,叶宣佐,等.一种基于密度和网格的簇心可确定聚类算法[J].控制与决策,2017,32(5):913-919.
[9] PATWARY M M A,PALSETIA D,AGRAWAL A,et al.A new scalable parallel DBSCAN algorithm using the disjoint-set data structure[C]//High Performance Computing,Networking,Storage and Analysis.IEEE,2013:1-11.
[10] HE Y,TAN H,LUO W,et al.MR-DBSCAN:a scalable MapReduce-based DBSCAN algorithm for heavily skewed data[J].Frontiers of Computer Science,2014,8(1):83-99.
[11] LAKOBA T I,KAUP D J,FINKELSTEIN N M.Modifications of the Helbing-Molnar-Farkas-Vicsek social force model for pedestrian evolution[J].Simulation,2005,81 (5):339-352.
[12] OSARAGI T.Modeling of pedestrian behavior and its applications to spatial evaluation[C]//Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems-Volume 2.IEEE Computer Society,2004:836-843.
[13] MOUSSA?D M,HELBING D,THERAULAZ G.How simple rules determine pedestrian behavior and crowd disasters[J].Proceedings of the National Academy of Sciences,2011,108(17):6884-6888.
[14] HUGHES R L.A continuum theory for the flow of pedestrians[J].Transportation Research Part B:Methodological,2002,36(6):507-535.
[15] HOOGENDOORN S,BOVY P.Gas-kinetic modeling and simulation of pedestrian flows [J].Transportarion Research Record:Journal of the Transportation Research Board,2000,1710(1):28-36.
[16] HELBING D,JOHANSSON A,AL-ABIDEEN H Z.Dynamics of crowd disasters:An empirical study[J].Physical Review E,2007,75(4):046109.
[17] STEFFEN B.A modification of the social force model by foresight[M]//Pedestrian and Evacuation Dynamics 2008.Berlin:Springer,2010:677-682.
[18] CAO M X,ZHANG G J,HUANG L J,et al.Crowd Animation Generation Method Based on Personalized Emotional Contagion[J].Computer Science,2017,44(6):306-311.(in Chinese)曹梦晓,张桂娟,黄丽君,等.基于个性化情绪感染的人群动画生成方法[J].计算机科学,2017,44(6):306-311.
[19] PARISI D R,GILMAN M,MOLDOVAN H.A modification of the Social Force Model can reproduce experimental data of pedestrian flows in normal conditions[J].Physica A Statistical Mechanics and Its Applications,2012,388(17):3600-3608.
[20] JI Q G,HE H,WANG F C.Social Force Model for Crowd Simulation Using Density Field[J].Computer Science,2015,42(6):12-17.(in Chinese)纪庆革,何浩,王福川.密度场下的短程社会力模型[J].计算机科学,2015,42(6):12-17.
[21] MUSSE S R,THALMANN D.A model of human crowd beha- vior:Group inter-relationship and collision detection analysis[J].Computer Animation and Simulation,1997,97(9):39-51.
[22] VIZZARI G,MANENTI L,CROCIANI L.Adaptive pedestrian behaviour for the preservation of group cohesion[J].Complex Adaptive Systems Modeling,2013,1(1):1-29.
[23] QIU F,HU X.Modeling group structures in pedestrian crowd simulation[J].Simulation Modelling Practice and Theory,2010,18(2):190-205.
[24] FU Y W,LIANG J H,LIU Q P,et al.Crowd Simulation for Evacuation Behaviors Based on Multi-agent System and Cellular Automaton[C]//International Conference on Virtual Reality and Visualization.IEEE,2015:103-109.
[25] QIU F,HU X.A Framework for Modeling Social Groups in Agent-Based Pedestrian Crowd Simulations[J].International Journal of Agent Technologies and Systems,2012,4(1):39-58.
[26] QIN X,LIU H,ZHANG H,et al.A collective motion model based on two-layer relationship mechanism for bi-direction pedestrian flow simulation[J].Simulation Modelling Practice and Theory,2018,84:268-285.
[27] ZHANG H,LIU H,QIN X,et al.Modified two-layer social force model for emergency earthquake evacuation[J].Physica A Statistical Mechanics and Its Applications,2018,492:1107-1119.
[28] LIU B,LIU H,ZHANG H,et al.A social force evacuation model driven by video data[J].Simulation Modelling Practice and Theo-ry,2018,84:190-203.
[29] XU X,ZHANG L,SOTIRIADIS S,et al.CLOTHO:A Large-Scale Internet of Things based Crowd Evacuation Planning System for Disaster Management[J].IEEE Internet of Things Journal,2018,99:1-1.
[30] LIU H,XU B,LU D,et al.A Path Planning Approach for Crowd Evacuation in Buildings Based on Improved Artificial Bee Colony Algorithm[J].Applied Soft Computing,2018,68:360-376.
[31] MOUSSA?D M,PEROZO N,GARNIER S,et al.The walking behaviour of pedestrian social groups and its impact on crowd dynamics[J].Plos One,2010,5(4):e10047.
[32] RODRIGUEZ A,LAIO A.Clustering by fast search and find of density peaks[J].Science,2014,344(6191):1492-1496.
[33] FRIDMAN N,KAMINKA G A.Comparing human and synthetic group behaviors:A model based on social psychology[C]//International Conference on Cognitive Modeling(ICCM-09).2009.
[34] FRIDMAN N,KAMINKA G A.Towards a cognitive model of crowd behavior based on social comparison theory[C]//National Conference on Artificial Intelligence.AAAI Press,2007:731-737.
[35] WANG L,CAI Y,XU Q.Modifications to Social Force Model [J].Journal of Nanjing University of Science and Technology(Natural Science),2011,35(1):144-149.(in Chinese)汪蕾,蔡云,徐青.社会力模型的改进研究[J].南京理工大学学报,2011,35(1):144-149.