大规模人群的并行仿真研究

周文平等

摘 要：本文针对大规模人群仿真对仿真真实性和实时性的仿真要求，提出了一种基于Agent的并行人群仿真方法，通过CPU-GPU混合并行的方式提高了仿真系统的性能和可扩展性。通过层次化的人群建模，使得个体更适合并行环境下的数据交互，仿真中通过感知区域视角约束对人群的运动进行控制，实现了人群平滑运动。实验部分对室外环境的人群漫游行为进行了仿真，验证了系统具有较高的性能和可扩展性。

关键字：分布式仿真；人群仿真； 统一计算设备架构

中图法分类号： TP242 文献标识码： A 文章编号：2095-2163（2014）06-

Abstract： To meet the authenticity of the simulation of large-scale crowd simulation and real-time simulation requirements， this paper proposed a Agent based parallel crowd simulation method . Through CPU-GPU hybrid parallel simulation approach， it improves the performance of the system and scalability. Hierarchical modeling of the individuals in the crowd makes the individual more suitable for data exchange in parallel environments. Simulation by perceptual constraints on regional perspectives to control the movement of people achieves a smooth movement of the crowd. Experiments of behavior of the crowd roaming the outdoor environment verify that the system has high performance and scalability.

Key words： Distributed Simulation；Crowd Simulation； CUDA；

0引言

大规模人群实时仿真的研究具有重要的社会意义，而在技术上存在很大的挑战性。大规模人群实时仿真研究主要包括两个方面的研究目标：如何提高人群仿真的真实性（包括行为真实性和动画视觉真实性）；如何提高人群仿真的实时性（即如何在扩大人群规模的同时提高仿真的效率）。前者可以通过对虚拟环境建模、人群行为模型、人群运动建模等问题的研究来实现；后者则可通过对人群实时渲染技术、人群仿真系统结构设计、并行人群仿真相关算法等问题的研究来实现。着眼于当前的发展状况可以推知，同时兼顾仿真真实性和实时性的大规模群体实时仿真即是时下亟需重点解决的研究难题。为此，本文采用并行计算的理论方法，并利用现有的多核CPU及多核GPU的硬件环境，实现了高性能人群仿真。

现有的并行群体仿真方法主要包括四种[1]：基于CPU的多线程并行，基于GPU的流式并行，基于分布式的多机并行以及基于GPU与分布式的混合并行方式。其中，混合并行既满足了可扩展性需求，又能充分挖掘每个计算节点的性能，现已成为并行群体仿真的重要研究分支[2]。群体仿真研究可基于Agent或流体进行并实现[3-4]，而且考虑到基于Agent的群体能够更丰富地表达个体特性和相应行为方式，同时设计的一定的AI算法亦可用于提高Agent的智能[5]，因此本文即采用基于Agent的方式开展群体仿真研究，并通过混合并行方式提高仿真性能和可扩展性。

1 基于CPU-GPU混合的仿真体系结构

混合式并行人群仿真系统包含三类节点，分别是：CC（Control Center）主控节点，CN（Compute Node）群体行为计算节点，Viewer视景节点。系统在任务划分过程[6]后，将划分形成的个体分组配发给各个CN节点，而在划分过程产生的每一条分割边则表示个体分组所在CN节点之间存在着感知关联，所以CN节点在个体避碰运算中即需将该边关联区域内的个体状态通过告知彼此而实现信息透明。三类节点组成的系统通讯结构可如图1所示。

首先，CC主控节点实现功能包括环境提取与群体管理，任务划分，同时还要维护每个CN节点的邻接CN节点列表以及与各CN节点关联的个体列表，另外也提供了运行过程中负载失衡后的任务重新调度功能。

其次，CN计算节点，主要负责所配发的个体分组中每一个体的路径导航、避碰、行为运算及个体运动状态实时更新等功能。具体来说，各CN节点接收来自CC主控节点分配的仿真任务，同时将运算状态反馈给主控节点，并将个体状态信息传递给Viewer节点进行渲染显示。更进一步地，各CN节点都要维护一个邻接CN节点列表，由此而实现CN节点之间分割边关联个体之运行状态的互相通告。

