人群模拟


人群模拟 Crowd simulation是对大量实体或人物的运动进行模拟的过程。[1]它常用于电影和视频游戏等视觉媒体中创建虚拟场景,也用于危机培训、[2]建筑和城市规划[3] 以及 人群疏散模拟 Evacuation Simulations[4]


人群模拟专注的方面可以针对不同应用。为了对 视觉媒体 visual media 虚拟摄影 virtual cinematography中的人群进行真实和快速渲染,可以减少 3D 场景的复杂性和基于图像的渲染,[5] 而外观的变化有助于展现一个真实的人群。[6][7]


在模拟真实人群运动的游戏和应用程序,比如人群疏散模拟中, 模拟的主体 Simulated Agents可能需要到达某个目标,避免碰撞,并表现出其他类似人的行为。现在已经有很多种 人群引导算法 Crowd Steering Algorithms能实际地引导模拟人群到达他们的目标。一些更普通的系统被研发出来支持不同的主体类型(如汽车和行人),[8]不同的抽象层次(如个体和 连续体 Continuum),[9]可以和智能对象交互的主体,[10]以及更复杂的物理和社会动态。[11]


历史

理解和控制人群的运动和行为一直是人们的兴趣所在。人群模拟领域的研究开始以来,人们已经取得了许多重大进展。显然,许多新发现正不断地被提出、被发表。这些发现提高了仿真模拟的可扩展性、灵活性、适用性和真实性 :


1987年,克雷格·雷诺兹 Craig Reynolds引入并发展了 行为动画 behavioral animation[12]为了研究群体直觉和运动,他模拟了一群鸟和一群鱼。在这些模拟中的所有主体都可以直接访问它们周围各个主体的位置和速度。雷诺兹建立的理论和研究是在Xiaoyuan Tu、特佐普洛斯 Demetri Terzopoulos和格兹兹丘克 Radek Grzeszczuk1994年的研究之上改进和发展的。.[13] 该模拟的真实性是有保证的,因为个体主体拥有合成视觉并对它们的居住环境有总体了解,从而可以对动态的栖息地有感性的认识。


最初的人群模拟领域研究始于1997年丹尼尔·塔尔曼 Daniel Thalmann指导苏拉娅·劳普·米塞尔 Soraia Raupp Musse的博士论文。他们两人提出了一个新的人群行为模型,以创建一个一般人群的仿真模拟。[14] 在这个模型中,他们给出了群体中个体的自主行为和由此产生的行为之间的一种关系。[15]


1999年,通过雷诺兹的持续研究, 个人主义导航 individualistic navigation开始了它在人群模拟领域的进程。[16]仿真中, 指导行为Steering Behaviors在自动化主体过程中起着重要的作用。雷诺兹指出,低水平运动的过程依赖中等水平的指导行为和高水平的目标状态以及 路径寻找策略 Path Finding Strategies。在 雷诺兹工作的基础之上,米塞尔和塔尔曼开始研究人群的实时模拟模型,以及它们在人类行为中的应用。对人群的控制被指定为一个具有不同主体自治水平的等级组织。这标志着在类人主体上以最基本的形式建立个体行为模型的开始。[17]


和人类行为模型和群体行为模拟的论文发表恰巧同一时期,马特•安德森 Matt Anderson、埃里克•麦克丹尼尔 Eric McDaniel和史蒂芬·切尼Stephen Chenney关于行为约束的研究计划[18]大受欢迎。他们展示了对 群体动画 Group Animations约束的定位能够在程序模拟中的任何时候完成。将约束应用到行为模型的过程分为两步: 首先,确定与约束条件一致的初始的 目标轨迹 goal trajectories集;然后,将行为规则应用到这些路径上,去选择那些不违反约束条件的路径。


塔尔曼基于他和米塞尔合作中提出的研究成果,和布拉迪斯拉发·乌利奇尼 Bratislava Ulicny以及巴勃罗·德·赫拉斯·切科姆斯基 Pablo de Heras Ciechomski提出了一种新的模型。这种模型允许在个人、一个群组和整个群体的层面上进行主体的 交互式创作 Interactive Authoring。他们引入了一个刷子隐喻,在即时反馈的情况下来进行实时分配、建模和控制人群成员。.[19]


人群动态

人群模拟的主要目标之一是真实地引导人群并重现人类的动态行为。


人群模拟和人工智能有几种主要的方法,每种方法根据人群规模和时间尺度具有不同的优缺点。时间尺度是指仿真的目标如何也会影响仿真的时间长度。例如,研究诸如意识形态在人群中的分布等社会问题将导致模拟运行的时间更长,因为意识形态分布这样的事件可能长达数月或数年。利用这两个特点,研究人员已经试图分类现有的人群模拟器,以更好地评估和组织它们。[20]


基于流的方法 Flow-based Approach: 基于流的人群模拟关注于人群作为一个整体,而不是人群的各种组成部分。这样人群中的个体没有任何独特的行为是由于他们周围的环境引起的,行为因素在很大程度上被减少了。[21]该模型主要用于估计给定环境下大型密集人群的运动流 the flow of movement。最适用于研究人群大、时间短的目标。


基于实体的方法 Entity-based Approach: 属于这种类别方法的模型会实施一系列物理的、预先确定的整体规则,这些规则旨在模拟发生在属于群体的个人身上的社会/心理因素。在这类模型中,实体在某种意义上没有自己思考的能力。他们所有运动都是由整体规则决定的。这个模型的仿真模拟经常用来研究人群动态,例如拥挤jamming和聚集。中小型群体和较短时间的目标适合使用这种方法。


