分布式環(huán)境下基于多Agent的人群模擬的研究與應(yīng)用

魏超,余臘生

（中南大學(xué)信息科學(xué)與工程學(xué)院,湖南長沙410083）

0 引言

一些大型公共設(shè)施的安全危機事件,如：恐怖襲擊、重大火災(zāi)、公眾聚集場所人員踩踏、危險化學(xué)制品泄漏爆炸、重大道路交通事故等,如果處置不當,不僅會帶來巨大的人員傷亡和經(jīng)濟損失,還會給國家造成重大的負面政治影響。我國每年因公共安全問題造成的GDP損失高達百分之六,奪去二十萬人的生命[1][2]。當前最通用的方法是模擬人群逃亡的過程,并對模擬的結(jié)果對公共設(shè)施做相應(yīng)的修改。

基于agent的分布式人群模擬,相對于傳統(tǒng)的人群模擬技術(shù)有很大的改進,具有更好的靈活性與可擴充性。它克服了機器性對人群數(shù)量的限制。

1 相關(guān)工作

在虛擬仿真研究領(lǐng)域,目前還沒有找到非常有效的模型來模擬人群運動。我們知道,傳統(tǒng)的模型存在很多限制。許多研究者在最大人群模擬數(shù)量與行為的多樣性之間找平衡點。例如,AvneeshSud和他的團隊提出了在復(fù)雜動態(tài)環(huán)境下,實時路徑規(guī)劃的新方法。他們引進了一種新的數(shù)據(jù)結(jié)構(gòu)叫做多agent導(dǎo)航圖,該圖由第一序列與第二序列的Voronoi圖構(gòu)成[3][4]。YongqingYe與QinggeJi在2007年提出了基于大規(guī)模人群分層路徑規(guī)劃的非實時算法[5]。此外,Avneesh Sud提出了在復(fù)雜動態(tài)環(huán)境下,通過設(shè)置適當?shù)穆窐?大規(guī)模自治的Agent同時執(zhí)行全局路徑規(guī)劃的模型[6]。另外,MubbasirKapadia提出了操控力行為的交互式框架,在不同的時間步長內(nèi),計算出周圍Agent與環(huán)境的變化,以利益驅(qū)動agent的行為[7]。還有,Hao Jiang和他的團隊提出了在復(fù)雜環(huán)境下語義模型的方案[8],RussellGayle和他的團隊提出了一個基于C/S模型的網(wǎng)絡(luò)拓撲結(jié)構(gòu)[9][10]。

本論文中,我們將介紹一個基于多agent的分布式人群模擬系統(tǒng),這個適用于復(fù)雜動態(tài)環(huán)境。我們便用了可擴展性系統(tǒng)結(jié)構(gòu)與高效的搜索算法,因此,可以模擬大量的人群。

2 人群疏散仿真系統(tǒng)的框架

基于多Agent的人群疏散仿真系統(tǒng)( Multi-Agent Simulation System,MASS)的體系結(jié)構(gòu)如圖 2-1所示。該系統(tǒng)由六個基本模塊組成：幾何圖形引擎,人員生成器,全局數(shù)據(jù)庫,人群疏散模擬引擎,事件注冊器及可視化工具。

圖2 -1疏散計算框架

(1)幾何圖形引擎用來構(gòu)造虛擬的物理環(huán)境(如建筑物或火車站等)。障礙物、出口、空間、樓層布局、出口指示牌等環(huán)境信息能很方便地用CAD工具(如AutoCAD,ADT等)定義。

(2)人員生成器動態(tài)地生成虛擬Agent來代表疏散人員,人員生成器根據(jù)人類特征(如年齡、身高、體重、性別等)及建筑物的類型(如醫(yī)院、辦公樓、車站、體育場等)生成不同類型的群體。隨建筑物類型不同,人員的組成及人員的行為也是有很大不同的。這個模型能夠很好地根據(jù)不同的建筑物類型生存不同的人員。

(3)全局數(shù)據(jù)庫維護所有有關(guān)的地理環(huán)境與模擬過程中的Agent的信息。這些信息包括狀態(tài)參數(shù)(如精神緊張程度、行為層次、所處位置等)。該數(shù)據(jù)庫還用于支持個體間的相互作用和對環(huán)境做出反應(yīng)。

