羅月童， 王曉靜， 瞿德清， 季 浩， 劉曉平

（合肥工業(yè)大學(xué)計算機(jī)與信息學(xué)院VCC研究室，安徽 合肥 230009）

路徑生成算法是仿真、游戲等領(lǐng)域的重要研究內(nèi)容，避障路徑生成算法是其重要組成部分。文獻(xiàn)[1]的算法（如圖1 所示）是早期研究工作的一個代表，它首先依據(jù)障礙物的凸包確定路徑上的關(guān)鍵點，然后用直線依次連接關(guān)鍵點構(gòu)成避障路徑。這種算法不僅所生成的路徑不真實，而且它沒有考慮運動物體固有的物理屬性，如車輛的尺寸、速度、轉(zhuǎn)彎半徑等。

本文以車輛為對象，考慮車輛的自身尺寸、速度、轉(zhuǎn)彎、半徑等物理屬性，提出并實現(xiàn)了一種基于物理模型的避障路徑生成算法。

圖1 利用直線和障礙物凸包得到路徑

1 問題分析

避障路徑生成可分為兩大步驟：首先按某種規(guī)則確定一組關(guān)鍵點，然后采用某種插值算法將所有關(guān)鍵點連接生成一條路徑。路徑插值算法很多，如文獻(xiàn)[1]中線性插值算法、文獻(xiàn)[2]中的基于Hermite 樣條曲線的路徑生成算法。因為，三次參數(shù)樣條曲線可以經(jīng)過每一個給定的型值點（路徑關(guān)鍵點），給定端點約束條件，便可生成一條C2連續(xù)的曲線，且具有幾何不變性及局部性等特 點[3-6]，本文基本采用三次參數(shù)樣條曲線擬合避障路徑。因此，問題的關(guān)鍵是確定避障路徑的關(guān)鍵點，本文的方法考慮以下因素：

· 障 礙 物 本文僅考慮障礙物的尺寸和形狀屬性；

· 運動車輛 本文考慮車輛尺寸屬性和轉(zhuǎn)彎半徑屬性；

· 原有路徑 為了保證避障路徑和原路徑之間的G1連續(xù)性，本文方法在確定避障路徑關(guān)鍵點時需要考慮原有路徑的屬性。

2 避障路徑生成算法

避障路徑生成過程如圖2 所示，首先需要根據(jù)某些條件來確定路徑關(guān)鍵點；對于給定的n 個關(guān)鍵點，只要知道各關(guān)鍵點處的空間坐標(biāo)和邊界條件，就可以計算得出各點處的切向量[5]，進(jìn)而得到各Hermite 曲線段的邊界條件，最終插值得到整個樣條曲線，即生成路徑。

圖2 避障算法流程

2.1 確定路徑關(guān)鍵點

作為算法的基礎(chǔ)，考慮到車輛的尺寸和障礙物尺寸等因素，本文提出了外擴(kuò)凸包的概念：設(shè)車輛的寬度為w，由障礙物凸包的各頂點，分別沿各自兩條鄰邊的外角平分線方向向外擴(kuò)展k 的距離(k＞w)，所形成的新的凸包多邊形，即為外擴(kuò)凸包，其中k 為外擴(kuò)系數(shù)。本文首先生成障礙物的外擴(kuò)凸包，然后基于外擴(kuò)凸包的頂點確定路徑關(guān)鍵點。

如圖3 所示，假設(shè)障礙物存在于原路徑L1上 pa、 pb之間。因為，避障路徑只能位于原路徑的同一側(cè)，因此在生成一條避障路徑時，只需考慮位于原路徑一側(cè)的外擴(kuò)凸包頂點，現(xiàn)將位于L1的某一側(cè)的頂點記為 p1… pn。

如果將 p1… pn全作為路徑關(guān)鍵點，則生成的路徑如圖3 中路徑L2，過于彎曲，不符合實際。本文按下述方法對 p1… pn進(jìn)行挑選，使得所生成路徑如L3所示，更加自然逼真。

