基于DPES Dueling DQN的路徑規劃方法研究

武 曲 張 義 郭 坤 王 璽

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

0 引 言

在路徑規劃領域,目前已經存在很多經典的算法。如迪杰斯特拉提出的Dijkstra算法,應用貪心的思想,通過每次在未標記的節點中選擇距離源點最近的節點實現最短路徑的求解[1]。在已知地圖的情況下,這種算法仍可以取得很好的效果。A*算法在Dijkstra算法的基礎上,加入了啟發式函數[2],也就是一種評估當前點到達目標的度量,用來決定下一步應該優先擴展哪個節點,這種算法在多維度規劃問題上,或是在較大規模的地圖上,算法復雜度很大。勢場法將規劃空間看作物理學中“場”的概念,將智能體看作一個粒子,障礙物會對這個粒子產生斥力,目標會對這個粒子產生引力,兩者的合力即為最后智能體運動的方向[3],勢場法成功的關鍵在于如何設計引力和斥力函數。這種方法實時性較好,同時產生的路徑通常十分平滑,適合于機械臂一類的應用,缺點是在合力為0的位置智能體容易陷入局部最優解。

近年來,由于人工智能的興起,很多基于人工智能的路徑規劃方法被提出,文獻[4]提出了一種基于模糊邏輯的移動機器人路徑規劃算法,將狀態空間與動作空間關聯起來,形成映射關系,解決了人工勢場法中容易陷入局部極小的問題;文獻[5]中詳細介紹了遺傳算法在路徑規劃中的研究,并提出了一種基于改進染色體編碼的自適應遺傳算法,使得算法能夠避免過早收斂的問題;文獻[6]中提出了利用雙向神經網絡來解決在未知環境中進行路徑規劃的方法。

盡管上述方法可以在各自的領域取得不錯的效果,但是它們都基于已知環境這個前提,需要人工將環境與路徑規劃算法結合,在實際應用時具有一定的局限性。強化學習是一類應用在未知環境的機器學習方法[7],作為機器學習的三大分支之一,不同于監督學習和無監督學習,強化學習無須提供數據,所有的學習資料都將從環境中獲取。智能體通過不斷地探索環境,根據不同的動作產生的不同的反饋進行模型的學習,最終智能體將能以最優策略在指定環境中完成任務。

在利用強化學習進行路徑規劃問題方面,也已經出現了一些研究成果,文獻[8]提出利用偏好評估的強化學習技術,結合降維的方法,實現了智能體在存在移動障礙物的環境中的路徑規劃;文獻[9]將深度強化學習技術與策略梯度法結合起來,解決自動駕駛中的路徑規劃問題,提升了路徑規劃問題的效率;文獻[10]將監督學習與強化學習相結合,為智能體提供規劃好的路徑,接下來智能體利用強化學習中函數近似的方法來進行泛化,實現在其他環境中的路徑規劃,具有較強的泛化能力。

將深度學習與強化結合的結合上,Mnih等[11]構建的DQN(Deep Q Network)無疑是一項重要的研究成果,通過經驗重放的off-policy方式,解決了強化學習領域的數據之間的強相關性無法在深度學習算法中取得好的效果的問題。可以說,經驗重放是深度學習與強化學習結合的關鍵所在,一些學者就此過程進行研究。Schaul等[12]提出了一種基于優先級經驗重放的(Prioritized Experience Replay,PER)的采樣方式,記憶庫中的數據按照被利用來進行訓練時的TD error計算其優先級,造成的TD error比較大的樣本說明模型對此類樣本還未能很好地收斂,在再次采樣時應該更多地選擇此類樣本,反之,造成TD error小的樣本應該盡量少地被再次采樣。這種方式被證明優于隨機采樣的方式,在多種Atari中的表現優于隨機采樣。陳希亮等[13]提出一種基于重抽樣優選緩存經驗回放的抽樣機制,解決了PER抽樣方式導致的抽樣不充分的問題。何明等[14]提出一種PES(Prioritized Experience Selected)的采樣方式,根據TD error排序序數的倒序為樣本設定優先級,解決了PER過程中TD error量級間隔過大而導致的多數樣本因采樣概率低而無法被采集到的問題,在MADDPG算法中取得了比PER采樣過程更好的效果。

