黃 穎 余玉琴

（上海理工大學光電信息與計算機工程學院 上海 200093）

1 引言

機器人路徑規(guī)劃問題就是給定環(huán)境、機器人模型，指定規(guī)劃目標（如無碰撞的到達目的地），自主地計算出機器人的運動路徑。

目前路徑規(guī)劃問題多轉化為搜索問題或者能量優(yōu)化問題解決，常用的方法有人工勢場法［1］、遺傳算法［2］和 A*算法［3］。隨著機器人路徑規(guī)劃面對的環(huán)境越來越復雜多變，傳統(tǒng)的路徑規(guī)劃算法并不能迅速響應復雜變化的環(huán)境。目前，直接利用視覺信息再結合深度網(wǎng)絡的函數(shù)近似功能［4］進行路徑規(guī)劃是路徑規(guī)劃領域的前沿研究方向，這主要依靠深度強化學習實現(xiàn)。2013年初，Google DeepMind提出直接利用游戲視頻信息進行游戲控制的深度Q網(wǎng)絡（DQN）算法［5］，是直接利用圖像信息進行強化學習任務處理的雛形。

DQN算法［5～6］是最原始且最常用的深度強化學習算法，可以用來解決路徑規(guī)劃問題，但是會學習到過高的動作狀態(tài)值。雙重深度Q網(wǎng)絡（DDQN）［7］、平均深度 Q 網(wǎng)絡［8］等算法均能減少DQN學習過程存在的動作狀態(tài)值高估現(xiàn)象，但是它們擁有復雜的卷積網(wǎng)絡結構，不能滿足高速路徑規(guī)劃的需求。為了滿足高速路徑規(guī)劃的需求，解決方案之一是使用輕量級卷積網(wǎng)絡DenseNets［9］和ResNets［10］作為深度強化學習方法中的函數(shù)逼近器，進而獲得更輕盈易訓練的模型、更少的模型參數(shù)和計算時間。

近年來，最流行的卷積網(wǎng)絡簡化方法是在層與層之間創(chuàng)建短路徑，如ResNets網(wǎng)絡、Highway網(wǎng)絡［11］、隨機深度網(wǎng)絡［12］、DenseNets網(wǎng)絡。其中，DenseNets網(wǎng)絡將之前層的輸出直接連接到該層后面的所有層，這樣之前層輸出的特征可以在其所有后續(xù)層中傳播和重利用，層與層之間的信息流將更加平滑地傳輸，從而有助于解決梯度消失問題，還能減少模型的參數(shù)量［9］。

故本文基于簡化的DenseNets和深度強化學習的競爭網(wǎng)絡架構（競爭網(wǎng)絡架構）［13］提出一種基于稠密卷積網(wǎng)絡和競爭架構的改進路徑規(guī)劃算法。該算法模型中包含兩個深度子網(wǎng)絡，其中每個子網(wǎng)絡中將競爭網(wǎng)絡架構和簡化的DenseNets以一定方式融合為一個更輕盈的深度卷積網(wǎng)絡，然后再使用DDQN或DQN算法訓練這兩個子網(wǎng)絡。最后，本文在自定義的gridmap環(huán)境中進行對比實驗。

實驗結果證明，本文提出的網(wǎng)絡架構不僅能加速模型的訓練過程和路徑規(guī)劃過程，減少計算量，提升路徑規(guī)劃的實時性，而且還能保證機器人對快速變化的環(huán)境具有很強的泛化能力，達到更加卓越的路徑規(guī)劃性能。

2 路徑規(guī)劃的深度強化學習方案

2.1 路徑規(guī)劃問題的強化學習解法

在強化學習中，若給定策略π，則動作狀態(tài)值定義為Qπ(s ，a)=π[Gt|St=s，At=a] ，是在狀態(tài) s上采取動作a后得到的累積折扣獎勵，其中：是 累 積回報，γ∈[0 ， 1]是折扣因子，[x]表示求隨機變量x的期望。最優(yōu)動作狀態(tài)值函數(shù)定義為反之，若在每個狀態(tài)上都選擇最高動作狀態(tài)值對應的動作，則從最優(yōu)動作值函數(shù)中可以輕松推導出最優(yōu)策略π*(s)=argmaaxQ*(s ，a )。

