基于深度Q學(xué)習(xí)的移動(dòng)機(jī)器人路徑規(guī)劃

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

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

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

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

1 Q-learning算法

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

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

(1)

式中，st為t時(shí)刻移動(dòng)機(jī)器人的狀態(tài)，在狀態(tài)st下執(zhí)行動(dòng)作at，移動(dòng)機(jī)器人狀態(tài)變?yōu)閟t+1，同時(shí)得到獎(jiǎng)勵(lì)值rt;rt是對(duì)狀態(tài)st+1的評(píng)估，表示機(jī)器人由當(dāng)前狀態(tài)執(zhí)行動(dòng)作到下一個(gè)狀態(tài)所獲得的獎(jiǎng)勵(lì)值；動(dòng)作a∈A，A為動(dòng)作空間；狀態(tài)st,st+1∈S,S為狀態(tài)空間；α為學(xué)習(xí)率，α越大Q值收斂越快，但越容易產(chǎn)生振蕩；maxaQ(st+1,a)表示從動(dòng)作集A中選擇一個(gè)動(dòng)作A使得Q(st+1,a)的取值最大；γ為折扣因子，表示未來(lái)獎(jiǎng)勵(lì)對(duì)當(dāng)前動(dòng)作的影響程度[14]。

將式(1)變形成

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

(2)

由式(2)可知，狀態(tài)st對(duì)應(yīng)的Q值穩(wěn)定的必要條件為狀態(tài)st+1對(duì)應(yīng)的maxaQ(st+1,a)恒定，否則上一個(gè)狀態(tài)的Q值會(huì)隨下一個(gè)狀態(tài)的Q值的改變而變化，因?yàn)檎w是一個(gè)回溯過(guò)程，前面所有的動(dòng)作對(duì)應(yīng)的狀態(tài)都不能達(dá)到穩(wěn)定值。

假設(shè)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)簡(jiǎn)寫成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)

因?yàn)?<α<1，所以0<(1-α)<1，當(dāng)n→∞，(1-α)n→0。

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

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

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

(6)

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

2 DQN算法實(shí)現(xiàn)

2.1 DQN模型結(jié)構(gòu)

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

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

(7)

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

2.2 DQN特點(diǎn)

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

2.2.1 記憶回放

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

2.2.2 建立雙層網(wǎng)絡(luò)結(jié)構(gòu)

DQN與傳統(tǒng)的利用神經(jīng)網(wǎng)絡(luò)逼近值函數(shù)方法相比，建立了一個(gè)與當(dāng)前Q網(wǎng)絡(luò)結(jié)構(gòu)相同、參數(shù)不同的Q-target神經(jīng)網(wǎng)絡(luò)，即在計(jì)算目標(biāo)Q值使用專門的Q-target網(wǎng)絡(luò)來(lái)計(jì)算，而不是直接使用預(yù)更新的當(dāng)前Q網(wǎng)絡(luò)，以此來(lái)減少目標(biāo)值與當(dāng)前值的相關(guān)性。損失函數(shù)公式為

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

(8)

式中,Q(s,a;w)為當(dāng)前網(wǎng)絡(luò)的輸出，用來(lái)評(píng)估當(dāng)前狀態(tài)動(dòng)作對(duì)的值函數(shù)。Q(s′,a′;w-)為Q-target的輸出，用來(lái)求得目標(biāo)值函數(shù)的Q值。

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

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

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

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

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

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

3 仿真結(jié)果及結(jié)果分析

3.1 動(dòng)作空間的表示

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

(10)

3.2 獎(jiǎng)賞函數(shù)的設(shè)計(jì)

獎(jiǎng)賞函數(shù)在強(qiáng)化學(xué)習(xí)過(guò)程中具有導(dǎo)向作用，對(duì)強(qiáng)化學(xué)習(xí)所采取動(dòng)作的好壞做出評(píng)價(jià)，用標(biāo)量r表示。強(qiáng)化學(xué)習(xí)的目的就是使機(jī)器人最終獲得的總的獎(jiǎng)賞值之和最大。所設(shè)置的獎(jiǎng)賞函數(shù)為

(11)

3.3 仿真結(jié)果與分析

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

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

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

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

圖2 仿真環(huán)境

圖3 Q-learning最短路徑圖

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

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

圖5 到達(dá)目標(biāo)點(diǎn)所需步長(zhǎng)隨迭代次數(shù)的變化曲線圖

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

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

圖6 仿真環(huán)境

圖7 回報(bào)值和到達(dá)目標(biāo)點(diǎn)所需步長(zhǎng)隨迭代次數(shù)變化圖

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

圖8 DQN最短路徑圖

圖9 回報(bào)值和到達(dá)目標(biāo)點(diǎn)所需步長(zhǎng)隨迭代次數(shù)變化圖

4 結(jié)束語(yǔ)

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