基于主体的方法 Agent-based Approach: 该方法的特点是拥有自治的、互动的个体。在这种方法中,人群中的每个主体都被赋予了一定程度的智能; 他们可以根据一组决策规则自行对每个情况做出反应。主体用来决定一个行动的信息是从其周围获得的局部信息。这种方法最常见是被用来模拟现实的人群行为,因为研究人员可以完全自由地执行任何行为。


粒子系统

一种模拟虚拟人群的方法是使用粒子系统 Particle System。1983年,W·T·里夫斯 W. T. Reeves 在计算机图形学 Computer Graphics中首次引入了粒子系统。[22]粒子系统是很多单个元素或粒子的集合。每个粒子都能够自主行动,并被赋予一组物理属性(如颜色、大小和速度)。


粒子系统是动态的,因为粒子的运动随着时间而改变。粒子系统的运动使这种方法很理想,且易于实现。计算这些粒子的运动只需要很少的时间。它仅仅涉及到物理学: 作用在一个粒子上的所有力的总和决定了它的运动。力包括了诸如重力、摩擦力、碰撞产生的力,以及诸如目标的吸引力之类的社会力。


通常每个粒子都有一个速度矢量和一个位置矢量,分别包含粒子当前的速度和位置信息。将粒子的速度矢量加到其位置矢量上,从而计算粒子的下一个位置。这是一个非常简单的操作(并再次说明了为什么粒子系统如此理想)。速度矢量在作用力影响下随时间变化。例如,与另一个粒子的碰撞将导致一个粒子改变方向。


粒子系统已经广泛应用于电影,如制作爆炸特效。具体的例子包括2000年的电影《完美风暴 The Perfect Storm》的水特效,以及1994年的电影《面具 Mask》的模拟气体特效等。


然而,粒子系统确实有一些缺点。使用粒子系统模拟那些领导会根据指令行动行动的人群中的主体,可能是个坏主意,因为确定哪些粒子属于主体,哪些不属于主体是非常困难的。


帕蒂尔 Patil和范登博格 Van Den Berg的算法

帕蒂尔 Patil和范登博格 Van Den Berg的算法是针对相对简单的群体设计的,群体中的每个主体只希望到达自己的目的地,同时避开障碍物。[23] 这个算法可以用来模拟时代广场 Times Square的人群。


帕蒂尔算法最重要且具有区分性的特征是它利用了 导航场 Navigation Fields的概念来指导主体。这不同于 指导场 Guidance Field; 指导场是主体周围的一个区域,主体可以在其中“看到”或检测到信息。指导场通常用于避开障碍物,特别是动态障碍物(移动的障碍物)。每个主体都有自己的指导场。另一方面,导航场是一个 向量场 vector field,它为每个主体计算 最小代价路径 minimum cost path,使每个主体到达自己的目标位置。


只有当从环境中的每一个 自由(无障碍)位置 free (non-obstacle) position到某一目标位置的路径存在时,导航场才能被正确使用。导航场是使用环境中静态对象的坐标、每个主体的目标位置和指导场计算的。为了保证每个主体达到自己的目标,导航场必须不受 局部极小值 local minima的限制,除非在特定目标处存在 汇 sinks


计算导航场的运行时间的公式是


[math]\displaystyle{ O(m*n*log(mn)) }[/math]

其中 m × n 是网格维数(类似于迪杰斯特拉算法)。因此,该算法仅依赖于网格分辨率,而不依赖于环境中的主体数量。但是,这种算法的内存消耗很大。


个体行为建模

基于AI的群体建模的技术之一,是通过对个体动机和决策的高级模拟来建立群体行为模型。一般来说,这意味着每个主体都被分配了一组变量来衡量不同的特征或状态,比如压力、人格或不同的目标。这导致更真实的群体行为,虽然可能比使用简单的技术计算量更大。


基于人格的模型

为人群的主体创建个体行为模型的一种方法是使用人格特质。[24] 每个主体可能会根据一个公式调整他们个性的某些方面,这个公式将侵略性或冲动性等方面与控制主体行为的变量联系起来。发现这种联系的一个方法是通过一个主观的研究,在这个研究中主体被随机分配这些变量的值,参与者被要求用这些人格特征来描述每个主体。然后可以进行回归,以确定这些特征和主体变量之间的相关性。人格特征可以被调整,并对主体行为产生适当的影响。


五大人格特征模型 Big Five personality traits/OCEAN personality model定义了人格特质与人群模拟参数之间的映射关系。自动调整人群的人格特征参数使得能够在错杂的人群中简便地创作场景。[25]


基于压力的模型

高压状态下的人群行为可以用 一般适应综合症理论 General Adaptation Syndrome theory来模拟。[26] 主体行为受到来自所处环境的各种压力源的影响,包括 时间压力 time pressure 区域压力 area pressure 位置压力 positional stressors 人际压力 interpersonal stressors四个原型,每个原型都有相关的数学模型。


时间压力是和达到特定目标的时间限制有关的压力源。例如,一个设有限时步行信号的十字路口,或在车门关闭前上车。这个原型是按照以下公式建模的:


[math]\displaystyle{ I_t = max(t_e - t_a, 0) }[/math]


其中 [math]\displaystyle{ I_t }[/math] 是时间压力强度,它是关于达到目标的估计时间[math]\displaystyle{ t_e }[/math]和时间限制 [math]\displaystyle{ t_a }[/math]的函数。


