群集運(yùn)動(dòng)行為的模型構(gòu)建與計(jì)算機(jī)仿真

邱 磊

(武漢船舶職業(yè)技術(shù)學(xué)院計(jì)算機(jī)教研室，湖北武漢430050)

自然界中很多種類的動(dòng)物中都存在著復(fù)雜的群集運(yùn)動(dòng)行為，典型的例子有鳥(niǎo)群、魚(yú)群、蟻群和蜂群等，以群集運(yùn)動(dòng)行為作為研究對(duì)象的模型系統(tǒng)是一個(gè)由大量自治個(gè)體組成的集合，一般通過(guò)個(gè)體的局部感知作用和相應(yīng)的反應(yīng)行為使其整體呈現(xiàn)出復(fù)雜的行為.在計(jì)算機(jī)虛擬世界中對(duì)群集運(yùn)動(dòng)行為進(jìn)行模擬，具有較強(qiáng)的理論意義和使用價(jià)值［1］，群集運(yùn)動(dòng)行為的模擬廣泛應(yīng)用于公共安全、游戲動(dòng)畫(huà)和影視特效等領(lǐng)域.本文在對(duì)群集運(yùn)動(dòng)機(jī)理分析的基礎(chǔ)上，對(duì)群集運(yùn)動(dòng)行為進(jìn)行了建模與仿真模擬.

1 群集運(yùn)動(dòng)行為研究

如果有一群能夠自行其事、自由移動(dòng)的個(gè)體，只需要使每個(gè)個(gè)體服從于3 個(gè)附加的規(guī)則［2－3］，就可以使由個(gè)體組成的集合并像自然界的魚(yú)群和鳥(niǎo)群那樣具有群體行為的能力，這3條規(guī)則是:1)分離規(guī)則:個(gè)體應(yīng)當(dāng)避免和自己的鄰居距離太近、造成碰撞;2)對(duì)齊規(guī)則:個(gè)體應(yīng)當(dāng)和自己附近的大多數(shù)鄰居保持相同的方向和速度;3)聚合規(guī)則:個(gè)體不能離自己附近的鄰居太遠(yuǎn)(見(jiàn)圖1).只要用此3條行為規(guī)則，就能讓計(jì)算機(jī)中的虛擬個(gè)體模擬現(xiàn)實(shí)世界中的群集運(yùn)動(dòng)行為.在群集運(yùn)動(dòng)過(guò)程中，每個(gè)個(gè)體都要遵守以上3條規(guī)則運(yùn)動(dòng)，3條規(guī)則對(duì)改變個(gè)體下一時(shí)刻運(yùn)動(dòng)的方向起作用［4］.

圖1 群集運(yùn)動(dòng)行為3規(guī)則示意圖

現(xiàn)以某群體為研究對(duì)象，將其建模為一個(gè)連續(xù)的三維空間且含有N個(gè)個(gè)體，每個(gè)個(gè)體的速度大小恒為v，設(shè)個(gè)體i在空間中的位置向量用ci=(x，y，z)來(lái)表示.迭代至第t步，個(gè)體i的位置向量為ci(t)，速度向量為vi(t)，速度方向?yàn)閐i(t)(模為1，即di(t)為vi(t)同方向的單位向量).將每一個(gè)體的感知范圍由里及外依次劃分為3個(gè)行為區(qū)域(如圖2所示):1)ZOR(Zone Of Repulsion)表示排斥區(qū)域:以個(gè)體i為球心，以rr為半徑的球，為分離規(guī)則的作用區(qū)域，在這個(gè)區(qū)域之內(nèi)的其他個(gè)體對(duì)個(gè)體i有排斥作用，即個(gè)體i希望遠(yuǎn)離排斥區(qū)域內(nèi)的其他個(gè)體;2)ZOO(Zone Of Orientation)表示一致區(qū)域:以個(gè)體i為中心，處于rr和ro之間的球形區(qū)域，為對(duì)齊規(guī)則的作用區(qū)域，在這個(gè)區(qū)域內(nèi)的其他個(gè)體對(duì)個(gè)體i總保持一致運(yùn)動(dòng)或保持一致運(yùn)動(dòng)的趨勢(shì);3)ZOA(Zone Of Attraction)表示吸引區(qū)域:以個(gè)體i為中心，處于ro和ra之間的球形區(qū)域，為聚合規(guī)則的作用區(qū)域，在此區(qū)域的其他個(gè)體對(duì)這個(gè)體i有吸引作用，即這個(gè)個(gè)體希望向它們靠近.ZOO和ZOA 2個(gè)球形區(qū)域要去除個(gè)體i背后的體積，該體積內(nèi)的鄰居是個(gè)體i無(wú)法感知的，因此稱之為盲區(qū)［5］，若個(gè)體的感知視角定義為α，則盲區(qū)定義為內(nèi)角(360－α)°的圓錐體.α=360°的個(gè)體則可感知行為區(qū)域內(nèi)任意方向的鄰居.

圖2 以個(gè)體i為球心的感知范圍所劃分的3個(gè)行為區(qū)域示意圖

在每一步，各個(gè)體會(huì)評(píng)估3個(gè)不重疊的行為區(qū)域內(nèi)其他鄰居的位置和(或)方向，依據(jù)群集運(yùn)動(dòng)行為3個(gè)規(guī)則，該評(píng)估信息可用來(lái)確定第t步時(shí)個(gè)體i的速度方向di(t).具體描述如下:

