基于深度強化學習的移動機器人動態路徑規劃算法

張柏鑫，楊毅鑌，朱華中，劉安東，倪洪杰

(浙江工業大學 信息工程學院，杭州 310012)

0 引言

為了豐富全民公共文化服務，特別是滿足基層文化多樣化服務需求，需要在基層小型文化服務綜合體[1]活動空間中開展文化演出、會議議事、展覽閱覽以及民俗活動等文化服務功能。因服務空間不同，其功能空間內的配置設施和使用要求也不同。為了達到小型文化綜合體“一廳多用”要求，往往要通過移動機器人協助完成多種功能空間相互快速組合以及切換，實現小型綜合體空間內擁擠環境下的動態路徑規劃與快速搬運服務等，從而滿足單一空間多種文化服務需求。

路徑規劃[2-3]是移動機器人實現各種功能的基礎，分為全局靜態路徑規劃[4]和局部動態路徑規劃[5]。在舞臺環境這種充滿動態障礙物的環境下對移動機器人的動態路徑規劃算法要求很高。目前的動態路徑規劃算法可以分成兩類：基于反應的避障算法[6]和基于預測的避障算法[7]?；诜磻谋苷纤惴ㄓ腥斯輬龇╗8-9]，通過假設機器人在一種虛擬立場下運動受到障礙物的斥力和目標點的引力，但是在復雜環境下會陷入局部最優解或震蕩。最佳反向碰撞(ORCA)[10-11]通過引入一個時間窗口，將相對位置轉化為速度，給每個動態障礙物都設定速度區間，最后對所有線性空間用線性規劃求出最優解，從而計算出最優路徑。但是會存在抖動問題以及在復雜環境下規劃不流暢的問題。基于反應的算法不能預測其他障礙物的運動趨勢，從整個規劃上來看，有時會產生不自然的軌跡，由于只考慮當前狀態，依賴傳感器快速更新速率對障礙物作出快速反應，所以規劃出來的路徑往往不是最優的。

基于預測的算法有動態窗口法[12-14]和基于深度強化學習的方法[15-18]，動態窗口法是在速度空間中采樣多組速度，并模擬機器人在這些速度下一定時間內的軌跡，得到多組軌跡之后，選取最優軌跡對應的速度來驅動機器人移動?；谏疃葟娀瘜W習的方法將深度學習的感知能力和強化學習的決策能力相結合，可以實現端到端的控制方法。通過傳感器直接獲得周圍的狀態信息，經過網絡處理，輸出動作指令，具有非常好的自適應性，成為路徑規劃領域新的研究熱點。

文獻[19]提出了一種基于深度強化學習的分布式多機器人避障策略(CADRL)，假設動態障礙物會主動避讓機器人，通過值函數網絡對周圍動態障礙物的狀態進行編碼，通過預測障礙物的運動趨勢，來規劃出動態路徑。文獻[20]在文獻[19]的基礎上通過引入雙經驗池來提高算法的收斂速度。文獻[21]提出了LSTM策略，通過引入長短期記憶神經網絡來將動態障礙物的可變大小狀態轉換為固定長度向量，并以與機器人距離相反的順序輸入人類狀態。上述的文獻只考慮單個動態障礙物對機器人的影響，卻沒有考慮多個動態障礙物同時對機器人的影響。文獻[22]提出了社會注意力機制，通過對動態障礙物的運動趨勢分析，來捕獲環境中動態障礙物的相對重要性。文獻[23]提出了SARL策略，使用了一種圖形結構來表示人群，并預測導航任務中的行人注意力得分。文獻[24]直接將原始傳感器數據和目標信息映射到控制命令上。文獻[25]采用漸進式的由易到難的訓練策略，將DQN與遷移學習相結合應用在導航中，提高了收斂網絡收斂速度。文獻[26]利用Delaunay三角剖分對障礙物進行編碼，并結合擴展的混合A*方法，在時間-狀態空間中有效地搜索最優解。

在現實環境下或擁擠的環境中，障礙物類型復雜，不僅存在動態障礙物，還存在靜態障礙物。機器人對不同類型的障礙物處理應該也不相同。針對上述現有技術存在的問題，本文提出一種新的基于深度強化學習的動態路徑規劃算法。主要工作有：

