人群建模仿真算法的研究与系统实现

1绪论

1.1论文的背景与意义

21世纪是信息爆炸的世纪，然而飞速增长的不仅仅是虚拟的信息，还有规模庞大的人口。根据2021年国家人口普查数据统计，中国人口己经达到了接近14亿,而2021年全世界总人口更是已经达到了接近77亿，这与20世纪初，全世界总人口只有不到20亿形成了鲜明的对比。图1-1为世界人口变化示意图，可以看出人口的增长依然十分迅速。人口的爆炸在带来更多生产力的同时，也会带来很多问题。抛开人口因素对于政治、经济等层面的影响不谈，大规模公共场所的人群活动中始终存在着很多的安全隐患，极有可能发生诸如推搡，探踏等等事故，给人民的正常生活带来威胁。图1-2为麦加朝圣现场图，图1-3为2021年元旦在上海跨年时发生的探踏事故现场图[2]。此外，在人们身边进行的一些政治活动、商业活动、军事行动，或者一些由社会上的极端分子，因其对社会存在的消极、不满情绪逐渐堆积，在外部刺激的作用下爆发所引起的突发事故，这些行为都会通过对当地人群行为的作用，使得所造成的影响不断扩大。因此，倘若能够对人群的行为进行预测、模拟、控制，就可以有效地规避，消除可能存在的安全隐患。而如果想要在这些舌动中，有计划地减少可能带来的骚动或者损失，对人群行为的模拟预测是十分必要的。

1.2国内外研究现状分析

国内外对于人群仿真的研宄早己起步。而为了使对领域内研宄现状的阐述更加清晰明确，本节中将首先对人群仿真研宄的核心内容进行阐述，即人群仿真研究的三要素。而后将就现有方法的分类进行描述，包括不同类型方法的区别和适用性等。最后将列举国内外研宄的相关实例，同时阐明所列举方法所属于的具体仿真方法类别。针对于人群仿真不同方面的应用，已有的人群仿真研宄将其研宄重点大体可以分成三个方面，即路径规划问题、行为决策问题、动画表现问题；这三点也被称为是人群仿真研宄关注的三要素[4]。路径规划问题，也叫导航问题。该问题关注的是如何驱使所仿真的个体使他们在虚拟环境中按照要求运动，从而使整个人群的活动得到表述。导航问题通常是通过实现一些路径规划导航算法来解决的。行为决策问题关注的是针对某些情景，如突发的爆炸或者火灾等，所仿真的个体应当采取什么应对方式。在处理决策问题时，通常是设置一些决策规则，然后按照这些决策规则来对个体的行为进行决策。然后这些规则的设置通常十分的直观并且具有一定的情景对应性，即对于某些情景适用的规则可能对于其他情景并不适用，目前还没有一个科学有效的办法能够证明所设置的决策规则的通用性。动画表现问题对应的主要应用就是数字媒体娱乐领域，以及所构建的人群仿真系统的一些交互应用等。对于动画好坏的评判，更多的是一些SMEs (SubjectMatter Experts)利用他们知识和经验与可视化的人群比较从而得出的结论。

..

2人群场景的宏观仿真建模

2.1区域分割

区域分割部分的主要工作是对待仿真场景的环境建模，即虚拟场景在计算机中应当如何存储、表示。整个区域分割的过程相当于简化了待仿真的场景；同时，适当的区域分割算法也可以给局部的仿真带来便利（如可以规避由于场景中一些转角或者场景大型障碍物遮挡等带来的势场法中的局部最小值问题）。对于场景的表述来说，最基本的方法就是常规的栅格法[34](Grid-based Method)。栅格法最早由Howden于1968年提出，他在进行路径规划时釆用了栅格结构(Grid)来对地图进行表示。对于栅格法来说，其以矩阵的形式存储场景中的可达区域，对于距离和关联性的计算都相对精确，但是由于矩阵的存储形式使得一般场景的存储没有进行压缩，因此存储的占用会比较大。而且由于具体应用是栅格粒度的不同，很容易忽略掉场景中的一些细节（栅格过大时）或者带来过大的计算存储开销（栅格过密时）。图2-1[35]中的(a)图就展示了对于相同场景中应用栅格法时的情况。场景中不断添加端点来得到的。不同于栅格法中的场景中每一个位置都对应栅格中的一个格子，PRM方法在场景中随机选取非障碍物的可达点，然后通过应用局部路径规划判断这两点之间是否存在通畅的边来连接（通常使用直线连接即可），逐渐添加随机点直到构成的图的规模满足预先设定的停止条件。