以上抽樣方法都著重于從記憶庫中采樣的方式,在離線學習的深度強化學習的機制中,需要設定一個記憶庫來存儲與環境的交互數據,通常,這個數據庫被設計為固定規格,當記憶庫存滿后,采用先進先出的替換原則用新的數據把當前記憶庫中最先存入的數據替換出去,以此來為模型提供較新的數據。這種抽樣的方式帶來的問題是對于早期存入的數據,即使有高的優先級,也有可能被替換出去,而排在末尾的低優先級的數據,也會因為有更長的存在時間而可能被抽樣。本文采用了一種基于堆結構的優先級經驗置換策略,在無須嚴格排序的基礎上實現了樣本替換優先級的定義與運用,保證了記憶庫中樣本的高可用性。此外為了解決訓練過程被某些異常高loss樣本所誘導產生的訓練不平穩的問題,本文提出使用基于層序數的優先級采樣進行解決。

另外,在多智能體聯動學習方面,OpenAI團隊在其提出的MADDPG[15]算法中使用了集中式學習、分布式執行的框架,不同進程之間共享最新的參數,可以使模型更快地收斂。

Dueling DQN[16]是在DQN算法上的一種改進,該算法將Q值分為Value和Advantage兩部分,經本文驗證Dueling DQN在復雜長回合問題中具有更好的表現。

綜上,本文提出一種分布式優先級經驗置換Dueling DQN(DPES Dueling DQN)的算法結構,并在較大規模的復雜環境中進行路徑規劃的仿真實驗,驗證了本文算法的可行性和高效性。

1 相關理論

1.1 DQN

Q-Learning算法是強化學習中一種經典的基于值的算法[17],該算法維護一個狀態與動作的Q值表格,在每一個狀態下,都可以通過查詢表格的方式獲得各個動作所對應的Q值,其中一個表項值Qij表示在狀態si下選擇動作aj的行為價值,通常依argmaxa(Qij)的策略進行動作選擇。在動作執行之后,根據從環境中獲得回報r按式(1)對當前值對應的Q值進行更新。

Q(s,a)←Q(s,a)+γ[r+maxa′Q(s′,a′)-Q(s,a)]

(1)

循環該過程直至整個Q值表收斂。式中:γ表示衰減度,用來表達一個回合中較后的動作所產生的回報對較前的動作選擇的影響。

Q-Learning算法可以近乎完美地解決低維簡單的強化學習問題,但是在處理多狀態多動作的復雜問題時,Q-Learning算法就會變得力不從心,復雜的狀態空間和動作空間讓Q值表變得非常巨大,兩相組合更是使得Q值表的數量級呈指數型增長,這就導致Q值表的收斂變得異常困難。另外對于未參與訓練的狀態,Q-Learning算法將無法為其生成動作,也就是說Q-Learning算法沒有泛化能力。

上述限制使得強化學習在很長一段時間沒有出現突破性的研究進展,一直到2013年,DeepMind團隊的Mnih等提出了DQN算法,這標志著DRL(Deep Reinforcement Learning) 時代的到來,自此不斷涌現出許多DRL的相關技術。

DQN由兩個結構相同但參數間隔更新的網絡構成,可以分別定義為Qtarget和Qeval,其中Qeval從記憶庫中提取數據進行學習,其參數實時更新,而Qtarget每隔一定步數之后同步Qeval的參數,通過如式(2)所示的loss值來進行Qeval網絡的學習。

(2)

深度學習的使用通常以訓練數據相互之間互不相關為前提,而在強化學習中,一個回合的前后動作之間往往存在著很強的相關性,這就為深度學習的使用帶了困擾。在DQN中,通過離線學習的方式解決了這個問題。DQN引入了記憶庫的概念,模型會將訓練過程中的所有實時產生的元組保存在記憶庫中,并不立即用來進行模型的學習,而是通過在記憶庫中隨機抽樣的方式選擇數據進行網絡的學習。這樣就有效地減弱了數據之間的相關性,使得訓練好的模型能夠具有泛化性。

1.2 Dueling DQN

Dueling DQN是DQN的一種改進,Dueling DQN將Q值分成了價值函數Value和優勢函數Advantage兩部分,其中:Value表示當前狀態的重要程度;Advantage則對應每個動作各有一個值代表每個動作的優勢,而后通過式(3)構造最終的Q值。

