結合LSTM的強化學習動態環境路徑規劃算法

武 曲，張 義，郭 坤，王 璽

(青島理工大學 信息與控制工程學院，山東 青島 266520)

1 引 言

路徑規劃是人工智能領域的一個重要研究方向，在各個領域得到了廣泛的應用.迄今已經有許多經典的路徑規劃算法被提出.

Dijkstra算法是一種很早就被提出的路徑規劃算法[1]，它將環境抽象為一個圖問題，利用廣度優先搜索策略遍歷圖，直到找到最短路徑.A*算法是Dijkstra算法[2]的改進.在原有算法的基礎上增加了啟發式函數，并定義了一種當區域與擴展點之間的一種度量作為擴展優先級，在進行路徑擴展時會優先擴展優先級高的節點.但當該方法用于處理多維復雜問題時，無論是把環境抽象為圖模型還是對圖模型求解都將變得很復雜.勢場法[3]把規劃空間看作物理學中的場，把智能體看作一種粒子.障礙物對粒子產生排斥力，目標對粒子產生引力.兩者的合力即為智能體的最終運動的方向.這種方法實時性較好，產生的路徑通常十分平滑，適合于機械臂一類的應用，缺點是在合力為0的位置智能體容易陷入局部最優解.

近年來，隨機人工智能的興起，很多基于人工智能的路徑規劃方法被提出，Chen等[4]提出了一種雙向神經網絡來解決未知環境下的路徑規劃問題.Wu等[5]將路徑規劃任務轉化為環境分類任務，使用CNN來進行路徑規劃.Yu等[6]提出了一種基于神經網絡的魯棒控制方案，并結合自適應補償器和自適應控制增益來實現具有避障能力的編隊控制.

強化學習是一類應用在未知環境的算法，作為機器學習的3大分支之一，不同于監督學習和無監督學習，強化學習無需提供數據，所有的學習資料都將從環境中獲取.智能體通過不斷的探索環境，根據不同的動作產生的不同的反饋進行模型的學習，最終智能體將能以最優策略在指定環境中完成任務.

自V. Mnih等提出DQN[7]以來，深度強化學習不斷取得突破性進展，也有一些研究者嘗試通過深度強化學習解決路徑規劃問題.Piotr Mirowski等[8]以多模態感知信息作為輸入，通過強化學習進行決策來完成網格空間中的導航任務.Panov等[9]使用神經Q-Learning算法來完成網格環境下的路徑規劃任務.Lei等[10]采用CNN和DDQN進行動態環境下的路徑規劃.Lv 等[11]提出了一種改進的基于DQN的學習策略，在學習的初始階段，創建一個體驗價值評價網絡，當發生路徑漫游現象時，利用并行探索結構考慮對漫游點之外的其他點的探索，提高體驗池的廣度.

盡管上述方法在各自的領域都取得了不錯的效果，但是他們實現路徑規劃仍存在一些不足之處.他們大多數只是在靜態環境中進行路徑規劃，缺乏處理動態場景的能力；動作空間或狀態空間是離散的，這與連續的現實環境是不符合的，而且在某些情況下，離散動作得出的最優解還可以被連續動作進一步優化；上述方法實現的路徑規劃多是從固定起點到固定終點的路徑規劃，這相當于模型只學習到了一個局部最優解，并不能完成整個環境的路徑規劃，這對指導現實應用具有很大的局限性.

為了實現全局動態環境下的路徑規劃任務，本文提出了一種結合了LSTM的路徑規劃算法.本文算法以環境圖像作為輸入,通過預訓練的自動編碼器進行降維提取特征.在訓練模型時，以連續4幀圖片降維后的特征信息作為輸入，通過LSTM構建的DDPG模型進行路徑規劃，利用LSTM處理時序數據的特性，實現了在動作選擇時進行有預測的規避環境中的危險區域的動態路徑規劃.

2 相關工作

2.1 自動編碼器

