基于改進強化學習算法的移動機器人路徑規劃研究

王 慧 秦廣義 夏 鵬 楊春梅 王 剛

(東北林業大學機電工程學院 黑龍江 哈爾濱 150040)

0 引 言

隨著科學技術的不斷進步，各式各樣的移動機器人逐漸進入到人們的日常生活中，在軍事、工業、探險、醫療等領域發揮了重大作用[1]。移動機器人的路徑規劃問題一直是機器人研究的核心內容，能夠直接影響到移動機器人的智能水平[2]。路徑規劃是指移動機器人在復雜的環境中，在滿足某些預先設定好的條件下，在初始點到達目標點之間找出一條無碰撞的路徑[3-5]。目前常用的算法主要有柵格法、A*算法、粒子群算法、蟻群算法、強化學習方法[6-7]。Q-learning算法是由Watkins在1989年提出的強化學習方法中的一種離軌策略下的時序差分控制算法。標準Q-learning算法應用在路徑規劃時，存在收斂速度慢、學習時間長等問題[8-9]。為此，國內外一些學者提出了一些解決方法。宋清昆等[10]提出一種基于經驗知識的Q-學習算法，該算法利用具有經驗知識信息的函數, 使智能體在進行無模型學習的同時學習系統模型, 避免對環境模型的重復學習, 從而加速智能體的學習速度，提高了算法的效率。Lillicrap等[11]使用人工神經網絡來擬合Q-learning中的Q函數，然后使用經驗回放方法來使得Q-learning保持收斂穩定性從而加快了Q-learning算法的收斂速度，進而提高了算法的效率。高樂等[12]在原有算法的基礎上增加了一層深度學習層，使得算法可以提前發現障礙物和目標位置，從而加快了標準Q-learning算法的收斂速度。董瑤等[13]使用具有競爭網絡結構的深度雙Q網絡的方法來改進深度Q網絡模型以提高深度Q網絡的收斂速度，但是深度網絡的搭建具有很強的經驗性，不同大小的柵格需要的網絡結構和超參數不同，在維數較小的柵格中依然需要較多的先驗數據的采集與回放，具有較長的計算時間，計算效率較低。徐曉蘇等[14]通過引入人工勢場來初始化環境信息來使得Q表在初始化時具有先驗知識來加快Q-learning算法的收斂速度，但其未對原有Q-learning算法進行改進且算法收斂速度較慢。

本文在標準Q-learning算法基礎上，借鑒增加學習層和先驗知識啟發搜索的思想，提出一種基于具有先驗知識的改進Q-learning移動機器人路徑規劃算法。該路徑規劃算法在原來標準Q-learning算法的基礎上增加了一層深度學習層、在算法初始化的過程中加入了關于環境的先驗知識作為啟發信息并且根據不同的狀態在構建的標量場中的位置獲得不同的獎賞值來使得獎賞值具有導向性。因此算法可以指引移動機器人快速向目標位置移動，解決了算法學習初始階段的無目的性，使得算法在學習過程中具有導向性，提高了算法的學習效率以及算法的收斂速度。

1 Q-learning算法原理

1.1 馬爾可夫決策過程

設環境建模為有限馬爾可夫決策過程，該馬爾可夫決策過程可由元組M=(S,A,T,R,γ)表示，其中：S為一組有限的狀態集合；A為全部狀態下的所有動作行為的集合；T(s,a,s′)=P{st=s′|st-1=s,at-1=a},s′,s∈S,a∈A，T表示在狀態s和動作a下，到達狀態s′的概率；R表示由狀態s在動作a作用下到達狀態s′的獎勵函數，如R(s,a)是在狀態s下執行動作a時所獲得的立即獎賞值；γ∈(0,1)為折扣因子，后面時刻的獎勵按照γ值進行衰減。

1.2 標準Q-learning原理

Q-learning算法是一種離軌策略下的時序差分學習方法[15]。關于Q-learning的一個關鍵假設是智能體和環境的交互看作為一個馬爾可夫決策過程。在Q-learning中每個狀態-工作對(s,a)的評價值為Q(s,a)。評價值的定義是如果執行當前相關的動作并且按照某一個策略執行下去，將得到回報的折扣總和。最優的評價值則可以定義為在當前狀態s下執行動作a，此后按照策略π執行下去獲得的折扣回報的總和，即：

s,s′∈Sa,a′∈A

(1)

Q-learning的學習過程如下：首先初始化Q(s,a)，然后初始化狀態s，選擇某一策略對動作進行選擇(通常為ε-greed策略)，執行選擇的動作a,根據獲得直接回報R(s,a),以及新狀態s′，來對Q(s,a)進行更新，更新公式為：

Q(s,a)←Q(s,a)+

(2)

式中：α∈(0,1)表示學習率；Q(s,a)表示在狀態s處執行動作a迭代時的估計值函數。然后令s←s′，繼續循環下去，直到到達算法停止的要求或達到最大迭代次數，算法停止運行。

