大規(guī)模人群的并行仿真研究

周文平等

摘 要：本文針對大規(guī)模人群仿真對仿真真實(shí)性和實(shí)時性的仿真要求，提出了一種基于Agent的并行人群仿真方法，通過CPU-GPU混合并行的方式提高了仿真系統(tǒng)的性能和可擴(kuò)展性。通過層次化的人群建模，使得個體更適合并行環(huán)境下的數(shù)據(jù)交互，仿真中通過感知區(qū)域視角約束對人群的運(yùn)動進(jìn)行控制，實(shí)現(xiàn)了人群平滑運(yùn)動。實(shí)驗(yàn)部分對室外環(huán)境的人群漫游行為進(jìn)行了仿真，驗(yàn)證了系統(tǒng)具有較高的性能和可擴(kuò)展性。

關(guān)鍵字：分布式仿真；人群仿真； 統(tǒng)一計算設(shè)備架構(gòu)

中圖法分類號： TP242 文獻(xiàn)標(biāo)識碼： 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引言

大規(guī)模人群實(shí)時仿真的研究具有重要的社會意義，而在技術(shù)上存在很大的挑戰(zhàn)性。大規(guī)模人群實(shí)時仿真研究主要包括兩個方面的研究目標(biāo)：如何提高人群仿真的真實(shí)性（包括行為真實(shí)性和動畫視覺真實(shí)性）；如何提高人群仿真的實(shí)時性（即如何在擴(kuò)大人群規(guī)模的同時提高仿真的效率）。前者可以通過對虛擬環(huán)境建模、人群行為模型、人群運(yùn)動建模等問題的研究來實(shí)現(xiàn)；后者則可通過對人群實(shí)時渲染技術(shù)、人群仿真系統(tǒng)結(jié)構(gòu)設(shè)計、并行人群仿真相關(guān)算法等問題的研究來實(shí)現(xiàn)。著眼于當(dāng)前的發(fā)展?fàn)顩r可以推知，同時兼顧仿真真實(shí)性和實(shí)時性的大規(guī)模群體實(shí)時仿真即是時下亟需重點(diǎn)解決的研究難題。為此，本文采用并行計算的理論方法，并利用現(xiàn)有的多核CPU及多核GPU的硬件環(huán)境，實(shí)現(xiàn)了高性能人群仿真。

現(xiàn)有的并行群體仿真方法主要包括四種[1]：基于CPU的多線程并行，基于GPU的流式并行，基于分布式的多機(jī)并行以及基于GPU與分布式的混合并行方式。其中，混合并行既滿足了可擴(kuò)展性需求，又能充分挖掘每個計算節(jié)點(diǎn)的性能，現(xiàn)已成為并行群體仿真的重要研究分支[2]。群體仿真研究可基于Agent或流體進(jìn)行并實(shí)現(xiàn)[3-4]，而且考慮到基于Agent的群體能夠更豐富地表達(dá)個體特性和相應(yīng)行為方式，同時設(shè)計的一定的AI算法亦可用于提高Agent的智能[5]，因此本文即采用基于Agent的方式開展群體仿真研究，并通過混合并行方式提高仿真性能和可擴(kuò)展性。

1 基于CPU-GPU混合的仿真體系結(jié)構(gòu)

混合式并行人群仿真系統(tǒng)包含三類節(jié)點(diǎn)，分別是：CC（Control Center）主控節(jié)點(diǎn)，CN（Compute Node）群體行為計算節(jié)點(diǎn)，Viewer視景節(jié)點(diǎn)。系統(tǒng)在任務(wù)劃分過程[6]后，將劃分形成的個體分組配發(fā)給各個CN節(jié)點(diǎn)，而在劃分過程產(chǎn)生的每一條分割邊則表示個體分組所在CN節(jié)點(diǎn)之間存在著感知關(guān)聯(lián)，所以CN節(jié)點(diǎn)在個體避碰運(yùn)算中即需將該邊關(guān)聯(lián)區(qū)域內(nèi)的個體狀態(tài)通過告知彼此而實(shí)現(xiàn)信息透明。三類節(jié)點(diǎn)組成的系統(tǒng)通訊結(jié)構(gòu)可如圖1所示。

首先，CC主控節(jié)點(diǎn)實(shí)現(xiàn)功能包括環(huán)境提取與群體管理，任務(wù)劃分，同時還要維護(hù)每個CN節(jié)點(diǎn)的鄰接CN節(jié)點(diǎn)列表以及與各CN節(jié)點(diǎn)關(guān)聯(lián)的個體列表，另外也提供了運(yùn)行過程中負(fù)載失衡后的任務(wù)重新調(diào)度功能。

