基于Frenet坐標的虛擬角色路徑規劃算法的研究

陳漢偉，陳光浩，陳威

(浙江安防職業技術學院，人工智能學院，溫州 325000)

0 引言

在虛擬現實仿真場景中，虛擬角色路徑規劃始終是需要解決的關鍵問題[1]。虛擬角色往往需要沿一條合理的路徑從起始位置移動到結束位置，移動過程中要避開障礙物、保證自身移動速度，并且在偏離路線后，需要及時調整移動狀態，回到既定路線?，F有的路徑規劃算法，雖然可以進行路徑規劃，但是存在路徑軌跡不夠真實、算法復雜度高或是無法應對復雜場景等問題。

針對虛擬現實仿真場景中的虛擬角色路徑規劃問題，提出了一種基于Frenet坐標的虛擬角色路徑規劃算法，算法根據已知的障礙物信息，較快地為虛擬角色規劃路徑，路徑平滑有效，能夠合理避開既有的障礙物。算法將虛擬角色和障礙物的位置信息轉換到Frenet坐標當中[2]，推算最優的運動軌跡，進而實現虛擬角色的障礙避讓、速度持續性以及合理并線等智能行為，算法性能較好，且模擬動畫效果真實，具備一定的應用價值。

1 基于Frenet坐標的虛擬角色路徑規劃算法

1.1 Frenet坐標與笛卡爾坐標的映射關系

在虛擬場景中，虛擬角色需要沿參考軌跡移動，但因為需要避開障礙物，實際規劃路徑和參考軌跡會產生偏差。路徑在笛卡爾坐標中，虛擬角色與參考軌跡的位置關系處理方法相對復雜。然而，在Frenet坐標系下，以參考軌跡為依據建立坐標系統，虛擬角色與參考軌跡的位置關系可簡易的表述為橫向偏移量d(t)和縱向偏移量s(t)，如圖1所示。

圖1 Frenet坐標與笛卡爾坐標的映射關系

d(t)表示虛擬角色實際位置和參考軌跡映射點之間產生的垂直距離，s(t)代表虛擬角色沿著參考軌跡移動的曲線距離。實際規劃路徑的點可以表示為：

x(s(t)，d(t))=r(s(t))+d(t)nr(s(t))

(1)

其中向量nr，tr分別表示，虛擬角色在參考路徑上映射點的法向量和切向量，r(s(t) )表示虛擬角色當前運動狀態下的笛卡兒坐標，nx，tx表示路徑規劃點的法向量和切向量[3]。

虛擬角色的路徑規劃，就是要將其當前狀態的位置、方向、曲率、速度和加速度信息先映射到Frenet坐標系下，通過求解Jerk最優化問題，得到備選路徑集合，然后將規劃的路徑點轉換回笛卡爾坐標系下，并推算出最優路徑，使虛擬角色能夠快速合理的移動。即存在如下轉換關系：

在笛卡爾坐標系下：x表示坐標向量；θx表示虛擬角色的朝向；κx表示曲率；vx表示速度，ax表示加速度。

1.2 笛卡爾坐標映射到Frenet坐標

當[x，θx，κx，vx，ax]已知，s是參考路徑點的一個自變量[4-5]：

d=[x-r(s)]Tnr

(3)

橫向坐標對縱向坐標的導數d′表示為：

d′=(1-κ，d)tanΔθ(6)

橫向坐標對縱向坐標的二階導數d″表示為：

(7)

(8)

1.3 Frenet坐標映射到笛卡爾坐標

x=r(s)+nrd

(10)

根據公式(4)，可推導速度vx為：

根據公式(6)，可知朝向θx為：

加速度ax是vx的導數，表示為：

(13)

曲率κx表示為：

(14)

1.4 Frenet坐標系中的路徑規劃

虛擬角色的路徑規劃問題可視為分別在水平方向s和垂直方向d上求解Jerk最優化問題，故針對不同的初始狀態(d0，s0)、結束狀態(d1，s1)及時間差Δt，可分別定義橫向和縱向的損失函數[9-10]：

