張秀國(guó)

摘 要： 計(jì)算機(jī)模擬行人的運(yùn)動(dòng)行為在人群模擬、數(shù)字娛樂(lè)及安全規(guī)劃等都有著廣泛的應(yīng)用。人群運(yùn)動(dòng)仿真的常用模型包括基于規(guī)則模型、基于社會(huì)力模型、元胞自動(dòng)機(jī)模型和基于Agent模型等。詳細(xì)介紹了各種模型的優(yōu)缺點(diǎn)，以及人群運(yùn)動(dòng)規(guī)劃，包括全局路徑規(guī)劃、局部路徑導(dǎo)航和個(gè)體之間的交互作用?，F(xiàn)階段要想實(shí)現(xiàn)真實(shí)的人群運(yùn)動(dòng)模擬效果，需要根據(jù)各種環(huán)境因素選用合適的模型來(lái)提高人群運(yùn)動(dòng)的仿真度。

關(guān)鍵詞： 人群運(yùn)動(dòng)模型； 碰撞避免； 運(yùn)動(dòng)控制； 路徑

中圖分類(lèi)號(hào)：TP391.9 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：1006-8228（2016）11-61-03

Analysis of crowd movement simulation model

Zhang Xiuguo

（Qingdao Technological University Qindao College， Department of Computer Engineering， Qingdao， Shandong 266100， China）

Abstract： The simulation of pedestrian movement behavior has a wide range of applications in the crowd simulation， digital entertainment and security planning. The commonly used crowd motion simulation models include the rule-based model， the social force based model， the cellular automata model and Agent based model， etc. This paper introduces the advantages and disadvantages of various models in detail， and the crowd movement planning， including the global path planning， the local path navigation and interaction effect between individuals and so on. In order to realize the real crowd movement simulation effect， a suitable model needs to be adopted according to various environmental factors to improve the simulation fidelity of the crowd movement.

Key words： crowd movement model； collision avoidance； moment control； path

0 引言

近年來(lái)由于計(jì)算機(jī)技術(shù)的不斷發(fā)展，模擬行人的運(yùn)動(dòng)行為在人群模擬、數(shù)字娛樂(lè)及安全規(guī)劃等都有著廣泛的應(yīng)用。雖然人類(lèi)在擁擠的地方能夠順利甚至毫不費(fèi)力的移動(dòng)，但對(duì)于計(jì)算機(jī)程序來(lái)說(shuō)，模仿這種行為的現(xiàn)實(shí)性仍然是一個(gè)挑戰(zhàn)性的任務(wù)。

人群運(yùn)動(dòng)仿真行為的研究大致有宏觀和微觀兩種行為的研究。人群運(yùn)動(dòng)宏觀行為研究一般針對(duì)大范圍的人群流動(dòng)場(chǎng)景，研究以組為單位的人群行為。而微觀行為研究則關(guān)注于人群中個(gè)體行為研究，適合于人群不太密集的場(chǎng)合。虛擬人和虛擬環(huán)境的相互作用在人群運(yùn)動(dòng)模擬中非常關(guān)鍵，人群在運(yùn)動(dòng)的過(guò)程中不斷感知周?chē)h(huán)境信息并進(jìn)行運(yùn)動(dòng)調(diào)整。

1 人群運(yùn)動(dòng)模擬模型

大量的學(xué)者在研究人群運(yùn)動(dòng)行為時(shí)，提出了一系列模型。具有代表性的模型有：基于規(guī)則模型、基于社會(huì)力模型、元胞自動(dòng)機(jī)模型和基于Agent模型等。下面將分別介紹這些模型。

1.1 基于規(guī)則模型

在計(jì)算機(jī)圖形學(xué)領(lǐng)域中，1987年Reynolds[1]對(duì)鳥(niǎo)群的開(kāi)創(chuàng)性工作，提出了Boid（鳥(niǎo)群仿真運(yùn)動(dòng)模型）是最早的關(guān)于行為模擬的文章之一。該模型可以模擬鳥(niǎo)群的聚集飛行行為，描述了一種分布式的行為模型來(lái)模擬鳥(niǎo)群的運(yùn)動(dòng)。