其次，CN計算節(jié)點(diǎn)，主要負(fù)責(zé)所配發(fā)的個體分組中每一個體的路徑導(dǎo)航、避碰、行為運(yùn)算及個體運(yùn)動狀態(tài)實(shí)時更新等功能。具體來說，各CN節(jié)點(diǎn)接收來自CC主控節(jié)點(diǎn)分配的仿真任務(wù)，同時將運(yùn)算狀態(tài)反饋給主控節(jié)點(diǎn)，并將個體狀態(tài)信息傳遞給Viewer節(jié)點(diǎn)進(jìn)行渲染顯示。更進(jìn)一步地，各CN節(jié)點(diǎn)都要維護(hù)一個鄰接CN節(jié)點(diǎn)列表，由此而實(shí)現(xiàn)CN節(jié)點(diǎn)之間分割邊關(guān)聯(lián)個體之運(yùn)行狀態(tài)的互相通告。

最后，Viewer視景節(jié)點(diǎn)，可實(shí)時采集來自CC主控節(jié)點(diǎn)的控制指令，收集各CN計算節(jié)點(diǎn)中個體的狀態(tài)信息并對個體進(jìn)行渲染。研究可知，高真實(shí)性的群體動畫渲染對系統(tǒng)運(yùn)算的需求較高，此時將渲染工作從系統(tǒng)單獨(dú)剝離出來，即可降低對其他功能所需運(yùn)算資源的占用，有效提高系統(tǒng)的運(yùn)行性能。目前，幾何實(shí)例化方法就是兼顧個體模型真實(shí)性及仿真結(jié)果效率的主要群體動畫方法，而且豐富的運(yùn)動方式還可以有效地增加群體行為的多樣性。具體地，則可通過采用文獻(xiàn)[7]中提出的一種基于運(yùn)動捕捉人體動畫的GPU幾何實(shí)例化算法來實(shí)現(xiàn)群體的動畫渲染。

2人群行為模型

2.1感知區(qū)域視角約束

人體可按當(dāng)前的行進(jìn)狀態(tài)預(yù)估前進(jìn)方向所能到達(dá)的區(qū)域范圍，文獻(xiàn)[8]中就對應(yīng)提到了環(huán)境感知中靜態(tài)障礙和動態(tài)障礙的不同感知方法，但卻沒有給出感知區(qū)域扇形夾角和感知半徑的取值依據(jù)。在此，即設(shè)個體的感知半徑為R、最大轉(zhuǎn)角速度為Va、最大前進(jìn)速度為V，感知角度為Ag，因而可通過個體的感知半徑、最大轉(zhuǎn)角速度、最大前進(jìn)速度、感知角度的四元組來定義個體的感知范圍。也就是，個體的感知區(qū)域范圍可由個體的感知半徑R、個體的最大轉(zhuǎn)動角速度Va、個體的最大前進(jìn)速度V以及感知角度Ag四個約束條件而聯(lián)合確定，則扇形BOC的夾角即感知角度Ag就需滿足如下約束：若 Agent以速率V，轉(zhuǎn)角速度Va沿弧a2前行，最終與扇形BOC在頂點(diǎn)B交匯，其中OB的長度大小為感知半徑R的數(shù)值。感知區(qū)域視角約束則如圖2所示。

人群行為的真實(shí)性也體現(xiàn)在環(huán)境的真實(shí)性上，形象逼真的環(huán)境多會表現(xiàn)有復(fù)雜多樣性。而個體對環(huán)境的感知就可以通過個體環(huán)境搜尋或環(huán)境廣播給個體這兩種相應(yīng)方法加以實(shí)現(xiàn)，但這些卻都需要環(huán)境的各結(jié)構(gòu)化組成依次具備各自的語義。其中，環(huán)境的幾何建模可采用層次化的組織結(jié)構(gòu)，環(huán)境的語義建模則通過對環(huán)境的人體可活動區(qū)域進(jìn)行語義描述，同時亦將環(huán)境的活動區(qū)域拓?fù)鋱D提取且存入語義數(shù)據(jù)庫中。尤其是，環(huán)境中如果有類似于著火點(diǎn)等特殊組成元素，即需記錄此元素，同時系統(tǒng)將定時向此元素所在分區(qū)及鄰區(qū)的個體進(jìn)行相應(yīng)的事件廣播。

3環(huán)境提取及人群導(dǎo)航