区域压力是指由于环境条件而产生的压力。例如某个地区的噪音或热量。这种压力源的强度在某一特定地区是恒定的,其模型如下:


[math]\displaystyle{ I_a = \begin{cases} c & \text{if }p_a\in A \\ 0 & \text{if }p_a\not\in A \end{cases} }[/math]


其中[math]\displaystyle{ I_a }[/math]是区域压力强度,[math]\displaystyle{ p_a }[/math] 是主体在A区的位置,c是一个常数。


位置压力是指与局部压力源相关的压力源。这种压力源的强度随着主体接近压力源而增加。一个例子就是火灾,或运动的物体比如攻击者。它可以用下面的公式来模拟:


[math]\displaystyle{ I_p = \lVert p_a - p_s \rVert }[/math]


其中 [math]\displaystyle{ I_p }[/math] 是位置压力源的强度,[math]\displaystyle{ p_a }[/math] 是主体的位置,[math]\displaystyle{ p_s }[/math] 是压力源的位置。另外,在一个大的区域产生高压力的压力源(如火灾),可以用一个带有正态分布的标准差[math]\displaystyle{ \sigma }[/math]的模型来模拟:


[math]\displaystyle{ I_p = \mathcal{N}(p_a - p_s, \sigma) }[/math]


人际压力源是由邻近主体的拥挤程度而产生的压力源。它可以用下面的公式来模拟:


[math]\displaystyle{ I_i = max(n_c - n_p, 0) }[/math]


其中[math]\displaystyle{ I_i }[/math]表示人际压力源的强度,[math]\displaystyle{ n_c }[/math] 表示当前单位空间内邻居的数量,[math]\displaystyle{ n_p }[/math] 表示单位空间内该特定主体理想的邻居数量。


感知到的压力遵循史蒂芬定律 Steven's Law ,并可以用下面的公式模拟:


[math]\displaystyle{ \psi(I) = kI^n }[/math]


其中[math]\displaystyle{ \psi(I) }[/math]是感知到的压力水平,[math]\displaystyle{ I }[/math]是客观的压力水平,[math]\displaystyle{ k }[/math] 是一个比例系数,[math]\displaystyle{ n }[/math]是一个取决于压力源类型的指数。


一个主体的压力反应可以通过以下公式得出:


[math]\displaystyle{ {dS \over dt} = \begin{cases} \alpha & \text{if } \psi \gt S \\ (-\alpha \leq {d\psi \over dt} \leq \alpha) & \text{if } \psi = S\\ -\alpha & \text{if } \psi \lt S\end{cases} }[/math]


其中,[math]\displaystyle{ S }[/math]是压力反应,它受到最大[math]\displaystyle{ \beta }[/math]值的限制,[math]\displaystyle{ \alpha }[/math]是主体的压力反应可以改变的最大速率。


值得注意的AI模拟例子可以在新线电影公司 New Line Cinema的《指环王 Lord of the Rings》系列电影中看到。在这部电影中,成千上万的AI角色互相争斗。这个人群模拟是用威塔数码公司 Weta Digital的Massive软件完成的。


社会学

人群模拟也可以指基于群体动力学 Group Dynamics群体心理学 Crowd Psychology的模拟,通常用于公共安全规划 Public Safety Planning。在这种情况下,研究的焦点只是人群的行为,而不是模拟的视觉真实性。自19世纪末以来,人们一直将人群作为一种科学兴趣进行研究。许多研究都关注人们在社会聚会、集会、抗议、叛乱、音乐会、体育赛事和宗教仪式上的集体社会行为。了解不同类型压力情况下的人类自然行为将创建更好的、可用于发展人群控制策略的模型。


警察、国民警卫队、军队甚至志愿者等紧急反应小组都必须接受某种形式的人群控制培训。运用研究出的群体中人类的行为原则,灾难训练设计者可以有更多元素来创造更逼真的模拟灾难。在恐慌和非恐慌情况下可以观察到群体行为。当自然和非自然的事件使社会理想状况陷入扭曲混乱的局面,比如“911”和飓风卡特里娜事件时,人类的社会能力就在真正地接受考验。军事项目更倾向于以模拟形式进行训练和应急反应,因为它们是成本低效益高的形式,并且能够有效地将所学转移到现实世界。许多事件一开始可能受到控制,但后来反转发展成为灾难性情况,因此需要当场做出决定。正是在这些情况下,对人群的动态理解将发挥重要作用,以减少出现混乱的可能性。


群体的建模技术从整体或网络到理解每个主体的个人或行为方面都各不相同。例如,社会力模型 Social Force Model描述了个体在社会互动和物理互动之间寻求平衡的需求。一种结合了这两个方面,并且能够根据具体情境进行调整的方法,将更好地描述自然的人类行为,并总是包含一些对不可预测性的测量。随着多主体模型的使用,理解这些复杂的行为已经成为一个易懂的任务。利用这种类型的软件,现在研究人员可以在极端条件下测试系统,也可以在几秒钟内模拟长期的情况变化。


在某些情况下,非人类动物群体的行为可以作为群体行为的一个实验模型。人们发现,蚂蚁在出口有限且封闭的空间里暴露于令人反感的化学物质中时产生的惊慌行为,与同样情况下的人类行为既有相似之处,也有不同之处。[27][28]


个体行为建模

