基于強化學習的移動機器人路徑規劃研究綜述

劉志榮，姜樹海

（1.南京林業大學 機械電子工程學院，南京 210037；2.南京林業大學 智能控制與機器人技術研究所，南京 210037）

0 引言

隨著電子信息技術，計算機技術以及機械制造技術不斷成熟，移動機器人正往著高度智能化方向邁進。智能機器人的一個重要特征就是在復雜動態環境下能夠進行良好的路徑規劃。所謂的路徑規劃就是指機器人根據各種傳感器對周圍環境進行感知，自主搜索出一條從起始點到目標點的無碰撞路徑。路徑規劃的核心是算法的設計，路徑規劃算法根據智能化程度可分為傳統算法、啟發式算法、智能算法、強化學習算法四類。

傳統算法可分為可視圖法、人工勢場法[1]、模擬退火法[2]和模糊邏輯算法[3]。傳統算法缺乏靈活、易于陷入局部最優值。啟發式算法是具有搜索能力的算法，該類算法在離散路徑拓撲中具有很好地運用[4]。智能算法是人們通過仿生學研究發現的算法。常用的智能算法有神經網絡算法、遺傳算法、群智能算法。

以上介紹的算法都是基于樣本的監督學習算法，監督學習算法的固有屬性使得機器人先驗知識不足時很難進行良好的路徑規劃。強化學習又稱再勵學習，是由美國學者Minsky[5]于1954年提出的仿生算法。該算法通過機器人與環境進行不斷試錯迭代獲取反饋信息來優化策略。它不依賴環境模型以及先驗知識，又具有自主學習和在線學習的特點，逐漸成為機器人在非結構環境下路徑規劃的研究熱點[6,7]。論文將對RL的研究現狀以及發展變化進行綜述，整體框架圖如圖1所示。

圖1 本文的整體框架

1 強化學習基礎

強化學習的基本要素包含策略、值函數、獎賞函數、環境模型[8]。根據求解方法不同，強化學習算法分為值函數法和直接策略搜索法。值函數法根據狀態轉移概率是否已知分為基于模型的強化學習算法和與模型無關強化學習算法兩類。前者利用已經獲得的學習經驗構建環境模型學習值函數來獲得策略，常用的基于模型的強化學習算法有DP、Dyna-Q、DDP算法。與模型無關的強化學習算法通過機器人與環境之間反復交互直接學習值函數來得到相應的策略。典型的與模型無關的強化學習算法包括Q-learning、Monte Carlo、TD、Sarsa。直接策略搜索法不考慮值函數，而是把策略參數化，直接尋找一個最優的決策。

強化學習以其模仿動物的思維方式進行學習，增加了系統的智能性，但以下三個問題使得基于強化學習的機器人在復雜動態環境下的路徑規劃無法滿足實際應用。一是在大規模狀態空間和動作空間情況下，算法對每個狀態和動作進行無限次重復訓練，將會導致維數災難[9]，二是機器人在執行完動作后，所獲得的回報函數值往往不是即時的，這很難滿足機器人在路徑規劃中實時性的需要，三是強化學習必須在利用和探索之間進行折中，即在已知的信息下進行最優策略選擇和進行新路徑探索之間的折中。接下來的兩章節將分別從值函數法和直接策略搜索法綜述學者們基于改進的強化學習算法在移動機器人的路徑規劃中的應用。

2 值函數法

值函數用來定義當前狀態下機器人選擇策略π的優劣程度。值函數法的目標是通過最大化每個狀態的值函數來得到最優策略。

Q-learning是最典型的基于值函數法求解的強化學習算法，由Watkins[10]在1989年提出。Q-learning算法無需知道模型就可以保證收斂，是目前應用于機器人路徑規劃中最有效的強化學習算法。Q-learning改進算法種類繁多，找其共性進行歸類，主要有以下五個角度。

1）將Dyna學習框架加入到Q-learning中。該算法利用少許真實數據建立環境模型，采用虛擬樣本更新值函數，通過增加計算復雜度來降低時間復雜度。Kao-Shing Hwang等[11]結合樹狀結構和Dyna-Q算法構建環境模型來加速算法收斂，他們為Dyna-Q的完善發展做出了有益的研究工作。VIET Hoang-huu等[12]利用Dyna-Q算法解決移動機器人在未知環境中的定位問題，這是Dyna-Q在定位導航中的第一次嘗試。

2）將啟發因子融入Q-learning中。啟發因子往往能增強算法的某個環節，最終獲得更好的效果。Bianchi RAC等[13]提出啟發式加速Q學習算法，即運用啟發因子影響動作選擇。Fengyun Zhang等[14]根據貪婪搜索因子來訓練神經網絡，通過RBF（Radial Basis Function）神經網絡進行權重更新，改進后的算法能夠提高初始先驗知識不足情況下的學習效率。此外，啟發因子還能緩解強化學習的延時回報問題[15]。

