深度強化學習及智能路徑規劃應用綜述

程浩鵬，朱 涵，楊高奇，晏為民，王慧婷

（1.中國民用航空飛行學院計算機學院，廣漢 618300；2.中國民用航空飛行學院理學院，廣漢 618300）

0 引言

機器人技術自上世紀六十年代起就有學者開始了相關的研究，并隨著自動控制技術與傳感器技術的進步，電子工業的逐步發展，經過近半個世紀的不斷發展，各類機器人幾乎應用到了各行各業［1］。在進入21 世紀以來，機器人技術熱度不減，并被工業界認為是可以引領未來產業發展的重要技術［2］。

機器人的使用領域從傳統工業制造領域不斷擴展，現已應用于醫療服務、教育服務、地質地理勘探、生物工程、搶險救災等不同領域［3］。按照作業空間來對機器人做劃分，可分類為：陸地移動機器人、水下作業機器人、無人飛機、外星探索機器人等［4］。目前需要突破的機器人關鍵技術包括：環境感知、導航和運動規劃、類人操作、人機交互、行為安全等［5］。本文選取小型移動機器人在路徑規劃上的應用作為典型研究對象進行分析。

路徑規劃作為機器人關鍵技術之一，其原型可視為早在上世紀60 年代就被提出的旅行商問題（Traveling Salesman Problem，TSP）［6］，旅行商問題后被證明是組合優化中的一個NP-難問題［7］。由旅行商問題可延伸到物流業中的車輛路徑規劃問題（Vehicle Routing Problem，VRP），最早是由Dantzig 等［8］提出的卡車調度問題。經典的車輛路徑規劃問題就是在一定約束條件下，尋找車輛從起點到終點狀態的無碰撞最優或次優路徑［9］。此約束條件由車輛本身內在約束的運動學和車輛動力學模型約束［10］，車輛所處環境的約束［11］等。移動機器人路徑規劃問題也可作為此類問題之一，是移動機器人導航和運動規劃研究內容的重要組成部分。

路徑規劃問題的求解，有傳統路徑規劃算法和智能仿生學路徑規劃算法，以及嘗試將深度學習與強化學習應用到路徑規劃問題的求解等方法?？蓮娜郑?2］、局部或是全局靜態與局部動態結合［13］的概念來對路徑規劃算法加以分類。除了路徑規劃問題求解，在小型移動機器人上的路徑規劃問題通常還包含環境建圖［14］這個子問題。此問題使用的建圖方式有可視圖法［15］、Voronoi 圖方法［16］、柵格圖法、SLAM 建圖等方法。

隨著人工智能技術的不斷發展，讓機器來學習，并像人類一樣思考是廣大人工智能領域研究者的目標。機器學習作為實現人工智能技術的一部分，經過了半個多世紀的研究后也有了很多分支，在模型上，有神經網絡和N個網絡疊加的深度神經網絡等；學習方法上，包括監督學習、無監督學習以及強化學習等方式。強化學習相比于其他需要更多先驗知識來進行訓練的學習方式，其具有直接與環境進行交互，通過環境的反饋信息來優化決策的特點。強化學習在游戲、機器人、推薦系統、廣告以及金融等各領域都有相關應用。但是最令人印象深刻的一次應用即是2016年AlphaGo［17-18］在圍棋上戰勝人類頂尖棋手，展示了超凡的學習和決策能力，其原理是將深度神經網絡（Deep Neural Network，DNN）與強化學習結合。

圖1展示了強化學習與人工智能各個部分之間的關系。

圖1 強化學習與人工智能的關系

強化學習與DNN 結合的算法為機器人的路徑決策提供了新的思路。本文針對小型移動機器人這一具體機器人種類，梳理深度強化學習的研究進展以及其中關于此類問題的解決方案。本文將從基于值函數的深度強化學習和基于策略的深度強化學習兩個方面做介紹。

1 深度強化學習