基于個(gè)體規(guī)則的方法只能模擬較簡(jiǎn)單的群體運(yùn)動(dòng)。對(duì)于人類(lèi)群體的運(yùn)動(dòng)行為由于規(guī)則數(shù)量的不斷增加，從而使規(guī)則順序大量增加，實(shí)驗(yàn)的難度也會(huì)增大。因此，基于個(gè)體行為規(guī)則的方法很難全面描述人群運(yùn)動(dòng)行為。基于規(guī)則的模型在實(shí)現(xiàn)避免碰撞時(shí)是根據(jù)預(yù)定義的規(guī)則狀態(tài)[2]，視覺(jué)上吸引人的模擬是可以實(shí)現(xiàn)的。但是，對(duì)于特定場(chǎng)景情況規(guī)則可能是緊密耦合。因此這樣的模型在一般情況下可能起不到很好的作用。

1.2 基于社會(huì)力模型

Drik Helbing等最初從人類(lèi)社會(huì)心理學(xué)和力學(xué)兩方面，模擬了人群在恐慌狀態(tài)下的特點(diǎn)，假設(shè)行人受到社會(huì)力的作用，提出了社會(huì)力學(xué)模型[3]。由于該模型是以牛頓力和個(gè)體間相互的社會(huì)心理影響力為基礎(chǔ)，可信度較高，因此被廣泛應(yīng)用和研究。在該模型里，行人在運(yùn)動(dòng)時(shí)會(huì)受到自身的期望速度大小和期望速度方向、人與人之間的作用力fij和障礙物對(duì)人的作用力fiw這三方面的影響。根據(jù)這三個(gè)因素，這些力的合力作用于行人，行人在時(shí)間t的速度改變量可由下面公式得到：

⑴

Helbing等通過(guò)真實(shí)實(shí)驗(yàn)測(cè)試了社會(huì)力模型的有效性，并對(duì)社會(huì)力模型進(jìn)行校正，他們發(fā)現(xiàn)了多個(gè)不常見(jiàn)的安全措施。例如障礙的合理設(shè)置將有利于產(chǎn)生穩(wěn)定的人流，之字形的通道有利于減輕恐慌人群擁擠的壓力等。Brogan提出了用算法去控制受復(fù)雜動(dòng)力學(xué)因素影響的個(gè)體運(yùn)動(dòng)，此模型適用對(duì)象是一些具有顯著物理特征的特殊人群[4]。在建模過(guò)程中使用動(dòng)力學(xué)原理來(lái)對(duì)人群的位置、前進(jìn)速度和加速度變化進(jìn)行量化?；谏鐣?huì)力模型的優(yōu)點(diǎn)是其物理意義比較直觀，模型中變量能夠較好的模擬人群真實(shí)運(yùn)動(dòng)情況，但是由于有較多的作用力參數(shù)，使各種作用力之間較難平衡，計(jì)算的復(fù)雜度高，因此難以得到較平滑的運(yùn)動(dòng)軌跡。

1.3 元胞自動(dòng)機(jī)模型

Von Neumann 和Stanislaw Ulam最早提出元胞自動(dòng)機(jī)模型，目前主要廣泛應(yīng)用于模擬各種物理系統(tǒng)和自然現(xiàn)象[5]等。元胞自動(dòng)機(jī)模型不需要經(jīng)過(guò)復(fù)雜的運(yùn)算，只要直接通過(guò)制定行為準(zhǔn)則就可以來(lái)模擬非線性物理現(xiàn)象。由于人群是一個(gè)具有高度復(fù)雜性和不確定性的群體，人群行為的模擬遠(yuǎn)比車(chē)輛等按一定規(guī)則進(jìn)行運(yùn)動(dòng)的物體模擬要困難得多，而元胞自動(dòng)機(jī)模型則是用來(lái)模擬人群行為的一種高效的技術(shù)。Fruin對(duì)行人流進(jìn)行了詳細(xì)的分析。受他的影響，上個(gè)世紀(jì)九十年代初，國(guó)外研究者們開(kāi)發(fā)出了一系列用于行人模擬的方法。