自動編碼器(Autoencoder)可以看做是利用深度學習的對數據進行降維的一種方式，通過一系列的神經網絡計算將高維數據壓縮到低維，再以對稱的方式將數據復原，其結構圖如圖1所示.

圖1 自動編碼器Fig.1 Autoencoder

當編碼器模型收斂后即可認為中間的低維數據為壓縮后的降維數據，再對低維數據進行其他操作，即可在保證達到與原數據相同效果的同時，亦能極大地降低操作過程的復雜度.

2.2 LSTM

循環神經網絡(Recurrent Neural Network，RNN)是一種處理時序數據的神經網絡，RNN以一條時序數據為輸入，其結構單元如圖2(a)所示，在一個計算單元的計算中，輸入部分除當前時刻數據xt之外，還有一項ht-1，該數據是由之前的t-1個時刻的數據傳導計算而得，同樣地，RNN在t時刻的輸出，除了yt之外，還會生成一項ht，而ht則是包含了前t個時刻的信息，ht將被傳送到t+1時刻參與到t+1時刻的輸出的計算過程中.

RNN的這種結構設計，使得RNN網絡具有了預測的能力.但是，在經典的RNN網絡中，隱藏單元ht所攜帶的信息是所有前t個時刻的信息，這樣的結構產生了兩個問題：有些前序時刻信息對當前時刻的輸出而言并沒有價值，參與到當前時刻輸出的計算過程中反而會造成誤差；大量的前序信息參與當前時刻輸出的處理過程將增加計算的負擔，該問題在序列較長時將會變得尤為突出.

長短期記憶(Long Short-Term Memory,LSTM)是一種改進的RNN，該網絡結構在產生當前時刻的輸出時又增加了一項遺忘門的設計，通過一個狀態參量c來實現遺忘功能，LSTM的結構但愿如圖2(b)所示.

圖2 RNN結構單元Fig.2 RNN unit

在LSTM的當前時刻，計算單元首先通過xt和ht-1計算出一個中間結果，而后通過狀態參量ct-1參與構建的遺忘門進行選擇，最終輸出yt、ht以及ct.LSTM的設計方式以一種更有效的方式利用了前序信息，同時也減少了中間過程攜帶的數據量，相對于經典RNN具有更好的效果.

2.3 DDPG

2.3.1 馬爾科夫決策

強化學習過程普遍遵循馬爾科夫決策過程( Markov Decision Process,MDP ).MDP由一個的四元組組成，其中S(State)為狀態空間，表示智能體在環境中可能存在的狀態描述的集合.A(Action)為動作空間，表示智能體在環境中可能采取的動作描述的集合.P(Policy)為轉移策略，處在某個狀態的智能體將依P進行動作選擇，進而從一個狀態轉移到另一個狀態.R(Reward)為回報，表示智能體在某個狀態下采取某個動作而從環境中獲得的回報值.強化學習的目標即為一個求取最佳策略P，在環境中進行執行一系列的動作，使智能體以最佳的回合回報完成給定任務.

2.3.2 Actor-Critic

Actor-Critic[12]是Vijay R. Konda和John N. Tsitsiklis提出的一種應用在馬爾科夫決策過程中的算法，該算法由兩部分構成，用來生成決策動作了Actor部分和用來對動作進行評價的Critic部分，Actor是動作生成器，以當前狀態作為輸入，輸出一個當前狀態下的要執行的動作.Critic則是一個評價器，即值函數生成器，以當前狀態和Actor生成的動作為輸入，生成一個價值量，該量用以衡量Actor生成的動作的優劣.

在訓練過程中，模型按式(1)所示對探索過程中產生的數據進行處理.

(1)

使Critic模型學會為Actor生成的動作進行評估，Actor則向著Critic評價高的方向學習.

2.3.3 Policy Grident

