基于DPES Dueling DQN的路徑規(guī)劃方法研究

武 曲 張 義 郭 坤 王 璽

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

0 引 言

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

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

盡管上述方法可以在各自的領(lǐng)域取得不錯(cuò)的效果,但是它們都基于已知環(huán)境這個(gè)前提,需要人工將環(huán)境與路徑規(guī)劃算法結(jié)合,在實(shí)際應(yīng)用時(shí)具有一定的局限性。強(qiáng)化學(xué)習(xí)是一類應(yīng)用在未知環(huán)境的機(jī)器學(xué)習(xí)方法[7],作為機(jī)器學(xué)習(xí)的三大分支之一,不同于監(jiān)督學(xué)習(xí)和無(wú)監(jiān)督學(xué)習(xí),強(qiáng)化學(xué)習(xí)無(wú)須提供數(shù)據(jù),所有的學(xué)習(xí)資料都將從環(huán)境中獲取。智能體通過(guò)不斷地探索環(huán)境,根據(jù)不同的動(dòng)作產(chǎn)生的不同的反饋進(jìn)行模型的學(xué)習(xí),最終智能體將能以最優(yōu)策略在指定環(huán)境中完成任務(wù)。

在利用強(qiáng)化學(xué)習(xí)進(jìn)行路徑規(guī)劃問(wèn)題方面,也已經(jīng)出現(xiàn)了一些研究成果,文獻(xiàn)[8]提出利用偏好評(píng)估的強(qiáng)化學(xué)習(xí)技術(shù),結(jié)合降維的方法,實(shí)現(xiàn)了智能體在存在移動(dòng)障礙物的環(huán)境中的路徑規(guī)劃;文獻(xiàn)[9]將深度強(qiáng)化學(xué)習(xí)技術(shù)與策略梯度法結(jié)合起來(lái),解決自動(dòng)駕駛中的路徑規(guī)劃問(wèn)題,提升了路徑規(guī)劃問(wèn)題的效率;文獻(xiàn)[10]將監(jiān)督學(xué)習(xí)與強(qiáng)化學(xué)習(xí)相結(jié)合,為智能體提供規(guī)劃好的路徑,接下來(lái)智能體利用強(qiáng)化學(xué)習(xí)中函數(shù)近似的方法來(lái)進(jìn)行泛化,實(shí)現(xiàn)在其他環(huán)境中的路徑規(guī)劃,具有較強(qiáng)的泛化能力。

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

以上抽樣方法都著重于從記憶庫(kù)中采樣的方式,在離線學(xué)習(xí)的深度強(qiáng)化學(xué)習(xí)的機(jī)制中,需要設(shè)定一個(gè)記憶庫(kù)來(lái)存儲(chǔ)與環(huán)境的交互數(shù)據(jù),通常,這個(gè)數(shù)據(jù)庫(kù)被設(shè)計(jì)為固定規(guī)格,當(dāng)記憶庫(kù)存滿后,采用先進(jìn)先出的替換原則用新的數(shù)據(jù)把當(dāng)前記憶庫(kù)中最先存入的數(shù)據(jù)替換出去,以此來(lái)為模型提供較新的數(shù)據(jù)。這種抽樣的方式帶來(lái)的問(wèn)題是對(duì)于早期存入的數(shù)據(jù),即使有高的優(yōu)先級(jí),也有可能被替換出去,而排在末尾的低優(yōu)先級(jí)的數(shù)據(jù),也會(huì)因?yàn)橛懈L(zhǎng)的存在時(shí)間而可能被抽樣。本文采用了一種基于堆結(jié)構(gòu)的優(yōu)先級(jí)經(jīng)驗(yàn)置換策略,在無(wú)須嚴(yán)格排序的基礎(chǔ)上實(shí)現(xiàn)了樣本替換優(yōu)先級(jí)的定義與運(yùn)用,保證了記憶庫(kù)中樣本的高可用性。此外為了解決訓(xùn)練過(guò)程被某些異常高loss樣本所誘導(dǎo)產(chǎn)生的訓(xùn)練不平穩(wěn)的問(wèn)題,本文提出使用基于層序數(shù)的優(yōu)先級(jí)采樣進(jìn)行解決。