路徑規(guī)劃問題是一個序列決策問題。用強化學習理論解決路徑規(guī)劃問題時，目標是求解最優(yōu)策略π*(s)。然后在路徑規(guī)劃的每個步驟上，根據(jù)機器人不同的位置狀態(tài)s和最優(yōu)策略π*(s)決定機器人的運動方向。最后，將機器人的運動軌跡連起來即為強化學習算法規(guī)劃出的路徑。

Q 學習［14］是一種常用的求 MDP 最優(yōu)解［15～16］的強化學習算法。實際中，鑒于多數(shù)場景的狀態(tài)空間太大，研究者們通常使用函數(shù)逼近方法［4，15］學習一個參數(shù)化的動作值函數(shù)Q(s ，a;θ )來表示給定狀態(tài)s上的所有可能的動作狀態(tài)值，再不斷用強化學習算法迭代訓練，最后使其收斂到Q*(s ，a )。使用函數(shù)逼近方法，Q學習的過程如式（1）所示：

式中：St，At，Rt+1分別為當前時間步上的環(huán)境狀態(tài)、動作、即時獎勵，St+1為環(huán)境的下一個狀態(tài)，θt為當前時間步上函數(shù)逼近器的參數(shù)，α是參數(shù)更新的步長，為當前時間步上的更新目標，其定義如式（2）：

2.2 常用的深度強化學習網(wǎng)絡及算法

深度強化學習網(wǎng)絡中最常用的函數(shù)逼近器是卷積神經(jīng)網(wǎng)絡。DQN網(wǎng)絡［5～6］是擬合動作狀態(tài)值函數(shù)的卷積網(wǎng)絡，也是從n維狀態(tài)空間?n到m維動作空間?m的映射函數(shù)。最原始的DQN網(wǎng)絡［5］僅是一個用Q學習訓練的多層卷積網(wǎng)絡，它對于一個給定的輸入狀態(tài)s輸出一個動作狀態(tài)值向量Q(s ，·;θ )，其中 θ 是卷積網(wǎng)絡的權重參數(shù)。

而DQN算法中則使用了經(jīng)驗回放和目標網(wǎng)絡的技術，它們能穩(wěn)定DQN的訓練過程，大大提高算法的性能［6］。經(jīng)驗回放技術將所收集的轉換信息存儲在經(jīng)驗回放緩沖區(qū)中，每個時間步上都從該存儲區(qū)中隨機地采樣一定數(shù)量的轉換信息按照式（1）更新在線網(wǎng)絡的參數(shù)。目標網(wǎng)絡的使用則是在DQN中使用兩個結構相同而參數(shù)不同的網(wǎng)絡近似動作狀態(tài)值函數(shù)。參數(shù)為θ的在線網(wǎng)絡和參數(shù)為θ-的目標網(wǎng)絡的更新方式不同，所起的作用不同。參數(shù)θ在每個時間步上都更新，參數(shù)θ-每隔τ時間步復制在線網(wǎng)絡的參數(shù)，而在其他時間步上保持參數(shù)θ-固定不變。DQN算法每個時間步上的更新目標是

研究表明，DQN算法的學習過程普遍存在動作值高估現(xiàn)象。DDQN算法可以降低DQN學習過程中的動作值高估，它以最簡單的方式將雙重Q學習與DQN結合，從而將Q學習中貪婪動作的選擇與評估操作分離［7］。所以，每個時間步上DDQN算法的更新目標是

3 改進的路徑規(guī)劃算法

為了使機器人能進行實時的路徑規(guī)劃，必須改進現(xiàn)存的路徑規(guī)劃算法，使改進后的深度強化學習算法擁有更少的網(wǎng)絡參數(shù)、計算時間與訓練開支。本文基于簡化的DenseNets和競爭網(wǎng)絡架構提出一種融合簡化稠密卷積網(wǎng)絡和競爭架構的新型路徑規(guī)劃算法，算法的網(wǎng)絡結構圖參見圖1。

