基于改進的DQN機器人路徑規(guī)劃

董永峰，楊 琛，董 瑤+，屈向前，肖華昕，王子秋

(1.河北工業(yè)大學(xué) 人工智能與數(shù)據(jù)科學(xué)學(xué)院，天津 300401；2.河北工業(yè)大學(xué) 河北省大數(shù)據(jù)計算重點實驗室，天津 300401；3.河北工業(yè)大學(xué) 河北省數(shù)據(jù)驅(qū)動工業(yè)智能工程中心，天津 300401)

0 引 言

移動機器人的研究已經(jīng)成為當(dāng)前社會和科技的研究方向，路徑規(guī)劃技術(shù)是機器人研究中的基礎(chǔ)問題[1]。硬件技術(shù)的進步促進了機器人路徑規(guī)劃算法的發(fā)展，包括傳統(tǒng)算法，例如：遺傳算法[2]、蟻群算法[3]、強化學(xué)習(xí)[4]。還有另一種新穎的方法，深度強化學(xué)習(xí)[5]，該方法是深度學(xué)習(xí)與強化學(xué)習(xí)的結(jié)合，深度強化學(xué)習(xí)解決了強化學(xué)習(xí)中狀態(tài)到動作映射所帶來的維數(shù)災(zāi)難問題[6]，能更好滿足機器人動作選擇需求。

Google DeepMind中Mnih等提出深度Q網(wǎng)絡(luò)模型[7]，該模型將深度網(wǎng)絡(luò)和Q-learning算法結(jié)合，不僅解決了傳統(tǒng)Q-learning算法中的維數(shù)災(zāi)難，也可以機器人所獲取的環(huán)境信息作為訓(xùn)練數(shù)據(jù)訓(xùn)練網(wǎng)絡(luò)，達到網(wǎng)絡(luò)收斂[8]。Tai Lei等[9]將DQN算法應(yīng)用到了移動機器人的路徑規(guī)劃中，但是在實驗過程中，出現(xiàn)了過估計對機器人動作選擇帶來的負面影響，造成機器人獲得的獎賞值和規(guī)劃出的路徑并非最優(yōu)。在DQN的基礎(chǔ)上又出現(xiàn)了很多改進的算法，比如深度雙Q網(wǎng)絡(luò)[10]、競爭深度Q網(wǎng)絡(luò)[11]、優(yōu)先回放DQN[12]、平均DQN[13]等。DDQN有效解決了DQN在實驗環(huán)境下存在Q學(xué)習(xí)算法固有的缺點——過估計問題[14]，使得智能體能夠選擇相對較優(yōu)的動作。但是DDQN優(yōu)化目標中，僅僅利用當(dāng)前估計網(wǎng)絡(luò)參數(shù)，忽略了先驗知識的重要性。在前期的網(wǎng)絡(luò)訓(xùn)練中，網(wǎng)絡(luò)參數(shù)均為初始化，并未進行網(wǎng)絡(luò)訓(xùn)練，即不存在先驗知識，若是利用平均DQN優(yōu)化目標進行估計網(wǎng)絡(luò)參數(shù)訓(xùn)練，會使得網(wǎng)絡(luò)參數(shù)訓(xùn)練效率降低。

為了更有效解決深度Q學(xué)習(xí)算法中的過估計問題，本文提出一種DTDDQN算法，融合平均DQN和DDQN的各自優(yōu)點，來減少過估計對移動機器人動作選擇的影響，實現(xiàn)最優(yōu)動作策略的選擇。

1 深度強化學(xué)習(xí)

1.1 深度Q學(xué)習(xí)