強化學習方法是在1954 年由Minsky［19］提出，但當時的研究僅僅限于有限的探索階段，并沒有引起太多的重視。強化學習是通過智能體/環境接口來實現學習的。其要素包括策略、獎勵函數、值函數和模型，強化學習的一種建模方法是Markov 決策過程［20］。強化學習問題的歸類可以從環境映射和學習方式兩方面分析，如圖2所示。

具體算法類型有值函數與策略函數。圖3簡要說明了兩者方法所產生的算法發展脈絡，其中包含了對兩者結合使用的算法。

2 基于值函數的深度強化學習

2.1 值函數強化學習算法

值函數更新的強化學習關鍵原理在于狀態動作價值函數Q（St，At）的設計：

通過使用此公式計算每個狀態的獎勵值，評估智能體在狀態St下所能獲得的長期價值，并對價值求期望，以此指導智能體選擇期望值最大的動作來幫助智能體決策。

深度強化學習自2013 年被Silver 及其團隊提出深度Q 網絡［21］之后，便獲得研究者們的廣泛關注，并在此基礎上對其進行各種改進。其團隊提出的深度Q 網絡是基于多層卷積神經網絡，并與值函數學習中的經典算法Q-learning算法結合，使用深度神經網絡（Deep Neural Net?works，DNN）來逼近值函數。在Atari 游戲平臺的良好表現證明此方法的良好適用性，但是DQN 也存在過估計、局部最優與全局最優的平衡、學習效率低、算法穩定性不高、智能體探索環境效率差等問題。

過估計問題不僅僅是在DQN 中產生的，而是在其基礎算法Q-learning 中已經產生，在Q-learning 中，更新Q值是通過價值函數來進行的，在每次選擇Q值時，都會選擇最大價值，然后再對價值求期望。正因如此，對于估計Q值的更新，勢必會比真實值大，就出現了過估計的問題，因而影響最終結果。Double DQN［22］是DQN 算法的改進版本，證明了在DQN 的某一些實驗平臺上存在過估計的問題，通過隨機分配經驗池中的兩套已有參數來更新值函數，對值函數更新兩次產生兩組權重，從而降低過估計的影響。多個對照實驗都表明Double DQN 獲得了比DQN 更高的分數。除了過估計問題導致的動作選擇差異，算法的不穩定性也會對性能造成影響。Ansche 等［23］提出了Averaged-DQN，對DQN 進行了擴展，基于之前學習的Q值估計進行平均，通過減少目標值中的近似誤差方差，從而具有更穩定的訓練過程并提高性能，顯著提高了穩定性和性能。Dong 等［24］提出了動態目標雙深度網絡（Dynamic Target Double Deep Q Network，DTDDQN），融合了Averaged-DQN 對Double DQN 進行改進，充分利用先驗知識對網絡進行訓練，使得網絡輸出更接近真實值。

針對DQN 算法采樣效率不高的問題，Nair等［25］展示了第一個用于深度強化學習的大規模分布式架構Gorila架構，該架構使用分布式重放內存和分布式神經網絡并行地行動和學習。利用大規模并行性，Gorila DQN 在49 款游戲中的41 款游戲中顯著優于單DQN。上述方式通過多機器同時訓練達到訓練效率的提升，在采樣方式上進行改進同樣也可以提高算法的性能，Google DeepMind 團隊的Horgan 等［26］為深度強化學習中的優先回放機制設計了一個分布式框架。這種架構將行為與學習解耦，依賴于優先經驗回放，只關注生成的最重要的數據。在Atari 平臺上，在其中的近50 種游戲上得到了比單純使用DQN 平均提高了80%，對單一游戲場景的最大提升可達106%。在強化學習采樣過程中，樣本所能提供的信息量比較少，這也是導致采樣效率不高的原因之一。Bellemare 等［27］提出了價值分布的理論，構建模型輸出對價值的分布估計，將傳統貝爾曼方程去掉了期望值，引入隨機變量Zπ的完全分布，將其稱為價值分布。并提出了一種基于分布貝爾曼最優算子的算法，并且在算法中使用51 個原子，生成了分類DQN（Categorical DQN）算法，結果顯示C51 的訓練性能優于完全訓練的DQN。在5000 萬幀內，C51在57 場比賽中的45 場比賽中的表現都優于經過全面訓練的DQN。