Q(s,a;θ,α,β)=V(s;θ,β)+(A(s,a;θ,α)-

(3)

式中:θ表示網絡卷積層的參數;α和β分別表示Advantage和Value函數全連接層的參數。

本文實驗證明,Dueling DQN的這種設計有利于長回合場景下的動作選擇,在復雜環境的路徑規劃應用中有較好的表現。

2 本文算法實現

2.1 分布式執行框架

本文算法采用一種分布式執行的框架,框架結構如圖1所示。通過多線程的方式構建多個智能體,多個智能體各自獨立地進行動作選擇、動作執行,在獲得回報后將數據樣本存入共享的記憶庫。

圖1 DPES Dueling DQN結構

智能體在執行時,首先加載最新的共享全局參數,再進行動作選擇。智能體在學習時,各自獨立地從記憶庫中進行樣本抽取,對參數進行梯度更新后將智能體參數上傳到全局共享參數,以保證全局參數獲得實時更新,通過多智能體分布式處理的方式,可以進一步降低樣本之間的相關性,減少模型收斂耗費的時間。

2.2 基于小根堆的PES策略

在傳統的離線學習模型中,當記憶庫存滿時,模型便采用先進先出的機制,從索引0開始替換掉最先存入的數據,這樣會導致高采樣優先級的數據樣本可能因為位于記憶庫開始而被替換出去,造成有價值數據被丟棄。

本文提出的PES策略采用小根堆的結構實現。堆是二叉樹的一種,不同于排序二叉樹在節點增刪時需要調整樹的結構來保證樹的平衡,堆結構在增刪節點的同時自動保證了自身的平衡性,也就保證了在插入刪除時的平均復雜度。堆有小根堆和大根堆之分,小根堆中的根節點是整個樹中的最小節點,其子樹中的根節點同樣滿足此性質。大根堆中則是根節點為最大節點。

小根堆在移動節點時的上浮和下沉兩種操作定義如下:

上浮若當前節點權重比父節點權重值小,交換當前節點與父節點的位置。

下沉若當前節點權重比左子節點權重或右子節點權重大,交換當前節點與較小的子節點位置。

記憶庫處在運行態時,在不同情境下的處理方式如下:

1) 新數據插入。

(1) 堆節點數未達到上限。為新節點賦予初始權重1,將節點插入到堆末尾。

(2) 堆節點數達到上限時。替換掉堆根節點,為新節點賦予初始權重等同堆尾節點的權重,對節點進行下沉操作,移動節點到合適位置。

2) 權重更新后的節點移動。改變被抽樣的節點權重,根據新的權重值大小決定節點上浮或是下沉,移動節點到合適位置。

本文利用數據樣本參與訓練時產生的TD-error即損失值作為構建堆的權重,loss越大,說明模型對此樣本尚不能很好地擬合,需要保留在記憶庫中繼續訓練。反之,loss越小,說明模型對該樣本擬合得很好,此樣本就應該從記憶庫中替換出去,避免該類樣本過多地參與訓練使模型陷入局部最優。而通過小根堆的方式,loss最小的樣本將會始終被放置在根節點的位置,可以以O(1)的時間復雜度拿到并完成樣本替換。而之所以在新樣本存入初始化其權重與堆尾節點相同,是為了保證新寫入數據的采樣優先級。

2.3 基于堆層序數的優先級采樣

在采樣環節,本文提出一種基于堆層序數的優先級采樣方法。在Schaul等提出的PER中,根據式(4)構建的優先級進行采樣。

(4)

式中:pi表示需要為i的樣本參與訓練時產生的損失值。本文通過實驗發現,模型在訓練前期所產生的誤差之間差異較大,依此方式產生的樣本抽樣概率將會更加懸殊,這并不利于模型的平滑收斂。

本文提出的基于小根堆層序數的優先級采樣方式減弱了這種現象的影響。基于小根堆層序數的優先級采樣并不嚴格依賴損失值的完整排序。在小根堆中的數據并不像二叉排序樹那樣滿足嚴格的排序關系,堆中的層級間滿足如下偏序關系:

Li≤Lji

(5)

式中:Li表是第i層的數據。依照此偏序關系構建每層的采樣優先級,既可以保證高損失的樣本具有較高的采樣優先級,又不至于采樣被限制在某些異常高的loss值上。基于層序數的優先級采樣具體實現方式為首先令pi=i,i=1,2,…,log2(n+1),其中:i為堆的層序數;n為堆中節點的總個數。將序列p代入式(4)中獲得堆中各層的采樣概率。在選中抽樣層后,層內采用隨機抽樣的方式進行采樣。本文方法的優勢在于實現代價低,無須對序列進行排序,且能保證按優先級進行采樣。此外,本文方法的采樣效率比較高,可以直接通過索引定位數據,時間復雜度為O(1),相較于PES中通過SumTree的O(log2n)的時間復雜度有了較大的提升。