赫尔本 Helbing 提出了一个基于物理学的模型,使用粒子系统和社会心理力量来描述人群在恐慌情况下的行为,这个模型现在被称为 赫尔本模型 Helbing Model。他的工作基于在特定情况下普通人如何反应。虽然这是一个很好的模式,但是在人群中总是有不同类型的人,他们每个人都有自己的个人特点和在群体结构中的行为方式。例如,一个人可能不会对恐慌的情况做出反应,而另一个人可能会停下脚步并干扰整个人群的运动。此外,根据群体结构的不同,作为群体的一部分主体的个人行为可能会发生变化。例如,为了拯救该群体的一个成员而返回到一个危险的地方。如布劳恩 Braun, Musse,奥利韦拉 Oliveira和布罗德曼 Bodmann 提出的那样,赫尔本的模型可以概括为融入个人主义。[29]


为了解决这个问题,应该给每个主体分配个性,从而允许模型处理不同类型的行为。解决这个问题的另一个方法是把人们分组,形成这样的群体会使人们作为群体结构的一部分而改变他们的行为。


每个主体(个体)可以根据以下参数定义:


  1. Id – 主体标识符
  1. IdFamily – 家族标识符。家族是由相互认识的主体组成的一个预先设定的组。
  1. DE – 主体的依赖水平 Dependence level,用来模拟主体对他人帮助的需求。取值范围:[0,1]
  1. AL – 利他主义水平 Altruism Level,代表了帮助他人的倾向。取值范围:[0,1]
  1. vi – 主体的速度


为了模拟单个主体的因变量参数的效应方程定义为:


[math]\displaystyle{ v_i = (1-DE)v_{max} }[/math]


在评估主体的速度时,很明显,如果依赖因子 DE 的值等于1,则表示该主体完全丧失行动能力。如果依赖因子等于0,那么该主体能够以其最大速度运动。


群体的形成与利他主义力有关。利他主义力是同一家族中两个或两个以上成员之间的相互作用力。用数学方法,它被描述为:


[math]\displaystyle{ F\overline{a}_i = K\sum \left ( AL_iDE_j \times \left | d_{ij}-d_{ip} \right | \times e_{ij} \right ) }[/math]


其中:

dij表示两个主体之间的距离,原点设在主体的位置;
dip是模拟环境中从主体到门的位置的距离矢量点;
K是一个常数
eij是原点位于i处的酉向量。


因此,主体i的利他主义水平ALi越高,指向主体ji就越大,j也具有较高的依赖水平DEj。当两个代理彼此足够接近时,具有较高依赖水平的主体(本例中的主体j)就采用主体i依赖水平([math]\displaystyle{ DE_j = DE_i }[/math])。这意味着主体i与主体j共享疏散能力,两者一起开始移动。


将这些方程应用于正态分布人口的模型检验,结果与赫尔本模型 Helbing Model非常相似。


这种模型会对疏散场景有所帮助。以发生火灾的建筑物疏散为例,考虑到个体的特点和他们在团队的表现从而确定人群会如何离开建筑的结果,对于设计建筑的布局至关重要。[29]


疏散模拟中的领导者行为

如前所述,赫尔本模型被用作群体行为的基础。同样类型的行为模型也同样被用于疏散模拟。


一般来说,首先需要假定的是,并不是每个人都了解环境或了解哪里有没有危险。根据这个假设,我们可以创建三种类型的主体。第一种类型是训练有素的领导者,这种主体了解环境并能够将知识传播给其他主体,因此他们知道如何从这种环境中退出。第二种类型的主体是未经训练的领导者。他们不了解环境,但是当这种主体探索环境并从其他类型的领导者那里获得信息时,他们能够传播有关环境的知识。最后一种类型是跟随者,这种类型的主体只能从其他领导者那里获取信息,不能与其他主体共享信息。


实现这些主体类型的方法相当简单直接。对于领导者,环境地图被保存为他们的属性之一。未经训练的领导者和追随者具有一张空地图的属性。未经训练的领导者和追随者将自己开始探索环境,并创建一个具有适合和不适合走地点信息的地图。领导者和未受过训练的领导者(一旦他们掌握了知识) ,会根据与其他主体的接近程度来分享信息。他们分享的信息包括网格上哪些点被阻塞,局部子地图和该地区的危险。


有两种类型的搜索算法试验了这种模型: 随机搜索 Random Search深度优先搜索 Depth First Search。随机搜索是指每个主体在环境中朝任意方向前进,并试图找到一条出路。深度优先搜索是指主体尽可能沿着一条路径搜索,如果它们所经过的路径不包含出口则返回并尝试另一条路径。结果发现,深度优先搜索比随机搜索的速度快15倍。[30]


可扩展的模拟

在人群模拟中有许多不同的情况出现。[31]近年来,人群模拟已经成为教育、训练、娱乐等虚拟环境应用中不可缺少的一部分。许多情况下的人群模拟是基于模拟的环境或一组局部主体的行为。在虚拟现实应用程序中,每个主体与环境中的许多其他主体进行交互,需要复杂的实时交互。由于主体行为允许复杂交互的特性,主体必须在环境中能够连续变化。可伸缩的架构 Scalable architecture可以通过行为和交互速率来管理大的人群。当应用几种不同的情境时,可以揭示人群在复杂的情况下的运动行为。情境可以是任何具有典型局部行为的环境。


我们可以把所有的情境分为两种不同的类型。


空间情境 Spatial Situation是指环境影响局部主体的区域。例如,一个售票亭前排队等候的人群就展示可一个空间情境。其他的例子,可能是一个公交车总站或者一个ATM机,在那里人依据其环境做出行动。因此,如果主体的行为可以是上车或下车,我们就可以把“公交车站”看作是一种空间情境。