1)將LSTM網絡和社會注意力機制融合建立的新的神經網絡模型來處理動態路徑規劃問題。

2)建立局部地圖和全局地圖來分別處理動靜態障礙物信息，設計新的獎勵函數來針對不同障礙物的情況。

3)針對訓練前期收斂慢的問題，通過模仿學習對網絡參數進行預訓練，引入優先級經驗回放技術來提高網絡的收斂速度。

4)設計不同的障礙物環境來對比不同策略的動態避障效果。

1 基于深度強化學習的動態路徑規劃

如圖1所示，在強化學習框架下，機器人通過與環境的交互來學習動作能夠使其在給定環境中所獲得的累計獎勵最大化。然而機器人僅僅依靠與環境的交互以及動作的獎勵來學習，在復雜環境下的表現往往不是很好。由于深度學習具有強大的感知能力，不僅能夠為強化學習帶來端到端優化的優勢，而且使得強化學習不再受限于低維的空間中，為此引入深度學習來提高系統的感知能力，極大地拓展了強化學習的使用范圍。

圖1 基于深度強化學習的動態路徑規劃流程

1.1 馬爾可夫決策過程

基于強化學習的移動機器人的路徑規劃問題首先需要通過利用馬爾可夫決策過程(MDP，markov decision process)來實現問題的形式化。MDP可以描述為：機器人在某一時刻t下的狀態為St，根據最優策略π*選擇動作at,機器人根據狀態轉移概率P，從當前狀態轉移到下一個狀態S(t+1)，時間間隔為△t然后根據當前狀態得到獎勵rt，再更新狀態值函數：

V*(St)=∑γ△tP(St,at)

(1)

其中：狀態值函數V*(St)是從狀態st出發，按照最優策略π*選取動作后得到的期望回報，機器人不僅要考慮當前的獎勵還要考慮未來的獎勵，所以設置折扣率γ∈ (0,1)。

最優策略則通過最大化累計回報獲得:

V*(uut+△t)dut+△t

(2)

其中：ut表示當前移動機器人和障礙物的聯合狀態，at表示t時刻的動作，γ表示折扣率，△t表示兩個動作之間的時間間隔，V*表示最優值函數，P表示狀態轉移函數，R表示為獎勵函數；模型的好壞主要在于狀態空間S、動作空間A和獎勵空間R的設計。

1.2 狀態空間

動態路徑規劃的狀態空間包含機器人的狀態和動靜態障礙物的狀態，機器人、動態障礙物和靜態障礙物的狀態分別定義為：

Sr=[Px,Py,Gx,Gy,Vx,Vy,θ,r]

(3)

SD=[Px,Py,Vx,Vy,r]

(4)

SS=[Px,Py,r]

(5)

其中：[Px,Py]是物體的當前坐標，[Gx,Gy]是機器人的目標點，[Vx,Vy]是機器人或者動態障礙物的當前時刻的速度，θ是機器人當前時刻的航向角,r是物體膨脹后的半徑。

機器人周圍的障礙物在T時刻內的聯合狀態即為網絡的輸入層：

ut=[Sr,SD,SS]

(6)

1.3 獎勵

機器人在移動過程中需要盡量避免與動態障礙物發生碰撞。由于動態障礙物的不確定性，隨著與動態障礙物距離的減少，發生碰撞的概率就越大，而面對靜態障礙物，隨著距離的靠近并不會增加發生碰撞的概率。所以針對以上情況，設計了如下的獎勵函數。

(7)

其中：Dd，Ds分別為為機器人和動態障礙物和靜態障礙物之間的距離，為了減了機器人和動態障礙物發生碰撞的概率，當機器人靠近動態障礙物0.5米時，即Dd<0.5時，則認為機器人可能會和動態障礙物發生碰撞，隨著距離的減少逐漸增加負獎勵的值，從而降低移動機器人與動態障礙物發生碰撞的概率。而機器人靠近靜態障礙物時，由于靜態障礙物沒有運動趨勢，只要機器人不接觸靜態障礙物就不會發生碰撞，當機器人與靜態障礙物發生碰撞時，即Ds≤0時，給予負的獎勵。從而在動態規劃過程中，實現對動靜態障礙物的不同應對策略。