圖1 融合競爭架構的簡化稠密卷積網(wǎng)絡的結構框圖

3.1 競爭網(wǎng)絡架構

深度強化學習的競爭網(wǎng)絡架構［13］是基于DQN網(wǎng)絡［5］提出的，它能進一步穩(wěn)定DQN算法的訓練過程，而且能將動作狀態(tài)值的學習推廣到整個行為空間［13］，圖2為競爭網(wǎng)絡架構的結構示意圖。

圖2 競爭網(wǎng)絡架構的結構示意圖

競爭架構應用于深度強化學習網(wǎng)絡時，將已有網(wǎng)絡的最后一個卷積層均分為兩半，再分別連接到一個全連接層，每個全連接層都是一個估計器，分別用于狀態(tài)值函數(shù)V(s ;θ，χ)和依賴于狀態(tài)的動作優(yōu)勢函數(shù)A(s ， a;θ，β)的估計。最后將兩個估計結果按照式（5）整合成動作狀態(tài)值函數(shù)Q(s ，a )：

式中：θ表示網(wǎng)絡中卷積層的權重，β和 χ分別是網(wǎng)絡中兩個完全連接層的連接權重， ||A為有效動作數(shù)。

3.2 簡化的稠密卷積網(wǎng)絡

DenseNets是由許多稠密塊和過渡層組成的卷積網(wǎng)絡。稠密塊中的每兩層間均以前饋方式連接，每一層都將之前所有層的輸出特征圖作為其輸入，而將自身的輸出特征圖作為其之后所有層輸入的一部分。在這種連接模式下，DenseNets模型更加緊湊，不易陷入過擬合，信息流能傳播到更深層，卷積網(wǎng)絡變得更加容易訓練，還能減少模型的參數(shù)量［9］，故本文將DenseNets作為改進路徑規(guī)劃網(wǎng)絡的切入點與基礎網(wǎng)絡。

假設圖片x0在稠密塊中傳播，網(wǎng)絡共有L層，每一層都有一個非線性轉換Hl(·)，其中l(wèi)表示層的維度。定義xl為第l層的輸出。則在稠密塊中，第 l層會將第 0，1，…，l-1層的輸出特征圖x0，x1，…，xl-1作為該層的輸入，如式（6）所示：

其中：[x0，x1，…，xl-1] 是指稠密塊中第 0，1，…，l-1層產(chǎn)生的輸出特征圖的拼接，為一個張量；Hl(·)為修正線性單元（ReLU）［17］和 3×3卷積這兩個連續(xù)操作的組合函數(shù)，每個Hl(·)產(chǎn)生k個特征圖，k為網(wǎng)絡的增長速率。

為了精簡計算，本文提出的改進算法的模型采用簡化的DenseNets，其稠密塊的結構如圖3所示。稠密塊的簡化操作如下：舍棄bottleneck卷積層［9］對特征圖進行降維的設計，過渡層是具有不同核大小的平均池化層，并取壓縮系數(shù)η=1，即稠密塊的輸出特征圖在過渡層的作用下數(shù)量保持不變。

圖3 簡化的DenseNets中稠密塊的結構圖

3.3 融合競爭架構的簡化稠密卷積網(wǎng)絡

本文提出改進的路徑規(guī)劃算法，其主要創(chuàng)新點是將競爭網(wǎng)絡架構與簡化的DenseNets融合得到新的深度強化學習網(wǎng)絡。該網(wǎng)絡中包含兩個深度子網(wǎng)絡，每個子網(wǎng)絡將簡化的DenseNets作為網(wǎng)絡主體，然后將該網(wǎng)絡主體最后的過渡層輸出按競爭架構的原理均分成兩個全連接層，這兩個全連接層分別用來估計狀態(tài)值函數(shù)和動作優(yōu)勢函數(shù)，最后再按式（5）合成為動作狀態(tài)值函數(shù)。融合后的網(wǎng)絡結構如圖1所示，網(wǎng)絡的細節(jié)如表1所示。表中conv操作對應于一個二維卷積層，[3 ×3 conv[]]×3操作表示該簡化稠密塊中包含3個3×3大小的卷積層。