非空间情境 Non-Spatial situation是没有空间区域的环境,因为它只涉及到人群的行为。在决定行为时,局部主体之间的关系是一个重要的因素。一个例子是一群朋友一起散步。朋友的典型行为是各个主体都会互相影响。这意味着“友谊”是作为一起散步的典型行为的情境。


任何情境的结构都建立在四个组件之上: 行为函数 Behavior Functions传感器 Sensors状态 States事件规则 Event Rules。行为函数表示特定情况下的特定行为。传感器是一种感知能力,可以让主体看到并对事件做出反应。状态是仅用于局部行为的不同运动和状态转移。事件规则是将不同的事件与其特定的行为联系起来的方法。当一个角色被置于一个情境中时,这四个组件将被同时考虑。对于空间情景,当个体最初进入影响角色的环境时就添加组件。对于非空间情境,只有当用户将情境赋给角色时,角色才会受到影响。当主体被带离情境区域或情境本身被移除时,这四个组件被移除。动态地添加和删除这些情境使我们能够实现可伸缩的主体 Scalable Agents


类人行为和群体人工智能

 
一个对英国Covent Garden广场人群的模拟,示了一群行人主体对街头艺人的反应

为了模拟在人群中人类活动的更多方面,我们需要路径和运动规划以外的更多东西。复杂的社会交互、智能对象操纵和混合模型是这一领域的挑战。模拟人群行为的灵感来自于现实世界中的人群流。研究者分析了人群在许多环境和建筑类型中的行为模式、运动速度和密度以及异常情况。个体的行动被跟踪记录下来,这样就可以得到算法并应用到人群模拟中。


群体中的独立的个体也称为主体。为了让一个群体真实地行动,每个主体应该自主地(能够独立于其他主体地)行动。这个想法被称为基于主体的模型 Agent-based Model。此外,人们通常希望主体的行为具有一定程度的智慧(即,主体不应采取伤害自己的行动)。为了使主体做出明智和真实的决定,他们应该根据他们周围的环境采取行动,对环境变化作出反应,并对其他主体作出反应。


基于规则的人工智能

生成缩略图出错:无法找到文件
马斯洛的需求层次理论

基于规则的人工智能 Rule-based AI中,虚拟主体遵循以下规则: “如果发生了这种情况,就那样做”。如果需要具有不同角色的主体,比如一个主角和几个背景角色,那么这是一个很好的方法。这种类型的人工智能通常是用层次结构来实现的,例如在马斯洛的需求层次结构 Maslow's hierarchy of needs中,需求层级越低,需求就越强。


例如,假设一个学生在走向教室的路上遭遇了爆炸并逃跑了。这背后的理论是他的前4个层次的需求得到了满足,并且学生是具有自我实现 self-actualization的需求并依次按照需求来行动。当爆炸发生时,他的安全受到威胁,这是一个比自我实现更强烈的需要,使他按照这种需要行事。


这种方法是可扩展的,可以应用于拥有大量主体的人群。然而,基于规则的人工智能确实有一些缺点。最值得注意的缺点是,主体的行为会变得可预测性很强,这可能导致群体的行为不现实。


学习型人工智能

学习型人工智能 Learning AI中,虚拟角色用一种经过了测试的方式帮助他们自己实现目标。主体用他们的环境或者一个类似于他们真实环境的样本环境进行测试。


主体进行各种各样的行动并从他们的错误中吸取经验。每个主体根据从环境中得到的奖励和惩罚改变其行为。随着时间的推移,每个主体都会发展更有可能获得高回报的行为。


如果使用这种方法,加上大量可能的行为和复杂的环境,主体将以一种现实的和不可预测的方式行事。


算法

人群模拟现在已经有各种各样可以应用的机器学习算法。


Q-Learning是机器学习的子领域强化学习中的一个算法。一个对该算法的基本描述:每个动作都被分配了一个Q值,每个主体都被赋予一个总是执行Q值最高的动作的指令。在这种情况下,学习效果取决于分配Q值的方式,这完全是基于奖励的。当一个主体接触到一个状态 s 和一个动作 a 时,算法就会估计这个主体执行这个状态动作对 state action pair所能得到的总回报值。在计算这些数据之后,它们被存储在主体的知识中,主体依据这些知识开始行动。


主体会根据最佳Q值不断地改变自己的行为。随着它对环境的探索越来越多,它最终将学习到几乎每种情况下最佳状态动作对。


下面的函数概括了算法的大部分内容:


Q(s, a) ←− r + maxaQ(s', a')


给定一个状态s和动作a,r和s’是执行(s,a)后的奖励和状态,a'动作集。[32]

人群渲染和动画

对大量主体进行真实地、特别是实时地渲染和动画绘制,是具有挑战性的。为了降低大规模人群3D渲染的复杂性,人们使用了剔除(舍弃不重要的物体)、顶替(基于图像的渲染)和降低细节的级别等技术。[33]


真实的人群中存在着外貌、体型大小、附件和(社会的或文化的)行为的差异,缺乏多样性的模型会影响视觉模拟的真实性。现有的系统可以创建具有不同肌理、[7] 颜色、[34] 大小、形状和动画的虚拟人群。[6]


在真实世界的应用

虚拟电影摄影