策略梯度(Policy Grident，PG)是由Richard S. Sutton等人提出的一種獨立與價值函數的、根據期望回報進行策略更新的強化學習方式[13]，PG采用回合更新的方式，在得到一條完成回合序列之后，對于序列中的狀態的值函數定義如式(3)所示.

(2)

多個回合后，st的值應表示為多個回合的期望值，其定義如式(3)所示.

(3)

在PG方法中，策略π按式(4)所示進行參數更新.

θ←θ+α▽θlogπθ(st,at)Vt

(4)

2.3.4 DQN

深度Q網絡(Deep Q Network，DQN)是深度強化學習的一個重要算法，它通過神經網絡來構造狀態價值函數，直接生成Q值，解決了傳統Q-Learning方法維度受限、無法處理未參與訓練的狀態數據的問題；通過off policy的策略解決了強化學習數據的強相關性導致的很難應用深度學習方法處理的問題.DQN由兩個結構相同，時間差分的網絡構成，通過式(5)所示的算法進行網絡參數的更新，由DQN開始，圍繞深度強化學習不斷涌現出許多優秀的研究成果.

(5)

2.3.5 DDPG

DDPG[14](Deep Deterministic Policy Gradient)算法結合了AC、PG、DQN中的諸多特點，率先將深度強化學習擴展到連續空間領域.DDPG整體采用Actor-Critic的框架結構，DDPG中的Actor和Critic兩部分都由神經網絡來構建，兩部分的網絡各自采用DQN的設計思路，分別為是兩個時間差分的網絡.在Critic更新時，采用策略梯度的更新方式、與傳統的策略梯度不同的是，DDPG采用一種確定性策略進行動作選擇.

3 結合LSTM的強化學習動態環境路徑規劃算法

在很多路徑規劃研究中，通常為智能體設置掃描射線，以此來觀察周圍的環境，智能體需要對當前周圍的不同類型的實體進行掃描，然后構建包含到這些物體距離的向量，提供給模型進行動作選擇.使用掃描射線的方式雖然可以盡可能的使得智能體獲取周圍的信息，但是仍然不可避免地會信息遺漏，針對這種情況，本文采用圖像為模型提供輸入.圖像雖然極大地保留了環境的真實數據，但是同樣存在著維度過大，模型難收斂的問題.自動編碼器是一種采用深度學習對數據進行降維的方式，本文在處理圖像數據時，首先采用預訓練的編碼器對圖像數據進行了降維.

3.1 預訓練圖像編碼器

為了降低高維圖像對模型收斂增加的復雜度問題，本文設計了圖像編碼器對圖像數據進行特征降維，本文構建的圖像編碼器結構如圖3所示.

圖3 LSTM DDPG結構圖Fig.3 Structure of LSTM DDPG

編碼器首先對圖片進行預處理，包括通過常規方法降低圖片尺寸和灰度化，然后對得到的灰色圖片進行編碼和解碼過程，通過解碼后的圖像與編碼器的圖像的差值作為損失來擬合編碼器的參數.表1所示為本文設計的編碼器參數表，本文編碼器由5層組成，前2層為編碼部分，后3層為解碼部分.

表1 編碼器參數Table 1 Parameters of autoencoder

3.2 結合LSTM的DDPG

本文算法的主要目標是更好的避開動態危險區域，根據到動態危險區域的距離來進行規避誠然是一種可行方式，但是這種被動的響應方式對整體的路徑規劃是不利的，它仍然避免不了智能體需要探索對應區域才能進行規避，這造成規劃路線上增加了一些額外的長度.如果模型能預測環境的變化趨勢，就可以避開某些未來不能通過的區域，避免一些沒有結果的探索工作，直接規劃出一條最佳的可行路徑.本文利用

