基于深度強化學習的路徑規(guī)劃算法研究

曹景祥 劉其成

(煙臺大學計算機與控制工程學院 山東 煙臺 264000)

0 引 言

隨著科技的快速發(fā)展和日益普及，機器人、無人駕駛、船只障礙規(guī)避、工程機械等都使用了路徑規(guī)劃。因此路徑規(guī)劃受到了許多的關注，越來越多的研究人員對路徑規(guī)劃算法進行改進[1]，并且將深度強化學習引入到路徑規(guī)劃中。

深度強化學習(Deep Reinforcement Learning,DRL)結合了深度學習的感知能力和強化學習的決策能力[2]。隨著深度強化學習在不同領域的成功應用，使得越來越多的研究人員開始將深度強化學習應用到路徑規(guī)劃[3]。在面對復雜環(huán)境和任務時，深度強化學習算法表現突出，有助于提高路徑規(guī)劃的效率[4]。

基于深度強化學習的路徑規(guī)劃算法通過神經網絡來選擇某一狀態(tài)的較優(yōu)動作，根據得到的較優(yōu)動作組成物體起始位置到目標的較優(yōu)動作集，最后得到較優(yōu)路徑。所以神經網絡的類型和神經網絡的參數更新對動作的選擇起到了重要的作用[5]。因此本文使用了多層感知機，通過改進的獎勵函數使得神經網絡參數更加精確，提高神經網絡的動作選擇效率，最終達到提高路徑規(guī)劃效率的目的。

1 相關工作

過去的許多研究中都是基于已知環(huán)境進行路徑規(guī)劃，如文獻[6]在已知倉儲信息中，提出了基于遺傳算法的倉儲貨位與AGV路徑規(guī)劃協同優(yōu)化算法，來解決易陷入局部最優(yōu)的問題。文獻[7]使用A*(A-Star)算法進行路徑規(guī)劃要事先存儲整個地圖，然后依據擴展節(jié)點選擇當前代價最低的方塊進行下一步搜索，直到搜索到終點，從而規(guī)劃出成本最低的路徑。文獻[8]提出了機器人避障路徑規(guī)劃的自適應人工勢場方法，通過自適應地改變障礙物勢場函數的權重，使得機器人逃離局部極小值。在一些領域中，隨著路徑規(guī)劃環(huán)境信息越來越復雜，存儲環(huán)境信息對內存的要求過高[9]，因此在未知環(huán)境中獲取較優(yōu)路徑成為研究熱點。

由于強化學習不需要先驗信息，通過物體和環(huán)境不斷地交互和試錯獲取信息，由獎賞機制進行策略優(yōu)化，是動作到行為映射的學習方式[10]，所以強化學習在路徑規(guī)劃中使用越來越廣泛。文獻[11]將強化學習中Q-learning算法應用到路徑規(guī)劃中，因為無須知道模型就可以保證收斂，在狀態(tài)空間較小的情況下能夠很好地規(guī)劃路徑。文獻[12]基于Q-learning算法，提出了一種自適應增強—探索Q學習算法，將探索因子ε的衰減過程分為兩個階段，提高探索效率。文獻[13]使用Q學習算法進行路徑，將Q學習算法中執(zhí)行每個動作回報值進行改變，把接收信號的強度作為回報值，大大減少了迭代次數，提高路徑規(guī)劃效率?；趶娀瘜W習的路徑規(guī)劃算法適用于低維狀態(tài)空間[14]，因為算法所需數據是通過物體與環(huán)境交互獲得的，所以當路徑規(guī)劃的環(huán)境過于復雜、數據維數過高時，路徑規(guī)劃效率將會下降。

