大規(guī)模人群模擬中的碰撞避免研究與實(shí)現(xiàn)

謝凱麗

（四川大學(xué)計(jì)算機(jī)系，成都610065）

0 引言

近年來隨著人們生活水平和計(jì)算機(jī)圖形技術(shù)的廣泛發(fā)展與影響，人們對(duì)大規(guī)模人群運(yùn)動(dòng)模擬也提出了越來越高的要求，例如人們需要更為真是貼切的虛擬現(xiàn)實(shí)場(chǎng)景，在這樣的一個(gè)場(chǎng)景中，在更為真實(shí)快速的渲染中，每個(gè)個(gè)體需要流暢地避開所有其他個(gè)體或者是靜態(tài)障礙物，真實(shí)穩(wěn)定地實(shí)現(xiàn)虛擬現(xiàn)實(shí)中的人群模擬運(yùn)動(dòng)的實(shí)時(shí)性、真實(shí)感與科學(xué)合理性。

本文主要介紹了筆者研究該課題過程中所做的相關(guān)算法分析和實(shí)現(xiàn)、碰撞避免的實(shí)現(xiàn)與數(shù)據(jù)處理過程中針對(duì)于算法求解的優(yōu)化分析。基于RVO 算法的大規(guī)模人群模擬中的碰撞避免問題的實(shí)現(xiàn)和分析過程中，在第一步構(gòu)建簡(jiǎn)單屬性機(jī)器人模型的過程中，初始化所有模型的速度、位置、目標(biāo)點(diǎn)和最大速度范圍，靜態(tài)障礙物的位置。在我們進(jìn)行RVO 計(jì)算前，我們考慮到對(duì)實(shí)驗(yàn)效率和真實(shí)感的要求，可以嘗試用一些尋路算法和搜索算法進(jìn)行每個(gè)模型的路徑的設(shè)置和其他需要納入計(jì)算的相關(guān)模型的搜索。在通過RVO 算法計(jì)算出速度可行域之后，我們需要通過一些方法來求得最終解，這也是筆者認(rèn)為本實(shí)驗(yàn)中最具考驗(yàn)的階段。在本實(shí)驗(yàn)中首先運(yùn)用ORCA 方法求出每個(gè)模型的最終可行速度范圍，進(jìn)而通過線性分析方法詳釋了在速度的各種分析情況下進(jìn)行最終解的計(jì)算。

1 RVO算法實(shí)現(xiàn)

1.1 算法描述

碰撞避免已經(jīng)很好地通過基于速度的方法解決了目標(biāo)個(gè)體與動(dòng)態(tài)障礙物之間的碰撞問題，它為目標(biāo)實(shí)體和移動(dòng)障礙物之間的碰撞避免提供了一種十分有效的方法。當(dāng)我們把這種方法擴(kuò)展到大規(guī)模人群模擬中的碰撞避免實(shí)現(xiàn)中，每一組參與計(jì)算的機(jī)器人模型都需要計(jì)算新速度和新位置。這個(gè)新速度能夠?qū)崿F(xiàn)目標(biāo)模型與其他機(jī)器人模型之間的碰撞避免，這是一種相互的碰撞避免的實(shí)現(xiàn)，它是在計(jì)算出不可行速度區(qū)域之后選擇出的可實(shí)行速度范圍。以上可以簡(jiǎn)單地理解成基于RVO 實(shí)現(xiàn)碰撞檢測(cè)和避免的過程。

1.2 RVO 的碰撞檢測(cè)避免

本小節(jié)對(duì)碰撞避免的整個(gè)算法流程進(jìn)行簡(jiǎn)單的概述。首先對(duì)于機(jī)器人A 我們需要獲取當(dāng)前機(jī)器人的位置p、初速度V、最大速度Vmax、最優(yōu)速度Vpref以及周邊機(jī)器人的位置和初速度，模型A 不斷地對(duì)其他機(jī)器人的數(shù)據(jù)進(jìn)行檢測(cè)獲取和計(jì)算，從而得到實(shí)現(xiàn)碰撞避免的新速度范圍，獲得這些范圍之后我們需要對(duì)n 個(gè)速度范圍運(yùn)用一定的方法從而得到最終解決方案。

所以：

在公式（2）中，t 代表將來的一段時(shí)間，pm和pn分別表示模型m 和模型n 的位置，rm和rn表示兩模型的半徑?？赏ㄟ^圖1 分析得到：