了循環神經網絡實現了這一設想，循環神經網絡是一種用來處理時序數據的神經網絡，會結合前序信息來生成當前時刻的輸出，當前時刻的輸出參考了之前時刻信息的變化趨勢，所以循環神經網絡是一種具有預測功能的網絡.LSTM的RNN的一種改進，解決了經典RNN無差別攜帶前序信息帶來的弊端.DDPG是一個在連續動作上有很好表現的強化學習算法，本文將LSTM融合到DDPG的框架中，構建了如圖3所示的LSTM-DDPG算法.

其中Actor網絡由3層構成，分別是兩層LSTM和1層全連接層，對于LSTM設置input size為400，隱藏層單元為64，之后接一個全連接層以64維數據為輸入計算生成2維的動作輸出.Critic網絡首先對輸入的環境數據和動作數據做分別處理，其中環境數據利用LSTM進行處理，網絡設置與Actor中的LSTM部分設置相同；對于Actor產生的Action，用一個全連接層將2維輸入映射到20維；然后將上面兩步的輸出拼接一個向量傳遞給下一層的全連接層，由這個全連接層計算生成對Action的評價Q值.

3.3 動作空間

本文模擬人類的動作行為方式設計了智能體的動作空間，采用連續的動作空間設計，將動作空間設計為兩個維度(δ,l)，其中δ表示智能體的轉動角度，取值范圍設定為(-180，180)，其中當δ<0時，智能體向左轉動相應角度，當δ>0時，智能體向右轉動相應角度.l表示智能體執行動作的位移大小，取值范圍為(-0.7，0.7)，其中l<0當時，表示智能體后退相應距離，l>0時，表示智能體前進相應距離.

3.4 環境回報

在強化學習中，智能體通過在環境獲得的累計回報來修正策略函數的參數，因此，環境回報的設定對策略函數能否收斂到理想的狀態而言至關重要.為了驗證本文方法處理動態環境的能力，本文除了設計墻體這種單純的靜態障礙之外，還設計一種危險區域，智能體接觸該區域即死亡，回合結束，視為一次失敗的路徑規劃.結合現實經驗和多次試驗結果作為參考，本文進行了以下環境回報的設定.

3.4.1 決策回報

在一條路徑生成的過程中，智能體通過一系列的動作選擇在不同狀態間切換，為了能保證智能體能以最少的狀態切換次數即為了使智能體盡可能規劃出一條更短的路徑，智能體每執行一步動作，為智能體設置-1的回報，即rstep=1.

3.4.2 碰壁回報

本文在環境中設置了墻體，用來圈圍邊界和構建智能體前進的障礙.對于智能體而言“撞墻”的行為是無意義的，不但增加了動作執行次數，也不會增加位移，因此對于智能體撞墻這種行為應該給予一定的負回報，在本文中設置rwall=-1.

3.4.3 遇險回報

本文設置了動態變化的危險區域來對提出的算法進行驗證，該區域設置在智能體和目標位置之間，其體積會隨著時間動態變化，對于智能體而言該區域的效果為在智能體接觸到該區域時，智能體即死亡，回合結束，路徑規劃任務失敗，因此應該對涉足該區域的智能體以最低的回報來使智能體遠離該區域，在本文中設置rdanger=-50.

3.4.4 目標回報

目標區域是路徑規劃任務的最終目標，應該給予其全局最大的回報，引導智能體向著最終目標進行路徑規劃.在本文中設置rtarget=200.

綜上，設置環境回報如式(6)所示.

(6)

4 實驗及結果分析

本文通過Unity-3D引擎構進行了強化學習環境的搭建，實驗所用的軟硬件配置如下：CPU i7-8750H，內存24G，顯卡GTX1060，顯存6G，軟件環境Unity2019.4.2f1，深度學習框架使用Pytorch.

4.1 實驗環境搭建

在Unity工具中構建如圖4所示的環境.

圖4 實驗環境 Fig.4 Experimental environment