大規(guī)模群體的并行仿真，可以借鑒現(xiàn)有的分布式虛擬環(huán)境和N-Body并行仿真方面的相關(guān)研究成果。在此基礎(chǔ)上，如果把群體并行仿真問題近似看作N-Body問題[9]，此時針對基于Agent的群體仿真來說，最簡單的看待Agent之間交互的方式就是每個Agent均與其他每一Agent之間發(fā)生交互，也可稱作全配對交互（All Pair）。并且，如果群體中的個體之間相互作用采取了全配對的方式，其復(fù)雜度將為O（n？），為了避免相鄰個體之間的搜索復(fù)雜度達(dá)到上述的O（n？），通常的做法則是假設(shè)行走動作中相鄰個體之間的交互將隨距離的增加而漸次減弱，從而可以采用分區(qū)的方法來實(shí)現(xiàn)高效仿真。本文即采用均勻網(wǎng)格的方法對仿真系統(tǒng)進(jìn)行了分區(qū)，但研究首要步驟即需計算得出三維場景的二維網(wǎng)格地圖。

3.1三維場景網(wǎng)格地圖生成

本文采用OpenGL的Z-Buffer來提取靜態(tài)場景中的可行網(wǎng)格地圖。首先，可將三維場景實(shí)現(xiàn)分割，具體地水平方向網(wǎng)格數(shù)為WSize，垂直方向網(wǎng)格數(shù)為HSize的二維網(wǎng)格，同時設(shè)網(wǎng)格單元的大小為CellSize，這樣整個場景的網(wǎng)格單元總數(shù)則為WSize*HSize，而且再將三維場景的網(wǎng)格地圖的長度MapHeight設(shè)為HSize*CellSize，寬度MapWidth也相應(yīng)設(shè)為WSize*CellSize。研究采用了正視投影的方法，視角選擇為場景水平面正上方往下的方向，這樣就能保證同一水平面的深度值相同，從而通過深度值來區(qū)分場景的可行區(qū)域和不可行區(qū)域。此時，OpenGL視口的選擇需要符合如下條件：

3.2人群導(dǎo)航

路徑導(dǎo)航是人群仿真研究的重要問題，其設(shè)定目標(biāo)是最優(yōu)化地導(dǎo)航范圍內(nèi)的每一個體Agent，使其到達(dá)指定目的地，同時確保在此過程中被導(dǎo)航個體Agent能夠避免與群體所在環(huán)境中的障礙物之間發(fā)生相互碰撞。本文就采用A*（A-Star）算法對人群中個體進(jìn)行路徑規(guī)劃，該算法是一種靜態(tài)路網(wǎng)中求解最短路徑的最佳方法，并且，如果估價值與實(shí)際值越接近，估價函數(shù)的選取就越臻于理想。

4群體動畫方法

在已有的處理群體動畫的實(shí)時渲染的方法中，針對個體模型復(fù)雜度而采用簡化表示和簡化逼近的方式來設(shè)計研發(fā)的主要有三種，具體來說包括：LOD細(xì)節(jié)層次方法[10-11]、基于圖像的imposer方法[12]和基于采樣點(diǎn)的渲染方法[13-14]。F. Carucci在文獻(xiàn)[15]中首次提出了靜態(tài)批次， 動態(tài)批次，頂點(diǎn)常量實(shí)例化和基于幾何實(shí)例化API的批次等四種幾何實(shí)例化方法，驗(yàn)證了幾何實(shí)例化方法能夠很好地應(yīng)用在小對象的動畫渲染中，如草葉，樹葉等，但對于大規(guī)模群體的仿真效果卻未達(dá)到酷似與逼真。進(jìn)而，D.Bryan[16]又在此基礎(chǔ)上提出了一種實(shí)例化的群體渲染方法，實(shí)現(xiàn)了DIRECTX環(huán)境下的大規(guī)模人群的快速渲染，而且通過分別對各關(guān)節(jié)使用不同的網(wǎng)格模型與紋理能夠即能更好地呈現(xiàn)仿真?zhèn)€體的多樣性，從而達(dá)到逼真的動畫效果，不過該方法主要針對的卻是基于幀動畫的運(yùn)動數(shù)據(jù)庫。

另外，作為圖形運(yùn)算的專用設(shè)備，GPU包含單指令多數(shù)據(jù)（SIMD）處理單元集合，而SIMD處理方式又具備較好的并行特性。迄今為止，由于GPU圖形處理單元的高性價比、硬件的可編程性以及超級的計算能力和速度，使得GPU應(yīng)用普及推廣到了除3D圖形渲染之外的計算研究領(lǐng)域。將GPU作為高性能通用并行流式處理器，并使用GPU的通用計算功能來實(shí)現(xiàn)并行計算的方式主要包括兩種。具體地，一種是在可編程像素處理階段，使用基于紋理的GPU通用計算方式；還有一種是基于CUDA統(tǒng)一計算架構(gòu)的通用計算方式。其中，CUDA是計算機(jī)統(tǒng)一設(shè)備架構(gòu)的英文縮寫，這是由NVidia公司提出的一個新的基于C語言的通用GPU計算框架，而且在基于GPU的群體仿真中將逐步取代先期的通用GPU計算方式。