元胞自動(dòng)機(jī)模型較明顯的優(yōu)點(diǎn)是通過(guò)少量簡(jiǎn)單的規(guī)則可以近似模擬實(shí)際中觀察到的行人現(xiàn)象，并且這些規(guī)則在直覺(jué)上很容易理解，與復(fù)雜的行為模型相比，其計(jì)算過(guò)程簡(jiǎn)單且高效。這種模型也有很明顯的缺點(diǎn)，比如把模擬空間離散成二維的網(wǎng)格時(shí)，模擬個(gè)體的運(yùn)動(dòng)通常受到限制，只能移動(dòng)到相臨近的四個(gè)空閑網(wǎng)格之一，另外當(dāng)較大人群擁擠在一起時(shí)，模擬出的人群效果就像棋盤(pán)格一樣均勻，人群之間的推擠和碰撞無(wú)法模擬出，因此會(huì)導(dǎo)致其結(jié)果嚴(yán)重失真。

1.4 基于Agent模型

基于Agent模型中，每個(gè)Agent可以看作是有自適應(yīng)性和智能性的實(shí)體，可以自主的感知其周?chē)h(huán)境。在仿真模型中對(duì)個(gè)體單獨(dú)建模，定義個(gè)體的運(yùn)動(dòng)規(guī)則和屬性，而不對(duì)每個(gè)具體的行為下定義。通常一個(gè)Agent包括以下幾個(gè)特征[6]：自主性，自動(dòng)感知外部環(huán)境的信息；社會(huì)性，通過(guò)某種行為與其他Agent的相互作用；主動(dòng)性，為了執(zhí)行預(yù)先設(shè)定的目標(biāo)而自主采取的行為規(guī)則。這些特點(diǎn)有利于研究群體當(dāng)中單個(gè)個(gè)體的屬性和行為，以及某種行為發(fā)生的原因。如圖1所示，表示的是典型的Agent圖。

通常單個(gè)的agent模型較少，常見(jiàn)的大多是Muti-agent模型。Muti-agent模型中包含多個(gè)單個(gè)agent模型，由多個(gè)agent相互合作來(lái)完成單個(gè)agent模型不能解決的復(fù)雜問(wèn)題。

2 人群運(yùn)動(dòng)控制

人群運(yùn)動(dòng)的模擬是個(gè)極其復(fù)雜的問(wèn)題，個(gè)體運(yùn)動(dòng)時(shí)需要全面考慮全局目標(biāo)和局部環(huán)境的影響。人群運(yùn)動(dòng)模擬通過(guò)控制個(gè)體在保持碰撞避免的條件下順利到達(dá)目標(biāo)，這是人群運(yùn)動(dòng)控制的目的，個(gè)體自身的特性和限制在運(yùn)動(dòng)控制的過(guò)程中需要加以考慮。針對(duì)人群的運(yùn)動(dòng)規(guī)劃，包括全局路徑規(guī)劃、局部路徑導(dǎo)航、碰撞的避免和個(gè)體之間的交互作用等。

2.1 全局路徑規(guī)劃和局部路徑導(dǎo)航

人群運(yùn)動(dòng)模擬中，個(gè)體從當(dāng)前位置到達(dá)目標(biāo)的大致路線可表示為全局路徑規(guī)劃和局部路徑導(dǎo)航。元胞自動(dòng)機(jī)模型常用于路徑規(guī)劃，將模擬區(qū)域劃分為二維網(wǎng)格，其中每個(gè)網(wǎng)格都是一個(gè)基本單元。從計(jì)算模型的角度來(lái)看，復(fù)雜的運(yùn)動(dòng)行為通常來(lái)自agent兩個(gè)方面的活動(dòng)：路徑規(guī)劃和運(yùn)動(dòng)。路徑規(guī)劃可以被認(rèn)為是更高級(jí)的行為，生成一個(gè)全局路徑目標(biāo)的agent。通常認(rèn)為環(huán)境的靜態(tài)方面比如墻和門(mén)。為了避免動(dòng)態(tài)障礙，運(yùn)動(dòng)被認(rèn)為是低級(jí)行為來(lái)促使agent的運(yùn)動(dòng)。這個(gè)雙層的方法在有些程序中是有效的，但在生成實(shí)際人類(lèi)運(yùn)動(dòng)時(shí)是不足的。使用更高級(jí)的認(rèn)知信息來(lái)調(diào)整路線的動(dòng)態(tài)性，這些調(diào)整是通過(guò)采取決策盡量減少碰撞的可能性。全局路徑規(guī)劃和局部路徑導(dǎo)航相搭配的方法可以引導(dǎo)個(gè)體向目標(biāo)運(yùn)動(dòng)。