另外,在多智能體聯(lián)動(dòng)學(xué)習(xí)方面,OpenAI團(tuán)隊(duì)在其提出的MADDPG[15]算法中使用了集中式學(xué)習(xí)、分布式執(zhí)行的框架,不同進(jìn)程之間共享最新的參數(shù),可以使模型更快地收斂。

Dueling DQN[16]是在DQN算法上的一種改進(jìn),該算法將Q值分為Value和Advantage兩部分,經(jīng)本文驗(yàn)證Dueling DQN在復(fù)雜長(zhǎng)回合問(wèn)題中具有更好的表現(xiàn)。

綜上,本文提出一種分布式優(yōu)先級(jí)經(jīng)驗(yàn)置換Dueling DQN(DPES Dueling DQN)的算法結(jié)構(gòu),并在較大規(guī)模的復(fù)雜環(huán)境中進(jìn)行路徑規(guī)劃的仿真實(shí)驗(yàn),驗(yàn)證了本文算法的可行性和高效性。

1 相關(guān)理論

1.1 DQN

Q-Learning算法是強(qiáng)化學(xué)習(xí)中一種經(jīng)典的基于值的算法[17],該算法維護(hù)一個(gè)狀態(tài)與動(dòng)作的Q值表格,在每一個(gè)狀態(tài)下,都可以通過(guò)查詢表格的方式獲得各個(gè)動(dòng)作所對(duì)應(yīng)的Q值,其中一個(gè)表項(xiàng)值Qij表示在狀態(tài)si下選擇動(dòng)作aj的行為價(jià)值,通常依argmaxa(Qij)的策略進(jìn)行動(dòng)作選擇。在動(dòng)作執(zhí)行之后,根據(jù)從環(huán)境中獲得回報(bào)r按式(1)對(duì)當(dāng)前值對(duì)應(yīng)的Q值進(jìn)行更新。

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

(1)

循環(huán)該過(guò)程直至整個(gè)Q值表收斂。式中:γ表示衰減度,用來(lái)表達(dá)一個(gè)回合中較后的動(dòng)作所產(chǎn)生的回報(bào)對(duì)較前的動(dòng)作選擇的影響。

Q-Learning算法可以近乎完美地解決低維簡(jiǎn)單的強(qiáng)化學(xué)習(xí)問(wèn)題,但是在處理多狀態(tài)多動(dòng)作的復(fù)雜問(wèn)題時(shí),Q-Learning算法就會(huì)變得力不從心,復(fù)雜的狀態(tài)空間和動(dòng)作空間讓Q值表變得非常巨大,兩相組合更是使得Q值表的數(shù)量級(jí)呈指數(shù)型增長(zhǎng),這就導(dǎo)致Q值表的收斂變得異常困難。另外對(duì)于未參與訓(xùn)練的狀態(tài),Q-Learning算法將無(wú)法為其生成動(dòng)作,也就是說(shuō)Q-Learning算法沒(méi)有泛化能力。

上述限制使得強(qiáng)化學(xué)習(xí)在很長(zhǎng)一段時(shí)間沒(méi)有出現(xiàn)突破性的研究進(jìn)展,一直到2013年,DeepMind團(tuán)隊(duì)的Mnih等提出了DQN算法,這標(biāo)志著DRL(Deep Reinforcement Learning) 時(shí)代的到來(lái),自此不斷涌現(xiàn)出許多DRL的相關(guān)技術(shù)。

DQN由兩個(gè)結(jié)構(gòu)相同但參數(shù)間隔更新的網(wǎng)絡(luò)構(gòu)成,可以分別定義為Qtarget和Qeval,其中Qeval從記憶庫(kù)中提取數(shù)據(jù)進(jìn)行學(xué)習(xí),其參數(shù)實(shí)時(shí)更新,而Qtarget每隔一定步數(shù)之后同步Qeval的參數(shù),通過(guò)如式(2)所示的loss值來(lái)進(jìn)行Qeval網(wǎng)絡(luò)的學(xué)習(xí)。