在越來越復雜的實際場景中，需要利用深度學習從大規(guī)模數據中提取高級特征。通過深度學習和強化學習相結合，在未知環(huán)境中自主學習，并預測出可行路徑，以實現自主規(guī)劃出較優(yōu)路徑，因此深度強化學習被引用到路徑規(guī)劃中。文獻[15]將深度Q學習與深度預測網絡技術相結合，提出了一種在全局范圍內快速實現路徑規(guī)劃的算法，利用時空、天氣等道路特征預測未來交通狀況，求得全局較優(yōu)路徑。文獻[16]提出了一種模糊貝葉斯-深度Q網絡算法，對ε-貪婪算法進行修改，將模糊綜合評判法和貝葉斯決策算法相結合替代ε-貪婪算法，使探索與利用兩種動作選擇方式更加高效，生成最優(yōu)的動作序列決策。文獻[17]將深度Q學習算法引入到海戰(zhàn)場中進行路徑規(guī)劃，并且將海戰(zhàn)場環(huán)境網格化，使用卷積神經網絡進行路徑規(guī)劃。

研究人員將路徑規(guī)劃的環(huán)境信息進行處理，使得環(huán)境網格化，環(huán)境信息就會相對簡單。如果在深度Q網絡算法使用卷積神經網絡可能會產生過擬合，無法得到較優(yōu)動作，降低了路徑規(guī)劃效率。在這種背景之下，本文將多層感知機應用到深度Q網絡算法中，并將改進獎勵的函數運用到神經網絡每次更新中，提出一種改進后的深度Q網絡路徑規(guī)劃算法。

2 相關知識

2.1 Q學習算法

2.1.1Q值表更新

Q學習算法是一種無模型的強化學習的算法，使用Q值表來存儲物體的不同狀態(tài)s和動作集合A之間的關系。通過物體執(zhí)行動作a∈A與環(huán)境不斷地交互，以此達到不同狀態(tài)之間相互轉換的目的，從而不斷地更新Q值表，再通過Q值表更新動作選擇策略，最終獲取最優(yōu)動作集。因為Q學習式求得全局最優(yōu)策略，所以Q值表中某時刻信息的更新是通過下一步的狀態(tài)值函數進行的。比如在t時刻物體選擇動作，觀察獎勵rt進入新狀態(tài)st+1，并對Q值表進行更新。迭代過程如式(1)所示。