人群模拟已经被广泛应用于电影中,它是一种相较雇佣演员和捕捉镜头来说更加低成本高收益且现实的替代方式,使用其他方法将是不真实的。电影《指环王》系列就是一个重要的例子。最初,制作团队面临最突出的问题之一是大规模的战斗,因为小说的作者约翰·罗纳德·瑞尔·托尔金 J. R. R. Tolkien设想这些战斗至少有50,000名参与者。如果制作团队决定只雇佣真人演员,这么多参与者是不现实的。他们决定使用CG来代替模拟这些场景,使用虚拟环境中的多主体仿真系统 Multiple Agent Simulation System,也就是众所周知的 MASSIVE 。群集动画 Miarmy,一个基于人类逻辑引擎 Human Logic Engine的人群模拟 Maya 插件,被用于开发这些动作序列。该软件允许制片人为每个角色提供一个基于主体的人工智能模型,这个模型可以利用一个有350个动画的数据库。基于通过模拟产生的视觉、听觉和触觉参数,主体将对每种不同的情况做出特定反应。因此,每个场景的模拟都是不可预知的。最终作品清晰地展示了使用人群模拟软件的优势。[35]


城市规划

人群模拟软件的发展为现代城市环境设计提供了一个有用的工具。传统的城市规划方法依赖于地图和抽象的草图,而数字仿真更能将设计的形式和意图从建筑设计师传达给行人。例如,街道标志和交通灯是局部视觉线索,能够影响行人的移动和相应的行为。按照这个逻辑,如果一个人能够以一种高效的方式从 a 点移动到 b 点,一群人就能够高效地运作。在更广泛的意义上,公交系统和路边餐馆通过对人类运动模式的理解,在其位置起到空间上的作用。[36]模拟城市SimCity视频游戏系列以一种更简单的方式举例说明了这个概念。在这个系列中,玩家在指定的区域指导城市的发展,同时保持平衡的收支。从空地到繁华城市的过程完全由玩家的选择来控制,而数字市民的行为则根据城市的设计和事件而定。


疏散和暴乱处理

模拟真实的人群可用于训练暴乱处理、建筑、安全科学(疏散计划 Evacuation )。


军队

由于人群模拟是如此普遍地应用于公共规划和建立混乱情境中的一般秩序,许多应用程序可以用于绘制政府的和军队的模拟。为了训练官兵对群众集会的应对能力,人群模型在警察和军队推演中是必不可少的。在这些模拟中,不仅进攻性的战斗人员很难处理,非战斗人员也在使这些斗争场景更加失控的方面发挥了重要的作用。因此游戏技术被用来模拟这些情境,以使士兵和技术人员实践他们的技能。[37]


社会学

模型群体的行为在分析问题时有重要的作用。这些动画依赖于独立主体在群体中的物理行为,而不是模型本身的视觉现实。多年来,人们在这些结构中的社会行为一直是研究者感兴趣的问题,支撑这些互动的社会学概念也被持续地研究。不同情境下的人群模拟使现实生活中不同场景地点集会的社会学研究得以进行。人类在压力水平不同的情境下的行为差异可以用来进一步发展和创造人群控制策略,这种策略可以更具体而不是空泛地应用于所有情况。


参见


人群模拟软件