在Q-learning算法中，利用一個Q值表來對狀態(tài)-動作值函數(shù)進行存儲和更新，并根據(jù)機器人所學(xué)習(xí)的經(jīng)驗知識對Q值表進行更新。然而隨著機器人所處環(huán)境狀態(tài)復(fù)雜程度的升高，使用Q值表存儲狀態(tài)-動作值函數(shù)的短板越發(fā)明顯，將會引起“維數(shù)”災(zāi)難。為解決Q-learning隨著環(huán)境復(fù)雜程度的升高而帶來的“維數(shù)”災(zāi)難，可以利用函數(shù)近似逼近來替代Q值表并對值函數(shù)進行計算。函數(shù)逼近可以是線性函數(shù)逼近或者是非線性函數(shù)逼近，比如利用深度學(xué)習(xí)中的神經(jīng)網(wǎng)絡(luò)，我們可以稱之為深度Q網(wǎng)絡(luò)(DQN)。

DQN是Q-learning算法的一種改進算法，它以神經(jīng)網(wǎng)絡(luò)作為狀態(tài)-動作值函數(shù)的載體，用參數(shù)為θ的f網(wǎng)絡(luò)來近似替代狀態(tài)-動作值函數(shù)，公式如式(1)所示

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

(1)

其中，f(s,a,θ)可以是一種任何類型的函數(shù)，通過函數(shù)來近似替代Q值表，無論輸入空間有多大，都能夠用神經(jīng)網(wǎng)絡(luò)的輸出值計算Q值。在深度Q網(wǎng)絡(luò)中，存在兩個網(wǎng)絡(luò)，分別為估計網(wǎng)絡(luò)和目標網(wǎng)絡(luò)，兩個網(wǎng)絡(luò)的結(jié)構(gòu)完全相同，不同之處在于網(wǎng)絡(luò)參數(shù)。其中估計網(wǎng)絡(luò)的輸出為Q(s,a,θ)，用來估計當(dāng)前狀態(tài)動作的值函數(shù)；目標網(wǎng)絡(luò)的輸出表示為Q(s,a,θ-)。網(wǎng)絡(luò)參數(shù)更新規(guī)則為，估計網(wǎng)絡(luò)中的參數(shù)實時進行更新，在經(jīng)過C步之后，估計網(wǎng)絡(luò)的參數(shù)會復(fù)制到目標網(wǎng)絡(luò)中。DQN網(wǎng)絡(luò)更新是利用TD誤差進行參數(shù)更新。公式如式(2)所示

Lt(θt)=E(yt-Q(s,a,θt))2

(2)

其中，yt為優(yōu)化目標，計算公式如下

(3)

DQN中訓(xùn)練網(wǎng)絡(luò)所用的樣本集來自于經(jīng)驗池中，在移動機器人與環(huán)境交互后，會將交互后的轉(zhuǎn)移樣本(st,at,rt,st+1)存儲到經(jīng)驗池D中。每次的網(wǎng)絡(luò)訓(xùn)練會從經(jīng)驗池D中取出一定數(shù)量的轉(zhuǎn)移樣本集，采用隨機梯度下降的方法進行網(wǎng)絡(luò)參數(shù)的更新。

1.2 深度雙Q學(xué)習(xí)

Van Hasselt等發(fā)現(xiàn)在實驗過程中，DQN在Q值的計算中，存在過估計的問題，即網(wǎng)絡(luò)輸出的Q值高于真實的Q值。為有效解決過估計問題，Van Hasselt等對DQN的優(yōu)化目標進行優(yōu)化改進，利用估計網(wǎng)絡(luò)輸出s狀態(tài)下的Q值計算出對應(yīng)Q值最高的動作a，再利用目標網(wǎng)絡(luò)輸出Q值計算優(yōu)化目標并進行網(wǎng)絡(luò)訓(xùn)練。DDQN利用估計網(wǎng)絡(luò)進行動作選擇，目標網(wǎng)絡(luò)進行策略評估，將動作選擇和策略評估進行了分離，有效解決了DQN中存在的過估計問題。其優(yōu)化目標的更新函數(shù)如式(4)所示

(4)

2 改進的算法

2.1 過估計問題