圖1（a）表示模型m 和n 的結(jié)構(gòu)和位置。圖1（b）中將二維平面中抽象的速度問題線性化，將速度表示為坐標(biāo)系中的二維矢量，VOtm|n即為我們要求的m 和n之間會(huì)產(chǎn)生碰撞的m 的相對(duì)速度范圍，其范圍是由一段半圓弧和兩條切線構(gòu)成，半圓弧的圓心為，半徑為，所以灰色區(qū)域即為我們實(shí)現(xiàn)m 與n 之間的碰撞避免的m 的速度的不可行區(qū)域，并且在模型的屬性一定的情況下，該范圍是由參與計(jì)算的時(shí)間t 決定的。圖1（c）表示在機(jī)器人n 速度為區(qū)域Vn中時(shí)，通過圖1（b）中方法的多次分析而得到的在時(shí)間t 范圍內(nèi)，實(shí)現(xiàn)模型m 與模型n 之間碰撞避免的m 的絕對(duì)速度的不可行區(qū)域。首先我們?cè)诠剑?）用X⊕Y 表示閔可夫斯基和（閔可夫斯基和是兩個(gè)歐幾里得空間的點(diǎn)集的和，以德國(guó)數(shù)學(xué)家閔可夫斯基命名）

對(duì)于機(jī)器人n 的可行速度的計(jì)算，其相對(duì)速度不可行線性化的結(jié)果與圖1（b）關(guān)于原點(diǎn)對(duì)稱的，詳細(xì)原因與上述分析步驟一致,所以：

其中Vm為模型m 的速度。

綜上所述，模型m 與模型n 不發(fā)生碰撞所要產(chǎn)生的新動(dòng)作（即它們的新速度）的可選范圍已被求出。當(dāng)，并且時(shí)，則Vm和Vn為m與n 避免相互碰撞的速度。

2 碰撞避免的實(shí)現(xiàn)與優(yōu)化

2.1 ORCA— —基于RVO 的碰撞避免的實(shí)現(xiàn)與優(yōu)化

圖1

圖2

因?yàn)楸菊n題研究的碰撞避免方法對(duì)于任何一個(gè)實(shí)例模型都是高效且平等地處理，所以模型m 和模型n的速度需要分別增加來進(jìn)行新動(dòng)作的計(jì)算。

因?yàn)槟Ｐ蚼 有最大速度限制，所以要求出最優(yōu)速度中符合固定屬性的范圍：

更新機(jī)器人m 的位置：

通過討論我們得出了在機(jī)器人m 避免與機(jī)器人n發(fā)生碰撞所需要的新速度的優(yōu)化范圍。然而在大規(guī)模人群模擬中機(jī)器人m 需要避開其他多個(gè)機(jī)器人，所以我們最終求解出了多個(gè)ORCA,并且需要求解出多個(gè)半平面的交集，當(dāng)多個(gè)半平面沒有交集時(shí)，我們需要對(duì)模型的初速度進(jìn)行修改。

需要注意的是，多個(gè)半平面不存在交集的情況是存在的。在我們進(jìn)行RVO 的實(shí)現(xiàn)時(shí)，我們需要每個(gè)機(jī)器人的速度位置大小來進(jìn)行計(jì)算，位置和大小是固定不變的屬性，我們需要合適的初速度來進(jìn)行計(jì)算（需要注意的是為了進(jìn)行更高效率的計(jì)算，最優(yōu)地實(shí)現(xiàn)碰撞避免，我們的初速度不一定要選擇機(jī)器人當(dāng)前的速度來進(jìn)行計(jì)算）。對(duì)于初速的合理選擇有助于我們算法的高效實(shí)現(xiàn)。

2.2 碰撞避免實(shí)現(xiàn)中的相關(guān)分析與優(yōu)化求解

前文我們討論了RVO 的實(shí)現(xiàn)和優(yōu)化，討論過程中我們將模型m 視為有著確切目標(biāo)的移動(dòng)中的實(shí)體。那么當(dāng)場(chǎng)景中存在靜態(tài)障礙物時(shí)，我們研究和計(jì)算的方法是一致的。我們可以將靜態(tài)障礙物視為由一些線性片段構(gòu)成的物體，如圖3 所示，假設(shè)O 為靜態(tài)障礙物，m 為處于pm一點(diǎn)半徑為rm的移動(dòng)的實(shí)體。通過前兩節(jié)算法的分析，我們可以得出如果m 的速度在范圍中，那么m 將會(huì)在時(shí)間t 內(nèi)與障礙物O 發(fā)生碰撞，反之如果m 的速度不在區(qū)域內(nèi)，那么m 與障礙物O 之間的碰撞避免就可以得到實(shí)現(xiàn)。單純求出并不能使我們通過線性分析從而求出m 最后的初速度，因此我們需要求出可行域半平面進(jìn)而求出初速度vopt到距離最短的點(diǎn)。