2.2 碰撞的避免

避免碰撞是運(yùn)動(dòng)過(guò)程中需要考慮的一個(gè)重要方面。人群運(yùn)動(dòng)仿真過(guò)程中，由于虛擬環(huán)境中通常存在不同的障礙物。因此個(gè)體之間可能發(fā)生碰撞，個(gè)體與障礙物之間也可能發(fā)生碰撞。并且碰撞可能是靜態(tài)物體與動(dòng)態(tài)物體碰撞，也可能是動(dòng)態(tài)物體的相互碰撞。人群運(yùn)動(dòng)模擬將行人看作移動(dòng)的障礙，而將個(gè)體之間的碰撞避免的問(wèn)題看作障礙物的避讓。人與人之間碰撞的避免，需要在模擬過(guò)程中設(shè)計(jì)有效的策略。個(gè)體對(duì)自己當(dāng)前環(huán)境認(rèn)知后更新其狀態(tài)，并盡快被其他個(gè)體所認(rèn)知。

另一種考慮是，將碰撞問(wèn)題集成在路徑規(guī)劃的框架下，通過(guò)進(jìn)行設(shè)計(jì)和尋找無(wú)碰撞的路徑來(lái)避免顯式的碰撞處理。

行人使用路徑規(guī)劃指導(dǎo)來(lái)確保他們的運(yùn)動(dòng)是光滑和有效從而避免碰撞。但是，這樣的現(xiàn)象不一定能反映任何智能機(jī)械確保碰撞及自由移動(dòng)。事實(shí)上，我們認(rèn)為行人在大多數(shù)情況下，不需要很復(fù)雜的決策。相反，他們很熟悉依靠簡(jiǎn)單的策略對(duì)應(yīng)不同的情況。大多數(shù)基于agent的方法依靠各種機(jī)械或者轉(zhuǎn)向規(guī)則阻止agent相互碰撞。這種方法有兩個(gè)主要的缺點(diǎn)：①很難設(shè)計(jì)針對(duì)不同情況的規(guī)則，將這類(lèi)規(guī)則與人類(lèi)行為聯(lián)系起來(lái)是很難的；②制造行為的實(shí)際情況很大程度上取決于設(shè)計(jì)者對(duì)優(yōu)化參數(shù)的經(jīng)驗(yàn)。

3 結(jié)束語(yǔ)

本文主要介紹了人群運(yùn)動(dòng)仿真中的常用模型，并通過(guò)個(gè)體間的相互作用對(duì)各個(gè)模型進(jìn)行了詳細(xì)分析，包括各個(gè)模型的優(yōu)缺點(diǎn)。由此可以看出，選用合適的運(yùn)動(dòng)模型對(duì)提高人群運(yùn)動(dòng)的仿真度是至關(guān)重要的。除此之外，碰撞避免也是人群運(yùn)動(dòng)仿真中一個(gè)不可回避的問(wèn)題。通過(guò)對(duì)碰撞避免的情況分析，決定出個(gè)體運(yùn)動(dòng)路徑規(guī)劃，從而更好的模擬出人群運(yùn)動(dòng)的方向及行為。

參考文獻(xiàn)（References）：

[1] Reynolds， Flocks， birds， and schools a distributed behavior

model， Computer Graphics，1987.21：25-34

[2] HELB NG D， FARKAS I， V ISCSEK T V .Simulating

dynamical feature of escape panic[J].Nature，2000.407（28）：487-490

[3] Lamarche， F.， Donikian， S.： Crowd of Virtual Humans： a

New Approach for Real Time Navigation in Complex and Structured Environments. Computer Graphics Forum，2004.23：509-518

[4] Brrun， A.， Musse， S.R.， Oliveira， L.P.L. and Bodmann， B.

E.J.， Modeling Individual Behaviors in Crowd Simulation. In Proceedings of Computer Animation and Social Agents，2003：143-148

[5] John von Neumann. The general and logical theory of

automata. Cerebral Mechanisms in Behavior-The Hixon Symposium， John Wiley &Sons， New York，1951：1-31

[6] 王紅衛(wèi).建模與仿真[M].科學(xué)出版社，2002.