1)每個(gè)個(gè)體都試圖與ZOR區(qū)域中的各個(gè)鄰居維持一個(gè)最小距離，假設(shè)第t步時(shí)，ZOR區(qū)域內(nèi)有nr個(gè)鄰居，則個(gè)體i為避讓鄰居將其速度方向調(diào)整為

式中，j為個(gè)體i的鄰居且rij(t)=(cj－ci).ZOR可被理解為個(gè)體維持自身空間、避免碰撞所對(duì)應(yīng)的行為區(qū)域.

2)ZOO區(qū)域的寬度Δro=ro－rr且滿足rr≤|(cj－ci)|＜ro，個(gè)體i不斷調(diào)整自己的方向使之與ZOO區(qū)域內(nèi)的鄰居對(duì)齊，假設(shè)第t步時(shí)，ZOO區(qū)域中含有no個(gè)可感知的鄰居，得出

這種方向一致性能使群集運(yùn)動(dòng)中個(gè)體之間發(fā)生碰撞的次數(shù)最少.

3)每個(gè)個(gè)體當(dāng)與各個(gè)鄰居距離太遠(yuǎn)時(shí)，都有向各鄰居中心靠攏的特性.ZOA區(qū)域的寬度Δra=ra－ro且滿足ro≤|(cj－ci)|≤ra，假設(shè)第t步時(shí)，ZOA區(qū)域中含有na個(gè)可感知的鄰居，得出

這種引力表征了動(dòng)物體具有集群性、避免邊緣化的趨向.

將3個(gè)行為區(qū)域?qū)€(gè)體的影響抽象為3種作用力:即排斥力、一致力和吸引力.個(gè)體i的速度方向由其受到的作用力決定，一共可以分為3個(gè)部分:即由排斥力產(chǎn)生的速度方向dr(t)、由一致力產(chǎn)生的速度方向do(t)和由吸引力產(chǎn)生的速度方向da(t).通過(guò)速度方向分量的改變，可以計(jì)算出迭代至第t步時(shí)個(gè)體i總的速度方向

3個(gè)行為區(qū)域?qū)€(gè)體i的作用力因群體不同而有不同的權(quán)重，故可以加入作用力權(quán)重因子.設(shè)排斥區(qū)域、一致區(qū)域和吸引區(qū)域?qū)€(gè)體i的作用力權(quán)重因子分別為λr，λo，λa，則式(4)可改寫(xiě)為

其中，λr，λo，λa?［0，1］，且 λr+ λo+ λa=1. 有了速度方向公式之后，此個(gè)體的速度可以計(jì)算為

此個(gè)體的新位置可以由當(dāng)前位置和速度共同確定

2 計(jì)算機(jī)仿真

利用Matlab仿真群集運(yùn)動(dòng)行為在三維空間內(nèi)的運(yùn)動(dòng)情況，取個(gè)體數(shù)N=50，設(shè)作用力權(quán)重因子λr=0.4，λo=0.2，λa=0.4.初始狀態(tài)個(gè)體的位置和速度是隨機(jī)的、相對(duì)分散的，隨著迭代步數(shù)的增加，個(gè)體在各自運(yùn)動(dòng)模型的基礎(chǔ)上通過(guò)個(gè)體間的相互作用，逐漸朝著聚合的趨勢(shì)運(yùn)動(dòng)，最終形成了方向一致的群集運(yùn)動(dòng)效果.筆者給出的軌跡圖很好地反映了這一點(diǎn)，由此證明該模型在模擬動(dòng)物的群集運(yùn)動(dòng)上是有效的.

圖3 群集運(yùn)動(dòng)行為仿真結(jié)果

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

本文將動(dòng)物群的信息傳遞機(jī)制體現(xiàn)在吸引力、排斥力和一致力3個(gè)方面，通過(guò)分析個(gè)體間的行為規(guī)則，確定了個(gè)體的總的速度方向，從而求解出個(gè)體位置的迭代方程，并最終構(gòu)建了能表示動(dòng)物群集行為的通用模型.該模型只考慮了個(gè)體間的相互影響，并未對(duì)個(gè)體周圍的環(huán)境因素進(jìn)行探討，并且假定了每個(gè)個(gè)體的運(yùn)動(dòng)速率是恒定的，因此，本文所述群集運(yùn)動(dòng)行為的模型有待于進(jìn)一步改進(jìn).

［1］李健.群體運(yùn)動(dòng)模擬中的控制與計(jì)算方法研究［D］.北京:中國(guó)科學(xué)院計(jì)算技術(shù)研究所，2010.

［2］REYNOLDS C W.Flocks，herds and schools:a distributed behavioral model［J］.Computer Graphics，1987，21(4):25 －34.

［3］REYNOLDS C W.Steering behaviors for autonomous characters:proceedings of Game Developers Conference 1999.San Jose，March 15 －19，1999［C］.［S.l］:［s.n.］.

［4］田寶美.基于Vicsek模型的自驅(qū)動(dòng)集群動(dòng)力學(xué)研究［D］.合肥:中國(guó)科學(xué)技術(shù)大學(xué)，2009.

［5］COUZINW D I，KRAUSEW J，JAMESZ R，et al.Collective memory and spatial sorting in animal groups［J］.Journal of Theoretical Biology，2002，218(1):1－11.