為了提升學習的效率，決斗網絡架構DQN（Dueling DQN）［28］使用改進的網絡架構可以獲得更高的平均獎勵，提高穩定性，能夠有效地學習狀態值函數。隨著決斗架構中Q 值的每次更新，價值流V 都會更新，這樣為V 分配了更多的資源，因此可以更好地逼近狀態值。在實驗中，當動作數量很大時，決斗架構相對于單流Q 網絡的優勢會增加。由于DQN 需要大量的訓練才能達到理想的性能要求，在學習時的表現很差，Todd Hester 的團隊［29］提出了Deep Qlearning from Demonstrations（DQfD），引入了監督學習的部分思想，使用少量的先驗數據來加速強化學習的過程，使用預訓練的過程來對學習進行加速，結果表明DQfD 比Prioritized Duel?ing Double Deep Q-Networks（PDD DQN）等三種算法的初始性能都更好，在42 場游戲環節中的41 場的前一百萬步中得分更高。Deep Mind 團隊［30］在分析了DQN 的各種改進版本之后，將各版本算法的優劣進行比較，并提出了集合優點后的算法Rainbow。同樣是在Atari 游戲中進行測試，結果顯示算法更能應對復雜環境，相比于其他算法能有更好的表現。

2.2 值函數強化學習算法在智能路徑規劃上的應用

基于值函數深度強化學習進行移動機器人的自動決策和路徑規劃，是強化學習在實際應用當中的探索之一，很多研究者在上述提出的算法當中進行了改進以及實驗。

Chen 等［31］將強化學習的經典算法Qlearning 算法應用在智能船舶的路徑決策上，船舶在模擬航道中使用Nomoto 模型進行建模。將距離、障礙物和禁區規則化為獎勵或懲罰，用于判斷船舶的性能或操縱決策，經過足夠多的訓練輪次后，產生令人信服的路徑和操縱策略。該方法在自學習和持續優化方面更有效，因此更接近人類操縱的結果。Lei 等［32］使用雙Q 網絡（DDQN）應用于未知環境的動態路徑規劃。在不同的訓練階段，動態調整起始位置和目標位置，將卷積神經網絡（CNN）用于泛化環境狀態。結果表明，經過不同動態環境的訓練和新環境的測試，智能體能夠在未知動態環境下成功到達局部目標位置。Yan 等［33］提出了一種基于全局態勢信息的無人機路徑規劃深度強化學習方法，以STAGE Scenario 軟件作為仿真環境，采用了決斗雙深度Q 網絡（D3QN）算法，證明了所提出的方法在靜態和動態任務設置下的性能。Gao等［34］提出將DRL 算法Twin Delayed Deep Deter?ministic Policy gradients（TD3）與傳統的全局路徑規劃算法Probabilistic Roadmap（PRM）相結合，作為一種新穎的路徑規劃器（PRM+TD3）。實驗結果表明，增量訓練模式可以顯著提高開發效率。而且，PRM+TD3 路徑規劃器可以有效提高模型的泛化能力。

3 基于策略的深度強化學習

3.1 策略更新的強化學習算法

強化學習的另一個狀態更新方式是基于策略的更新，和基于值函數的更新方式不同，基于策略的更新方式是根據狀態St輸出的行動概率，由行動概率來計算狀態的價值［35］。在基于策略處理的深度強化學習中，策略梯度的使用非常廣泛。其參數更新方式如下：