最后，Viewer视景节点，可实时采集来自CC主控节点的控制指令，收集各CN计算节点中个体的状态信息并对个体进行渲染。研究可知，高真实性的群体动画渲染对系统运算的需求较高，此时将渲染工作从系统单独剥离出来，即可降低对其他功能所需运算资源的占用，有效提高系统的运行性能。目前，几何实例化方法就是兼顾个体模型真实性及仿真结果效率的主要群体动画方法，而且丰富的运动方式还可以有效地增加群体行为的多样性。具体地，则可通过采用文献[7]中提出的一种基于运动捕捉人体动画的GPU几何实例化算法来实现群体的动画渲染。

2人群行为模型

2.1感知区域视角约束

人体可按当前的行进状态预估前进方向所能到达的区域范围，文献[8]中就对应提到了环境感知中静态障碍和动态障碍的不同感知方法，但却没有给出感知区域扇形夹角和感知半径的取值依据。在此，即设个体的感知半径为R、最大转角速度为Va、最大前进速度为V，感知角度为Ag，因而可通过个体的感知半径、最大转角速度、最大前进速度、感知角度的四元组来定义个体的感知范围。也就是，个体的感知区域范围可由个体的感知半径R、个体的最大转动角速度Va、个体的最大前进速度V以及感知角度Ag四个约束条件而联合确定，则扇形BOC的夹角即感知角度Ag就需满足如下约束：若 Agent以速率V，转角速度Va沿弧a2前行，最终与扇形BOC在顶点B交汇，其中OB的长度大小为感知半径R的数值。感知区域视角约束则如图2所示。

人群行为的真实性也体现在环境的真实性上，形象逼真的环境多会表现有复杂多样性。而个体对环境的感知就可以通过个体环境搜寻或环境广播给个体这两种相应方法加以实现，但这些却都需要环境的各结构化组成依次具备各自的语义。其中，环境的几何建模可采用层次化的组织结构，环境的语义建模则通过对环境的人体可活动区域进行语义描述，同时亦将环境的活动区域拓扑图提取且存入语义数据库中。尤其是，环境中如果有类似于着火点等特殊组成元素，即需记录此元素，同时系统将定时向此元素所在分区及邻区的个体进行相应的事件广播。

3环境提取及人群导航

大规模群体的并行仿真，可以借鉴现有的分布式虚拟环境和N-Body并行仿真方面的相关研究成果。在此基础上，如果把群体并行仿真问题近似看作N-Body问题[9]，此时针对基于Agent的群体仿真来说，最简单的看待Agent之间交互的方式就是每个Agent均与其他每一Agent之间发生交互，也可称作全配对交互（All Pair）。并且，如果群体中的个体之间相互作用采取了全配对的方式，其复杂度将为O（n？），为了避免相邻个体之间的搜索复杂度达到上述的O（n？），通常的做法则是假设行走动作中相邻个体之间的交互将随距离的增加而渐次减弱，从而可以采用分区的方法来实现高效仿真。本文即采用均匀网格的方法对仿真系统进行了分区，但研究首要步骤即需计算得出三维场景的二维网格地图。

3.1三维场景网格地图生成

本文采用OpenGL的Z-Buffer来提取静态场景中的可行网格地图。首先，可将三维场景实现分割，具体地水平方向网格数为WSize，垂直方向网格数为HSize的二维网格，同时设网格单元的大小为CellSize，这样整个场景的网格单元总数则为WSize*HSize，而且再将三维场景的网格地图的长度MapHeight设为HSize*CellSize，宽度MapWidth也相应设为WSize*CellSize。研究采用了正视投影的方法，视角选择为场景水平面正上方往下的方向，这样就能保证同一水平面的深度值相同，从而通过深度值来区分场景的可行区域和不可行区域。此时，OpenGL视口的选择需要符合如下条件：

3.2人群导航