2 改進Q-learning移動機器人路徑規劃

2.1 依據環境先驗知識初始化Q值

本文算法的基本思想是在將Q-learning算法增加深度學習層后，在Q-learning學習的初始階段引入對環境的先驗知識。令任意狀態柵格到目標狀態柵格的歐氏距離為D(si,sg)，任意狀態柵格到初始狀態柵格的歐氏距離為D(si,ss)，取D(si)=(1-η)·D(si,sg)+η·D(si,ss)，使用D(si)的線性歸一化數值來初始化各個狀態的Q值(η∈(0,0.2)，η為權重系數)，這就避免了Q-learning學習前期盲目地進行探索，使得算法在前期就有目的地選擇下一個路徑點，大幅提高算法的收斂速度。

標準Q-learning算法僅使得移動機器人對下一步進行搜索，使得搜索的范圍很有限，借鑒增加深度學習層搜索的思想，本文中Q值函數的更新公式為：

(3)

式中：ω∈(0.5,1)為深度學習因子；Q(s′,a′)為在s狀態執行動作a后到達的狀態s′后，狀態-動作對(s′,a′)所對應的Q值；Q(s″,a″)為在s′狀態執行動作a′到達的狀態s″后，狀態-動作對(s″,a″)所對應的Q值。

在學習的過程中，Q-learning的動作策略是沿著Q值上升的方向進行移動，因此應該在移動機器人的狀態空間內形成一個以目標點狀態為中心的標量場，場的值從側面向中心依次上升，在中心處達到最高值。為達到這個目的，做了以下工作。

取歐氏距離來對任意柵格之間的距離進行描述，假設垂直和水平方向上相鄰的柵格之間為距離為1。令起始狀態坐標為ss，目標狀態坐標為sg，任意狀態坐標為si，記任意點到目標點的距離為D(si,sg),任意點到起始點的距離為D(si,ss)。D(si,sg)、D(si,ss)可以表示為：

(4)

(5)

令D(si)=(1-η)·D(si,sg)+η·D(si,ss)，其中η∈(0,0.2)，獲得的D(si)為si點到目標點和起始點的加權后的距離值。使用歸一化函數對D(si)進行歸一化。

2.2 改進Q-learning算法的步驟

步驟1初始化學習率α，選擇合適的折扣因子γ，選取合適的ε-greed選擇策略的ε值，深度學習因數學習率衰減步數STEP，學習率衰減率decay-rate，設置最大循環次數epoch_max，循環次數epoch=0，初始化最優路徑記錄器Pathrecord_best=[]。

步驟2確定起始點的坐標位置ss和目標點坐標sg,初始化以目標點為中心的標量場，保存標量場中各個狀態對應場的數值Dnorm(si)，路徑記錄器Pathrecord=[ss]。

步驟3對Q值進行初始化，即令Q(s,a)=Dnorm(s′)。

步驟4將移動機器人置于起始狀態點。

步驟5移動機器人對動作進行選擇，選擇策略使用ε-greed方法，系統在(0,1)中隨機取值E，若E>ε,則從狀態的動作空間選取動作a：

a={ai,|ai,=argmaxQ(s,ai),ai∈A}

(6)

否則在狀態的動作空間中隨機選擇一個動作a。

步驟6選擇動作a后，對到達的狀態s′進行檢測，到達s′的直接獎勵值為:

(7)

步驟7若檢測狀態為障礙物，則停止進一步探索，該Q(s,a)更新為：

Q(s,a)←Q(s,a)+α[R(s,a)-Q(s,a)]

(8)

狀態返回s，返回步驟5。

若檢測狀態為目標點，則停止進一步探索，該Q(s,a)更新為：

Q(s,a)←Q(s,a)+α[R(s,a)-Q(s,a)]

(9)

若檢測狀態為其他，則進行下一步的探索，選擇動作a′為：

a={ai,|ai,=argmaxQ(s,ai),ai∈A}

(10)

沿著動作a′，對狀態s″進行檢測，若s″為障礙物或目標點，Q(s,a)更新為：

(1-ω)R(s′,a′))-Q(s,a)]

(11)

若s″為其他，則Q(s,a)更新為：

步驟8進入狀態s′，將s′坐標記入路徑記錄器Pathrecord。

步驟9判斷狀態s′是否為目標點狀態，若目標點狀態為True，結束該次嘗試學習；若目標點狀態為False則s=s′，返回步驟5。

步驟10判斷是否epoch==1，為True則Pathrecord_best= Pathrecord。

步驟11判斷Pathrecord的長度是否小于Pathrecord_best,為True則Pathrecord_best=Pathrecord。運行柵格步數steps為Pathrecord長度。

步驟12判斷判讀循環次數是否達到最大循環次數，為True則算法停止，為Flase則循環次數epoch加1并返回步驟2進行下一次嘗試學習。

3 實驗仿真

3.1 標量場仿真實驗驗證