(4)事件記錄器用于捕獲數(shù)據(jù)和回放模擬過程。模擬結(jié)果可被記錄下來做進一步的分析,例如,為了獲得疏散模式和統(tǒng)計資料。捕獲的事件也可以用來比較已知的和存檔的方案。

(5)可視化工具對于顯示仿真結(jié)果非常重要。在我們系統(tǒng)中,采用了OGRE來實現(xiàn)的,當接收到Agent的位置,然后動態(tài)生成并顯示2D/3D的視覺圖像。

(6)人群仿真引擎是多Agent仿真系統(tǒng)的核心模塊。按照行為模式和分類規(guī)則,人員生成器在生成一個Agent的時候,給每個Agent分配特有的行為模型。個體行為模式由三個子系統(tǒng)組成——感知系統(tǒng)、行為系統(tǒng)、執(zhí)行系統(tǒng),我們將會在后面的章節(jié)做詳細討論。人群的模擬引擎的基本算法步驟如圖2-2所示。

圖2 -2人群仿真引擎的基本步驟

這種設(shè)計使得整個系統(tǒng)高效模塊化,能非常方便地加入新的行為模式和規(guī)則,以便今后進一步研究動態(tài)人群行為。

3 基于Agent模型的行為仿真

在這個MASS系統(tǒng)中,每個人員都被表示為一個自治的Agent模型,Agent可以通過感知系統(tǒng)與虛擬環(huán)境及其它Agent相互交互。由于人群中的個體在行為上有很大差別,因此我們把人群歸為幾個類型,如老人、小孩,男人、女人等,并對這些類型建立不同的Agent行為模型。 Agent的行為模型主要由三個子系統(tǒng)組成：感知系統(tǒng),行為系統(tǒng),運動系統(tǒng)；這些子系統(tǒng)實現(xiàn)了Agent感知環(huán)境的狀態(tài)信息,行為模型制定決策等功能(如圖3-1)。涂曉媛在模擬人工魚的行為采用了類似的模型[10]。

圖3 -1自治Agent的三大系統(tǒng)

3.1 感知系統(tǒng)

每個Agent的感知系統(tǒng)由一個或多個感知器構(gòu)成。一個感知器又包含三個要素：輸入?yún)?shù),感官機制,以及輸出參數(shù)。輸入?yún)?shù)是由感知器探測到的一些有關(guān)環(huán)境狀態(tài)的信息。感官機制是一組處理數(shù)據(jù)的算法,它的輸入?yún)?shù)為感知到的環(huán)境狀態(tài)信息,并把輸出結(jié)果交給行為系統(tǒng)。

感知系統(tǒng)參數(shù)含有視覺、聽覺、情緒狀態(tài),以及其它一些影響Agent在疏散過程中做出決策的參數(shù)。目前,在MASS中應(yīng)用了一套計算 Agent虛擬視覺的方法。虛擬視覺的輸入?yún)?shù)包括出口、集結(jié)點、其他Agent,以及障礙物等。對于感官機制,我們采用“視覺體積”定義視覺范圍(圖3-2),該方法把視覺范圍看成一個圓錐體(由頂角與高度兩個參數(shù)限定)。圓錐的體積代表了Agent的可視范圍——一個對象對Agent可視是指它處在這個圓錐里面,并沒有被任何障礙阻擋。

圖3 -2視覺體積

圖3 -3點測試算法

計算Agent的虛擬視覺一直是計算機圖形學(xué)研究的熱點,目前已研究出許多有效的方法。根據(jù)前人的實驗結(jié)果,我們采用了一種混合計算模型(即結(jié)合點測試算法和光線跟蹤算法相結(jié)合)。結(jié)點檢測算法是用來確定出口或某個可達的點是否在視野范圍內(nèi)。假設(shè)人眼位于O點,最大視角為θ、可視距離為Vr(如圖 3-2),我們用該算法測試點P是否在視野范圍內(nèi),如圖3-3所示。因為結(jié)點測試算法只對少量的點(即出口與結(jié)點集)進行測試,因此它設(shè)計簡單且計算高效。

