宋 宇， 王志明

(長(zhǎng)春工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院， 吉林 長(zhǎng)春 130012)

0 引 言

由于具有廣泛的應(yīng)用場(chǎng)景，如機(jī)械臂運(yùn)動(dòng)規(guī)劃、機(jī)器人運(yùn)動(dòng)規(guī)劃等，近年來，路徑規(guī)劃得到國內(nèi)外學(xué)者的關(guān)注，路徑規(guī)劃的相關(guān)算法被不斷提出。從蟻群算法[1]、A*算法、D*算法、RRT算法、PRM算法、人工勢(shì)場(chǎng)法[2]、優(yōu)化算法[3]到模糊邏輯算法、神經(jīng)網(wǎng)絡(luò)算法、強(qiáng)化學(xué)習(xí)算法[4]。其中人工勢(shì)場(chǎng)法在數(shù)學(xué)描述上簡(jiǎn)潔、美觀,且規(guī)劃出的路徑較安全、平滑，但存在目標(biāo)點(diǎn)不可達(dá)、障礙物附近抖動(dòng)的問題。針對(duì)人工勢(shì)場(chǎng)法的不足,國內(nèi)外許多學(xué)者提出了改進(jìn)方法,如文獻(xiàn)[5]提出了扇區(qū)劃分后增加虛擬障礙物的方法,文獻(xiàn)[6]提出了預(yù)規(guī)劃路徑后增加虛擬質(zhì)點(diǎn)的方法，文獻(xiàn)[7]采用高斯組合隸屬函數(shù)建立引力點(diǎn)函數(shù)，消除了極小值問題。近年來，基于強(qiáng)化學(xué)習(xí)算法[8-9]已經(jīng)被初步用于路徑規(guī)劃問題中。SARSA(λ)算法是一種基于值函數(shù)的強(qiáng)化學(xué)習(xí)算法,如果直接將 SARSA(λ)應(yīng)用于路徑規(guī)劃,會(huì)使初次探索隨機(jī)性和撞墻概率較大,學(xué)習(xí)時(shí)間較長(zhǎng)。

文中通過人工勢(shì)場(chǎng)法的合力引導(dǎo)機(jī)制減少了路徑搜索時(shí)間，首次探索時(shí)選擇勢(shì)場(chǎng)合力方向最大的概率最大，再次探索時(shí)，Q值最大方向所占的比重增大。仿真實(shí)驗(yàn)表明，改進(jìn)算法改善了人工勢(shì)場(chǎng)法易陷入局部極值的現(xiàn)象。

1 Khatib人工勢(shì)場(chǎng)法

Khatib人工勢(shì)場(chǎng)法是通過計(jì)算合力機(jī)器人在一個(gè)虛擬勢(shì)場(chǎng)環(huán)境中受到的合力來決定機(jī)器人下一步的方向，目標(biāo)點(diǎn)在環(huán)境中任一點(diǎn)x產(chǎn)生的吸引力勢(shì)場(chǎng)值為:

(1)

式中：xd----目標(biāo)點(diǎn)坐標(biāo);

kp----引力增益系數(shù)。

如電場(chǎng)力等于電勢(shì)的負(fù)梯度一樣，引力為吸引力勢(shì)場(chǎng)的負(fù)梯度，方向由機(jī)器人指向目標(biāo)點(diǎn)。吸引力的大小為:

Fatt(x)=-grad[Uxd(x)]=-kp(x-xd)(2)

單個(gè)障礙物在環(huán)境中任一點(diǎn)x產(chǎn)生的排斥力勢(shì)場(chǎng)值為:

(3)

式中：xobs----目標(biāo)點(diǎn)坐標(biāo);

ε----斥力增益系數(shù);

ρ(x,xobs)----機(jī)器人與障礙物之間的距離。

如電場(chǎng)力等于電勢(shì)的負(fù)梯度一樣，斥力為斥力勢(shì)場(chǎng)的負(fù)梯度，方向由障礙物指向機(jī)器人。機(jī)器人排斥力的大小為:

(4)

2 SARSA(λ)算法

SARSA(λ)算法是一種基于值函數(shù)的強(qiáng)化學(xué)習(xí)算法，在強(qiáng)化學(xué)習(xí)中，狀態(tài)行為值函數(shù)的定義為：

(5)

γ----折扣因子。