通過使用DNN 來逼近策略的方法就是基于策略的更新方式。值函數由于其需要對動作進行采樣，就只能處理離散動作的情況，而基于策略的算法則是直接利用整體策略對動作進行選擇，因而可以用于處理連續動作空間的情況?，F在最先進的深度強化學習研究都是以值函數與策略更新方式二者結合方式進行，將兩種更新方式中的優良思想融合，也能獲得很好的效果?；诓呗缘纳疃葟娀瘜W習可以從基于深度確定性策略梯度［36］（Deterministic Policy Gradi?ent，DPG），行動者-評論家［37］（Actor-Critic，AC）以及策略優化［38］（Policy Optimization，PO）三個角度來進行改進。

3.1.1 AC框架和確定性策略梯度方法

單獨使用價值更新的方式在AC 框架中被稱為Critic-only 方法，完全依賴于價值函數近似，旨在學習貝爾曼方程的近似解，然后有望制定一個接近最優的策略，但在結果策略的接近最優性方面缺乏可靠的保證。而單獨使用基于策略更新的方式在AC 框架中被稱為Actor-only 方法，存在的問題主要是學習效率低下、環境探索度不高［39］。結合兩者的優點就提出了Actor-Critic 算法，訓練時可以交替更新參數，一定程度上提高了算法的性能。但是高樣本復雜性和對超參數的脆弱性仍然未能解決。Haarnoja等［40］推出了基于最大熵RL 框架的軟策略Actor-Critic 算法（Soft Actor-Critic，SAC）。能夠提供樣本高效學習，同時保留熵最大化和穩定性的優勢，使用軟策略迭代收斂到最優策略。Za?havy 等［41］提出自調整AC 算法（Self-Tuning Actor-Critic，STAC）。通過元梯度下降自動在線調整超參數，并使用一種新的V-trace 算子來改進離策略學習。當應用于Arcade 學習環境時，STAC 中將人類標準化分數的中位數從243%提高到364%。Flet-Berliac 等［42］提出了第三個角色：對手。并形成了對抗性引導下的AC 算法（Adversarially Guided Actor-Critic，AGAC），使行動者行為在獎勵極為罕見的任務中具有創新性。實驗分析表明，由此產生的對抗性引AGAC算法會導致更詳盡的探索。在異步學習方式上，Babaeizadeh 等［43］使用異步優化方式稱為Asynchronous Advantage Actor-Critic（A3C）的新型輕量級并行方法，在許多游戲任務上實現了最先進的結果。當使用適當的學習率時，A3C從原始屏幕輸入中學習玩Atari 游戲比以前的方法更快、更有效。

確定性策略梯度算法是由Silver 等［44］在AC架構上提出的，可以從探索性行為策略中學習確定性目標策略?；舅枷胧峭ㄟ^參數概率分布來表示策略。根據參數向量θ隨機選擇狀態s中的動作a。策略梯度算法通常通過對該隨機策略進行采樣并朝著更大累積獎勵的方向調整策略參數來進行。深度確定性策略梯度算法（De?terministic Policy Gradient，DDPG）［45］是由確定性策略梯度算法演變而來的，適合于連續控制的場景，在AC 架構基礎上，同時又結合了DQN，使之具有深度的特點。此算法只需要一個簡單的actor-critic 架構和學習算法，幾乎沒有“移動部件”，使其易于實現和擴展到更困難的問題和更大的網絡。