(2)

深度學(xué)習(xí)的使用通常以訓(xùn)練數(shù)據(jù)相互之間互不相關(guān)為前提,而在強(qiáng)化學(xué)習(xí)中,一個(gè)回合的前后動(dòng)作之間往往存在著很強(qiáng)的相關(guān)性,這就為深度學(xué)習(xí)的使用帶了困擾。在DQN中,通過(guò)離線學(xué)習(xí)的方式解決了這個(gè)問(wèn)題。DQN引入了記憶庫(kù)的概念,模型會(huì)將訓(xùn)練過(guò)程中的所有實(shí)時(shí)產(chǎn)生的元組保存在記憶庫(kù)中,并不立即用來(lái)進(jìn)行模型的學(xué)習(xí),而是通過(guò)在記憶庫(kù)中隨機(jī)抽樣的方式選擇數(shù)據(jù)進(jìn)行網(wǎng)絡(luò)的學(xué)習(xí)。這樣就有效地減弱了數(shù)據(jù)之間的相關(guān)性,使得訓(xùn)練好的模型能夠具有泛化性。

1.2 Dueling DQN

Dueling DQN是DQN的一種改進(jìn),Dueling DQN將Q值分成了價(jià)值函數(shù)Value和優(yōu)勢(shì)函數(shù)Advantage兩部分,其中:Value表示當(dāng)前狀態(tài)的重要程度;Advantage則對(duì)應(yīng)每個(gè)動(dòng)作各有一個(gè)值代表每個(gè)動(dòng)作的優(yōu)勢(shì),而后通過(guò)式(3)構(gòu)造最終的Q值。

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

(3)

式中:θ表示網(wǎng)絡(luò)卷積層的參數(shù);α和β分別表示Advantage和Value函數(shù)全連接層的參數(shù)。

本文實(shí)驗(yàn)證明,Dueling DQN的這種設(shè)計(jì)有利于長(zhǎng)回合場(chǎng)景下的動(dòng)作選擇,在復(fù)雜環(huán)境的路徑規(guī)劃應(yīng)用中有較好的表現(xiàn)。

2 本文算法實(shí)現(xiàn)

2.1 分布式執(zhí)行框架

本文算法采用一種分布式執(zhí)行的框架,框架結(jié)構(gòu)如圖1所示。通過(guò)多線程的方式構(gòu)建多個(gè)智能體,多個(gè)智能體各自獨(dú)立地進(jìn)行動(dòng)作選擇、動(dòng)作執(zhí)行,在獲得回報(bào)后將數(shù)據(jù)樣本存入共享的記憶庫(kù)。

圖1 DPES Dueling DQN結(jié)構(gòu)

智能體在執(zhí)行時(shí),首先加載最新的共享全局參數(shù),再進(jìn)行動(dòng)作選擇。智能體在學(xué)習(xí)時(shí),各自獨(dú)立地從記憶庫(kù)中進(jìn)行樣本抽取,對(duì)參數(shù)進(jìn)行梯度更新后將智能體參數(shù)上傳到全局共享參數(shù),以保證全局參數(shù)獲得實(shí)時(shí)更新,通過(guò)多智能體分布式處理的方式,可以進(jìn)一步降低樣本之間的相關(guān)性,減少模型收斂耗費(fèi)的時(shí)間。

2.2 基于小根堆的PES策略

在傳統(tǒng)的離線學(xué)習(xí)模型中,當(dāng)記憶庫(kù)存滿時(shí),模型便采用先進(jìn)先出的機(jī)制,從索引0開(kāi)始替換掉最先存入的數(shù)據(jù),這樣會(huì)導(dǎo)致高采樣優(yōu)先級(jí)的數(shù)據(jù)樣本可能因?yàn)槲挥谟洃泿?kù)開(kāi)始而被替換出去,造成有價(jià)值數(shù)據(jù)被丟棄。