通過仿真實驗來驗證本文算法的有效性及其先進性。仿真實驗的環境為MATLAB(2016b)以及Python3.5.3。由于柵格法建模的廣泛性和實用性[16]，本文實驗環境使用柵格法進行建模。本文在柵格地圖上對提出的改進方法和標準Q-learning算法及增加深度學習層的Q-learning算法進行效果對比。

建立20×20的柵格，設起始點選擇為點(1,1)，目標點選擇為點(10,10)，觀察形成的標量場的形狀，如圖1所示。

圖1 20×20柵格標量場

可以看出，標量場場值的最大值在目標點坐標(10,10)處取到并且滿足各點場值的大小與D(si)成反比關系，即D(si)值越大，其場值越小。

3.2 算法仿真實驗驗證及分析

仿真實驗采用22×22的柵格來組成，以左下角點(1,1)為原點建立坐標系，取水平方向為x軸，豎直方向為y軸。仿真實驗中學習率使用線性衰減的方法，即每循環STEP次，α=α·decay-rate，使得Q值趨于穩定。

在圖2中，黑色的圓形表示移動機器人所處的起始點，黑色的星形表示移動機器人的目標點，白色部分為移動機器人移動區域，黑色的方形部分為障礙物，移動機器人的動作A={向上移動，向下移動，向左移動，向右移動}。

圖2 柵格環境一

首先以圖2障礙物擺放較為簡單的柵格環境進行仿真實驗分析。仿真實驗的各個參數如表1所示。

表1 仿真實驗參數

在圖2柵格環境中對標準Q-learning算法，增加深度層的Q-learning算法、本文算法、引入引力場的算法、深度雙Q網絡算法進行仿真實驗。實驗結果如圖3-圖8所示。

圖3 環境一中前四種算法收斂過程

圖4 環境一中深度雙Q網絡算法收斂過程

圖5 標準Q-learning算法

圖6 增加學習層Q-learning算法

圖7 本文算法

圖8 引入引力場算法

由圖3可以看出，在障礙物擺放較為簡單的環境中，標準Q-learning算法、增加學習層的Q-learning算法、引入引力場的算法在算法初始學習階段迭代次數較多，浪費較多的規劃時間。本文算法由于在學習的初始階段具有較強的目的性，大幅減少了算法前期的迭代次數；因在探索過程中增加一層學習層并且獎賞值具有導向性，于是使用較少的嘗試次數便收斂。

由圖4可以看出深度雙Q網絡在訓練時損失值隨迭代次數增加的變化情況，當迭代次數達到6 326時，損失值處于平穩狀態，算法達到收斂。由圖5可得標準Q-learning算法在85次嘗試后達到收斂，由圖6可得增加學習層的Q-learning算法在60次嘗試后達到收斂，由圖7可得本文算法在42次嘗試后便進入收斂狀態，由圖8可得引入引力場算法在82次嘗試后便進入收斂狀態。

由表2可以得到在環境一的柵格中各種算法達到收斂時的總迭代次數。由此可以得到本文算法在環境一柵格中具有較快達到收斂的能力。

表2 環境一五種算法達到收斂的迭代次數

五種算法在圖3柵格環境中規劃出的路徑完全相同，路徑如圖9所示，其中，黑色的圓形和線條組成了由點(2,2)到達點(21,21)規劃出的路徑。

圖9 環境一路徑規劃圖

接下來在障礙物擺放較為復雜的環境中對三種算法進行仿真實驗，環境柵格如圖10所示。

圖10 柵格環境二

在圖10障礙物擺放較為復雜的環境中，前四種算法收斂過程如圖11所示，深度雙Q網絡算法收斂過程如圖12所示。

圖11 環境二中四種算法收斂過程

圖12 環境二中深度雙Q網絡算法收斂過程

從圖11中可以看出，在障礙物擺放較為復雜的環境中，本文算法相較于其他算法在較少的嘗試次數下便可以達到收斂。由表3可以看出在局部較為復雜的環境下，本文算法相較于其他算法具有迭代次數少、計算效率高的優點。在環境二中，移動機器人的軌跡如圖13所示。

表3 環境二五種算法達到收斂的迭代次數

圖13 環境二路徑規劃圖

為了進一步驗證算法的環境適應性，在障礙物更為復雜的40×40柵格中進行仿真，結果如圖14所示。

圖14 40×40復雜柵格的路徑軌跡

4 結 語

本文提出一種具有先驗知識的增加深度學習層的改進Q-learning算法，該算法在原有算法的基礎上通過構建標量場來對Q進行初始化，根據不同狀態所在標量場的位置返回不同的獎賞值并且在原有算法上增加了一層學習層來使得算法更快地尋找到目標位置。

由仿真實驗可以看出，在低維度的環境下本文算法相較于標準Q-learning算法、引入引力場的算法、深度雙Q網絡算法具有更低的迭代次數，從而節省了計算時間，提高了計算效率。