在討論與靜態(tài)障礙物的碰撞避免時(shí)，我們將初速度vopt設(shè)為0，因?yàn)榭紤]障礙物不會(huì)動(dòng)，而其他模型會(huì)動(dòng)，所以其他移動(dòng)中的模型的對(duì)新速度v 的偏差影響要遠(yuǎn)遠(yuǎn)大于障礙物的，所以在考慮障礙物的時(shí)候我們可以允許盡量的靠近障礙物來避免與其他模型碰撞。當(dāng)vopt=0 時(shí)，能夠最大限度地保證m 存在一個(gè)速度能夠和所研究靜態(tài)障礙物在時(shí)間t 內(nèi)實(shí)現(xiàn)碰撞避免。在與靜態(tài)障礙物作討論時(shí)，我們計(jì)算的時(shí)間t 可以遠(yuǎn)小于與其他模型作討論時(shí)的時(shí)間，因?yàn)闉榱藢?shí)現(xiàn)與其他移動(dòng)中的模型實(shí)現(xiàn)碰撞避免，我們可以極大地靠近靜態(tài)障礙物。

圖3

3 實(shí)驗(yàn)結(jié)果和分析

為了展示我們的算法結(jié)果，我們將數(shù)據(jù)通過OpenGL 繪制算法將數(shù)據(jù)直觀地展示出來。

如圖4。

圖4

圖4 （a）表示各個(gè)模型的初始位置包括障礙物的位置，圖4（b）展示了各個(gè)模型在運(yùn)動(dòng)過程中某個(gè)時(shí)刻的位置，圖4（c）表示運(yùn)動(dòng)趨于結(jié)束。這個(gè)實(shí)驗(yàn)將各個(gè)模型的初始位置和目標(biāo)位置分別初始化為障礙物兩邊的位置。

在上述實(shí)驗(yàn)中，我們給實(shí)驗(yàn)場(chǎng)景初始化了兩個(gè)靜態(tài)障礙物，注意在這種情況下，如果不進(jìn)行Dijkstra 尋路規(guī)劃，每個(gè)機(jī)器人都有可能為了避免彼此的碰撞而從障礙物的兩側(cè)移動(dòng)到達(dá)我們的目的地,而我們的實(shí)驗(yàn)結(jié)果是每個(gè)機(jī)器人都從兩個(gè)靜態(tài)障礙物之間的空隙中運(yùn)動(dòng)至對(duì)面的目的地，這樣便使我們的研究結(jié)果更加科學(xué)美觀。

4 結(jié)語(yǔ)

對(duì)具有真實(shí)感典型的大規(guī)模人群模擬是計(jì)算機(jī)圖形學(xué)虛擬現(xiàn)實(shí)領(lǐng)域研究的熱點(diǎn)和難點(diǎn)之一，實(shí)時(shí)的大規(guī)模人群模擬的相關(guān)研究成為最為關(guān)注的話題之一?；赗VO 算法的碰撞避免是一種有效地大規(guī)模人群模擬的研究方法實(shí)現(xiàn)時(shí)數(shù)學(xué)線性分析和計(jì)算機(jī)圖形學(xué)的交叉結(jié)合。RVO 算法是一種能夠有效實(shí)現(xiàn)大規(guī)模人群模擬中碰撞避免的方法之一，本文對(duì)RVO 算法進(jìn)行了基本的算法概述和實(shí)現(xiàn)，并通過各種尋路和搜索算法，結(jié)合線性分析的方法求出了碰撞避免的相關(guān)數(shù)據(jù)范圍，最后通過OpenGL 繪制算法實(shí)現(xiàn)了在保證實(shí)時(shí)性下得到碰撞避免的動(dòng)畫效果。在RVO 算法實(shí)時(shí)的模擬出無碰撞的大規(guī)模人群運(yùn)動(dòng)的基礎(chǔ)上，通過理論以及前人的相關(guān)研究，對(duì)最后結(jié)果的求解過程及其各種特殊情況以及結(jié)果的通過線性規(guī)劃進(jìn)行優(yōu)化分析進(jìn)行了充分的考慮和研究并得出分析結(jié)果。