3）與其他算法進行融合。單一算法在解決特定問題上往往有比較好的表現，而機器人在復雜環境下的路徑規劃問題是一個NP難題，因此融合不同算法的優點成為學者們的研究熱點。Ni Jianjun等[16]在Q學習基礎上通過神經網絡來估計難以獲得的狀態，為群體機器人路徑規劃提供了一個解決方案。另外，動態障礙物的路徑軌跡也取得了發展，Mihai Duguleana等[17]在已知全局信息基礎上，通過Q-learning和神經網絡融合算法可以在動態和靜態障礙物并存的環境中獲得無碰撞地軌跡。Khanduja等[18]為群機器人的路徑規劃的發展做了有益的工作。

4）將分層思想引入到Q-learning中。分層強化學習算法[19]將原來的整個任務分解成一些彼此獨立的子任務進行學習，加快學習速率。很多學者基于這一思想對Q學習進行了研究。Buitrago等[20]提出了基于選擇的分層學習方法，在第一層里利用Q-learning算法分別訓練運動的基本行為，在第二層里協調這些基本行為來解決規劃的任務，仿真結果表明該算法能夠很好地應用于未知環境的路徑規劃。

5）將深度學習框架融入Q-learning算法中。深度強化學習算法是近幾年在深度學習發展的基礎上而興起的新的算法，該算法將深度學習的感知能力和強化學習的決策能力進行了有機統一，是一種更接近人類思維方式的人工智能方法，可以有效解決維數災難問題。Lei Tai等[21]利用深度強化學習實現了移動機器人在復雜環境下的導航。之后他們[22]通過深度強化學習以視覺傳感器為平臺，以RGB-D圖片為輸入信息，直接輸出機器人的控制動作，該思想將強化學習算法上升到了新的高度。Linhai Xie等[23]利用單眼RGB視覺傳感器，構建雙層強化學習網絡結構就能獲得很好的避障效果，為路徑規劃的實現打下了很好的基礎。Yu Fan Chen等[24]利用深度強化學習實現了機器人小車在行人密集的環境中自動導航的任務。

3 直接策略搜索法

直接策略搜索法將策略參數化，通過梯度上升思想來尋找最優參數。直接策略搜索算法包括模仿學習、策略梯度方法和基于演化算法的強化學習[25]。在機器人路徑規劃上主要使用前兩種算法。

模仿學習[26]是從人類社會的教學過程中受到啟發，通過引入“導師”來解決問題的一種方法。模仿學習分為逆向強化學習和直接策略學習兩大類，前者先從示范數據中學習獎賞函數，然后基于此通過RL算法學習最優策略。論文[27]中，機器人從給定的數據庫中學習獎賞函數獲得最優策略。后者直接從示范數據中學習從狀態到動作的映射函數。Hazara M等[28]讓機器人從人類示范動作中挑選出最合適的動作。

策略梯度方法[29]是通過梯度上升思想，最大化累積期望獎賞來優化帶參策略。策略梯度避免了基于值函數的方法帶來的策略退化[30]現象。Kober J等[31]通過優化策略參數來獲得最優參數。

相比于值函數法，策略搜索的方法容易收斂到局部最小值，此外，機器人進行路徑規劃中的動作空間一般都是離散動作，策略搜索的優越性并不能體現出來，因此策略搜索方法在機器人的路徑規劃中應用較少。

4 結束語

強化學習無需任何的環境先驗知識，在經過反復試錯后就能進行良好的路徑規劃，這將使得其在動態環境下的路徑規劃具有更加廣泛的應用。從移動機器人路徑規劃的研究現狀以及發展需求來看，未來移動機器人的路徑規劃研究主要集中在以下三個方面。

1）更廣義的路徑規劃。傳統機器人的路徑規劃一般以路徑最短為原則，但隨著機器人應用越來越廣泛，路徑規劃的評判標準也越來越多樣化。例如對人流量密集的場所來說，能否遵循社會準則或許是評判機器人路徑規劃好壞的依據。

2）新的路徑規劃方法的研究。隨著現代科技的發展，將會出現新的智能方法，結合現代科技尋找更優越的路徑規劃方法已成為一種趨勢。比如近幾年興起的深度強化學習算法。

3）多機器人多任務路徑規劃的研究。隨著移動機器人應用范圍的不斷擴大，移動機器人的工作環境與任務會更加復雜。需要考慮怎樣將單個機器人的路徑規劃擴展到多機器人的路徑規劃。此外，未來機器人在路徑規劃的同時可能還要執行其他任務。