周文平等

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

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

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

現(xiàn)有的并行群體仿真方法主要包括四種[1]：基于CPU的多線程并行，基于GPU的流式并行，基于分布式的多機(jī)并行以及基于GPU與分布式的混合并行方式。其中，混合并行既滿足了可擴(kuò)展性需求，又能充分挖掘每個(gè)計(jì)算節(jié)點(diǎn)的性能，現(xiàn)已成為并行群體仿真的重要研究分支[2]。群體仿真研究可基于Agent或流體進(jìn)行并實(shí)現(xiàn)[3-4]，而且考慮到基于Agent的群體能夠更豐富地表達(dá)個(gè)體特性和相應(yīng)行為方式，同時(shí)設(shè)計(jì)的一定的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）群體行為計(jì)算節(jié)點(diǎn)，Viewer視景節(jié)點(diǎn)。系統(tǒng)在任務(wù)劃分過程[6]后，將劃分形成的個(gè)體分組配發(fā)給各個(gè)CN節(jié)點(diǎn)，而在劃分過程產(chǎn)生的每一條分割邊則表示個(gè)體分組所在CN節(jié)點(diǎn)之間存在著感知關(guān)聯(lián)，所以CN節(jié)點(diǎn)在個(gè)體避碰運(yùn)算中即需將該邊關(guān)聯(lián)區(qū)域內(nèi)的個(gè)體狀態(tài)通過告知彼此而實(shí)現(xiàn)信息透明。三類節(jié)點(diǎn)組成的系統(tǒng)通訊結(jié)構(gòu)可如圖1所示。

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

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

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

2人群行為模型

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

人體可按當(dāng)前的行進(jìn)狀態(tài)預(yù)估前進(jìn)方向所能到達(dá)的區(qū)域范圍，文獻(xiàn)[8]中就對(duì)應(yīng)提到了環(huán)境感知中靜態(tài)障礙和動(dòng)態(tài)障礙的不同感知方法，但卻沒有給出感知區(qū)域扇形夾角和感知半徑的取值依據(jù)。在此，即設(shè)個(gè)體的感知半徑為R、最大轉(zhuǎn)角速度為Va、最大前進(jìn)速度為V，感知角度為Ag，因而可通過個(gè)體的感知半徑、最大轉(zhuǎn)角速度、最大前進(jìn)速度、感知角度的四元組來定義個(gè)體的感知范圍。也就是，個(gè)體的感知區(qū)域范圍可由個(gè)體的感知半徑R、個(gè)體的最大轉(zhuǎn)動(dòng)角速度Va、個(gè)體的最大前進(jìn)速度V以及感知角度Ag四個(gè)約束條件而聯(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)境多會(huì)表現(xiàn)有復(fù)雜多樣性。而個(gè)體對(duì)環(huán)境的感知就可以通過個(gè)體環(huán)境搜尋或環(huán)境廣播給個(gè)體這兩種相應(yīng)方法加以實(shí)現(xiàn)，但這些卻都需要環(huán)境的各結(jié)構(gòu)化組成依次具備各自的語義。其中，環(huán)境的幾何建?？刹捎脤哟位慕M織結(jié)構(gòu)，環(huán)境的語義建模則通過對(duì)環(huán)境的人體可活動(dòng)區(qū)域進(jìn)行語義描述，同時(shí)亦將環(huán)境的活動(dòng)區(qū)域拓?fù)鋱D提取且存入語義數(shù)據(jù)庫中。尤其是，環(huán)境中如果有類似于著火點(diǎn)等特殊組成元素，即需記錄此元素，同時(shí)系統(tǒng)將定時(shí)向此元素所在分區(qū)及鄰區(qū)的個(gè)體進(jìn)行相應(yīng)的事件廣播。

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

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

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

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

3.2人群導(dǎo)航

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

4群體動(dòng)畫方法

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

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

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

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

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

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

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

5.2 室外場(chǎng)景仿真及性能分析

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

6 結(jié)束語

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

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

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

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

參考文獻(xiàn)

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