1.4 動作空間

機器人的動作空間由線速度和角速度組成A=[w,v]，v為線速度w為角速度。為了符合動力學約束，本文將角速度在[0,90]區間內分成15等分，線速度按照函數y=1/x，x取1，2，3，4，5可獲得5個變化平滑的線速度，動作空間共有75種動作組合，其中不同的顏色代表那個區間動作選擇的可能性，如圖2所示。

圖2 動作空間

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

2.1 網絡結構

文獻[19]使用一個淺層的網絡編碼了障礙物信息，缺乏對障礙物信息的處理，本文此基礎上通過引入LSTM網絡[21]來編碼障礙物信息。通過局部地圖和社會注意力機制[22]來提取動態障礙物的特征，預測動態障礙物的運動趨勢，通過全局地圖來避開靜態障礙物，網絡模型具有更強的自適應性以及魯棒性。

如圖3所示，網絡處理流程主要有：首先建立全局地圖獲取機器人和周圍障礙物的狀態，然后通過建立局部地圖，通過LSTM網絡編碼動態障礙物狀態和機器人狀態輸入社會注意力機制網絡，來確定周圍每個動態障礙物的注意力分數，然后通過LSTM網絡處理靜態障礙物的信息，將處理后的狀態輸入全連接層，最后通過激活函數對其進行歸一化處理來得到最優值函數。

圖3 深度神經網絡結構

2.2 網絡輸入模塊

網絡的輸入參數由三部分組成：移動機器人的狀態、動態障礙物的狀態和靜態障礙物的狀態。靜態障礙物的狀態可視為已知信息存儲，通過預先建立環境地圖。動態障礙物的狀態通過局部地圖獲得。本文以機器人為中心將地圖參數化建立二維柵格局部地圖。如圖4所示，機器人位于原點，構造一個L×L× 3 映射張量Mi，來編碼動態障礙物Di的位置和速度信息，張量Mi表示為：

Mi(a,b)=∑j∈Ni?Di

(8)

其中:Di是第i個動態障礙物的狀態信息，(a,b)用來存放坐標信息，? 是一個特征函數來確保障礙物在范圍之內，Ni是周圍所有動態障礙物的狀態信息的集合。

圖4 維柵格局部地圖

2.3 社會注意力機制模塊

社會注意力機制由多個多層感知器(MLP)組成，首先將移動機器人的狀態和動態障礙物的狀態以及映射張量Mi通過MLP編碼到固定長度的向量ei中，然后再將ei送入到下一層MLP中來獲得機器人與動態障礙物之間的交互特征hi，然后再送入下一層MLP中來獲得不同動態障礙物的注意力分數αi，注意力分數代表著動態障礙物與移動機器人發生碰撞的可能性。然后將所有的交互特征通過加權組合來表示所有動態障礙物對移動機器人的下一步動作的整體影響，將聯合狀態和交互特征輸入到MLP來作為最優值函數的估計值。

ei=?e(s,Mi;we)

(9)

hi=Φh(ei;wh)

(10)

(11)

αi=Φα(ei,em;wα)

(12)

(13)

V=fv(s,ss,c;wv)

(14)

其中：?e是激活函數，we是權重，Φh是一個具有ReLU非線性的全連通層，wh是網絡權值。em是所有ei向量的總和，Φα是具有ReLU激活的MLP，wα是權重。fv是具有ReLU激活的MLP，權重用wv表示。s是機器人的狀態，ss是靜態障礙物的狀態。

圖5 社會注意力機制模型

2.4 LSTM模塊

前饋神經網絡需要固定長度的輸入。然而移動機器人在移動的過程中遇到的障礙物的數量不固定，從而導致網絡輸入層的輸入的參數也會發生變化，目前的方法通過設定固定的輸入層參數，當障礙物數量過多或者很少的時候都會影響網絡的性能。長短期記憶網絡可以接收任意長度的序列參數，產生固定長度的輸出，因此本文引入LSTM網絡優化深度強化網絡模型的性能。