表1 融合競爭架構的簡化稠密卷積網(wǎng)絡的結構表

上述結構圖中，每個子網(wǎng)絡的輸入圖像大小為84×84×3，它先經(jīng)過一個有32個卷積通道、卷積核大小8×8、步長為4的卷積層。隨后將卷積層的輸出特征圖輸入到后續(xù)網(wǎng)絡中，后續(xù)網(wǎng)絡包含三個簡化稠密塊，每一個稠密塊有相同的增長速率k和不同的網(wǎng)絡層數(shù)，且都會緊跟一個大小不同的平均池化層。對于三個稠密塊中的3×3卷積層，在輸入圖像的每一側都用0像素填充一個像素位置以保證特征圖尺寸不變［9］。在本文的路徑規(guī)劃實驗中，深度網(wǎng)絡中三個簡化稠密塊的輸出特征圖尺寸分別是20×20、9×9和7×7。然后，將第3個池化層的輸出均分為兩個全連接層，再按式（5）合成為動作狀態(tài)值函數(shù)。最后，基于該路徑規(guī)劃網(wǎng)絡在路徑規(guī)劃的每個時間步上使用DDQN算法訓練。

經(jīng)過足干次迭代訓練，本文得到訓練好的路徑規(guī)劃智能體，然后在不同大小的Gridmap環(huán)境中驗證智能體的路徑規(guī)劃效果。

4 實驗結果與分析

本節(jié)通過實驗證明了改進的路徑規(guī)劃算法有如下優(yōu)點：它不僅能減少模型參數(shù)量和計算量，加速模型的訓練過程，提升路徑規(guī)劃的實時性，而且還能保證機器人對環(huán)境具有很強的泛化能力，并達到更加卓越的路徑規(guī)劃性能。

4.1 實驗環(huán)境與超參數(shù)設置

4.1.1 Gridmap環(huán)境與基本設置

Gridworld是一個常用的強化學習測試平臺，它允許精確地計算最優(yōu)值函數(shù)。Gridmap是Grid?world的變體，二者唯一的區(qū)別在于Gridmap中有很多障礙物而Gridworld中沒有，詳見圖4。Gridmap問題的目標是使智能體在避開所有障礙物的情況下盡快達到目標點。

圖4 左：不同大小的Gridmap；右：Gridworld

本文在Gridmap環(huán)境中進行路徑規(guī)劃實驗，其狀態(tài)空間包含二維離散網(wǎng)格的所有可能點對，動作空間包含四個與羅盤方向?qū)膭幼?。路徑?guī)劃智能體通過原始像素特征、具有one-hot特征的動作與環(huán)境交互。智能體從Gridmap中的深色塊出發(fā)，避開淺色的障礙物塊，在黑色塊上移動，以其中的白色塊為目標點。若智能體到達目標點，則獲得+1的獎勵；若撞上障礙物和墻壁（Gridmap邊界），則獲得-1的獎勵并退回到上一個位置；否則，智能體每走一步就獲得-0.01的獎勵。每執(zhí)行一次動作，智能體在選定方向上前進一定的距離。在訓練智能體時，每個路徑規(guī)劃任務中的起點、目標點和障礙物都是隨機分布的，目的是使訓練的智能體對快速變化的環(huán)境具有很強的泛化能力，同時具有魯棒性。

4.1.2 實驗超參數(shù)設置

本文在自定義的Gridmap環(huán)境中分別對本文提出的改進路徑規(guī)劃算法和已有算法做對比實驗，實驗中使用的超參數(shù)如表2所示。本文實驗中，有效動作數(shù) ||A=4，所有路徑規(guī)劃網(wǎng)絡的輸入圖像大小均為84×84×3。