通常引起估計值函數(shù)和真實值函數(shù)之間誤差有兩方面：函數(shù)模型的不靈活性和環(huán)境中的噪聲。深度Q學(xué)習(xí)的基本框架仍然是Q-learning算法，深度Q學(xué)習(xí)只是利用神經(jīng)網(wǎng)絡(luò)來代替table表來記錄狀態(tài)動作函數(shù)，所以深度Q學(xué)習(xí)無法克服Q-learning算法本身固有的缺點—過估計。

(5)

2.2 DTDDQN算法

假設(shè)在狀態(tài)s下，機器人有動作a1,a2可以進行選擇并執(zhí)行，其中對應(yīng)的真實的值函數(shù)為Q(s1,a1),Q(s2,a2)，并且在真實值情況下Q(s,a1)>Q(s,a2)，說明動作a1為狀態(tài)s下的最優(yōu)動作，動作a2為狀態(tài)s下的次優(yōu)動作。由于模型輸出存在過估計，則有可能出現(xiàn)值函數(shù)Qestimation(s,a2)誤差幅度大于值函數(shù)Qestimation(s,a1)誤差幅度，從而導(dǎo)致模型輸出的值函數(shù)Qestimation(s,a2)大于值函數(shù)Qestimation(s,a1)，由于機器人選擇策略為greedy策略，所以在該情況下機器人所選擇的動作為次優(yōu)動作a2，而并非最優(yōu)動作a1，造成機器人最終選擇的策略并非最優(yōu)。

在深度強化學(xué)習(xí)中，一種改進的方法是利用減少目標近似誤差(target approximation error，TAE)來減少過估計對動作選擇的影響，目標近似誤差指的是目標期望值與估計網(wǎng)絡(luò)的輸出值的差值。公式如式(7)所示

(6)

(7)

引起目標近似誤差TAE的原因有兩個：第一個是損失函數(shù)不精確的計算影響到了參數(shù)的訓(xùn)練；第二個是經(jīng)驗回放緩沖區(qū)的大小有限，看不見狀態(tài)動作對的泛化誤差。為了有效解決過估計在路徑規(guī)劃中的影響，需要減少TAE的值。利用先前參數(shù)的網(wǎng)絡(luò)對優(yōu)化目標值進行計算取平均并進行網(wǎng)絡(luò)參數(shù)的訓(xùn)練則能夠有效減少TAE的值，從而解決深度強化學(xué)習(xí)在路徑規(guī)劃中的過估計問題[15]。

(8)

(9)

(10)

其中，式(10)為利用先前K代的參數(shù)計算出來的Q值的平均，動態(tài)融合后的優(yōu)化目標更新網(wǎng)絡(luò)參數(shù)能夠減少目標近似誤差，從而有效避免在動作選擇時過估計問題的影響。利用改進后的優(yōu)化目標進行TD誤差計算，然后利用損失函數(shù)進行網(wǎng)絡(luò)參數(shù)的更新，本文網(wǎng)絡(luò)參數(shù)更新具體公式為

(11)

本文DTDDQN算法流程見表1。

表1 DTDDQN算法流程

3 基于DTDDQN的機器人路徑規(guī)劃

移動機器人的路徑規(guī)劃是機器人在與陌生環(huán)境的不斷的交互學(xué)習(xí)中規(guī)劃出一條避開障礙物最優(yōu)路徑。本文提出了一種DTDDQN算法，并將該算法用于機器人的路徑規(guī)劃。本文DTDDQN算法的訓(xùn)練模型如圖1所示。

圖1 DTDDQN算法模型

首先，機器人在陌生的環(huán)境中不斷的學(xué)習(xí)并采集樣本，用機器人當(dāng)前所處狀態(tài)的特征作為網(wǎng)絡(luò)輸入，將當(dāng)前位置下的Q值作為網(wǎng)絡(luò)輸出，并利用動作選擇策略進行動作選擇，到達下一個狀態(tài)，并將該系列的數(shù)據(jù)存儲到經(jīng)驗回放池D中作為網(wǎng)絡(luò)訓(xùn)練的樣本。機器人在探索環(huán)境的最優(yōu)路徑過程中，不斷利用改進的優(yōu)化目標進行網(wǎng)絡(luò)參數(shù)的更新，一直循環(huán)迭代直到訓(xùn)練完成。