SARSA(λ)的Q值更新公式可以由式(5)得到，設(shè)狀態(tài)行為對(duì)(s,a)的當(dāng)前Q值估計(jì)值為Q(s,a)，機(jī)器人在狀態(tài)s做出動(dòng)作a后得到獎(jiǎng)勵(lì)r以及到達(dá)下一個(gè)狀態(tài)s_，若用r+Q(s_,a_)去估計(jì)Q(s,a)，分別給當(dāng)前估計(jì)值Q(s,a)與新的估計(jì)值r+Q(s_,a_)一定的概率置信度1-aa和aa，aa為一個(gè)0到1的數(shù)，則

Q(s,a)=(1-aa)*Q(s,a)+aa*(r+Q(s_,a_))(6)

展開得

Q(s,a)=Q(s,a)+aa*(r+Q(s_,a_)-

γ*Q(s,a))(7)

為了記錄獲得獎(jiǎng)勵(lì)之前的所有狀態(tài)動(dòng)作對(duì)，當(dāng)機(jī)器人獲得獎(jiǎng)勵(lì)或懲罰時(shí)，所有已經(jīng)記錄的機(jī)器人經(jīng)歷過的狀態(tài)動(dòng)作對(duì)都一定程度更新Q值，引入資格跡矩陣E(s,a)，得到SARSA(λ)的Q值更新公式為：

Q(s,a)=Q(s,a)+aa*(r+Q(s_,a_)-γ*Q(s,a))*E(s,a)

E(s,a)=γ*λ*E(s,a)(8)

機(jī)器人在一個(gè)回合內(nèi)每走一步，之前步經(jīng)歷的資格跡衰減γ*λ倍。

3 改進(jìn)算法

若地圖大小為n*n，則初始化一個(gè)n*n行，8列的值全為k的Q表矩陣，k為一個(gè)大于0的正數(shù)，機(jī)器人可移動(dòng)方向?yàn)樯?、下、左、右、上左、上右、下左、下?個(gè)方向，此矩陣每一行代表一個(gè)柵格的Q值信息。同時(shí)初始化一個(gè)n*n行，8列的值全為0的資格跡矩陣。

3.1 選擇動(dòng)作

機(jī)器人選擇下一個(gè)動(dòng)作時(shí)，分別計(jì)算周圍8個(gè)鄰居格子的a值與q值，式(9)為由合力與Q表共同確定的轉(zhuǎn)移概率。其中的qi值是查詢Q表得到的，ai值的確定方法見4.2。機(jī)器人最終轉(zhuǎn)移概率由式(10)確定，即50%的概率轉(zhuǎn)移到由式(9)得到的P最大的柵格處，40%的概率轉(zhuǎn)移到q值最大的動(dòng)作所對(duì)應(yīng)的柵格處，10%的概率向周圍8個(gè)柵格方向隨機(jī)移動(dòng)一步。

(9)

3.2a值

計(jì)算當(dāng)前點(diǎn)(即當(dāng)前位置)受到的合力大小與方向，將此合力在上、下、左、右、上左、上右、下左、下右8個(gè)方向上投影，得到8個(gè)分力，將這8個(gè)分力的大小(可正可負(fù))從小到大排序，ai為一個(gè)大小為1～8序號(hào)值，ai值越大，表示此方向合力越大，即機(jī)器人向此方向移動(dòng)的概率越大。

3.3 獎(jiǎng)勵(lì)函數(shù)

機(jī)器人第一次到達(dá)目標(biāo)點(diǎn)時(shí)獎(jiǎng)勵(lì)為R，記錄此次機(jī)器人經(jīng)過的總路徑長(zhǎng)度mindistance，以后每輪比較路徑長(zhǎng)度與此路徑長(zhǎng)度，若出現(xiàn)更小的路徑長(zhǎng)度，則更新最優(yōu)路徑長(zhǎng)度mindistance。從第2輪開始的獎(jiǎng)勵(lì)規(guī)則由式(11)確定，其中的distance為本次從起點(diǎn)到終點(diǎn)的路徑長(zhǎng)度，其中的正負(fù)號(hào)由判斷語句決定，若distance小于mindistance取正號(hào)，若distance大于mindistance取負(fù)號(hào)。dis為執(zhí)行a動(dòng)作前機(jī)器人到目標(biāo)點(diǎn)的距離，dis_為執(zhí)行a動(dòng)作后機(jī)器人到目標(biāo)點(diǎn)的距離。

(11)

3.4 Q值更新公式