光跟蹤算法主要用來計算靜態(tài)障礙物的可見性。一個有趣的視覺現(xiàn)象是,個體并不是同時看見他們可視范圍內(nèi)的所有對象。個體在某一時刻通常只會將注意力集中在一個對象上,由于該對象的某些特征對個體的吸引最大。因此,沒有必要計算在個體可視范圍內(nèi)的所有物體,而只需計算那一時刻所關(guān)注的物體即可。當有人員的周圍存在大量的物體時,我們首先會對離他最近的物體做測試。假設(shè)人眼位點O,可視距離為Dr,M∈( 0,1]的一個實數(shù),ε是一個很小的大于0的常量,圖3-4描述了光線跟蹤算法判斷障礙物是否在可視范圍內(nèi)。

該算法可以很好地用于探測附Agent周圍的障礙物,以避免Agent在移動過程中與障礙物發(fā)生碰撞。該算法與人的視覺機制十分相似,同時它的效率也是較高的。

圖3 -4光測試算法

3.2 Agent 的行為系統(tǒng)

行為系統(tǒng)好比Agent的大腦。根據(jù)從感知系統(tǒng)收到的數(shù)據(jù),Agent在內(nèi)部因素(即心理因素和社會因素)的作用下做出行為決策。行為系統(tǒng)的主要組成部分是一個基于決策樹一組決策規(guī)則,在決策樹中,非葉子結(jié)點代表條件或某些操作,而葉節(jié)點表示一個行為決策。不同的決策樹會生成不同的行為決策行為。

在人群疏散模型中,心理因素與社會因素作為制定決策的主要依據(jù)：

(1)對環(huán)境的熟悉程度：這一因素在系統(tǒng)中表示為,在Agent的記憶空間中存儲的出口列表?？偟脑瓌t是,Agent在疏散過程中往往會選擇存儲在記憶空間中的出口。

(2)決策類型：由于人物特征(如性格、經(jīng)驗)各不相同,不同類型的Agent對應(yīng)不同的決策樹。每一個決策類型由一個特定的決策樹的形式表現(xiàn)出來。

(3)疏散的緊張程度：這一因素用來模擬心理壓力對Agent行為的影響?？偟膩碚f,出口越擁擠Agent就越希望快速地通過出口,這樣就會導(dǎo)致群體的競爭行為。在這個系統(tǒng)中,出口負載參數(shù)是一個介于0到 1之間的浮點數(shù),“1”表示出口達到了最大負載。

(4)心理壓力閾值：這個參數(shù)表示心理壓力大小會影響Agent的決策,并導(dǎo)致Agent做出不同行為決策。例如,當Agent的心理壓力低于某一閾值,那么Agent會排在出口隊列的后面,而不在群體中表現(xiàn)出競爭行為。在我們的疏散模型中,每個人的心理壓力值是各不相同的,并且對每個人心理壓力閾值定義也不相同。

(5)羊群效應(yīng)：這一因素反應(yīng)了人類行為的社會學(xué)理論——當一個人不知道該做什么的時候,那么別人在做什么,他也跟著做什么。當一個Agent探測到多個出口的時候,那么在群體因素的影響下,他會走向群體最大的那個出口；否則就會走向最近的那個出口。

由于MASS是基于模塊化設(shè)計的,在系統(tǒng)集成之前,我們可以對決策規(guī)則與行為系統(tǒng)等模塊做單獨測試——一個決策規(guī)則或行為事件可用指派給Agent用于測試。該設(shè)計靈活性且可擴展性好,能非常方便地將心理學(xué)與社會學(xué)相關(guān)的模塊集成到系統(tǒng)中去。

圖3 -5行為例程算法

3.3 執(zhí)行系統(tǒng)

執(zhí)行系統(tǒng)用來執(zhí)行行為系統(tǒng)制定的行為決策。一個行為事件往往包含一個或多個操控行為,而每個操控行為通常包含一系列的移動。

在MASS中,行為決策代表了一個Agent的意圖,如確定和選擇出口,然后走向它。在圖3-5講述了行為事件執(zhí)行的算法步驟。

操控行為的概念來源于機器人和人工生命。它以逼真的方式實現(xiàn)在虛擬環(huán)境下的現(xiàn)路徑導(dǎo)航,組合一些操控行為可完成更高層次目標[6],如避開中間的障礙物移動到指定的目的地。對于每一個時間步長,操控行為的主函數(shù)都會：計算操控力并執(zhí)行合法移動,在圖3-6中作了算法描述。注意：合法移動受常數(shù)k的約束,因為某個時刻一個合法移動也許是不可能執(zhí)行的(例如,當Agent處于一個密集的人群中)。一個移動事件的選擇是根據(jù)某個決策行為的決策樹來決定的。