本文提出的PES策略采用小根堆的結(jié)構(gòu)實(shí)現(xiàn)。堆是二叉樹(shù)的一種,不同于排序二叉樹(shù)在節(jié)點(diǎn)增刪時(shí)需要調(diào)整樹(shù)的結(jié)構(gòu)來(lái)保證樹(shù)的平衡,堆結(jié)構(gòu)在增刪節(jié)點(diǎn)的同時(shí)自動(dòng)保證了自身的平衡性,也就保證了在插入刪除時(shí)的平均復(fù)雜度。堆有小根堆和大根堆之分,小根堆中的根節(jié)點(diǎn)是整個(gè)樹(shù)中的最小節(jié)點(diǎn),其子樹(shù)中的根節(jié)點(diǎn)同樣滿足此性質(zhì)。大根堆中則是根節(jié)點(diǎn)為最大節(jié)點(diǎn)。

小根堆在移動(dòng)節(jié)點(diǎn)時(shí)的上浮和下沉兩種操作定義如下:

上浮若當(dāng)前節(jié)點(diǎn)權(quán)重比父節(jié)點(diǎn)權(quán)重值小,交換當(dāng)前節(jié)點(diǎn)與父節(jié)點(diǎn)的位置。

下沉若當(dāng)前節(jié)點(diǎn)權(quán)重比左子節(jié)點(diǎn)權(quán)重或右子節(jié)點(diǎn)權(quán)重大,交換當(dāng)前節(jié)點(diǎn)與較小的子節(jié)點(diǎn)位置。

記憶庫(kù)處在運(yùn)行態(tài)時(shí),在不同情境下的處理方式如下:

1) 新數(shù)據(jù)插入。

(1) 堆節(jié)點(diǎn)數(shù)未達(dá)到上限。為新節(jié)點(diǎn)賦予初始權(quán)重1,將節(jié)點(diǎn)插入到堆末尾。

(2) 堆節(jié)點(diǎn)數(shù)達(dá)到上限時(shí)。替換掉堆根節(jié)點(diǎn),為新節(jié)點(diǎn)賦予初始權(quán)重等同堆尾節(jié)點(diǎn)的權(quán)重,對(duì)節(jié)點(diǎn)進(jìn)行下沉操作,移動(dòng)節(jié)點(diǎn)到合適位置。

2) 權(quán)重更新后的節(jié)點(diǎn)移動(dòng)。改變被抽樣的節(jié)點(diǎn)權(quán)重,根據(jù)新的權(quán)重值大小決定節(jié)點(diǎn)上浮或是下沉,移動(dòng)節(jié)點(diǎn)到合適位置。

本文利用數(shù)據(jù)樣本參與訓(xùn)練時(shí)產(chǎn)生的TD-error即損失值作為構(gòu)建堆的權(quán)重,loss越大,說(shuō)明模型對(duì)此樣本尚不能很好地?cái)M合,需要保留在記憶庫(kù)中繼續(xù)訓(xùn)練。反之,loss越小,說(shuō)明模型對(duì)該樣本擬合得很好,此樣本就應(yīng)該從記憶庫(kù)中替換出去,避免該類樣本過(guò)多地參與訓(xùn)練使模型陷入局部最優(yōu)。而通過(guò)小根堆的方式,loss最小的樣本將會(huì)始終被放置在根節(jié)點(diǎn)的位置,可以以O(shè)(1)的時(shí)間復(fù)雜度拿到并完成樣本替換。而之所以在新樣本存入初始化其權(quán)重與堆尾節(jié)點(diǎn)相同,是為了保證新寫(xiě)入數(shù)據(jù)的采樣優(yōu)先級(jí)。

2.3 基于堆層序數(shù)的優(yōu)先級(jí)采樣