該環境由面積為40×20矩形區域構成，在地面平面建立坐標系，以矩形區域中點為坐標原點，分別以向右和向上為x軸，y軸的正方向.其中中部較小的圓形個體為智能體，半徑為0.5，在每個回合訓練開始時智能體將會隨機生成在環境中的任意位置.兩處黑色圓形區域為危險區域，智能體碰撞到該區域即死亡，回合結束.該區域為動態變化區域，兩處危險區域各自由初始半徑為0.5的規格隨智能體決策次數的增加而擴大，其半徑依0.3單位/次的速度增加，此處之所以設置危險區域依智能體決策次而變化，是因為執行一個回合的具體時間會因計算機處在不同狀態而有所差異，從而造成訓練結果不穩定.左邊危險區域的底面圓心坐標為(-6.5,-1.5)，右邊危險區域的底面圓心坐標為(6,-6).圖中的灰色條形實體為墻體，該區域為靜態障礙.左右兩面邊界墻的中線分別為x=±20.5，上下兩面邊界墻的中線分別為y=±10.5，內部的障礙墻的中心線為x=10，墻的長度為12.圖中右下角的深灰色區域為安全出口，智能體到達此處視為路徑規劃成功的標志.

根據上述設定，隨著智能體決策次數的增加，障礙墻下方的通道將會被危險區域封堵，智能體只能選擇從上方的通道繞行到達終點.另外，為了避免智能體在訓練前期探索環境的階段不停地在環境中往返而不能結束一個回合，設定智能體單個回合的最大步數為200.

4.2 圖形編碼器訓練結果

首先，通過隨機動作的方式令智能體在環境中探索，獲得不同狀態下的環境截圖，為了減小模型訓練的難度，在訓練時將環境地面設置為白色，并為智能體設置添加一個箭頭用來指示方向.截取的原始圖像大小為1200×600.

在本文實驗中，共截取1萬張環境圖像用來訓練編碼器.在正式訓練之前，為了降低模型的處理難度，首先使用OpenCV模塊下的函數將截圖初步降維到200×100， 再對圖片進行灰度化處理，處理后如圖5(a)所示.本文使用小批量梯度下降的方式訓練自動編碼器，設置學習率為0.01，經過1000輪訓練之后，模型趨于收斂.提取訓練好的模型，對一張環境截圖進行編碼解碼過程，得到如圖5所示“編碼-解碼”過程前后的兩張圖片對比，可以看到降維后的數據被比較完整的復原了，說明本文構建額的編碼器成功的完成了圖像數據降維的工作，訓練的編碼器可以應用到后續的任務中.

圖5 “編碼-解碼”過程前后的圖片Fig.5 Images before and after encode-decode

4.3 LSTM DDPG實驗結果

通過上一步的編碼器，環境圖像被壓縮到了400維的大小.通過連續4幀圖像編碼后的數據構成時序數據作為LSTM-DDPG算法的輸入數據.實驗設置Actor學習率為0.001，Critic學習率為0.001，回報衰減設置為0.95，采用小批量梯度下降的方式進行模型訓練，批次大小設置為128；模型收斂后，收集到的訓練過程中的數據變化如圖6所示.

圖6 LSTM DDPG模型訓練數據Fig.6 Training data of LSTM DDPG

其中圖6(a)為Actor部分的損失變化曲線，圖6(b)為Critic部分的損失變化曲線，觀察兩圖可以發現，模型的兩個部分都可以收斂，說明本文設計的模型是合理的，具有可行性.圖6(c)為平均回合步數(/1000步)的變化，圖6(d)為平均回合回報(/1000步)的變化，結合兩圖可以發現，在訓練的前期，算法模型還不能進行正確的路徑規劃，動作選擇多為隨機動作，智能體在環境中執行較多的步數才能結束一個回合，結合圖6(d)可以發現，此時智能體結束一個回合多因為陷入危險區域或達到回合步數上限而結束.在訓練后期，算法模型逐漸收斂，平均回合步數和平均回報都趨于穩定，回報穩定在140上下，回合步數穩定在60步左右，這基本上可以說明智能體可以在不碰到墻壁和危險區域的情況下到達目標位置，進一步說明了本文的算法是可行的.