LSTM 網絡由其權重{wi,wf,wo}和偏差 {bi,bf,bo}參數化，其中{i,f,o}對應于輸入門、遺忘門和輸出門。如圖6所示，機器人周圍的障礙物按照距離依次送入LSTM單元，每個 LSTM 單元具有3個輸入：障礙物的狀態S、先前的隱藏狀態hi和先前的單元狀態ci。

圖6 LSTM網絡模型

在每個決策步驟中，每個障礙物的狀態依次輸入到LSTM 單元中。 LSTM單元的初始狀態h0,c0為0，然后通過輸入第一個狀態s1生成 {h1,c1}，然后運送到第二個LSTM單元生成 {h2,c2}，從而編碼所有障礙物的狀態信息。在輸出障礙物信息時，可以通過LSTM網絡調整障礙物信息的順序，通過訓練網絡權重參數，通過遺忘門將遠離機器人的障礙物信息遺忘，將靠近機器人的障礙物信息優先放置在最后編碼的向量中。最后通過隱藏狀態hn將機器人周圍障礙物的狀態信息編碼成一個固定長度的向量，并輸送到前饋網絡處。不僅可以解決前饋網絡參數不固定的問題，還可以對障礙物狀態信息進行排序，使移動機器人具有更好的性能。

2.5 模仿學習

網絡訓練初期，由于環境復雜，障礙物多，發生碰撞的概率很大，網絡需要很長時間才能度過探索階段，網絡的初始權重很差，機器人需要很久才能到達目標點。如圖7所示。

圖7 未引入模仿學習和引入模仿學習的回報曲線

左圖是未引入模仿學習的回報函數，總獎勵在很長一段時間內處于負值狀態，而引入模仿學習的總獎勵一直處于正值狀態。所以通過使用模仿學習，對網絡進行一定次數的預訓練來優化網絡權重。由于仿真環境一樣，只是改變機器人使用的避障策略，可以使策略度過探索期，所以通過預訓練的網絡可以提高收斂的速度。

2.6 優先級經驗回放

DQN算法采用了經驗回放機制來解決經驗數據的相關性和非平穩分布的問題，但存在一個問題是其采用均勻采樣和批次更新，導致特別少但價值特別高的經驗沒有被高效的利用。本文采用一種“優先級經驗回放”技術解決采樣問題，從而提高算法的收斂速度。在優先級經驗回放中，通過TD-error來給每一條經驗添加重要性，TD-error是某個時刻動作的值函數和當前網絡的最優值函數的一個差值，差值越大則說明當前的經驗比較差。所以我們定義：

Pt=(|δt|+ε)α(15)

其中：Pt是選擇當前經驗的概率，α、ε為常數，δt為TD-error。

3 實驗驗證

3.1 算法仿真與分析

本節主要對改進后的策略和當前主流策略的動態避障效果進行對比分析。本文的網絡模型在Python中使用Pytorch實現，在GeForce RTX 970 GPU和i7-4790K的電腦上訓練并測試。仿真環境實驗是基于python中的gym庫搭建的，動態障礙物在6X6的正方形邊上隨機生成起點，目標點為對應邊上的一點，半徑大小為0.3的圓，靜態障礙物隨機在環境下隨機位置生成，為半徑為0.5～1.3的圓。動態障礙物通過ORCA策略控制移動，可以避免動態障礙物之間以及和靜態障礙物發生碰撞，其仿真參數如表1所示，通過時間差分法來對網絡模型進行訓練，通過Adam優化器[27]來優化最優值函數，網絡的訓練流程如下所示。

表1 仿真參數

算法1:網絡訓練流程。

步驟1:使用模仿學習對網絡進行預訓練；

步驟2:預訓練結果初始化經驗池；

步驟3:初始化目標網絡參數；

步驟4:開始訓練；

步驟5:隨機生成障礙物位置；

步驟6:是否發生碰撞、到達目標或者超出限制時間；

步驟7:步驟6成立結束當前episode否則執行步驟8；

步驟8:將聯合狀態輸入網絡；

步驟9:根據當前狀態使用最大化獎勵選擇動作；

步驟10:獲得獎勵，更新下一刻狀態；

步驟11:將狀態、動作、獎勵和下一刻狀態存儲到經驗池；

步驟12:使用優先級經驗回放從經驗池里選擇batch；

步驟13:根據batch 優化價值網絡；