路径导航是人群仿真研究的重要问题，其设定目标是最优化地导航范围内的每一个体Agent，使其到达指定目的地，同时确保在此过程中被导航个体Agent能够避免与群体所在环境中的障碍物之间发生相互碰撞。本文就采用A*（A-Star）算法对人群中个体进行路径规划，该算法是一种静态路网中求解最短路径的最佳方法，并且，如果估价值与实际值越接近，估价函数的选取就越臻于理想。

4群体动画方法

在已有的处理群体动画的实时渲染的方法中，针对个体模型复杂度而采用简化表示和简化逼近的方式来设计研发的主要有三种，具体来说包括：LOD细节层次方法[10-11]、基于图像的imposer方法[12]和基于采样点的渲染方法[13-14]。F. Carucci在文献[15]中首次提出了静态批次， 动态批次，顶点常量实例化和基于几何实例化API的批次等四种几何实例化方法，验证了几何实例化方法能够很好地应用在小对象的动画渲染中，如草叶，树叶等，但对于大规模群体的仿真效果却未达到酷似与逼真。进而，D.Bryan[16]又在此基础上提出了一种实例化的群体渲染方法，实现了DIRECTX环境下的大规模人群的快速渲染，而且通过分别对各关节使用不同的网格模型与纹理能够即能更好地呈现仿真个体的多样性，从而达到逼真的动画效果，不过该方法主要针对的却是基于帧动画的运动数据库。

另外，作为图形运算的专用设备，GPU包含单指令多数据（SIMD）处理单元集合，而SIMD处理方式又具备较好的并行特性。迄今为止，由于GPU图形处理单元的高性价比、硬件的可编程性以及超级的计算能力和速度，使得GPU应用普及推广到了除3D图形渲染之外的计算研究领域。将GPU作为高性能通用并行流式处理器，并使用GPU的通用计算功能来实现并行计算的方式主要包括两种。具体地，一种是在可编程像素处理阶段，使用基于纹理的GPU通用计算方式；还有一种是基于CUDA统一计算架构的通用计算方式。其中，CUDA是计算机统一设备架构的英文缩写，这是由NVidia公司提出的一个新的基于C语言的通用GPU计算框架，而且在基于GPU的群体仿真中将逐步取代先期的通用GPU计算方式。

本文通过使用基于运动捕捉的GPU实例化方法[7]对并行人群仿真系统的Viewer视景节点进行设计。设计后的Viewer视景节点的功能结构图即如图4所示。

5.1 实验参数设置

本节对所提的任务划分方法及分布式运行模式开展了仿真实验及相关性能评估。针对分布式仿真系统的性能评估指标主要包含两类：延迟和吞吐率。参照文献[17]所提及服务器响应时间及动画渲染帧率，可设置最大可接受响应时间为250ms，设置最低仿真动画帧率为30fps（可接受的下限）。

根据文中设计的分布式运行模型，具体采用的分布式仿真平台则为一组9台Intel平台机器（至强4核@2.50GHz，3.8GB内存，NVIDIA Quadro FX 580显卡），其中1台作为CC主控节点，其余8台作为CN运算节点；1台Intel机器（三代i5，4核@3.40GHz，GTX 760显卡）作为Viewer群体动画渲染节点。所有机器的操作系统均采用内核版本为2.6.32的Linux系统， 机组则采用千兆路由互联组成的内部局域网。

在分布式仿真平台中的室外场景的群体行为应用分布式运行模型而进行了仿真试验。

5.2 室外场景仿真及性能分析

EnvSUTP算法适用于室外场景的分布群体仿真。图5为城镇的人群日常活动的仿真结果。人群中每位个体均有自己随机的去往目标，通过路径搜索最终到达目的地，移动过程中采用RVO速度障碍规则进行避碰处理。

6 结束语

本文通过对比现有并行人群仿真算法的优劣，总结出混合式体系结构的优越性。通过结合使用分布式和GPU几何实例化动画方法实现了一种混合式体系结构的并行人群仿真系统。进而又通过实验证明了系统具有较高的性能，同时相同规模人群的仿真性能与计算节点数呈现了近线性关系，由此则证明了系统对室外环境仿真也同样有着良好的可扩展性。但在未来的工作中仍然需要在以下方面进行更深入的研究：