在采樣環(huán)節(jié),本文提出一種基于堆層序數(shù)的優(yōu)先級(jí)采樣方法。在Schaul等提出的PER中,根據(jù)式(4)構(gòu)建的優(yōu)先級(jí)進(jìn)行采樣。

(4)

式中:pi表示需要為i的樣本參與訓(xùn)練時(shí)產(chǎn)生的損失值。本文通過(guò)實(shí)驗(yàn)發(fā)現(xiàn),模型在訓(xùn)練前期所產(chǎn)生的誤差之間差異較大,依此方式產(chǎn)生的樣本抽樣概率將會(huì)更加懸殊,這并不利于模型的平滑收斂。

本文提出的基于小根堆層序數(shù)的優(yōu)先級(jí)采樣方式減弱了這種現(xiàn)象的影響?；谛「褜有驍?shù)的優(yōu)先級(jí)采樣并不嚴(yán)格依賴損失值的完整排序。在小根堆中的數(shù)據(jù)并不像二叉排序樹(shù)那樣滿足嚴(yán)格的排序關(guān)系,堆中的層級(jí)間滿足如下偏序關(guān)系:

Li≤Lji

(5)

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

2.4 模型核心網(wǎng)絡(luò)

DPES Dueling DQN的網(wǎng)絡(luò)如圖2所示,其中包含三個(gè)全連接的隱藏層,每層設(shè)置300個(gè)節(jié)點(diǎn),以ReLU作為激活函數(shù)。第4層采用Dueling的設(shè)計(jì)方式,分為Value和Advantage兩部分,輸出層即為Q值,由第四層中的兩部分相加而得。

圖2 DPES Dueling DQN核心網(wǎng)絡(luò)結(jié)構(gòu)

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θf(wàn)rom 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θf(wàn)romQevaltoQtarget

end if

do model_P learn

updateθto global_θ

end if

ifs′∈Stargetors′∈Sdanger:

end while

end if

3 強(qiáng)化學(xué)習(xí)環(huán)境搭建

本文的環(huán)境借助OpenAI團(tuán)隊(duì)構(gòu)筑的gym環(huán)境框架搭建而成,環(huán)境以某建筑其中一層平面構(gòu)建模擬環(huán)境,其可視化效果如圖3所示。

圖3 環(huán)境仿真

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

圖4 發(fā)生險(xiǎn)情的環(huán)境仿真

假定發(fā)生險(xiǎn)情后,智能體可能會(huì)分布在地圖中的任意位置,要求強(qiáng)化學(xué)習(xí)模型可以為智能體規(guī)劃最短最安全的逃生路徑。智能體到達(dá)安全出口(圖中的exit區(qū)域)視為逃生路徑規(guī)劃成功。在地圖中間區(qū)域附近出現(xiàn)兩處危險(xiǎn)點(diǎn)(圖中的danger區(qū)域),若智能體不慎步入其中,將隨即死亡,本回合路徑規(guī)劃失敗。另外,環(huán)境中原本的一處安全出口因?yàn)殡U(xiǎn)情無(wú)法通過(guò),也變?yōu)槲ｋU(xiǎn)區(qū)域。

3.1 狀態(tài)空間構(gòu)建

環(huán)境中的狀態(tài)由網(wǎng)格點(diǎn)的二維坐標(biāo)表示,狀態(tài)空間為平面中智能體所有可能處于的位置。即去除墻體和樓梯井之外的所有網(wǎng)格點(diǎn)。

3.2 動(dòng)作空間構(gòu)建

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

3.3 環(huán)境回報(bào)構(gòu)建

強(qiáng)化學(xué)習(xí)主要依賴環(huán)境的回報(bào)優(yōu)化動(dòng)作選擇策略以完成任務(wù),所以環(huán)境的回報(bào)對(duì)于任務(wù)的成功與否具有決定作用,本文基于先驗(yàn)知識(shí)和實(shí)驗(yàn)經(jīng)驗(yàn)進(jìn)行了下述的回報(bào)設(shè)定。