一個特定的操控行為是由一組移動序列構(gòu)成的。一個最基本最簡單的移動可由Agent的制動器來完成,如‘前進一步’。移動基本步驟在圖3-7中進行了描述。

在MASS中,我們定義了八種移動類型來模擬人群的疏散過程：前進,左轉(zhuǎn),右轉(zhuǎn),后轉(zhuǎn),左移,右移,后退,停止。

圖3-6 操控行為算法

圖3-7 移動算法

4 分布式網(wǎng)絡(luò)模型

在大規(guī)模人群模擬實現(xiàn)中,計算機的體系結(jié)構(gòu)會對我們的結(jié)果產(chǎn)生很大影響,我們常用的模型有：單機模型,集中式服務(wù)器—客戶端模型,全分布式網(wǎng)絡(luò)模型(P2P模型),基于黑板的分布式模型(P2P與集中式混雜模型)。在我們的實驗中,選用了基于黑板的分布式模型,如圖4-1所示。下面我們就分析這幾種模型的優(yōu)缺點及選擇基于黑板的分布式模型的原因。

圖4-1 混合模型網(wǎng)絡(luò)拓撲結(jié)構(gòu)

(1)單機模型這種結(jié)構(gòu)的優(yōu)點：結(jié)構(gòu)最簡單,易于實現(xiàn)。不用考慮網(wǎng)絡(luò)延遲與客戶端間的同步。缺點：對機器的性能要求較高,人群模擬的數(shù)量在很大程度上受到限制。

(2)集中式網(wǎng)絡(luò)模型優(yōu)點：結(jié)構(gòu)相對簡單,所有事務(wù)由服務(wù)器集中管理,客戶端同步代價較小,每個客戶端只需向客戶端發(fā)請求,等待服務(wù)器的響應(yīng),實現(xiàn)起來也比較簡單。缺點：服務(wù)器成為整個系統(tǒng)的瓶頸,整個系統(tǒng)的通信都需服務(wù)器的參與才能完成,一旦服務(wù)器出現(xiàn)問題,整個系統(tǒng)都不能工作,而且對服務(wù)器的性能要求較高。

(3) P2P模型優(yōu)點：每個 Peer都能與其它 Peer獨立通信,解決了集中式中服務(wù)器造成的瓶頸問題。在理論上可以模擬任意多個人群。缺點：為一個事務(wù)的同步,系統(tǒng)的通信量很龐大。每個Peer得向所有peer(除自己)發(fā)出詢問,待收到應(yīng)答后才能做出決定,時間復(fù)雜度為O( N2).

(4)混合模型優(yōu)點：服務(wù)器用來同步,接受,發(fā)送,處理控制信號,降低了P2P系統(tǒng)中同步的通信代價,O( N2)到 O( N)。每個 Peer間都可完成通信,因此,除控制信號外的其它信號可采用端到端傳送,無需服務(wù)器的參與,大大降低了服務(wù)器的負載。相對于以上三種,在很大程度上提高了整個系統(tǒng)的性能。缺點：相對復(fù)雜,不易維護,服務(wù)器仍然是整個系統(tǒng)的關(guān)節(jié)點。

混合式繼承了第二種與第三種方式的優(yōu)點。能夠在普通的PC機群上模擬 100000個以上的人群。我們將地圖分割成N塊,每塊地圖對應(yīng)網(wǎng)絡(luò)中一個Peer,服務(wù)器將人群隨機的分配到每個Peer中,每個虛擬人都能在整個環(huán)境中自由運動。當一個虛擬人從地圖的一個分塊走到另一個分塊(既從一個Peer到另一個Peer中)時,這塊地圖對應(yīng)的Peer會通知下塊地圖對應(yīng)的Peer,并將這個虛擬人的所有狀態(tài)(包含目標與路徑)傳送過去,且將結(jié)果報告給服務(wù)器。服務(wù)器將所有人的位置渲染出來。

5 實驗結(jié)論與結(jié)果

在我們的實驗中,我們采用了多種方法對系統(tǒng)進行測試并取得了較好的實驗結(jié)果。我們的系統(tǒng)在一組處理器為AMD 4400+,內(nèi)存1G的一組臺式機上運行。在單機環(huán)境下,我們的系統(tǒng)能流暢地模擬4000人；在分布式環(huán)境下(15個 PEER),我們的系統(tǒng)能流暢地模擬50000人。下圖 5-1為 4個 peer情況人群狀態(tài),人群運動狀態(tài)。

