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

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

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

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

1 Q-learning算法

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

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

(1)

式中，st為t時刻移動機器人的狀態(tài)，在狀態(tài)st下執(zhí)行動作at，移動機器人狀態(tài)變?yōu)閟t+1，同時得到獎勵值rt;rt是對狀態(tài)st+1的評估，表示機器人由當前狀態(tài)執(zhí)行動作到下一個狀態(tài)所獲得的獎勵值；動作a∈A，A為動作空間；狀態(tài)st,st+1∈S,S為狀態(tài)空間；α為學習率，α越大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)可知，狀態(tài)st對應的Q值穩(wěn)定的必要條件為狀態(tài)st+1對應的maxaQ(st+1,a)恒定，否則上一個狀態(tài)的Q值會隨下一個狀態(tài)的Q值的改變而變化，因為整體是一個回溯過程，前面所有的動作對應的狀態(tài)都不能達到穩(wěn)定值。

假設st+1狀態(tài)穩(wěn)定，即Qt+1恒定，為求Q(st,at)的穩(wěn)定狀態(tài)，借助式(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收斂于最優(yōu)值，即

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

(6)

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

2 DQN算法實現(xiàn)

2.1 DQN模型結構

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

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

(7)

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

2.2 DQN特點

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

2.2.1 記憶回放

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

2.2.2 建立雙層網(wǎng)絡結構

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

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

(8)

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

Q-target網(wǎng)絡參數(shù)w-由參數(shù)w延遲更新獲得，即參數(shù)w實時更新，經過若干輪迭代后，將當前Q網(wǎng)絡的參數(shù)賦值給Q-target網(wǎng)絡。對參數(shù)w進行求導，可得值函數(shù)的更新，如式(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ǎng)絡參數(shù)w-和當前網(wǎng)絡參數(shù)w。

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

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

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

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

⑥ 每隔N步將參數(shù)w復制給參數(shù)w-。

3 仿真結果及結果分析

3.1 動作空間的表示

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

(10)

3.2 獎賞函數(shù)的設計

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

(11)

3.3 仿真結果與分析

3.3.1 簡單的仿真環(huán)境

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

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

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

圖2 仿真環(huán)境

圖3 Q-learning最短路徑圖

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

圖4 回報值隨迭代次數(shù)變化曲線圖

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

3.3.2 復雜的仿真環(huán)境

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

圖6 仿真環(huán)境

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

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

圖8 DQN最短路徑圖

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

4 結束語

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