(1) 單步回報(bào)。因?yàn)榄h(huán)境中發(fā)生了險(xiǎn)情,對(duì)于智能體來(lái)說(shuō),每多走一步,就會(huì)增加一分危險(xiǎn),因此設(shè)定rstep=-1。這樣的設(shè)定也會(huì)使得智能體會(huì)選擇多條可行路徑中最短的一條路徑。

(2) 越界、碰壁回報(bào)。如果智能體在墻體邊緣選擇了“撞墻”的動(dòng)作,這是一步無(wú)意義的動(dòng)作,因此應(yīng)當(dāng)為此類動(dòng)作設(shè)定一個(gè)負(fù)值回報(bào)rwall=-1。

(3) 險(xiǎn)地回報(bào)。智能體踏入險(xiǎn)地即死亡,回合結(jié)束,因此險(xiǎn)地的回報(bào)應(yīng)該為全局最小值。同時(shí)為了保證智能體能通過(guò)險(xiǎn)地之間的過(guò)道,險(xiǎn)地的設(shè)定值不應(yīng)該太小,經(jīng)過(guò)多次實(shí)驗(yàn),最終設(shè)定rdanger=-50。

(4) 安全出口回報(bào)。安全出口處是路徑規(guī)劃任務(wù)的最終目標(biāo),因此應(yīng)給予全局最大的正值回報(bào)。安全出口的回報(bào)應(yīng)該能保證即使長(zhǎng)路程的規(guī)劃路徑回合的總回報(bào)大于短路程的死亡回合的總回報(bào),在本實(shí)驗(yàn)中,設(shè)定其回報(bào)為rtarget=200。

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

(6)

4 仿真實(shí)驗(yàn)

4.1 實(shí)驗(yàn)參數(shù)設(shè)置

對(duì)于模型的核心網(wǎng)絡(luò),設(shè)計(jì)的層數(shù)、節(jié)點(diǎn)越少,則網(wǎng)絡(luò)無(wú)法完成對(duì)復(fù)雜環(huán)境的全局收斂;設(shè)計(jì)的層數(shù)、節(jié)點(diǎn)過(guò)多,則可能會(huì)產(chǎn)生過(guò)擬合,且十分耗費(fèi)計(jì)算資源。經(jīng)過(guò)多次實(shí)驗(yàn)測(cè)試,最終設(shè)定網(wǎng)絡(luò)結(jié)構(gòu)如圖2所示,為3×300節(jié)點(diǎn)的全連接層,以ReLU作為激活函數(shù)。設(shè)定學(xué)習(xí)率為10-4,采用批量梯度下降的方式進(jìn)行學(xué)習(xí),設(shè)定batch_size為256,Qtarget每2 000步與Qeval同步參數(shù)。

設(shè)定記憶庫(kù)的規(guī)模memory_size為50 000,記憶庫(kù)中存儲(chǔ)數(shù)據(jù)到達(dá)10 000條時(shí)開(kāi)始進(jìn)行模型的學(xué)習(xí)。

軟件環(huán)境為Ubuntu18.04,內(nèi)存24 GB,顯卡為GTX1060,顯存6 GB,采用Pytorch的深度學(xué)習(xí)框架。

4.2 實(shí)驗(yàn)結(jié)果分析

為了驗(yàn)證本文方法,還同時(shí)進(jìn)行與DQN、Dueling DQN、DPER Dueling DQN算法的對(duì)比實(shí)驗(yàn),表1對(duì)比DQN、Dueling DQN、DPER Dueling DQN、DPES Dueling DQN在各自在訓(xùn)練的不同階段的模型效果。

表1 測(cè)試效果對(duì)比表

表1中的完成率指標(biāo)是加載當(dāng)時(shí)的訓(xùn)練模型進(jìn)行100次隨機(jī)初始起點(diǎn)的模擬逃生路徑規(guī)劃成功次數(shù)所占的比例。其中的回報(bào)值為這100次路徑規(guī)劃的回合回報(bào)的均值,為了避免智能體在環(huán)境中徘徊,設(shè)置單回合最大步數(shù)為200,超過(guò)此限制則認(rèn)為路徑規(guī)劃任務(wù)失敗。

