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

周文平等

摘 要：本文針對大規模人群仿真對仿真真實性和實時性的仿真要求，提出了一種基于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.