大規模人群模擬中的碰撞避免研究與實現

謝凱麗

（四川大學計算機系，成都610065）

0 引言

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

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

1 RVO算法實現

1.1 算法描述

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

1.2 RVO 的碰撞檢測避免

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

所以：

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

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

對于機器人n 的可行速度的計算，其相對速度不可行線性化的結果與圖1（b）關于原點對稱的，詳細原因與上述分析步驟一致,所以：

其中Vm為模型m 的速度。

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

2 碰撞避免的實現與優化

2.1 ORCA— —基于RVO 的碰撞避免的實現與優化

圖1

圖2

因為本課題研究的碰撞避免方法對于任何一個實例模型都是高效且平等地處理，所以模型m 和模型n的速度需要分別增加來進行新動作的計算。

因為模型m 有最大速度限制，所以要求出最優速度中符合固定屬性的范圍：

更新機器人m 的位置：

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

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

2.2 碰撞避免實現中的相關分析與優化求解

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

在討論與靜態障礙物的碰撞避免時，我們將初速度vopt設為0，因為考慮障礙物不會動，而其他模型會動，所以其他移動中的模型的對新速度v 的偏差影響要遠遠大于障礙物的，所以在考慮障礙物的時候我們可以允許盡量的靠近障礙物來避免與其他模型碰撞。當vopt=0 時，能夠最大限度地保證m 存在一個速度能夠和所研究靜態障礙物在時間t 內實現碰撞避免。在與靜態障礙物作討論時，我們計算的時間t 可以遠小于與其他模型作討論時的時間，因為為了實現與其他移動中的模型實現碰撞避免，我們可以極大地靠近靜態障礙物。

圖3

3 實驗結果和分析

為了展示我們的算法結果，我們將數據通過OpenGL 繪制算法將數據直觀地展示出來。

如圖4。

圖4

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

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

4 結語

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