在實驗中，為了減少機器人所規(guī)劃出的路徑長度，本文中的實驗機器人能夠采用8個方向動作，如圖2所示，動作1、2、3、4、5、6、7、8分別表示向上、右上、向右、右下、向下、左下、向左、左上。

圖2 方向圖

在強化學(xué)習(xí)中，獎懲函數(shù)是影響路徑規(guī)劃的重要因素。在路徑規(guī)劃中，機器人的目的為最大化從初試狀態(tài)到目標狀態(tài)的累積回報期望。因此，獎懲函數(shù)直接影響路徑規(guī)劃的結(jié)果。在實驗中，機器人碰到障礙物將會獲得-1的懲罰值，到達自由柵格將獲得1的獎賞值，到達終點獲得5的獎賞值。本文的獎懲函數(shù)公式如下

(12)

4 實驗結(jié)果與分析

4.1 實驗環(huán)境和參數(shù)配置

本文在柵格法環(huán)境下進行兩組路徑規(guī)劃實驗，DTDDQN、DDQN、DQN這3種算法的迭代次數(shù)均為5000次，機器人到達終點為一次迭代的結(jié)束標志：

(1)實驗一：與傳統(tǒng)算法對比。環(huán)境為20×20的柵格環(huán)境。起始點位置為S點，目標點位置為E點，柵格圖的環(huán)境如圖3(a)所示。該環(huán)境為文獻[16]中的環(huán)境。

(2)實驗二：與DQN和DDQN算法對比。環(huán)境為20×20的柵格環(huán)境。起始點位置為S點，目標點位置為E點，與實驗一環(huán)境進行對比，該環(huán)境障礙物分布復(fù)雜且不均勻。柵格圖的環(huán)境如圖3(b)所示。

其中黑色的柵格表示環(huán)境中的障礙物區(qū)域，白色的柵格表示環(huán)境中非障礙物可移動區(qū)域。

圖3 柵格環(huán)境

實驗環(huán)境為Windows下的頻率為2.6 GHz的CPU服務(wù)器，網(wǎng)絡(luò)框架為Tensorflow 1.8.0，選用python3.5.2版本進行編程實現(xiàn)。

本文算法與DQN、DDQN兩種算法進行對比。3種算法的網(wǎng)絡(luò)模型結(jié)構(gòu)均為5層：輸入層為機器人所在環(huán)境的特征向量；隱藏層有3層，每層有30個神經(jīng)元，各層的激活函數(shù)均為relu函數(shù)；輸出層為機器人所處環(huán)境狀態(tài)下的Q值，Q值的維數(shù)為可執(zhí)行動作的個數(shù)(即8維向量)。本文對比實驗的超參數(shù)配置見表2。

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

在本文路徑規(guī)劃訓(xùn)練過程中，探索因子初始化為1，采用模擬退火原則，每次迭代后乘以0.99，最后趨于0.1。模擬退火的原則可以使得機器人充分探索陌生的環(huán)境，獲得充足的樣本來訓(xùn)練穩(wěn)定的網(wǎng)絡(luò)，最終規(guī)劃出一條更優(yōu)的路線。

4.2 實驗結(jié)果對比分析

4.2.1 與傳統(tǒng)算法對比

本文DTDDQN算法在文獻[16]的柵格環(huán)境下與改進的蟻群算法的文獻[16]、文獻[17]、文獻[18]進行對比，對比指標包括以下兩個：一是規(guī)劃出的路徑長度；二是規(guī)劃出的路徑拐點數(shù)。所得路徑規(guī)劃線路圖如圖4所示，指標對比數(shù)據(jù)見表3。

圖4 4種算法路徑規(guī)劃

表3 4種算法對比

