基于Frenet坐標(biāo)的虛擬角色路徑規(guī)劃算法的研究

陳漢偉，陳光浩，陳威

(浙江安防職業(yè)技術(shù)學(xué)院，人工智能學(xué)院，溫州 325000)

0 引言

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

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

1 基于Frenet坐標(biāo)的虛擬角色路徑規(guī)劃算法

1.1 Frenet坐標(biāo)與笛卡爾坐標(biāo)的映射關(guān)系

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

圖1 Frenet坐標(biāo)與笛卡爾坐標(biāo)的映射關(guān)系

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

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

(1)

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

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

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

1.2 笛卡爾坐標(biāo)映射到Frenet坐標(biāo)

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

d=[x-r(s)]Tnr

(3)

橫向坐標(biāo)對縱向坐標(biāo)的導(dǎo)數(shù)d′表示為：

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

橫向坐標(biāo)對縱向坐標(biāo)的二階導(dǎo)數(shù)d″表示為：

(7)

(8)

1.3 Frenet坐標(biāo)映射到笛卡爾坐標(biāo)

x=r(s)+nrd

(10)

根據(jù)公式(4)，可推導(dǎo)速度vx為：

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

加速度ax是vx的導(dǎo)數(shù)，表示為：

(13)

曲率κx表示為：

(14)

1.4 Frenet坐標(biāo)系中的路徑規(guī)劃

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

(15)

而其最優(yōu)解可使用五次多項式表示：

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

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

通過調(diào)整結(jié)束狀態(tài)的值，獲得水平方向備選路徑集合Pd和垂直方向備選路徑集合Ps，將兩個集合進行笛卡爾卷積運算Pd×Ps，通過加權(quán)橫向和縱向的損失函數(shù)，獲得新的損失函數(shù)Cpath=kdCd+ksCs，剔除會與障礙物碰撞的路徑，最終確定最優(yōu)規(guī)劃路徑。

2 算法的實現(xiàn)及應(yīng)用

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

圖2 構(gòu)建虛擬場景

基于Frenet坐標(biāo)的虛擬角色路徑規(guī)劃算法具體實現(xiàn)方式如下：

(1)首先，算法獲取笛卡爾坐標(biāo)下的虛擬角色運動狀態(tài)[x，θx，κx，vx，ax]，作為算法輸入?yún)?shù)；

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

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

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

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

(6)最終輸出最優(yōu)路徑，虛擬角色根據(jù)最優(yōu)路徑調(diào)整自身運動狀態(tài)，沿最優(yōu)路徑執(zhí)行移動任務(wù)。

算法流程如圖3所示。

圖3 算法實現(xiàn)流程

3 算法效果及分析

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

4-a 無障礙狀態(tài)移動

4-b 有障礙狀態(tài)移動

4-c 恢復(fù)無障礙狀態(tài)移動

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

5-a 全程無障礙場景一

5-b 全程無障礙場景二

5-c 全程無障礙場景三

5-d 全程無障礙場景四

4 結(jié)語

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