從表1的數(shù)據(jù)可以看出保證了采樣空間中的數(shù)據(jù)的高價(jià)值性、并通過(guò)優(yōu)先級(jí)進(jìn)行數(shù)據(jù)采樣的PES策略的表現(xiàn)最佳,可以使訓(xùn)練產(chǎn)生的模型具有更好的全局可用性。

用三種算法分別訓(xùn)練200 000個(gè)回合,得到損失變化如圖5所示。

圖5 loss變化

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

圖6所示為隨著訓(xùn)練進(jìn)行,平均回合回報(bào)的變化趨勢(shì),通過(guò)對(duì)比平均回合回報(bào)的變化趨勢(shì)也可以得到與上文同樣的結(jié)論。本文方法可以更快地完成收斂,Dueling的結(jié)構(gòu)可以更好地幫助智能體找尋前進(jìn)方向,能盡快地完成收斂。PES的采樣方式則可以使模型盡快適應(yīng)某些尚未收斂的格點(diǎn),更快地達(dá)到在全局任意位置都能安全逃生的路徑規(guī)劃效果。

圖6 平均回合回報(bào)

訓(xùn)練到20 000輪的參數(shù)進(jìn)行測(cè)試效果如圖7所示,其中每個(gè)格點(diǎn)上的小三角形指示了智能體位于該位置時(shí)應(yīng)該選擇的動(dòng)作方向?？梢钥吹綄?duì)于地圖上的絕大部分區(qū)域,智能體都能找到安全逃生路徑。

圖7 第20 000輪的路徑規(guī)劃效果

取第110 000輪的參數(shù)進(jìn)行測(cè)試,效果如圖8所示,此時(shí)無(wú)論在地圖上的任意位置,智能體都能完成安全逃生的路徑規(guī)劃。

圖8 第110 000輪的路徑規(guī)劃效果

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

圖9 無(wú)險(xiǎn)情發(fā)生時(shí)路徑規(guī)劃效果

圖10 險(xiǎn)情阻塞主干道路徑規(guī)劃效果

綜合上述的實(shí)驗(yàn)可以看出,本文提出的PES策略可以在深度強(qiáng)化學(xué)習(xí)算法的訓(xùn)練過(guò)程中取得較好的加速表現(xiàn),記憶庫(kù)中樣本質(zhì)量的提高有助于模型更快、更穩(wěn)定地收斂。此外,結(jié)合Dueling DQN提出的DPES Dueling DQN算法應(yīng)用在路徑規(guī)劃場(chǎng)景中很好地完成了路徑規(guī)劃任務(wù),通過(guò)不同實(shí)驗(yàn)場(chǎng)景的訓(xùn)練,本文算法的泛化性也得到了證明。

5 結(jié) 語(yǔ)

本文將深度強(qiáng)化學(xué)習(xí)應(yīng)用在路徑規(guī)劃領(lǐng)域,提出使用DPES Dueling DQN算法進(jìn)行復(fù)雜環(huán)境下的路徑規(guī)劃。采用PES策略將欠擬合的樣本數(shù)據(jù)保留在記憶庫(kù)中,使記憶庫(kù)中的樣本對(duì)于模型的全局收斂而言是高收益的。采用分布式的方式既有利于收集全局樣本,也提高了模型收斂的速度及學(xué)習(xí)效率。又結(jié)合了在較大環(huán)境中表現(xiàn)更佳Dueling DQN算法進(jìn)行最優(yōu)路徑規(guī)劃。最終通過(guò)實(shí)驗(yàn)與DQN、Dueling DQN、DPER Dueling DQN進(jìn)行對(duì)比,驗(yàn)證了DPES Dueling DQN方法進(jìn)行路徑規(guī)劃的高效性和泛化能力。