步驟14:通過Adam 優化器優化網絡參數；

步驟15:更新目標網絡參數；

步驟16:返回最優值函數。

3.2 仿真結果

本節主要將本文的策略模型與CADRL[19]、LSTM-RL[21]和SARL[23]3種策略模型進行比較，來驗證網絡模型的性能。

圖8(a)比較了不同策略的累計回報曲線，從圖中可以看出我們的模型由于引入優先經驗回放技術，在預訓練的時候就獲得了很好的效果，初始經驗很高，所以收斂速度也是最快的。圖8(b)、(c)和(d)中比較了不同模型到達目標點所花費的時間，以及在仿真過程中的成功率和碰撞率，從圖中可以看出我們的模型在相同起點和終點的條件下到達終點所花費的時間最短、碰撞率較低以及成功率很高。說明引入率LSTM網絡和社會注意力機制后的模型效果表現很好，結合模仿學習以及最優經驗回放后的網絡訓練效果更好，很好的驗證了本文的網絡模型的有效性。

3.3 不同策略的動態路徑規劃圖

由于我們的模型對動態障礙物和靜態障礙物都做了訓練，因此設計了兩組實驗用來做對比實驗。實驗測試了4種策略在500次的實驗下的動態規劃結果。

3.3.1 不存在靜態障礙物

首先在沒有靜態障礙物的環境下對比了不同策略的路徑規劃效果，設定了5個動態障礙物，動態障礙物采用ORCA策略，不會主動避讓移動機器人。

本文的策略通過注意力機制，可以預測動態障礙物的運動趨勢，避免與動態障礙物發生碰撞，當面對多個動態障礙物的時候，通過對障礙物排序可以實現更好的動作抉擇，成功的避開障礙物。LSTM_RL雖然可以對障礙物進行排序，優先躲避最近的障礙物，但是卻忽略了即將到來的障礙物對將來動作的影響，會出現即使躲避開當前障礙物，又在移動過程中與下一個障礙物相遇，導致規劃的時間過長。SARL雖然能夠預測動態障礙物的趨勢，但是太注重未來的障礙物而忽視了靠近的動態障礙物。從表2中和圖9可以看到本文的策略，到達目標點的時間最短且路徑更加平滑。

圖8 10 000次訓練結果

表2 不存在靜態障礙物的500次測試結果

圖9 不同策略的一次測試案例

圖10 不同策略的一次測試案例

3.3.2 存在靜態障礙物

由于障礙物的增加，為了更好的體現避障效果擴大了地圖環境，由于靜態障礙物的隨機生成，本文主要分析了不同策略的避障效果，設定了4個靜態障礙物和3個動態障礙物。

如圖10所示CADRL僅使用一個淺層的網絡不能很好的提取復雜動態環境中的信息，當環境復雜時很容易發生碰撞，LSTM_RL策略根據離障礙物的距離進行排序，但是容易陷死在擁擠的環境下，SARL策略提取了行人的交互特征的有較好的避障效果，但是當被障礙物包圍時，會出現"凍結"的問題，只有當障礙物離開時才能繼續移動。而我們的策略不僅提取了行人的交互特征，而且排序了障礙物，針對不同的障礙物設置了不同的獎勵策略，使機器人有更好的動作選擇，更好的躲避不同的障礙物，即使在擁擠的環境下，也能規劃出平滑的路徑。如表3所示本文的模型成功率最高，花費的時間最短，均優于其他策略。

表3 存在靜態障礙物的500次測試結果

4 結束語

本文提出了一種基于深度強化學習的動態路徑規劃算法。首先通過構建全局地圖獲取移動機器人周圍的障礙物信息，將障礙物分類成動態障礙物和靜態障礙物。然后建立局部地圖通過LSTM網絡編碼動態障礙物信息，通過社會注意力機制計算每個動態障礙物的重要性來實現更好的避障。通過構建新的獎勵函數來應對動靜態障礙物的不同躲避情況。最后通過模仿學習和優先級經驗回放技術來提高網絡的收斂速度，實驗結果驗證了該模型的準確性和有效性，表明了該模型能夠實現更好的動態避障效果，但是沒有現實機器人上實現，因此下一步研究如何在現實機器人上實現動態路徑規劃。