(15)

而其最優解可使用五次多項式表示：

d(t)=αd0+αd1t+αd2t2+αd3t3+αd4t4+αd5t5(17)

s(t)=αs0+αs1t+αs2t2+αst3+αs4t4+αs5t5(18)

通過調整結束狀態的值，獲得水平方向備選路徑集合Pd和垂直方向備選路徑集合Ps，將兩個集合進行笛卡爾卷積運算Pd×Ps，通過加權橫向和縱向的損失函數，獲得新的損失函數Cpath=kdCd+ksCs，剔除會與障礙物碰撞的路徑，最終確定最優規劃路徑。

2 算法的實現及應用

本文基于Blender平臺構建虛擬角色的移動場景，場景中包含虛擬角色，參考的行動路線，及若干障礙物，如圖2所示。

圖2 構建虛擬場景

基于Frenet坐標的虛擬角色路徑規劃算法具體實現方式如下：

(1)首先，算法獲取笛卡爾坐標下的虛擬角色運動狀態[x，θx，κx，vx，ax]，作為算法輸入參數；

(2)算法先將虛擬角色的運動狀態通過公式(3)-(9)映射到Frenet坐標系中；

(3)在Frenet坐標系中求解Jerk最優化問題，得到備選路徑集合；

(4)根據參考路徑的信息，將Frenet路徑集合通過公式(10)-(18)映射到笛卡爾坐標系中；

(5)執行障礙物檢測，并校驗相關約束條件，剔除集合中不滿足條件的路徑；

(6)最終輸出最優路徑，虛擬角色根據最優路徑調整自身運動狀態，沿最優路徑執行移動任務。

算法流程如圖3所示。

圖3 算法實現流程

3 算法效果及分析

為驗證算法性能，本文進行了多組路徑跟蹤試驗。在試驗中，虛擬角色需要沿預先設定的參考路徑執行移動任務。在圖4場景中，虛擬角色需沿一條多彎曲線進行移動，寬線為參考路徑，虛線為實際移動路徑，點狀連續線表示規劃路徑。圖4-a顯示虛擬角色在無障礙的路徑中，實際移動路徑和參考路徑近似，運行穩定；當參考路徑中出現障礙物，路徑規劃算法會充分考慮障礙物的位置信息，并在路徑規劃時，逐步避開障礙物，如圖4-b所示；當避開所有障礙物后，虛擬角色又逐步回到參考路徑的中線上，直至完成移動任務。

4-a 無障礙狀態移動

4-b 有障礙狀態移動

4-c 恢復無障礙狀態移動

而在圖5場景中，虛擬角色處于全程無障礙的相對特殊場景中執行移動任務。在圖5-a和圖5-b場景中，虛擬角色的實際移動路徑依然較好地趨近參考路徑的中心線；在圖5-c中，虛擬角色在經過第一個曲率較大的彎道時，已無法保持在參考路徑的中線，產生一定的軌跡偏離，但能夠迅速調整，回到參考路徑的中線上繼續移動；在圖5-d中，因彎道曲率過大，虛擬角色已無法完成正常的路徑規劃，有待進行改進和優化。

5-a 全程無障礙場景一

5-b 全程無障礙場景二

5-c 全程無障礙場景三

5-d 全程無障礙場景四

4 結語

本文提出了一種基于Frenet坐標的虛擬角色路徑規劃算法，根據已知的障礙物信息，較快地為虛擬角色規劃路徑，路徑平滑有效，能夠避開障礙物并保證路徑的合理性。算法將虛擬角色和障礙物的位置信息轉換到Frenet坐標當中，構建路徑的五次多項式備選路徑集合，通過障礙物位置信息等特定約束條件推算最優的運動軌跡，進而實現虛擬角色的障礙避讓、速度持續性以及合理并線等智能行為，算法性能較好，適用于虛擬角色移動的多數場景，且模擬效果真實，在虛擬角色仿真場景中具備一定的應用價值。