2.4 模型核心網絡

DPES Dueling DQN的網絡如圖2所示,其中包含三個全連接的隱藏層,每層設置300個節點,以ReLU作為激活函數。第4層采用Dueling的設計方式,分為Value和Advantage兩部分,輸出層即為Q值,由第四層中的兩部分相加而得。

圖2 DPES Dueling DQN核心網絡結構

2.5 DPES Dueling DQN算法步驟

DPES Dueling DQN的算法偽代碼如算法1所示。

算法1DPES Dueling DQN算法

Initialize Agent_Ps, Heap, Learn_point, Global_θ

To every Agent_P:

Repeat max_loop:

while True:

loadθfrom Global_θ

take actionai, returnr,s′

replace the root element in heap with the new data and sink it

if Counter_Memory>Memory_size:

if Counter_Learn%Replace_point:

updateθfromQevaltoQtarget

end if

do model_P learn

updateθto global_θ

end if

ifs′∈Stargetors′∈Sdanger:

end while

end if

3 強化學習環境搭建

本文的環境借助OpenAI團隊構筑的gym環境框架搭建而成,環境以某建筑其中一層平面構建模擬環境,其可視化效果如圖3所示。

圖3 環境仿真

模擬環境由40×40的格點區域組成,仿真地圖區域主要包含房間、樓道、樓梯井三部分。為驗證算法處理復雜環境的能力,本文在實驗時除了普通障礙(即環境中的“wall”)外另添加了一種“危險區域”(即環境中的“danger”)。加入該場景后的環境如圖4所示。

圖4 發生險情的環境仿真

假定發生險情后,智能體可能會分布在地圖中的任意位置,要求強化學習模型可以為智能體規劃最短最安全的逃生路徑。智能體到達安全出口(圖中的exit區域)視為逃生路徑規劃成功。在地圖中間區域附近出現兩處危險點(圖中的danger區域),若智能體不慎步入其中,將隨即死亡,本回合路徑規劃失敗。另外,環境中原本的一處安全出口因為險情無法通過,也變為危險區域。

3.1 狀態空間構建

環境中的狀態由網格點的二維坐標表示,狀態空間為平面中智能體所有可能處于的位置。即去除墻體和樓梯井之外的所有網格點。

3.2 動作空間構建

本文設定的動作空間為離散空間,包括5個動作,分別為原地不動、上、下、左、右,分別以整型數0、1、2、3、4表示。

3.3 環境回報構建

強化學習主要依賴環境的回報優化動作選擇策略以完成任務,所以環境的回報對于任務的成功與否具有決定作用,本文基于先驗知識和實驗經驗進行了下述的回報設定。

(1) 單步回報。因為環境中發生了險情,對于智能體來說,每多走一步,就會增加一分危險,因此設定rstep=-1。這樣的設定也會使得智能體會選擇多條可行路徑中最短的一條路徑。

(2) 越界、碰壁回報。如果智能體在墻體邊緣選擇了“撞墻”的動作,這是一步無意義的動作,因此應當為此類動作設定一個負值回報rwall=-1。

(3) 險地回報。智能體踏入險地即死亡,回合結束,因此險地的回報應該為全局最小值。同時為了保證智能體能通過險地之間的過道,險地的設定值不應該太小,經過多次實驗,最終設定rdanger=-50。

(4) 安全出口回報。安全出口處是路徑規劃任務的最終目標,因此應給予全局最大的正值回報。安全出口的回報應該能保證即使長路程的規劃路徑回合的總回報大于短路程的死亡回合的總回報,在本實驗中,設定其回報為rtarget=200。

綜上,智能體獲得的回報定義如式(6)所示。

(6)

4 仿真實驗

4.1 實驗參數設置

對于模型的核心網絡,設計的層數、節點越少,則網絡無法完成對復雜環境的全局收斂;設計的層數、節點過多,則可能會產生過擬合,且十分耗費計算資源。經過多次實驗測試,最終設定網絡結構如圖2所示,為3×300節點的全連接層,以ReLU作為激活函數。設定學習率為10-4,采用批量梯度下降的方式進行學習,設定batch_size為256,Qtarget每2 000步與Qeval同步參數。

設定記憶庫的規模memory_size為50 000,記憶庫中存儲數據到達10 000條時開始進行模型的學習。