表2 論文實驗所使用的超參數(shù)列表

4.2 實驗效果

4.2.1 路徑規(guī)劃模型的性能評估

本文進行以下對比實驗：實驗組分別使用DQN算法和DDQN算法在大小為5×5和8×8的gridmap中訓練融合競爭架構的簡化稠密卷積網(wǎng)絡，對照組分別使用DQN算法和DDQN算法在大小為5×5和8×8的Gridmap中訓練Dueling DDQN網(wǎng)絡。

圖5展示了所有訓練過程中平均預測Q值的變化曲線，實驗組和對照組的變化曲線均是10次獨立訓練過程的平均曲線，其中每個獨立的訓練過程包含若干完整的路徑規(guī)劃試驗。鑒于動作狀態(tài)值的高估現(xiàn)象在涉及Q學習的過程中均真實存在，所以本文用訓練過程中平均預測Q值的大小來反映動作值高估的程度，而無需計算真正的動作值。平均預測Q值的計算模仿文獻［7］，平均預測Q值越大，動作值高估現(xiàn)象越嚴重。比較圖5中實驗組、對照組的平均預測Q值變化曲線可知：大部分曲線的取值相近，而本文提出的改進算法的訓練過程所得的虛線和實線取值相對更低。所以，本文提出的改進算法可以有效地減少動作值高估，而不會加重該現(xiàn)象。

本文統(tǒng)計了兩組對比實驗中模型參數(shù)、訓練時間和訓練開支等方面的結果，詳見表3，它展示了本文所有的路徑規(guī)劃算法的模型在5×5和8×8大小的Gridmap中各自的模型參數(shù)量、平均訓練時間、平均評估時間和模型所需的訓練回合。注意，本節(jié)所示結果中的DenseDDQN和DenseDQN分別代表使用DDQN算法和DQN算法訓練融合競爭架構的簡化稠密卷積網(wǎng)絡，DDQN和DQN分別代表使用DDQN算法和DQN算法訓練Dueling DDQN網(wǎng)絡，訓練回合定義為使實驗中每個路徑規(guī)劃試驗的平均累積獎勵達到同一獎勵所需要的試驗個數(shù)。

圖5 模型訓練過程中平均估計Q值的變化曲線圖

由表3中的加粗數(shù)據(jù)可知，實驗組結果分別約為對照組結果的2/3、1/2、1/2（5×5）或2/3（8×8）、1/2（5×5）或1/4（8×8）。故本文提出的改進算法的模型擁有更少的模型參數(shù)、更低的模型訓練開支和更少的計算時間，路徑規(guī)劃算法的實時性更好。

表3 各網(wǎng)絡模型參數(shù)、平均訓練時間和訓練開支列表

表4 Gridmap上路徑規(guī)劃性能的比較表（ε=0.01）

4.2.2 路徑規(guī)劃策略的性能評估

本小節(jié)進一步通過實驗結果證明：本文提出的改進算法不僅擁有更少的模型參數(shù)量、更少的計算時間和更低的模型訓練開支，而且能學習到質(zhì)量更優(yōu)的路徑規(guī)劃策略。

本文在10000個起點、目標點和障礙物都隨機放置的路徑規(guī)劃回合中對所有訓練得到的智能體以ε-greedy策略進行評估，評估環(huán)境的隨機性不僅檢驗了所訓練的路徑規(guī)劃智能體對環(huán)境的泛化能力，還驗證了其魯棒性。本文分別在5×5和8×8大小的Gridmap中作如下比較：DenseDDQN vs.DDQN、DenseDQN vs.DQN。

用以下四個評估指標來衡量路徑規(guī)劃算法的性能［18］。

1）成功率：每次試驗能成功避開所有障礙物到達目標點的概率（越高越好）；

2）路徑差異：智能體的規(guī)劃路徑與最短路徑之間的平均差異（越低越好），本文用A*算法［3］尋找最短路徑；

3）期望獎勵：總折扣獎勵的均值（越高越好）；