和其他DRL 方法一樣，高估偏差和大量的訓練時間是制約DDPG 算法應用的主要瓶頸。為了克服Actor-Critic 中的高估現象，雙延遲深度確定性（Twin Delayed DDPG，TD3）策略梯度算法［46］應用了一對critic 函數進行值估計，并在這兩個估計之間取最小值進行目標更新。這種最小化操作可以有效緩解連續控制設置中的高估現象，但可能會在每次更新迭代時造成低估偏差，對此有一個簡單的解決方案，即批量約束深度Q 學習（BCQ）［47］，用于限制TD3 中的低估現象。為了平衡高估和低估的現象，Wu等［48］提出了三元平均深度確定性策略梯度算法（Triplet-Average Deep Deterministic Policy Gradi?ent，TADDPG）。算法采用三元批評者的加權動作值和平均Q 值方法來進行穩健的目標更新，此方法在OpenAI gym 的幾個控制任務上實現了比原始方法更好的性能。對于深度確定性策略梯度算法也有很多其他的改進，Dirichlet DDPG（D3PG）是Ale 等［49］提出的基于DDPG 的算法，這樣就能夠解決連續動作空間并滿足移動邊緣計算（Mobile Edge Computing，MEC）任務劃分的約束。為了滿足動作空間約束，使用了Dirich?let distribution（狄利克雷分布）來捕獲受限動作。另一種D3PG（Decomposed Deep Deterministic Policy Gradient，分解的深度確定性策略梯度）的算法是由Dong等［50］提出的，是DDPG的多代理擴展，將全局評論家分解為局部評論家的加權和，提出了一種在學習過程中學習權重的方法，以捕獲智能體之間不同級別的依賴關系，另一個優點是它能夠提供對最終學習策略的明確解釋以及學習機器人關節之間的潛在依賴關系。關于DDPG改進的另一個方案是分布式深度確定性策略梯度算法［51］（Distributed Distributional Deep Determinis?tic Policy Gradient，D4PG）。使用ApeX 框架［52］大大節省了困難控制任務的掛鐘（wall-clock）時間。算法實現了分布式評論家更新、分布式并行參與者的使用、N 步返回（N-step returns）和優先經驗回放。該算法在各種控制任務硬操作和運動任務（Hard Manipulation and Locomotion Tasks）中獲得了最先進的性能。

3.1.2 策略優化方法

在強化學習策略優化方法中，更新過程中適當的步長對訓練效率有著很大的影響。信任域方法是一類流行的算法，其中包括信任區域策略優化（TRPO）和近端策略優化（PPO）。在這些方法中，需要迭代地最小化兩項內容：目標函數的線性化以及限制兩個連續更新到彼此互相接近的臨近項，例如Mirror Descent（MD）［53］?；诖?，Schulman 等［54］提出了信賴域策略優化（Trust Region Policy Optimization，TRPO）算法，分析了優化隨機控制策略的信任域方法，該算法使用KL 散度懲罰反復優化策略的預期成本的局部近似值。實驗證明，其算法在神經網絡上的優化是非常有效的，并且具有可擴展性，此算法可以讓由各種關節組成的類人智能體學習跳躍、行動等復雜策略。在使用策略優化方法進行模型優化時，傾向于利用沒有足夠數據來訓練模型的區域，導致訓練不穩定，這也被稱為模型偏差。Kurutach 等［55］分析了基于vanilla模型的強化學習方法的行為，為了解決上述問題，使用模型集合來保持模型的不確定性并規范學習過程，并提出了模型集成信任域策略優化（Model-Ensemble Trust-Region Policy Optimi?zation，ME-TRPO）算法，與連續控制基準任務的無模型深度RL 方法相比，顯著降低了樣本復雜度。Kamyar 等［56］提出了廣義信任區域策略優化（Generalized Trust Region Policy Optimization，GTRPO），將模型假設放寬到回合設置和具有無記憶策略的部分可觀察模型。算法上，使用Q函數的變體，使得計算效率很高。GTRPO 中的策略更新提高了預期的累積回報，并且GTRPO保證能夠收斂。Li 等［57］將信任區域策略優化（TRPO）擴展到多智能體強化學習（MARL）問題。轉化為多智能體案例的分布式共識優化問題。通過對共識優化模型進行一系列近似，提出了一種去中心化的MARL 算法，稱之為多智能體TRPO（MATRPO）算法，可以基于局部觀測和個體獎勵來優化分布式策略。實驗證明了它在復雜的MARL任務上的強大性能。

