基于深度Q學習的移動機器人路徑規劃

劉志榮， 姜樹海， 袁雯雯， 史晨輝

(1.南京林業大學 機械電子工程學院，江蘇 南京 210037；2.南京林業大學 智能控制與機器人技術研究所，江蘇 南京 210037)

路徑規劃是移動機器人導航的重要組成部分，其目標是在復雜環境下能夠尋找一條從起點到終點的無碰撞路徑。路徑規劃的核心是算法設計，根據訓練方法的不同，算法可分為監督學習、無監督學習和強化學習。監督學習和無監督學習以大量的樣本數據為基礎，這使得機器人在先驗知識匱乏的情況下很難通過監督學習和無監督學習進行良好的路徑規劃。強化學習是一種不需先驗知識、與環境直接進行試錯迭代獲取反饋信息來優化策略的人工智能算法，因而廣泛應用于復雜環境下的移動機器人路徑規劃中[1-2]。根據求解方法不同，強化學習算法分為直接策略搜索法和值函數法。直接策略搜索法將策略參數化表示，通過優化指標進行梯度上升，最后得到最優或者局部最優策略，可解決連續動作空間的問題[3]，主要應用于機器人的控制方面[4]，但在離散動作空間問題上并不能很好地評估單個策略，易于收斂到局部最小值。值函數法根據狀態轉移概率是否已知又分為基于模型的強化學習算法和與模型無關的強化學習算法兩類。基于模型的強化學習算法進行路徑規劃時需要知道環境特征，依據環境特征構建環境模型，因此只適用于簡單的結構化環境中的路徑規劃。與模型無關的強化學習算法，無需構建環境模型就可應用于復雜環境下的機器人路徑規劃中。Q-learning是典型的與模型無關的強化學習算法，無需知道模型就可以保證收斂，是目前應用于機器人路徑規劃中最有效的強化學習算法，在狀態空間較小的情況下能夠獲得很好的路徑規劃[5]，但Q-learning通過構建Q值表選擇最優策略，在維數很大時會導致維數災難[6]，因此很難推廣到大狀態空間中。

深度Q學習(Deep Q-Learning Network，DQN)算法是在深度學習發展的基礎上而興起的新的算法，它統一了深度學習的感知能力和強化學習的決策能力，是一種更接近人類思維方式的人工智能方法。近幾年來，在游戲等方面利用DQN探索原始圖像進行實時決策已經超越人類的表現[7]。同時，深度強化學習在控制系統決策方面有良好的表現，廣泛應用于機器人的各種任務，如機器人的運動、抓取、操作[8]、控制[9]、自動駕駛[10]等方面。Pfeiffer等人[11]利用深度學習模型將激光傳感器測距結果和目標位置映射為移動機器人的控制命令。Lei Tai等人[12]在未創建地圖的基礎上利用DQN實現了移動機器人的導航，之后他們[13]又構建深度卷積神經網絡框架，以RGB-D傳感器圖片為輸入信息，輸出為機器人的下一步動作，該思想將強化學習算法上升到了新的高度。感知能力與決策能力是衡量智能的兩大指標，強化學習的弱感知能力致使機器人難以直接通過學習高維狀態輸入去控制輸出決策，而深度學習可用網絡結構來映射Q值表，從而解決Q-learning的維數災難問題。本文在分析Q-learning進行路徑規劃的優點和不足的基礎上，將深度學習框架融于Q-learning中，構建記憶回放矩陣和兩層網絡結構，提高DQN收斂性，使其能夠在復雜狀態環境下進行良好的路徑規劃。

1 Q-learning算法

Q-learning是一種典型的與模型無關的強化學習算法，由Watkins[6]在1989年提出。Q-learning算法首先建立一張Q值表，然后通過機器人與環境交互，得到獎賞函數值，通過不斷迭代修改Q值表，使選擇正獎賞的動作的概率不斷增加，隨著不斷與環境交互，更改動作策略集，使機器人的動作最終趨于最優動作集。Q-learning采用狀態-動作對Q(s,a)迭代方式來獲得最優策略。算法在每一次迭代時需要考察每一個狀態-動作對Q(s,a)的值。Q-learning算法的基本形式為

Q(st,at)=Q(st,at)+α[rt+γmaxaQ(st+1,a)-Q(st,at)]

(1)

式中，st為t時刻移動機器人的狀態，在狀態st下執行動作at，移動機器人狀態變為st+1，同時得到獎勵值rt;rt是對狀態st+1的評估，表示機器人由當前狀態執行動作到下一個狀態所獲得的獎勵值；動作a∈A，A為動作空間；狀態st,st+1∈S,S為狀態空間；α為學習率，α越大Q值收斂越快，但越容易產生振蕩；maxaQ(st+1,a)表示從動作集A中選擇一個動作A使得Q(st+1,a)的取值最大；γ為折扣因子，表示未來獎勵對當前動作的影響程度[14]。

將式(1)變形成

Q(st,at)=(1-α)Q(st,at)+α[rt+γmaxaQ(st+1,a)]

(2)