本文除了通過上述方式驗證了提出算法的可行性，還在相同的環境下，設計了與經典的A*算法、遺傳算法以及文獻[11](Improved DQN)和文獻[14](DDPG)中的深度強化學習方法實現效果的對比實驗.對比實驗分別以環境中的3處為起點測試3種算法的路徑規劃能力，這3個點分別是(5,0)、(-10,5)和(-10,-5)，圖7給出了LSTM-DDPG與其他4種算法的規劃路徑結果對比.

*為了避免軌跡被危險區域遮擋，在展示軌跡時將危險區域設定為了初始化狀態，其中(b)和(c)中A*算法產生的路徑在中途停止是因為接觸危險區域而結束.

其中圖7(a)表示以(-10,5)為起點時5種路徑規劃算法所規劃的路徑，圖7(b)表示以(-10,-5)為起點時5種路徑規劃算法所規劃的路徑.表2所示是LSTM-DDPG同其他4種算法進行路徑規劃的相關數據.

表2 LSTM-DDPG與其他算法的路徑規劃對比Table 2 Comparison of LSTM-DDPG with other algorithms in path planning

通過就表2中的數據進行橫向對比，發現本文提出的算法在同等條件下擁有較好的表現.在以離目標點比較近的(0,5)點為起點時，A*算法取得了最好的表現，可以看到 A*算法所規劃的軌跡為直線，是以距離最短，回報值最佳.離散動作的強化學習算法Improved DQN的取得了次之的效果.遺傳算法和DDPG在躲避動態危險時產生了撞墻的動作，LSTM-DDPG算法所規劃的路徑雖然并非最短，但是相對較為平滑，也沒有產生撞墻的行為.在選擇較遠處的點為起點，其中與目標之間的環境更復雜時，A*算法的表現不佳，不能完成路徑規劃任務，這是因為A*算法在進行路徑規劃時只能以初始環境為參考進行規劃，可以看出A*算法缺乏處理動態環境的能力.同樣是離散動作的強化學習算法Improved DQN雖然完成了路徑規劃，但是在面對危險區域時沒有預測能力，又因為可供選擇的動作有限，規劃出的路徑不如連續動作的算法所規劃的路徑效果好.在連續動作的算法中，相較于遺傳算法和DDPG，可以看到本文算法生成的軌跡更加平滑，路徑更短，回報更高，這是因為遺傳算法和DDPG雖然具有處理動態環境的能力，但是也只是被動的應對變化的環境，規劃的路徑中增加了對某些區域的探索.而本文的算法具有預測環境變化的能力，該特性在圖7(b)有較為明顯的體現，可以看到其他算法會向右下方的通道進行探索，本文算法則預測到了右下方的通道將會被封堵，直接選擇從右上方通過到達目標地點，減少了探索過程的路徑長度，使規劃的總路徑最短.綜上，本文的算法在動態路徑規劃任務中能夠取得較好的表現.

5 總 結

本文針對傳統的路徑規劃算法多基于靜態環境；缺乏對動態環境的處理能力的問題，提出了一種結合LSTM的強化學習路徑規劃算法.本文的方法以環境圖像作為輸入，首先構造了能夠壓縮圖像特征的編碼器，在盡可能完整地保留環境圖像原始信息的前提下，降低圖像的特征維度，進而從整體上降低了路徑規劃任務的復雜程度.本文基于在連續動作空間上具有良好表現的DDPG算法，在DDPG算法中結合了LSTM結構，利用LSTM能夠處理時序數據的特性，使其在生成動作時能夠有選擇的參考之前時刻的信息，做出基于對環境預測的動作輸出，預先規避環境中可能發生的危險.最后通過實驗與經典路徑規劃算法和其他強化學習算法進行性能對比，證明了本文算法對動態環境的預測能力以及路徑規劃的高效性.