4）平均步數(shù)：智能體到達目標點所用步數(shù)的平均值（越低越好）。

表4展示了總體實驗結果，所有數(shù)據(jù)均為多個評估結果的均值。為了突出結果，本文做了標記，將性能優(yōu)于現(xiàn)存模型的結果加粗，將最好的結果額外用斜體標注。如表4中的粗體部分所示，DenseDDQN和DenseDQN學習到的路徑規(guī)劃策略在成功率、路徑差異、期望獎勵和平均步數(shù)方面的表現(xiàn)均優(yōu)于DDQN和DQN學習到的路徑規(guī)劃策略。性能的大幅提升體現(xiàn)在8×8大小的Gridmap上，與DDQN和DQN上分別為94.7%與94.26%的成功率相比，DenseDDQN和DenseDQN能達到99.42%和99.01%的成功率，均能在迅速變化的環(huán)境中將路徑規(guī)劃成功率提高約5%。

圖6 智能體在評估過程中的成功率曲線圖

此外，圖6繪制了本文所有訓練好的智能體在其評估過程中路徑規(guī)劃成功率的變化曲線，其中每條曲線都是100個獨立評估過程的平均變化曲線，而每個獨立的評估過程均由10000個獨立的路徑規(guī)劃試驗組成。觀察圖6可知，圖中的藍色曲線和橙色曲線明顯高于圖中的紅色和綠色曲線。所以，在相同的評估策略下，由本文提出的改進路徑規(guī)劃算法學習到的策略始終優(yōu)于由Dueling DDQN算法學習到的策略，且本文提出的改進路徑規(guī)劃算法的學習曲線相對更穩(wěn)定、收斂更快。

綜上，本文提出的改進路徑規(guī)劃算法學習到的路徑規(guī)劃策略不僅質(zhì)量更優(yōu)，且能取得更頂尖的路徑規(guī)劃性能。

4.3 實驗結果分析

實驗結果表明，本文提出的改進路徑規(guī)劃算法不僅能加速模型的訓練，減少計算量，提升路徑規(guī)劃的實時性，而且還能保證機器人對快速變化的環(huán)境具有很強的泛化能力，并達到更加卓越的路徑規(guī)劃性能。

但是，智能體在到達目標點的過程中偶爾會走一些彎路，甚至會在一個局部區(qū)域徘徊而無法到達目標點，如圖7中實例第二、三列所示。其可能原因如下：因為本文實驗中的每一次路徑規(guī)劃試驗的起點、目標點和障礙物都是隨機放置的，所以Grid?map問題的狀態(tài)空間非常大，在有限數(shù)量的訓練步驟中不能保證將所有的狀態(tài)至少遍歷一遍。圖7為實驗中幾個成功和失敗的例子，其中灰色點線為A*算法尋找的最短路徑，白色虛線為訓練好的智能體規(guī)劃的路徑。

圖7 5×5和8×8的Gridmap中一些路徑規(guī)劃結果

5 結語

本文提出了一種基于稠密卷積網(wǎng)絡和競爭架構的改進路徑規(guī)劃算法。基于現(xiàn)有的深度強化學習路徑規(guī)劃網(wǎng)絡的不足之處，本文首先提出了融合競爭架構的簡化稠密卷積網(wǎng)絡，該網(wǎng)絡比現(xiàn)有的路徑規(guī)劃網(wǎng)絡更加輕盈。然后，本文用強化學習解決路徑規(guī)劃問題，使用DDQN算法訓練該網(wǎng)絡，從而近似最優(yōu)動作狀態(tài)值函數(shù)。最后，基于自定義的Gridmap環(huán)境進行實驗。實驗結果證明，該算法擁有更少的模型參數(shù)、更少的計算時間、更低的訓練開支，提升路徑規(guī)劃的實時性，而且能保證機器人對快速變化的環(huán)境具有很強的泛化能力，并達到更加卓越的路徑規(guī)劃性能?？傊?，在路徑規(guī)劃速度和成功率方面，本文提出的算法有顯著優(yōu)勢。