..

2.2全局路径规划

全局规划是整个层次式结构设计的一部分，其目的是获得一条全局路径来指导之后局部的具体仿真。需要注意的是，全局路径并不是仿真对象所严格行进的路径，而更多的起到的是一种指示，指引的作用，可以类比为公共场所中的Exit安全出口标志牌。因而在全局规划时，可以使用路径搜索算法，如A*算法或者Dijstra算法在所获得的拓扑结构中搜索全局的路径。路径的起点和终点可以是所获得拓扑图中的待仿真个体可能位于的任意节点，当然这样所要计算的路径数目可能会很大，而且会有一些被覆盖的冗余路径。此时，我们可以通过结合人群运动的特征来简化路径的运算。对于全局路径的搜索，应用搜索算法从而搜索到全局最优的路径。在前文中我们讨论过这些算法在人群仿真中的应用。由于人群规模很大，场景十分复杂，因此在整个场景中对每个个体都应用一遍路径搜索算法所带来的幵销是很巨大的。而此时我们并不是针对每个仿真个体都搜索其具体的路径，而是在拓扑图上，对于某个特定的区域，确定其所应该行进的全局路径。此时的开销等因素都不再构成问题。

3人群的微观仿真建模..........21

3.1基于改进的势场法的人群建模..........21

3.2交通流模型..........30

3.3基于改进的势场法与交通流模型的微观人群仿真..........32

3.4 本章小结..........36

4人群仿真系统的实现与实验结果..........37

4.1人群仿真系统的分析与设计..........37

4.2开发环境及原型系统介绍..........40

4.3 实验结果..........44

5总结与展望..........51

5.1工作内容总结..........51

5.2未来工作展望..........51

4人群仿真系统的实现与实验结果

前文中对于所提出的基于改进的势场法和交通流理论速度密度关系模型的人群仿真方法进行了详细的阐述。其中介绍了本文主要的创新点，即通过引入速度密度关系模型，改善势场法速度控制机制，从而对传统势场法中存在的最大速度问题;提出了相应的处理方案。通过对于势场法本身的改进，使得该方法更加适用于人群仿真。为了能够直观地表现出本文所做出的改动，同时将本文所述方法的优点体现出来。本章将具体介绍基于本文所述人群仿真方法的人群建模仿真原型系统的构建。依托所构建的原型系统可以构造若干实验，从而使本文前文所述对于最大速度问题;的理论推导得到验证，使对于势场法的改动能够较直观地体现出来，也使得本文所述方法在人群建模仿真实践中的有效性得到展示。宏观场景建模层对应Delaunay三角划分模块：对于所输入的场景结构信息，需要给出其Delaunay三角划分的结果。由于场景结构信息是由场景中的结构点表示的，而这些结构点就是三角划分中的点集，因此模块的输出为三角划分的边集，以及所构成所有三角形的重心位置。由三角形的重心位置和邻接三角形之间的连通关系，就可以得到场景的拓扑表述，即拓扑结构图。

总结

本文第一至四章的内容己经详细描述了本文中所提出的层次式人群仿真方法的理论知识，以及相对应的人群仿真系统的构建。其中微观仿真部分的结合改进的势场法与速度密度关系模型的人群微观仿真是本文研究内容的核心，也是相比于传统基于势场法的人群仿真的优势之所在。而对于层次式的人群仿真方法架构，近几年来在关于人群仿真的学术论文中被广泛地使用。究其原因就是层次式的方法的泛用性要强于一般方法，而且层次式的方法在优化和改进上，思路更加的清晰，实现更加简洁。在国内的一些相关文章中，会把所述层次式方法按照层次分成场景建模层，路径层，仿真层，局部仿真层等等，其中局部仿真层主要针对的是局部的一些碰撞避免事宜。而本文中根据各个具体方法所围绕的核心内容，将整个层次式的方法按照其逻辑关系分成了全局和局部两部分。在这两部分中，又都分别包含了具体的内容。如全局路径规划部分包含了区域分割（即场景表述）和全局路径规划，局部仿真部分包含了基于改进势场法的局部仿真和基于交通流理论速度密度关系模型的速度优化。从逻辑上讲同一层内部的相互依赖的关系更加紧密，因此将其划分在同一层次。

............

参考文献(略)