以 pa點為原點，以原路徑L1在 pa的切向量方向為x 軸正向建立局部坐標(biāo)系。設(shè)原路徑L1的曲線方程為 f ( x,y)=0，分別從 pa, pb向障礙物外擴(kuò)凸包的各頂點引切線，可得切線斜率kia和 kib, 其中1≤i ≤ n 。顯然，無論凸包形狀如何，都會存在這樣的兩個點 ps和pt，它們在原路徑曲線的同一側(cè)， ps先于或等于 pt且斜率ksa, ktb的絕對值分別為最大。即滿足下面條件：

（1） s ≤ t；

（2） f ( xs,ys)? f(xt,yt)＞0；

將 ps、 pt兩點選入控制點集，若它們之間存在其它點 pj,s ≤ j ≤ t，由凸包性可知，其一定在 ts pp 連線的外側(cè)（遠(yuǎn)離障礙物的一側(cè)），則 加入控制點集，直到控制點集為最大。依次以這些控制點為關(guān)鍵點，可以生成一條樣條曲線路徑。

圖3 路徑關(guān)鍵點的選擇

2.2 生成候選路徑

為了保證與原路徑的G1連續(xù)，本文以新路徑與原路徑連接點處的切向量 p'a、 p'b作為邊界條件，可以得到矩陣表達(dá)式[5]

從而得到各Hermite 曲線段的端點約束，即得到樣條曲線路徑。

三次Bézier 曲線需要4 個控制點，因為三次參數(shù)樣條曲線具有幾何不變性和局部性，本文用如下方法來確定控制點（如圖4 所示）：

圖4 第一段曲線的改進(jìn)

（1） 局部坐標(biāo)系的建立同2.1；

（3） 依次以 Pa、 A1、 A2、Ps為控制點，形成控制多邊形，則生成的Bézier 曲線不會超出控制多邊形的區(qū)域。

由Bézier 曲線的端點性質(zhì)可知， Pa、 Ps兩點處的切向量方向不會發(fā)生變化，故可以保證路徑的G1連續(xù)。bp 點可用同樣方法處理。

2.3 確定避障路徑

該算法未考慮避障路徑上存在障礙物的情況，針對該情況，可以將新障礙物的外擴(kuò)凸包頂點加入到預(yù)選頂點中來，然后再應(yīng)用該算法，找出避障路徑。

3 實驗和應(yīng)用

本算法在某軍的三維戰(zhàn)場仿真決策系統(tǒng)中得到應(yīng)用，如圖5 所示。圖中原路徑C1上存在障礙物，C2為避障路徑，仿真效果良好。

4 總結(jié)與展望

本算法在基于物理模型的基礎(chǔ)上，利用三次參數(shù)樣條曲線生成避障路徑，可以保證新生成路徑本身的C2連續(xù)性和與原路徑的G1連續(xù)；在計算插值點三維坐標(biāo)時，只關(guān)心車輛的x 和y 坐標(biāo)，至于車輛的高度信息（z 坐標(biāo)值），可以在具體的應(yīng)用中實時獲取地面信息，保證車輛隨時緊貼地面運動即可；障礙物位于pa, pb中點位置附近時，避障路徑生成效果最好，所以本算法與合適的障礙物檢測算法配合能達(dá)到較好的仿真效果。

[1] 吳風(fēng)光, 叢 爽. 自動避障中的一種路徑生成、選擇與實現(xiàn)[C]//自動化理論、技術(shù)與應(yīng)用. 2002： 63-68.

[2] 劉曉平, 曹 力, 張 靜. 物體運動路線多樣化模擬[J]. 工程圖學(xué)學(xué)報, 2007, 28(3)： 39-43.

[3] 包 曄. 樣條插值在運動模擬中的應(yīng)用[J]. 杭州師范學(xué)院學(xué)報(自然科學(xué)版), 2004, 3(5)： 373-377.

[4] 賴舜男, 吳學(xué)禮, 汪國平. G2三次Hermite 樣條曲線形狀的交互修改[J]. 計算機(jī)應(yīng)用研究, 2004, (10)： 106-109.

[5] 唐澤圣, 周嘉玉, 李新友. 計算機(jī)圖形學(xué)基礎(chǔ)[M]. 北京： 清華大學(xué)出版社, 1995. 78-87.

[6] 銀紅霞, 杜四春, 蔡力軍. 計算機(jī)圖形學(xué)[M]. 北京：中國水利水電出版社, 2005. 130-159.