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

陳漢偉，陳光浩，陳威

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

0 引言

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

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

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

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

在虛擬場景中，虛擬角色需要沿參考軌跡移動(dòng)，但因?yàn)樾枰荛_障礙物，實(shí)際規(guī)劃路徑和參考軌跡會(huì)產(chǎn)生偏差。路徑在笛卡爾坐標(biāo)中，虛擬角色與參考軌跡的位置關(guān)系處理方法相對(duì)復(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)表示虛擬角色實(shí)際位置和參考軌跡映射點(diǎn)之間產(chǎn)生的垂直距離，s(t)代表虛擬角色沿著參考軌跡移動(dòng)的曲線距離。實(shí)際規(guī)劃路徑的點(diǎn)可以表示為：

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

(1)

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

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

d=[x-r(s)]Tnr

(3)

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

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

橫向坐標(biāo)對(duì)縱向坐標(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)化問題，故針對(duì)不同的初始狀態(tài)(d0，s0)、結(jié)束狀態(tài)(d1，s1)及時(shí)間差Δt，可分別定義橫向和縱向的損失函數(shù)[9-10]：

(15)

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

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，將兩個(gè)集合進(jìn)行笛卡爾卷積運(yùn)算Pd×Ps，通過加權(quán)橫向和縱向的損失函數(shù)，獲得新的損失函數(shù)Cpath=kdCd+ksCs，剔除會(huì)與障礙物碰撞的路徑，最終確定最優(yōu)規(guī)劃路徑。

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

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

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

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

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

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

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

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

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

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

算法流程如圖3所示。

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

3 算法效果及分析

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

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

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

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

而在圖5場景中，虛擬角色處于全程無障礙的相對(duì)特殊場景中執(zhí)行移動(dòng)任務(wù)。在圖5-a和圖5-b場景中，虛擬角色的實(shí)際移動(dòng)路徑依然較好地趨近參考路徑的中心線；在圖5-c中，虛擬角色在經(jīng)過第一個(gè)曲率較大的彎道時(shí)，已無法保持在參考路徑的中線，產(chǎn)生一定的軌跡偏離，但能夠迅速調(diào)整，回到參考路徑的中線上繼續(xù)移動(dòng)；在圖5-d中，因彎道曲率過大，虛擬角色已無法完成正常的路徑規(guī)劃，有待進(jìn)行改進(jìn)和優(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)建路徑的五次多項(xiàng)式備選路徑集合，通過障礙物位置信息等特定約束條件推算最優(yōu)的運(yùn)動(dòng)軌跡，進(jìn)而實(shí)現(xiàn)虛擬角色的障礙避讓、速度持續(xù)性以及合理并線等智能行為，算法性能較好，適用于虛擬角色移動(dòng)的多數(shù)場景，且模擬效果真實(shí)，在虛擬角色仿真場景中具備一定的應(yīng)用價(jià)值。