（1）在大规模人群仿真场景中，人群中个体的路径导航占用较多的开销，现有方法在并行环境中存在一定的不足，若能设计出适合并行环境的快速的群体导航算法将有效提升系统仿真的性能。

（2）现有的人群动画渲染技术主要在单机中实现，如何将分布式并行绘制技术应用到人群的动画绘制中，需对其加大研究力度，如此将有望突破人群动画绘制的瓶颈。

（3）基于Agent智能体的个体模型是人群仿真的研究趋势，在并行环境中，如何应用AI智能算法对个体行为进行控制，亦是一个重要的研究发展方向。

参考文献

[1]周文平， 唐好选， 季振洲. 并行群体仿真研究进展[J]. 计算机应用研究， 2013， 30（1）： 30-35.

[2]. Vigueras G， Orduna J M， Lozano M. A gpu-based multi-agent system for real-time simulations[M].Advances in Practical Applications of Agents and Multiagent Systems， Springer Berlin Heidelberg， 2010： 15-24.

[3] WANG Y， LEES M， CAI W. Grid-based partitioning for large-scale distributed agent-based crowd simulation[A] .Proceedings of the Winter Simulation Conference[C]//Winter Simulation Conference， 2012： 241-252.

[4] MAO Tianlu， JIANG Hao， LI Jian， et al.Parallelizing continuum crowds[A].VRST '10 Proceedings of the 17th ACM Symposium on Virtual Reality Software and Technology[C]//New York ：ACM， 2010：231-234.

[5] YILMAZ E， ？SLER V， YARDIMCI Y C. The Virtual Marathon： Parallel computing supports crowd simulations[J]. IEEE Computer Graphics & Applications， 2009，29（4）：26-33.

[6] ZHOU Wenping， TANG Haoxuan， JI Zhenzhou. A load balance algorithm for distributed crowd simulation based on connected graph partition [J]. ICIC Express Letters， 2013， 7（8）： 2377-2383.

[7] ZHOU Wenping， TANG Haoxuan， JI Zhenzhou. GPU instancing method for crowd animation based on motion capture data [J]. Journal of Computational Information Systems， 2013， 9（11）： 4459-4467.

[8] SHAO W， TERZOPOULOS D. Environmental modeling for autonomous virtual pedestrians[R]. SAE Technical Paper， 2005.

[9]NYLAND L， HARRIS M， PRINS J. Fast n-body simulation with cuda[J]. GPU gems， 2007， 3（1）： 677-696.

[10] Pablo de HERAS C B U， CETRE R， THALMAN D. A case study of a virtual audience in a reconstruction of an ancient Roman Odeon in Aphrodisias [C]//the 5th International Symposium on Virtual Reality，Archaeology and Cultural Heritage，2004.

[11] ULICNY B P， de HERAS C D， THALMANN. Crowdbrush： interactive authoring of real-time crowd scene[C]//Proceedings of the 2004 ACM SIGGRAPH/Eurographics symposium on Computer animation，2004：243-252.

[12] TECCHIA F Y. CHRYSANTHOU. Real-Time Rendering of Densely Populated Urban Environments，2000：83-88.

[13] WAND M ，STRASSER W .Multi-resolution rendering of complex animated scenes [C]// Proc of Computer Graphics Forum.Boston：Blackwell Publishing，2002.

[14] SU Bo， MAO Tianlu， XU Wenbin， et al. Point based large-scale crowds real-time 3D visualization method[J]. Computer Research and Development，2008，45（10）：1731-1738.

[15] Carucci F. Inside Geometry Instancing[M]. Indianapolis， Indiana， USA： Addison-Wesley， 2005.

[16] B. Dudash. Animated crowd rendering[M]. GPU Gems 3.Addison-Wesley， 2007：39–52.

[17] VIGUERAS G， LOZANO M， PEREZ C， et al. A scalable architecture for crowd simulation：Implementing a parallel action server[A]. Proceedings of the 37th International Conference on Parallel Processing （ICPP-08）[C].2008：430–437.