由式(2)可知，狀態st對應的Q值穩定的必要條件為狀態st+1對應的maxaQ(st+1,a)恒定，否則上一個狀態的Q值會隨下一個狀態的Q值的改變而變化，因為整體是一個回溯過程，前面所有的動作對應的狀態都不能達到穩定值。

假設st+1狀態穩定，即Qt+1恒定，為求Q(st,at)的穩定狀態，借助式(2)迭代。

一次迭代：

Q(st,at)=(1-α)Qt+α[rt+γQt+1](Q(st,at)簡寫成Qt)

二次迭代：

Q(st,at)=(1-α)Qt+α[rt+γQt+1]

=(1-α)[(1-α)Qt+α[rt+γQt+1]]+α[rt+γQt+1]

=(1-α)2Qt+[1-(1-α)2][rt+γQt+1]

(3)

三次迭代：

Q(st,at)=(1-α)Qt+α[rt+γQt+1]

=(1-α)[(1-α)2Qt+[1-(1-α)2][rt+γQt+1]]+α[rt+γQt+1]

=(1-α)3Qt+[1-(1-α)3][rt+γQt+1]

(4)

以此類推，N次迭代：

Q(st,at)=(1-α)Qt+α[rt+γQt+1]

=(1-α)nQt+(1-α)nQt+[1-(1-α)n][rt+γQt+1]

(5)

因為0<α<1，所以0<(1-α)<1，當n→∞，(1-α)n→0。

Q(st,at)→rt+γQt+1，此時Q(st,at)收斂。

Q-learning借助式(2)更新，最終整個Q值表會達到一個極限ΔQ=rt+γmaxaQ(st+1,a)-Q(st,at)，當Q值不斷迭代更新，n→∞時，Q(st,at)將以概率1收斂于最優值，即

Q(st,at)=rt+γmaxaQ(st+1,a)

(6)

由式(6)可知，Q-learning算法前一個狀態的收斂依賴于后一個狀態，與初值無關，并且無需知道模型就可以保證收斂，是目前應用于機器人路徑規劃中最有效的強化學習算法。但是Q-learning在復雜的障礙物密集的環境下需要構建龐大的Q值表，然后根據回報值循環更新Q值表的對應值，該方法極其耗時，因此Q-learning很難應用到大狀態空間下的移動機器人路徑規劃。

2 DQN算法實現

2.1 DQN模型結構

DQN是Q-learning的變體算法，它以卷積神經網絡為載體，用參數為w的f網絡近似代替值函數，公式為

f(s,a,w)≈Q*(s,a)

(7)

f(s,a,w)可以是任何類型的函數，通過函數近似替代，無論狀態空間有多大，都可用神經網絡的輸出表示Q值，這就是用神經網絡近似替代Q值的基本思路，具體如圖1所示。s為輸入狀態，如在迷宮環境中，s代表一個小網格的特征，可以用網格對頂角坐標表示，則s=(x1,y1,x2,y2)表示機器人的一個狀態，輸出F(s,ai,w)(i=1,2,3,4)是一個值，表示當前狀態s下動作ai的Q值。因此只要輸入狀態s，就可以得到所有動作的Q值。通過網絡從根本上代替了Q-learning的Q值表，減少了維度災難的發生。

2.2 DQN特點

對于離散動作狀態空間的決策問題，DQN將狀態作為輸入，輸出為每個動作的Q值估計，以此近似值函數。但是神經網絡的加入破壞了Q-learning的無條件收斂性[15]。為了解決DQN的收斂性，可以從下面兩個方面進行改進。

2.2.1 記憶回放

DQN在與環境互相迭代過程中，前一個狀態與下一個狀態具有高度相關性，導致神經網絡過擬合而無法收斂。在與環境交互過程中，機器人在狀態s時執行動作a，得到回報值r并到達下一個狀態s′，反復執行這個過程，直到到達目標點。記憶回放的思想是在每次學習過程中，隨機抽取記憶庫中的一批樣本，并對其梯度下降進行學習。通過記憶矩陣中的經驗單元(s,a,r,s′)，可以將新的經驗單元和老的經驗單元隨機按批次混合進行更新，從而打斷相鄰數據樣本之間的相關性。并且很多經驗單元會不止一次地被用于更新，從而提高樣本的利用率。

2.2.2 建立雙層網絡結構

DQN與傳統的利用神經網絡逼近值函數方法相比，建立了一個與當前Q網絡結構相同、參數不同的Q-target神經網絡，即在計算目標Q值使用專門的Q-target網絡來計算，而不是直接使用預更新的當前Q網絡，以此來減少目標值與當前值的相關性。損失函數公式為

I=(r+γmaxa′Q(s′,a′；w-)-Q(s,a;w))2

(8)

式中,Q(s,a;w)為當前網絡的輸出，用來評估當前狀態動作對的值函數。Q(s′,a′;w-)為Q-target的輸出，用來求得目標值函數的Q值。