軟件環境為Ubuntu18.04,內存24 GB,顯卡為GTX1060,顯存6 GB,采用Pytorch的深度學習框架。

4.2 實驗結果分析

為了驗證本文方法,還同時進行與DQN、Dueling DQN、DPER Dueling DQN算法的對比實驗,表1對比DQN、Dueling DQN、DPER Dueling DQN、DPES Dueling DQN在各自在訓練的不同階段的模型效果。

表1 測試效果對比表

表1中的完成率指標是加載當時的訓練模型進行100次隨機初始起點的模擬逃生路徑規劃成功次數所占的比例。其中的回報值為這100次路徑規劃的回合回報的均值,為了避免智能體在環境中徘徊,設置單回合最大步數為200,超過此限制則認為路徑規劃任務失敗。

從表1的數據可以看出保證了采樣空間中的數據的高價值性、并通過優先級進行數據采樣的PES策略的表現最佳,可以使訓練產生的模型具有更好的全局可用性。

用三種算法分別訓練200 000個回合,得到損失變化如圖5所示。

圖5 loss變化

可以看出,Dueling的結構在較大規模復雜環境中有較好的表現,體現在訓練之初,通過代表狀態重要性的Value值更能確定準確的方向選擇,體現在loss圖中為在訓練開始時可以更快地向著擬合模型,降低loss。而PER和PES策略能在處理訓練后期尚未收斂的個別數據時發揮作用,PER策略可以提高這些個別數據的抽樣優先級,而本文的PES策略在保證其優先級的同時,又能確保這些數據能夠保持在記憶庫中不被替換出去,在loss圖中可以看出PER策略幾乎把loss降低了一個量級,而本文的PES策略又進一步降低了loss。而且本文方法得到的曲線更加平滑,這也印證了本文方法不會被個別異常數據所左右的觀點。結合表1的數據也可以看出本文提出的PES策略具有更好的全局收斂效果。

圖6所示為隨著訓練進行,平均回合回報的變化趨勢,通過對比平均回合回報的變化趨勢也可以得到與上文同樣的結論。本文方法可以更快地完成收斂,Dueling的結構可以更好地幫助智能體找尋前進方向,能盡快地完成收斂。PES的采樣方式則可以使模型盡快適應某些尚未收斂的格點,更快地達到在全局任意位置都能安全逃生的路徑規劃效果。

圖6 平均回合回報

訓練到20 000輪的參數進行測試效果如圖7所示,其中每個格點上的小三角形指示了智能體位于該位置時應該選擇的動作方向。可以看到對于地圖上的絕大部分區域,智能體都能找到安全逃生路徑。

圖7 第20 000輪的路徑規劃效果

取第110 000輪的參數進行測試,效果如圖8所示,此時無論在地圖上的任意位置,智能體都能完成安全逃生的路徑規劃。

圖8 第110 000輪的路徑規劃效果

另外,本文還利用DPES Dueling DQN算法進行如圖9和圖10場景下的測試。圖9是在未發生險情的安全路徑規劃場景,可以看到在地圖中的任何位置,智能體都能按照指示方向到達安全出口,且所選路徑為最短路徑。圖10所示環境中,一處險情阻塞了主要通道,可以看到模型在進行路徑規劃時會選擇穿過其他房間到達安全出口。

圖9 無險情發生時路徑規劃效果

圖10 險情阻塞主干道路徑規劃效果

綜合上述的實驗可以看出,本文提出的PES策略可以在深度強化學習算法的訓練過程中取得較好的加速表現,記憶庫中樣本質量的提高有助于模型更快、更穩定地收斂。此外,結合Dueling DQN提出的DPES Dueling DQN算法應用在路徑規劃場景中很好地完成了路徑規劃任務,通過不同實驗場景的訓練,本文算法的泛化性也得到了證明。

5 結 語

本文將深度強化學習應用在路徑規劃領域,提出使用DPES Dueling DQN算法進行復雜環境下的路徑規劃。采用PES策略將欠擬合的樣本數據保留在記憶庫中,使記憶庫中的樣本對于模型的全局收斂而言是高收益的。采用分布式的方式既有利于收集全局樣本,也提高了模型收斂的速度及學習效率。又結合了在較大環境中表現更佳Dueling DQN算法進行最優路徑規劃。最終通過實驗與DQN、Dueling DQN、DPER Dueling DQN進行對比,驗證了DPES Dueling DQN方法進行路徑規劃的高效性和泛化能力。