信任域方法的另一種策略梯度方法是近端策略優化類型方法?；A算法由Schulman 等［58］提出，使用隨機梯度上升優化“代理”目標函數。提出了一種新的目標函數，可實現小批量更新的多個訓練次數，稱之為鄰近策略優化（Proximal Policy Optimization，PPO）。此算法具有信任區域策略優化（TRPO）的一些優點，但它們實現起來更簡單、更通用，并且具有更好的樣本復雜度（根據經驗）。在模擬機器人運動和Atari 游戲的實驗上，表明PPO 優于其他在線策略梯度方法，并且總體上在樣本復雜性、簡單性和掛鐘時間之間取得了良好的平衡。Zou等［59］提出了一種適度的強化學習策略更新方法，基于最大熵框架建立了分離的信任區域并進行優化，稱之為策略均值和方差分離信任方法（Sepa?rated Trust Region for policy Mean and Variance，STRMV），是對鄰近策略優化（PPO）的擴展，但它對策略更新更溫和，對探索更活躍。實驗表明，STRMV 優于以前最先進的on-policy 方法，不僅獲得了更高的獎勵，而且提高了樣本效率。針對近端策略優化（PPO）容易出現探索不足的風險，導致訓練失敗或陷入糟糕的局部最優。Wang 等［60］提出了信任區域引導PPO（Trust Region-Guided PPO，TRGPPO），它可以自適應地調整信任區域內的裁剪范圍。方法不僅提高了信任區域內的探索能力，而且具有更好的性能界限。表1展示了各算法的總結。

表1 深度強化學習模型改進總結

續表1

3.2 基于策略更新方式在智能路徑規劃中的應用

Lakshmanan 等［61］提出了一個完整的覆蓋路徑規劃（CCPP）模型，基于Tetromino 的可重構機器人平臺hTetro，使用經驗回放的Actor Critic（ACER）強化學習算法訓練具有長短期記憶（LSTM）層的卷積神經網絡（CNN）。該模型還與基于旅行商問題（TSP）的遺傳算法（GA）和蟻群優化（ACO）方案進行了比較。所提出的方案生成了一條成本較低的路徑，需要較少的時間來生成。該模型也非常健壯，可以在任何預訓練的環境中生成路徑。

近年來，對于多智能體的協同控制以及多智能體強化學習的研究也是強化學習研究的熱點之一，Qie 等［62］針對無人機協同控制系統中多無人機目標分配與路徑規劃（MUTAPP）問題，提出了一種基于多智能體深度確定性策略梯度（MADDPG）算法，被稱為同步目標分配和路徑規劃（STAPP），由于系統中使用的神經網絡簡單，因此可以保證實時性能。Sunehag 等［63］、Iqbal等［64］從多機器人協作控制方面進行了研究，都取得了比較好的效果。

4 結語

本文主要關注深度強化學習的兩種基本類型，以及兩者結合的算法的發展歷程。關注移動機器人路徑規劃這一場景，雖然現在深度強化學習的模型較為豐富，各種改進方法層出不窮，但是其效果主要是在視頻游戲平臺、機械臂仿真等仿真環境，在實際應用上，還是未能完全替代已經成熟的路徑規劃算法。這主要是因為深度強化學習的特點，需要大量的樣本來進行學習，而實際環境空間過大，也會有無法快速探索的問題，這就在效率方面對算法應用提出了要求。

未來在深度強化學習算法落地上還是有不小的挑戰，需要在環境、智能體、狀態、動作空間、深度網絡結構、迭代方式上進行改進，并且在算法的選擇上還需要慎重，每種算法的特點各不相同，適用領域也有區別，在算法落地方面也需要進行不同程度的改進，以適應場景。未來對DRL 的研究也可以從多學科合作開展，在移動機器人傳感器、運動學與自動控制理論上的分析研究等也可以減輕DRL 應用上的困難，讓DRL向著更智能、更實用的方向發展。