從表3和圖4可以得出，在路徑長度上，DTDDQN算法和文獻[16]、文獻[17]、文獻[18]這4種算法規(guī)劃出的路徑長度均為28.627，但是本文的DTDDQN算法規(guī)劃的路徑拐點數(shù)為4，而文獻[16]、文獻[17]、文獻[18]規(guī)劃的路徑拐點數(shù)分別為6,7,5。在實際的環(huán)境下，本文路徑規(guī)劃路線拐點數(shù)的減少也會減少機器人從起始點到目標點所用的時間。

4.2.2 與DQN、DDQN對比

本文在多種指標下與DQN、DDQN算法進行對比，其中包括機器人執(zhí)行某一動作所能獲得的獎賞值，該指標越高說明機器人能夠在特定的環(huán)境下選擇更優(yōu)的動作。二是網(wǎng)絡(luò)參數(shù)訓(xùn)練過程中機器人碰撞障礙物次數(shù)、算法所規(guī)劃出路徑的長度和拐點數(shù)。

圖5 平均每步獎賞值對比

表4 平均每步獎賞值對比

從圖5和表4可以看出，在大多數(shù)情況下，DTDDQN算法的平均獎賞值都在DDQN和DQN之上，DTDDQN算法在訓(xùn)練過程中的平均獎賞值為1.013，而DDQN算法和DQN算法分別為0.957和0.911。DTDDQN的平均獎賞值比DDQN高出6%，比DQN高出10%，說明在躲避障礙物上和動作選擇方面，DTDDQN算法比DDQN算法和DQN算法能夠提供更好的行動策略。

圖6(a)、圖6(b)、圖6(c)分別是經(jīng)過5000次迭代后，DQN、DDQN、DTDDQN算法按照網(wǎng)絡(luò)輸出的最大Q值所對應(yīng)的動作所規(guī)劃出的路線圖。從路線規(guī)劃圖和表5中得出，DQN、DTDDQN、DDQN算法均能規(guī)劃出了一條無碰撞的路線。

圖6 3種算法路徑規(guī)劃

從表5和圖6可以看出，在路徑長度上，DTDDQN算法規(guī)劃出了一條最優(yōu)路徑，路徑長度為28.627，拐點數(shù)為8，而DQN、DDQN算法并未規(guī)劃出一條最優(yōu)路徑，DDQN算法規(guī)劃的路徑長度為29.213，拐點數(shù)為11。最差的是DQN算法，DQN算法規(guī)劃出的路徑長度為30.385，拐點數(shù)為10。在訓(xùn)練中，DTDDQN算法中的機器人障礙物碰撞次數(shù)為21 640次，而DDQN和DQN訓(xùn)練中機器人的碰撞次數(shù)分別為25 471次和28 182次。DTDDQN算法與DDQN、DQN算法障礙物碰撞次數(shù)相比，分別減少了18%、30%的碰撞次數(shù)。由此可以看出，與DQN、DDQN算法相比，DTDDQN算法在陌生的環(huán)境和在減少碰撞次數(shù)的條件下，能夠規(guī)劃出一條更優(yōu)的路線。

表5 指標對比

5 結(jié)束語

本文提出的DTDDQN算法動態(tài)融合了DDQN和平均DQN各自優(yōu)點，DTDDQN算法前期先以較大權(quán)重的DDQN優(yōu)化目標對網(wǎng)絡(luò)參數(shù)進行更新并進行先驗知識的積累，到網(wǎng)絡(luò)訓(xùn)練的中后期，增大平均DQN優(yōu)化目標的更新的權(quán)重，從而充分利用先驗知識進行網(wǎng)絡(luò)訓(xùn)練，在減少TAE值的同時，使得網(wǎng)絡(luò)輸出的Q值更加接近真實Q值，以減少過估計對機器人在選擇動作時的影響，達到所選動作策略最優(yōu)。經(jīng)過不同環(huán)境的仿真實驗驗證，DTDDQN算法較DQN算法和DDQN算法在訓(xùn)練過程中障礙物碰撞次數(shù)和平均獎賞值以及規(guī)劃出的路徑長度方面都有一定程度的提升和優(yōu)化。