謝凱麗

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

0 引言

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

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

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

1.1 算法描述

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

1.2 RVO 的碰撞檢測避免

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

所以：

在公式（2）中，t 代表將來的一段時間，pm和pn分別表示模型m 和模型n 的位置，rm和rn表示兩模型的半徑。可通過圖1 分析得到：

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

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

其中Vm為模型m 的速度。

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

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

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

圖1

圖2

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

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

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

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

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

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

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

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

圖3

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

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

如圖4。

圖4

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

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

4 結(jié)語

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