参考文献

  1. Thalmann, Daniel (2016). "Crowd Simulation". Encyclopedia of Computer Graphics and Games. pp. 1–8. doi:10.1007/978-3-319-08234-9_69-1. ISBN 978-3-319-08234-9. 
  2. http://cc.ist.psu.edu/BRIMS/archives/2007/papers/07-BRIMS-025.pdf Jérôme Comptdaer, Emmanuel Chiva, Stéphane Delorme, Henri Morlaye, Jérôme Volpoët, Multi-scale behavioral models for urban crisis training simulation.
  3. Drettakis, George; Roussou, Maria; Reche, Alex; Tsingos, Nicolas (2007). "Design and Evaluation of a Real-World Virtual Environment for Architecture and Urban Planning" (PDF). Presence: Teleoperators and Virtual Environments. 16 (3): 318–32. doi:10.1162/pres.16.3.318.
  4. Gwynne, S.; Galea, E.R.; Owen, M.; Lawrence, P.J.; Filippidis, L. (1999). "A review of the methodologies used in the computer simulation of evacuation from the built environment". Building and Environment. 34 (6): 741–9. doi:10.1016/S0360-1323(98)00057-2.
  5. Tecchia, Franco; Loscos, Celine; Chrysanthou, Yiorgos (2002). "Visualizing Crowds in Real-Time". Computer Graphics Forum. 21 (4): 753–65. doi:10.1111/1467-8659.00633.
  6. 6.0 6.1 Thalmann, Daniel; Grillon, Helena; Maim, Jonathan; Yersin, Barbara (2009). "Challenges in Crowd Simulation". 2009 International Conference on CyberWorlds. pp. 1–12. doi:10.1109/CW.2009.23. ISBN 978-1-4244-4864-7. 
  7. 7.0 7.1 Maim, J.; Yersin, B.; Thalmann, D. (2009). "Unique Character Instances for Crowds". IEEE Computer Graphics and Applications. 29 (6): 82–90. doi:10.1109/MCG.2009.129. PMID 24806782.
  8. Chao, Qianwen; Deng, Zhigang; Jin, Xiaogang (2015). "Vehicle-pedestrian interaction for mixed traffic simulation". Computer Animation and Virtual Worlds. 26 (3–4): 405–12. doi:10.1002/cav.1654.
  9. Sewall, Jason; Wilkie, David; Lin, Ming C. (2011). "Interactive hybrid simulation of large-scale traffic". ACM Transactions on Graphics. 30 (6): 1. doi:10.1145/2070781.2024169.
  10. Kallmann, Marcelo; Thalmann, Daniel (1999). "Modeling Objects for Interaction Tasks". Computer Animation and Simulation '98. Eurographics. pp. 73–86. doi:10.1007/978-3-7091-6375-7_6. ISBN 978-3-211-83257-8. 
  11. http://dl.acm.org/citation.cfm?id=1272705 Pelechano, N. and Allbeck, J. M. and Badler, N. I. Controlling individual agents in high-density crowd simulation. In Proceedings of the 2007 ACM SIGGRAPH/Eurographics Symposium on Computer Animation.
  12. Reynolds, Craig (1987). Flocks, herds, and schools: A distributed behavior model.. July 1987. pp. 25–34. doi:10.1145/37401.37406. ISBN 978-0897912273. 
  13. Terzopoulos, Demetri; Tu, Xiaoyuan; Grzeszczuk, Radek (1994). "Artificial Fishes: Autonomous Locomotion, Perception, Behavior, and Learning in a Simulated Physical World". Artificial Life. 1 (4): 327–51. CiteSeerX 10.1.1.33.8131. doi:10.1162/artl.1994.1.4.327.
  14. Thalmann, Daniel; Musse, Soraia Raupp (2012-10-04) (in en). Crowd Simulation. Springer Science & Business Media. ISBN 978-1-4471-4449-6. https://books.google.com/?id=3Adh_2ZNGLAC&pg=PR8&dq=history+of+crowd+simulation#v=onepage&q=history%20of%20crowd%20simulation&f=false. 
  15. Musse, S. R.; Thalmann, D. (1997). "A Model of Human Crowd Behavior : Group Inter-Relationship and Collision Detection Analysis". Computer Animation and Simulation '97. Eurographics. pp. 39–51. doi:10.1007/978-3-7091-6874-5_3. ISBN 978-3-211-83048-2. 
  16. "Steering Behaviors For Autonomous Characters". www.red3d.com. Retrieved 2016-12-17.
  17. Musse, S.R.; Thalmann, D. (2001). "Hierarchical model for real time simulation of virtual human crowds". IEEE Transactions on Visualization and Computer Graphics (Submitted manuscript). 7 (2): 152–64. doi:10.1109/2945.928167.
  18. Matt Anderson; Eric McDaniel; Stephen Chenney (July 26–27, 2003). "Constrained animation of flocks". SCA '03 Proceedings of the 2003 ACM SIGGRAPH/Eurographics symposium on Computer animation. pp. 286–297. ISBN 1-58113-659-5.
  19. Ulicny, Branislav; Ciechomski, Pablo de Heras; Thalmann, Daniel (2004). "Crowdbrush". Proceedings of the 2004 ACM SIGGRAPH/Eurographics symposium on Computer animation – SCA '04. pp. 243–52. doi:10.1145/1028523.1028555. ISBN 978-3-905673-14-2. 
  20. Zhou, Suiping; Chen, Dan; Cai, Wentong; Luo, Linbo; Low, Malcolm Yoke Hean; Tian, Feng; Tay, Victor Su-Han; Ong, Darren Wee Sze; Hamilton, Benjamin D. (2010). "Crowd modeling and simulation technologies" (PDF). ACM Transactions on Modeling and Computer Simulation. 20 (4): 1–35. doi:10.1145/1842722.1842725. hdl:10149/118022.
  21. Degond, Pierre; Navoret, Laurent; Bon, Richard; Sanchez, David (2010). "Congestion in a macroscopic model of self-driven particles modeling gregariousness". Journal of Statistical Physics. Springer. 138 (1–3): 85–125. arXiv:0908.1817. Bibcode:2010JSP...138...85D. doi:10.1007/s10955-009-9879-x.
  22. Cohen, Eyal; Cohen, Eyal; Najman, Laurent (1997). "From crowd simulation to airbag deployment: Particle systems, a new paradigm of simulation". Journal of Electronic Imaging. 6: 94–107. Bibcode:1997JEI.....6...94B. doi:10.1117/12.261175.
  23. Patil, Sachin; Van Den Berg, Jur; Curtis, Sean; Lin, Ming C; Manocha, Dinesh (2011). "Directing Crowd Simulations Using Navigation Fields". IEEE Transactions on Visualization and Computer Graphics. 17 (2): 244–54. CiteSeerX 10.1.1.183.7823. doi:10.1109/TVCG.2010.33. PMID 21149879.
  24. Guy, Stephen J.; Kim, Sujeong; Lin, Ming C.; Manocha, Dinesh (2011). "Simulating heterogeneous crowd behaviors using personality trait theory". Proceedings of the 2011 ACM SIGGRAPH/Eurographics Symposium on Computer Animation – SCA '11. pp. 43–52. doi:10.1145/2019406.2019413. ISBN 978-1-4503-0923-3. 
  25. Durupinar, Funda; Pelechano, Nuria; Allbeck, Jan; Gudukbay, Ugur; Badler, Norman I. (2011). "How the Ocean Personality Model Affects the Perception of Crowds". IEEE Computer Graphics and Applications. 31 (3): 22–31. doi:10.1109/MCG.2009.105. hdl:11693/11800. PMID 24808089.
  26. Kim, Sujeong; Guy, Stephen J.; Manocha, Dinesh; Lin, Ming C. (2012). "Interactive simulation of dynamic crowd behaviors using general adaptation syndrome theory". Proceedings of the ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games – I3D '12. pp. 55–62. doi:10.1145/2159616.2159626. ISBN 978-1-4503-1194-6. 
  27. N. Shiwakoti et al., "Animal dynamics based approach for modeling pedestrian crowd egress under panic conditions", Transportation Research Part B 45 (2011) 1433-1449.
  28. S. Wang et al., "Behavior of Ants Escaping from a Single-Exit Room", PLoS One. 2015; 10(6): e0131784.
  29. 29.0 29.1 Braun, A.; Musse, S.R.; De Oliveira, L.P.L.; Bodmann, B.E.J. (2003). "Modeling individual behaviors in crowd simulation". Proceedings 11th IEEE International Workshop on Program Comprehension. pp. 143–8. doi:10.1109/CASA.2003.1199317. ISBN 978-0-7695-1934-0. 
  30. Pelechano, Nuria; Badler, Norman (2006). "Modeling Crowd and Trained Leader Behavior during Building Evacuation". IEEE Computer Graphics and Applications. 26 (6): 80–6. doi:10.1109/MCG.2006.133. hdl:2117/10047. PMID 17120916.
  31. Vigueras, G.; Lozano, M.; Pérez, C.; Orduña, J.M. (2008). "A Scalable Architecture for Crowd Simulation: Implementing a Parallel Action Server". 2008 37th International Conference on Parallel Processing. pp. 430–7. doi:10.1109/ICPP.2008.20. 
  32. Torrey, L. Crowd Simulation Via Multi-agent Reinforcement Learning. In: Proceedings of the Sixth AAAI Conference On Artificial Intelligence and Interactive Digital Entertainment. AAAI Press, Menlo Park (2010)
  33. Aubel, A.; Boulic, R.; Thalmann, D. (2000). "Real-time display of virtual humans: Levels of details and impostors". IEEE Transactions on Circuits and Systems for Video Technology. 10 (2): 207–17. doi:10.1109/76.825720.
  34. Gosselin, David R.; Sander, Pedro V.; Mitchell, Jason L. (2004). "Drawing a Crowd". In Engel, Wolfgang. ShaderX3: Advanced Rendering Techniques in DirectX and OpenGL. Cambridge, MA: Charles River Media. pp. 505–17. 
  35. http://people.ucalgary.ca/~far/Lectures/SENG697/PDF/tutorials/2002/Multiple_Agent_Simulation_System_in_a_Virtual_Environment.pdf Davis Guy. Multiple Agent Simulation System in a Virtual Environment.
  36. http://papers.cumincad.org/data/works/att/ecaade2008_160.content.pdf Aschwanden, Gideon. Halatsch, Jan. Schmitt, Gerhard. Crowd Simulation for Urban Planning.
  37. McKenzie, F. D.; Petty, M. D.; Kruszewski, P. A.; Gaskins, R. C.; Nguyen, Q.-A. H.; Seevinck, J.; Weisel, E. W. (2007). "Integrating crowd-behavior modeling into military simulation using game technology". Simulation & Gaming. 39: 10–38. doi:10.1177/1046878107308092.


