基于改進SARSA(λ)移動機器人路徑規劃

宋 宇， 王志明

(長春工業大學 計算機科學與工程學院， 吉林 長春 130012)

0 引 言

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

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

1 Khatib人工勢場法

Khatib人工勢場法是通過計算合力機器人在一個虛擬勢場環境中受到的合力來決定機器人下一步的方向，目標點在環境中任一點x產生的吸引力勢場值為:

(1)

式中：xd----目標點坐標;

kp----引力增益系數。

如電場力等于電勢的負梯度一樣，引力為吸引力勢場的負梯度，方向由機器人指向目標點。吸引力的大小為:

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

單個障礙物在環境中任一點x產生的排斥力勢場值為:

(3)

式中：xobs----目標點坐標;

ε----斥力增益系數;

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

如電場力等于電勢的負梯度一樣，斥力為斥力勢場的負梯度，方向由障礙物指向機器人。機器人排斥力的大小為:

(4)

2 SARSA(λ)算法

SARSA(λ)算法是一種基于值函數的強化學習算法，在強化學習中，狀態行為值函數的定義為：

(5)

γ----折扣因子。

SARSA(λ)的Q值更新公式可以由式(5)得到，設狀態行為對(s,a)的當前Q值估計值為Q(s,a)，機器人在狀態s做出動作a后得到獎勵r以及到達下一個狀態s_，若用r+Q(s_,a_)去估計Q(s,a)，分別給當前估計值Q(s,a)與新的估計值r+Q(s_,a_)一定的概率置信度1-aa和aa，aa為一個0到1的數，則

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)

為了記錄獲得獎勵之前的所有狀態動作對，當機器人獲得獎勵或懲罰時，所有已經記錄的機器人經歷過的狀態動作對都一定程度更新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)

機器人在一個回合內每走一步，之前步經歷的資格跡衰減γ*λ倍。

3 改進算法

若地圖大小為n*n，則初始化一個n*n行，8列的值全為k的Q表矩陣，k為一個大于0的正數，機器人可移動方向為上、下、左、右、上左、上右、下左、下右8個方向，此矩陣每一行代表一個柵格的Q值信息。同時初始化一個n*n行，8列的值全為0的資格跡矩陣。

3.1 選擇動作

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

(9)

3.2a值

計算當前點(即當前位置)受到的合力大小與方向，將此合力在上、下、左、右、上左、上右、下左、下右8個方向上投影，得到8個分力，將這8個分力的大小(可正可負)從小到大排序，ai為一個大小為1～8序號值，ai值越大，表示此方向合力越大，即機器人向此方向移動的概率越大。

3.3 獎勵函數

機器人第一次到達目標點時獎勵為R，記錄此次機器人經過的總路徑長度mindistance，以后每輪比較路徑長度與此路徑長度，若出現更小的路徑長度，則更新最優路徑長度mindistance。從第2輪開始的獎勵規則由式(11)確定，其中的distance為本次從起點到終點的路徑長度，其中的正負號由判斷語句決定，若distance小于mindistance取正號，若distance大于mindistance取負號。dis為執行a動作前機器人到目標點的距離，dis_為執行a動作后機器人到目標點的距離。

(11)

3.4 Q值更新公式

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

(12)

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

即將式(8)改為:

(13)

式中：n----格子序號。

分別計算s_周圍8個格子到目標點的距離加機器人從s_到8個格子的移動距離的和，將8個格子的對應距離值從大到小排序，n為格子的距離值的序號，即距離越小，n值越大，n為1～8的整數。

4 仿 真

文中在PyCharm2017.1.2環境下進行了仿真實驗，學習率aa為0.01，折扣因子γ為0.9，資格跡衰減因子λ為0.9，其余參數的設置見表1。

表1 參數設置

4.1 人工勢場法目標點不可達地圖環境

在合力為0的柵格附近人工勢場法出現了在障礙物附近抖動的情形，如圖1所示。

SARSA(λ)算法路徑規劃結果和改進算法路徑規劃結果分別如圖2和圖3所示。

圖1 人工勢場法路徑 圖2 SARSA(λ)路徑 圖3 改進算法路徑

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

4.2 人工勢場法目標點可達地圖環境

在人工勢場法與改進算法都能找到目標點的情況下，這里比較了直接應用SARSA(λ)算法與改進算法的從起點首次到達目標點用時，100次迭代內，成功到達目標點的路徑的平均路徑長度，100次迭代內，成功到達目標點的路徑最短路徑長度與從起點到達目標點的平均用時，相關指標對比見表2。

表2 算法結果對比

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

改進算法100次迭代輸出最優路徑如圖5所示。

圖4 SARSA(λ)算法路徑圖

圖5 改進算法路徑圖

5 結 語

由于SARSA(λ)具有隨機性與記憶性，尋路過程中隨機掙脫極小值點的概率被增大。仿真實驗表明，相比直接應用SARSA(λ)于路徑規劃，勢場力的引入大幅減少了路徑規劃所用的時間，由于SARSA(λ)具有隨機性與記憶性，一方面克服了傳統人工勢場法的目標點不可達的缺陷,另一方面增加了尋找到更優路徑的概率。