如前所述，傳統(tǒng)SARSA(λ)的Q(s,a)值是由當(dāng)前的Q(s,a)值與r+Q(s_,a_)的加權(quán)平均得到的，其中Q(s_,a_)是由機(jī)器人做出動(dòng)作a后到達(dá)位置s_，再次根據(jù)ε-greedy策略選擇動(dòng)作a_，查詢Q表得到的。為了充分利用之前探索過的信息，此處將Q(s_,a_)改為

(12)

式中：Q(s_,i)----機(jī)器人在位置s_，選擇動(dòng)作i(i為1個(gè)1～8的整數(shù)，代表上、下、左、右、上左、上右、下左、下右)查詢Q表得到的值。

即將式(8)改為:

(13)

式中：n----格子序號(hào)。

分別計(jì)算s_周圍8個(gè)格子到目標(biāo)點(diǎn)的距離加機(jī)器人從s_到8個(gè)格子的移動(dòng)距離的和，將8個(gè)格子的對(duì)應(yīng)距離值從大到小排序，n為格子的距離值的序號(hào)，即距離越小，n值越大，n為1～8的整數(shù)。

4 仿 真

文中在PyCharm2017.1.2環(huán)境下進(jìn)行了仿真實(shí)驗(yàn)，學(xué)習(xí)率aa為0.01，折扣因子γ為0.9，資格跡衰減因子λ為0.9，其余參數(shù)的設(shè)置見表1。

表1 參數(shù)設(shè)置

4.1 人工勢(shì)場(chǎng)法目標(biāo)點(diǎn)不可達(dá)地圖環(huán)境

在合力為0的柵格附近人工勢(shì)場(chǎng)法出現(xiàn)了在障礙物附近抖動(dòng)的情形，如圖1所示。

SARSA(λ)算法路徑規(guī)劃結(jié)果和改進(jìn)算法路徑規(guī)劃結(jié)果分別如圖2和圖3所示。

圖1 人工勢(shì)場(chǎng)法路徑 圖2 SARSA(λ)路徑 圖3 改進(jìn)算法路徑

柵格地圖大小為20×20，起點(diǎn)為左下角方塊，終點(diǎn)為上方圓形，障礙物為黑色方塊。圖3中五角星為改進(jìn)算法100次迭代輸出的最優(yōu)路徑。傳統(tǒng)SARSA(λ)容易撞墻而無法在100回合內(nèi)找到目標(biāo)點(diǎn)(見圖2)，五角星為傳統(tǒng)SARSA(λ)算法100次迭代中機(jī)器人所經(jīng)過的所有路徑點(diǎn)。

4.2 人工勢(shì)場(chǎng)法目標(biāo)點(diǎn)可達(dá)地圖環(huán)境

在人工勢(shì)場(chǎng)法與改進(jìn)算法都能找到目標(biāo)點(diǎn)的情況下，這里比較了直接應(yīng)用SARSA(λ)算法與改進(jìn)算法的從起點(diǎn)首次到達(dá)目標(biāo)點(diǎn)用時(shí)，100次迭代內(nèi)，成功到達(dá)目標(biāo)點(diǎn)的路徑的平均路徑長(zhǎng)度，100次迭代內(nèi)，成功到達(dá)目標(biāo)點(diǎn)的路徑最短路徑長(zhǎng)度與從起點(diǎn)到達(dá)目標(biāo)點(diǎn)的平均用時(shí)，相關(guān)指標(biāo)對(duì)比見表2。

表2 算法結(jié)果對(duì)比

SARSA(λ)算法100次迭代輸出最優(yōu)路徑如圖4所示。

改進(jìn)算法100次迭代輸出最優(yōu)路徑如圖5所示。

圖4 SARSA(λ)算法路徑圖

圖5 改進(jìn)算法路徑圖

5 結(jié) 語

由于SARSA(λ)具有隨機(jī)性與記憶性，尋路過程中隨機(jī)掙脫極小值點(diǎn)的概率被增大。仿真實(shí)驗(yàn)表明，相比直接應(yīng)用SARSA(λ)于路徑規(guī)劃，勢(shì)場(chǎng)力的引入大幅減少了路徑規(guī)劃所用的時(shí)間，由于SARSA(λ)具有隨機(jī)性與記憶性，一方面克服了傳統(tǒng)人工勢(shì)場(chǎng)法的目標(biāo)點(diǎn)不可達(dá)的缺陷,另一方面增加了尋找到更優(yōu)路徑的概率。