外部链接

  • SteerSuite, An open-source framework for developing and evaluating crowd simulation algorithms


编者推荐

 
《Crowd Simulation》

集智课程推荐

Netlogo是一个用来对自然和社会现象进行仿真的可编程建模环境。在建模中Netlogo可以控制成千上万的个体,能很好地模拟微观个体的行为和宏观模式的涌现及其两者之间的联系,特别适合于模拟随时间发展的复杂系统。

在该课程中我们将从理论回到现实中学习到实际的本领:关于Netlogo的操作。


NetLogo多主体建模入门

《NetLogo多主体建模入门》课程就是通过数个案例教会大家如何去动手搭建一个多主体仿真模型,以及如何利用NetLogo软件实现这些模型,是一门既有理论又有实操的入门课程。它将会循序渐进地给你介绍如何使用NetLogo软件,如何通过算法来理解数值微分、数值积分,甚至求解微分方程、动力系统。通过学习,你就能搭建一个人工生命的世界,一个人工经济系统,以及一个人工生态系统。通过计算模拟,你还能理解到什么叫做捕食与被捕食的依存关系,病毒如何沿着网络进行传播甚至大爆发,你还能对人类财富不平等的起源拥有全新的洞察。其实,所有这一切真没有那么复杂,无非就是几行NetLogo的代码而已。而所有这些不同领域的知识都可以从玩弄这些代码得到。


本课程通过数个案例教会大家如何去动手搭建一个多主体仿真模型,以及如何利用NetLogo去实现。从生命游戏到人工鸟群,从模拟经济系统到病毒沿网络的传播,通过循序渐进的案例,该课程带你逐步走入NetLogo多主体建模的神奇世界。


复杂性思维2020

本课程中,张江老师将用一套自己搭建的“复杂性阶梯”的框架串联起众多复杂性科学概念,包括混沌、秩序、自催化网络、涌现、混沌边缘、热力学第二定律、分形、网络、自指等等。


书籍推荐

《人群模拟 Crowd Simulation》

本书由提出人群模拟概念的Daniel Thalmann 和 Soraia Raupp Musse 编著,包括人群建模和评价模型的方法。本书在2013年有最新版本(第二版),尚无中文译本。




本中文词条由WIldBoar审校,薄荷编辑,如有问题,欢迎在讨论页面留言。

本词条内容源自wikipedia及公开资料,遵守 CC3.0协议。