圖5-1 四個對等下實驗結(jié)果

我們針對不同的情況,統(tǒng)計CPU利用率與循環(huán)一次所耗時間,結(jié)果如下表所示。表5-2為單機運行的結(jié)果,表5-3為兩個 Peer運行的結(jié)果,表5-4為四個peer運行的結(jié)果。

表5 -2單機結(jié)果分析

在我們的實驗中,盡量使整個系統(tǒng)達到負載均衡。從上表中我們可以清晰的看到,分布式系統(tǒng)能夠模擬更多的人群。隨著Peer的增加,模擬的總?cè)藬?shù)也會不斷增加,但每個Peer的平均人數(shù)在減少。

6 實驗結(jié)論與展望

在我們的論文中,我們介紹了一個基于agent的分布式人群模擬系統(tǒng)。我們利用agent的自治性與社會性很好地模擬了人群行為。此外,我們設(shè)計了一個P2P與 C/S相結(jié)合的混合網(wǎng)絡(luò)模型,我們的實驗取得了較好的效果。在分布式環(huán)境中,我們使用了地圖分層策略,大大提高了路徑規(guī)劃的效率。實驗結(jié)果展示,我們的系統(tǒng)非常成功并能很好地適用于大型公共設(shè)施人群運動情況。

在未來的工作中,我們將設(shè)計不同類型的Agent(如,小孩、老人、男人、女人),并對系統(tǒng)的一些算法進行優(yōu)化,此外,我們應(yīng)運用圖形學(xué)知識,對人物的動作進行擬合,使人物的動作看起來更流暢。

[1] 徐高.人群疏散的仿真研究[D].西南交通大學(xué),2003.

[2] G.Keith Still,Crowd Dynam ics:[PhD Thesis],UK:University ofWarw ick,2000.

[3] Xiaoshan Pan,Charles S.Han and Kincho H.Law;A Multi-Agent Based Simulation Framework for the Study of Human and Social Behavior in EgressAnalysis.

[4] AvneeshSud,Erik Andersen,Sean Curtis,Ming Lin,Dinesh Manocha;Real-time Path Planning for Virtual Agents in Dynamic Environments;Virtual Reality Conforence,2007,IEEE.10-14March,2007:91-98.

[5] Yongqing Ye,QinggeJi;Real.Real-Time Path Planning of Large-scale VirtualCrowd;Third InternationalConference on International Information Hiding and Multimedia Signal Processing,November26-28,2007,Kaohsiung,Taiwan.

[6] vneeshSud,Erik Andersen,Sean Curtis,Ming Lin,Dinesh Manocha;Real-time Navigation of IndependentAgents Using Adaptive Roadmaps;ACMSiggraph 2008.

[7] Mubbasir Kapadia,Shawn Singh,Brian Allen,Glenn Reinman,Petros Faloutsos,SteerBug:An Interactive Framework for Specifying and Detecting Steering Behaviors;Proceedings of the 2009 ACMSIGGRAPH/Eurographics Symposium on Computer Animation,August 01-02,2009,New Orleans,Louisiana.

[8] Hao Jiang,Wenbin Xu,Tianlu Mao,Chunpeng Li,Shihong Xia,Zhaoqi Wang;A Semantic Environment Model for Crowd Simulation in Multi-layered Complex Environment;Proceedings of the 16th ACMSymposium on Virtual Reality Software and Technology,November 18-20,2009,Kyoto,Japan.

[9] Russell Gayle,Dinesh Manocha,Navigating Virtual Agents in Online Virtual W orlds;Proceedings of the 13th international symposium on 3D web technology,August 09-10,2008,LosAngeles,California.

[10] Miguel Lozano,Pedro Morillo,Daniel Lew is,Dirk Reiners and Carolina Cruz-Neira;A Distributed Framework for Scalable Large-Scale Crowd Simulation;Virtual Reality,HCII2007,LNCS 4563,pp.111-121,2007.

[11] u,X.,ArtificialAnimals forComputerAnimation:Biomechanics,Locomotion,Perception,and Behavior,Ph.D Dissertation,Department of Computer Science,University of Toronto,1996.