本文通過使用基于運(yùn)動捕捉的GPU實(shí)例化方法[7]對并行人群仿真系統(tǒng)的Viewer視景節(jié)點(diǎn)進(jìn)行設(shè)計。設(shè)計后的Viewer視景節(jié)點(diǎn)的功能結(jié)構(gòu)圖即如圖4所示。

5.1 實(shí)驗(yàn)參數(shù)設(shè)置

本節(jié)對所提的任務(wù)劃分方法及分布式運(yùn)行模式開展了仿真實(shí)驗(yàn)及相關(guān)性能評估。針對分布式仿真系統(tǒng)的性能評估指標(biāo)主要包含兩類：延遲和吞吐率。參照文獻(xiàn)[17]所提及服務(wù)器響應(yīng)時間及動畫渲染幀率，可設(shè)置最大可接受響應(yīng)時間為250ms，設(shè)置最低仿真動畫幀率為30fps（可接受的下限）。

根據(jù)文中設(shè)計的分布式運(yùn)行模型，具體采用的分布式仿真平臺則為一組9臺Intel平臺機(jī)器（至強(qiáng)4核@2.50GHz，3.8GB內(nèi)存，NVIDIA Quadro FX 580顯卡），其中1臺作為CC主控節(jié)點(diǎn)，其余8臺作為CN運(yùn)算節(jié)點(diǎn)；1臺Intel機(jī)器（三代i5，4核@3.40GHz，GTX 760顯卡）作為Viewer群體動畫渲染節(jié)點(diǎn)。所有機(jī)器的操作系統(tǒng)均采用內(nèi)核版本為2.6.32的Linux系統(tǒng)， 機(jī)組則采用千兆路由互聯(lián)組成的內(nèi)部局域網(wǎng)。

在分布式仿真平臺中的室外場景的群體行為應(yīng)用分布式運(yùn)行模型而進(jìn)行了仿真試驗(yàn)。

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

EnvSUTP算法適用于室外場景的分布群體仿真。圖5為城鎮(zhèn)的人群日?；顒拥姆抡娼Y(jié)果。人群中每位個體均有自己隨機(jī)的去往目標(biāo)，通過路徑搜索最終到達(dá)目的地，移動過程中采用RVO速度障礙規(guī)則進(jìn)行避碰處理。

6 結(jié)束語

本文通過對比現(xiàn)有并行人群仿真算法的優(yōu)劣，總結(jié)出混合式體系結(jié)構(gòu)的優(yōu)越性。通過結(jié)合使用分布式和GPU幾何實(shí)例化動畫方法實(shí)現(xiàn)了一種混合式體系結(jié)構(gòu)的并行人群仿真系統(tǒng)。進(jìn)而又通過實(shí)驗(yàn)證明了系統(tǒng)具有較高的性能，同時相同規(guī)模人群的仿真性能與計算節(jié)點(diǎn)數(shù)呈現(xiàn)了近線性關(guān)系，由此則證明了系統(tǒng)對室外環(huán)境仿真也同樣有著良好的可擴(kuò)展性。但在未來的工作中仍然需要在以下方面進(jìn)行更深入的研究：

（1）在大規(guī)模人群仿真場景中，人群中個體的路徑導(dǎo)航占用較多的開銷，現(xiàn)有方法在并行環(huán)境中存在一定的不足，若能設(shè)計出適合并行環(huán)境的快速的群體導(dǎo)航算法將有效提升系統(tǒng)仿真的性能。

（2）現(xiàn)有的人群動畫渲染技術(shù)主要在單機(jī)中實(shí)現(xiàn)，如何將分布式并行繪制技術(shù)應(yīng)用到人群的動畫繪制中，需對其加大研究力度，如此將有望突破人群動畫繪制的瓶頸。

（3）基于Agent智能體的個體模型是人群仿真的研究趨勢，在并行環(huán)境中，如何應(yīng)用AI智能算法對個體行為進(jìn)行控制，亦是一個重要的研究發(fā)展方向。

參考文獻(xiàn)

[1]周文平， 唐好選， 季振洲. 并行群體仿真研究進(jìn)展[J]. 計算機(jī)應(yīng)用研究， 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.