Qnew(st,at)←(1-α)·Q(st,at)+α(rt+

式中：Q(st,at)表示在t時刻時，處于s狀態(tài)執(zhí)行動作a的Q值；γ為影響因子；α為學習率。

2.1.2獎勵函數

路徑規(guī)劃中的最終目的就是找到長期累積獎勵值最大的路徑，因此獎勵函數有著重要的作用。在Q學習算法中，根據給定的獎勵函數判斷在某種狀態(tài)下執(zhí)行的動作的好壞程度。其中，獎勵函數的反饋分為正反饋和負反饋，通過獲得的反饋計算下一狀態(tài)的預期獎勵來決定下一步的行動。式(2)為狀態(tài)-行動-下一狀態(tài)的預期獎勵。

式中：r(s,a,s′)為預期獎勵，s為當前狀態(tài)，a為執(zhí)行的動作，s′為下一狀態(tài)；rt+1為下一狀態(tài)得到的獎勵值；R′為獎勵空間；p(s′,r|s,a)表示在狀態(tài)s，執(zhí)行動作a時，下一狀態(tài)為s′并且得到獎勵值為r的概率；p(s′|s,a)表示在狀態(tài)s，執(zhí)行動作a時，下一狀態(tài)為s′的概率。

2.2 深度Q網絡

2.2.1神經網絡

深度Q網絡[18](DQN)以Q學習算法為核心，將深度學習和Q學習算法融入到一起。Q學習算法中的狀態(tài)-動作值函數使用神經網絡表示，將狀態(tài)作為神經網絡的輸入，得到當前狀態(tài)的每個動作的價值，根據每個動作的價值選擇要執(zhí)行的動作。通過參數為θ的f網絡近似代替狀態(tài)-動作值函數如式(3)所示。

f(s,a,θ)≈Q(s,a)

(3)

式中：f可以是任意類型的函數；s為狀態(tài)；θ為網絡參數；a為動作；通過函數來近似代替Q值表，減少了內存的使用。

在深度Q網絡中存在兩個結構相同但參數不同的神經網絡，分別為預測網絡Qe和目標網絡Qt。預測網絡會通過時序差分法的誤差不斷更新，計算出Qe估計值，目標網絡則是計算Qt現實值。目標網絡每隔一段時間獲取預測網絡參數進行更新，降低了當前Qe值和目標Qt值之間的相關性，避免神經網絡的訓練參數陷入到局部最優(yōu)解中。

2.2.2記憶回放機制

在最初的深度強化學習中，神經網絡根據輸入的狀態(tài)得到每個動作的Q值，選擇這些Q值中最大的一個。但是這些訓練樣本都是通過前一個狀態(tài)得到的，因此各個狀態(tài)之間有著明顯的關聯性。后來Google的DeepMind團隊在學習過程中加入了記憶回放(Memory Replay)機制[19]，通過從經驗池中隨機獲得訓練樣本，降低樣本之間的相關性，打破了陷入局部最優(yōu)解的可能，使得學習到的策略趨向平穩(wěn)。也正是因為記憶回放機制才使得深度學習順利地應用于強化學習。

3 改進DQN的路徑規(guī)劃算法

3.1 DQN算法設計

隨著研究人員將路徑規(guī)劃的環(huán)境信息進行處理，使得環(huán)境網格化，如果在深度Q網絡算法使用卷積神經網絡可能會產生過擬合，在這種背景之下，本文將多層感知機使用到深度Q網絡算法中，將改進獎勵函數運用到神經網絡每次更新中，提出一種改進后的深度Q網絡路徑規(guī)劃算法。

3.1.1多層感知機

在多層感知機(Multilayer Perceptron,MLP)中除了輸入層和輸出層，中間可以有多個隱層。如圖1所示，MLP含有n個輸入神經元代表輸入n維的數據，m個輸出神經元代表輸出的類別為m種，中間含有一個隱藏層，隱藏層的神經元越多代表模型的擬合能力越強。

圖1 多層感知機結構

圖1中，x為輸入數據，y為輸出在模型訓練的過程中以最小化分類誤差為目標函數。使用反向梯度傳播算法對模型進行訓練，訓練完成后得到使樣本分類誤差最小的一組參數w進行前向傳播得到結果y。單層感知機如式(4)所示。

式中：i為上一層神經元的下標；j為當前層神經元的下標；wij為神經元j的權重。

根據多層感知機可得出DQN算法的兩個網絡的網絡結構圖并且兩個網絡相同，如圖2所示，其中：k表示動作的個數；n和m表示不同網絡層的神經元個數。

圖2 網絡結構

預測網絡輸入是從經驗池中獲得的數據(s,a)，狀態(tài)s為物體位置(x,y)。由三層全連接層計算當物體處于狀態(tài)s時執(zhí)行a動作所獲得的獎勵。目標網絡的輸入是從經驗池中獲取的數據(s′,r)，r表示為狀態(tài)為s執(zhí)行動作為a時獲得的獎勵，將處于s′狀態(tài)下獲得的獎勵與r相加得到兩個動作的獎勵。

3.1.2獎勵函數

在現有的獎勵函數中，當物體處于探索路徑狀態(tài)時，不同動作可能返回相同的固定獎勵值，然而不同動作的相同獎勵值與較優(yōu)的動作選擇關聯性較小，導致更新后的神經網絡與較優(yōu)動作-狀態(tài)值函數擬合較低。因此本文將三次函數引用到獎勵函數中，根據不同動作返回不同獎勵值，將不同的獎勵值應用到神經網絡的更新中，使得更新后的神經網絡與較優(yōu)的動作-狀態(tài)值函數更加擬合。因此本文設置了以目標位置為中心的范數約束如式(5)所示。

式中：p為物體位置；t為目標位置；d為約束距離。

通過范數約束設置獎勵函數，返回物體處于某個狀態(tài)的獎勵值，如式(6)所示。當物體處于探索路徑狀態(tài)時，通過式(5)獲得參數l、h。

R=l×(x-h)3

(6)

式中：參數l確定函數的單調性，并決定圖像的趨向于對稱中心的速度；參數h是X軸的截距；當物體處于探索路徑狀態(tài)而不是終止或尋找到目標狀態(tài)時，x為當前時刻物體到目標之間的歐氏距離；R為物體執(zhí)行動作后的獎勵值。

根據物體狀態(tài)是否滿足式(5)，使用式(6)計算執(zhí)行某動作返回的獎勵值為正獎勵或負獎勵。不同狀態(tài)的獎勵值如表1所示，其中，Value1和Value2分別為設置的到達目標狀態(tài)和撞到障礙物狀態(tài)時返回的獎勵值。

表1 獎勵表

將R設為獎勵函數，在狀態(tài)s下根據表1所獲得的獎勵期望如下：

Rs=E[Rt+1|s=st]

(7)

式中：E為期望；Rs是處在t時刻的狀態(tài)s的下一個時刻所獲得的獎勵期望。因此當前狀態(tài)的動作價值如式(8)所示。

式中：Rt+i為在t+i時刻獲得的獎勵值。

3.1.3動作選擇機制

動作選擇通常會有兩種方式，分別為Exploration(探索)和Exploitation(利用)。為了平衡兩種動作選擇方式使用了ε-貪心算法，該算法采用了ε概率選擇較優(yōu)動作，在1-ε概率內選擇隨機探索。而本文使動作選擇概率ε隨著訓練步數線性增加，通過線性增加ε-動作選擇概率來解決訓練后期存在的過度探索錯過較優(yōu)路徑的問題。

3.2 模型訓練

在模型訓練的每一次迭代中DQN網絡參數更新是從經驗池中隨機取出一批數據。將這些數據傳入到兩個網絡中，在兩個網絡所得到的值的基礎上通過對損失函數梯度下降實現的，損失函數如式(9)所示。

L(θ)=E[(Qt-Qe(s,a,θ))2]

(9)

然后對得到的損失函數求梯度，如式(10)所示。

執(zhí)行N步后，將預測網絡的參數覆蓋目標網絡的參數。其中經驗池中的數據是通過物體不斷與環(huán)境交互獲得的信息(s,a,R,s′)。

通過對損失函數進行梯度下降實現預測網絡的更新如式(11)所示。

式中：η為梯度下降的學習率；θi為上一次的網絡參數。

圖3為DQN更新流程，將當前的環(huán)境狀態(tài)輸入給預測網絡，然后由預測網絡通過動作選擇機制與環(huán)境進行交互，會得到該動作獎勵和下一步狀態(tài)。將此四元組存入到回放記憶單元，當記憶回放單元的記錄滿足隨機存取記憶回放單元記錄個數時，從中隨機取得一小批量樣本并進行訓練。每個N時間步后預測網絡會將函數拷貝給目標網絡，最后根據損失函數進行預測網絡的參數更新。

圖3 DQN更新流程

通過圖3可得改進的DQN算法的路徑規(guī)劃的偽代碼，如算法1所示。

算法1基于DQN的路徑規(guī)劃算入：物體的狀態(tài)s。

輸出：目標網絡參數。

初始化經驗池D

初始化目標網絡Qt和預測網絡Qe參數，網絡參數均服從與期望為0、標準差為0.2的高斯分布，未撞到障礙物的獎勵為0 for episode=1 tokdo

初始化物體位置

While True:

利用ε貪婪策略選擇狀態(tài)動作：

執(zhí)行動作at后得到下一個狀態(tài)st+1

If rect=target:

未撞到障礙物的獎勵為式(6)

通過表1得到的即時回報Rt

將(st,at,Rt,st+1)放入經驗池D

if rect=block or rect=target

break;

隨機從經驗池D中采集一組數據(sj,aj,Rj,sj+1)

設定

利用式(9)對Qe(s,a;θ)和yi求損失函數L根據公式(11)對L進行梯度下降，實現網絡的更新

ε←ε+0.000 01

式中：rect表示物體當前的位置；block代表障礙物的位置；target表示物體目標的位置。

4 實驗仿真與分析

4.1 實驗場景

通過將文獻[17]的實際環(huán)境網格化進行實驗，如圖4所示，將不同的網格連接，以此來模擬不同大小的長方形障礙物，總共有八個障礙。正方形為起點，即物體所在位置；圓形為追逐目標，即目標位置。最后結果獲得的路徑為從起點躲避所有障礙物到達終點的最短路徑。

圖4 仿真環(huán)境

4.2 實驗參數

在實驗中，仿真環(huán)境中每個網格邊長為1，網格的對角線長度為21/2。通過前期獲得訓練獲得目標位置計算范數約束距離d，將(0,d)作為式(6)的零點，則d=l×(0-h)3。設置物體在目標四周距離為0時，狀態(tài)的獎勵值為15，代入式(6)中，得到0=l×(15-h)。由此可得l=-0.2，h=4.24，則獎勵值表示如式(12)所示。

r=-0.2×(x-4.24)3

(12)

因為路徑規(guī)劃的最重要目的就是找到最大的獎勵值，從而找到目標。為了和其他狀況有較大的區(qū)分，到達目標的獎勵為50。而撞到障礙物要比其他狀況獲得的獎勵值要小，獎勵值為-5。當物體處于探索路徑狀態(tài)時，在沒有發(fā)現目標階段則獎勵值為0，當發(fā)現目標之后獎勵值通過式(12)獲得，因此不同狀態(tài)的獎勵值如表2所示。

表2 確定參數的獎勵表

在多層感知機中，如果網絡參數數量過大會出現動作價值的過擬合，如果較小會出現動作價值的欠擬合。為了更好地訓練網絡，將網絡參數的個數設為15。

4.3 實驗結果

在上述實際場景，基于仿真環(huán)境進行實驗，每200次進行目標網絡的參數更新。開始訓練時，因為經驗池沒有記錄，所以開始的前400次訓練在不斷地探索，積累一些記錄并將這些記錄進行存儲。因為隨機取出記錄的個數為100，將訓練設置400后可以將樣本的相關性降得更低，當400次訓練結束后，開始通過隨機取出經驗池中的記錄進行網絡的訓練，使用梯度下降算法更新網絡的參數。剛開始時因為經驗池里面沒有記錄，無法取出進行訓練，所以開始的路徑會出現各種碰撞障礙物的情況，無法找出最優(yōu)路徑。如圖5所示。

圖5 初始路徑尋找

而隨著訓練次數的提升，經驗池里面的記錄增加，網絡參數的更新，并且ε-貪心算法中的ε=0.9也會以0.000 01的速度隨著路徑探索而慢慢增加，ε的上限為0.999 9，以此將動作選擇慢慢趨向于利用方式，但不會完全使用利用方式。因此使得路徑的選擇就會越來越好，最后獲得最優(yōu)路徑，如圖6所示。

圖6 最優(yōu)路徑

本文與DQN算法和Action-critic算法進行比較，當物體訓練1 000輪時三種算法的不同獎勵值如圖7-圖9所示。圖7為本文算法的獎勵值，開始訓練的前400步，因為是隨機探索的，沒有根據在經驗池里的記錄更新網絡參數，所以獎勵值會比較亂。而隨著前300次的訓練結束，經驗池有充足的經驗，則可以來進行參數更新。隨著訓練次數的增加，ε越來越大，動作選擇越來越趨向于某個狀態(tài)的最大獎勵的動作，獎勵值也就變得平穩(wěn)。圖8和圖9分別表示普通DQN算法和Action-critic算法的獎勵值。

圖7 本文算法1 000步獎勵值

圖8 DQN算法1 000步獎勵值

圖9 Action-critic算法1 000步獎勵值

本文選取探索規(guī)劃輪數為評價指標，將DQN算法和Action-critic算法作為對照算法，比較了三個算法的總規(guī)劃步數，如圖10所示。

圖10 總規(guī)劃輪數

觀察圖10可以發(fā)現在達到相同的效果目的下，本文的總探索規(guī)劃步數比其他兩種算法明顯減少，表明本文算法有更好的路徑規(guī)劃和規(guī)避障礙的能力。

5 結 語

本文提出一種基于深度Q網絡的路徑規(guī)劃算法，該算法可以幫助物體進行路徑規(guī)劃、障礙規(guī)避和目標跟蹤。與基于DQN和基于Action-critic的路徑規(guī)劃算法相比，實驗結果表明本文算法與其他方法在相同環(huán)境下，總探索步數更少，尋找最佳路徑速度更快。因此，本文方法在路徑規(guī)劃方面具有更快的規(guī)避障礙的能力和跟蹤速度。