Q-target網絡參數w-由參數w延遲更新獲得，即參數w實時更新，經過若干輪迭代后，將當前Q網絡的參數賦值給Q-target網絡。對參數w進行求導，可得值函數的更新，如式(8)所示。

wt+1=wt+α[r+γmaxa′Q(s′,a′;w-)-Q(s,a;w)]Q(s,a;w)

(9)

2.3 DQN算法流程

DQN算法流程如下。

① 初始化記憶矩陣D，初始化Q-target網絡參數w-和當前網絡參數w。

② 將移動機器人的環境信息和攝像頭采集的圖像數據傳遞給機器人的多融合傳感器，獲取環境的特征信息(s,a,r,s′)并將其保存于記憶矩陣D中。

③ 從記憶矩陣B中取出一批樣本。

④ 用Q-target網絡計算：y=r+γmaxa′Q(s′,a′;w-)。

⑤ 用I=(r+γmaxa′Q(s′,a′;w-)-Q(s,a;w))2來提升參數。

⑥ 每隔N步將參數w復制給參數w-。

3 仿真結果及結果分析

3.1 動作空間的表示

仿真過程中將移動機器人近似為質點，用紅色圓圈表示。以移動機器人為中心，定義機器人的動作空間包含前進、后退、左移、右移4個基本動作。程序中用0,1,2,3表示，動作空間矩陣為[0,1,2,3]。采用ε-greedy策略，一方面以1-ε的概率選擇Q值最大的動作a，來盡可能利用環境信息，該過程為利用過程。另一方面以小概率ε隨機選擇動作進行環境探索，以此保證所有的狀態空間都有可能被搜索過。所設置的探索分布為

(10)

3.2 獎賞函數的設計

獎賞函數在強化學習過程中具有導向作用，對強化學習所采取動作的好壞做出評價，用標量r表示。強化學習的目的就是使機器人最終獲得的總的獎賞值之和最大。所設置的獎賞函數為

(11)

3.3 仿真結果與分析

3.3.1 簡單的仿真環境

本實驗主要分析傳統強化學習的路徑規劃過程。該仿真環境較為簡單。采用Python建立二維網格地圖表示環境信息，網格地圖將機器人所處環境分解為小柵格。網格模型尺寸為400×400，最小移動單元為20。每個柵格對應機器人的一個狀態。狀態空間為20×20的網格大小的對頂角坐標(x1,y1,x2,y2)。環境GUI如圖2所示。

圖2中圓圈代表初始點，圓心坐標為(10,10)；淺灰色方塊代表目標點，中心坐標為(350,350)；深灰色方框代表障礙物；白色區域代表安全區域。

圖3為機器人在迭代5000次過程中所得到的最短路徑軌跡。該軌跡也是機器人從初始點到目標點的最短距離。說明通過機器人與環境的不斷交互，強化學習能夠讓機器人在簡單環境中進行良好的路徑規劃。

圖2 仿真環境

圖3 Q-learning最短路徑圖

圖4為迭代過程中的回報值變化曲線，由圖可知，隨著迭代步數的增加，回報值有越來越大的趨勢，這說明機器人在與環境迭代過程中，所規劃的路徑越來越趨于最優路徑。圖5為迭代過程中的步長，由圖可知，隨著迭代步數的增加，起始點到終點的規劃步長趨于減少，最終收斂于最優步長。

圖4 回報值隨迭代次數變化曲線圖

圖5 到達目標點所需步長隨迭代次數的變化曲線圖

3.3.2 復雜的仿真環境

環境狀態很復雜時，簡單的Q-learning很難獲得好的效果，用同樣方法構建圖6仿真環境。圖7為回報值和到達目標點所需步長隨迭代次數變化圖，由圖可知，迭代30000次時，回報值仍為負數，說明算法并沒有很好的學習，到達目標點所需步長值一直大于200，顯然算法沒有收斂，機器人不能到達目標點。

圖6 仿真環境

圖7 回報值和到達目標點所需步長隨迭代次數變化圖

將構建的DQN算法應用到圖6仿真環境中，結果機器人能到達終點。圖8為機器人在迭代5000次過程中所得到的最短路徑軌跡。該軌跡也是機器人從初始點到目標點的最短距離。說明在復雜的環境中，DQN算法沒有維數災難的困惱，能夠讓機器人進行良好的路徑規劃。圖9為回報值和到達目標點所需步長隨迭代次數變化圖，從圖中可以看出，DQN在迭代1000次附近就開始收斂，相比于Q-learning，不僅收斂速度較快，而且能夠在復雜環境中進行良好的路徑規劃。

圖8 DQN最短路徑圖

圖9 回報值和到達目標點所需步長隨迭代次數變化圖

4 結束語

提出了一種基于深度學習的強化學習算法，以網絡輸出代替Q值表，解決Q-learning的維數災難問題，通過構建記憶回放矩陣和兩層網絡結構打斷數據相關性，提高網絡收斂性。仿真實驗說明該方法的有效性和可行性。本文主要針對靜態環境下的復雜路徑規劃的研究，針對DQN在更復雜的動態環境下的路徑規劃問題，還有待進一步的研究。