基于深度強化學習和動態(tài)窗口法的移動機器人路徑規(guī)劃?

王鵬凱 梁中華 楊 闊 胡雅悅 唐 趙

（長安大學 西安 710064）

1 引言

近年來，移動智能機器人技術飛速發(fā)展，機器人應用到各個領域，如倉儲物流、搬運貨物、自動駕駛等。因此，移動機器人探索不明、復雜、動態(tài)的環(huán)境成為機器人應用的一個普遍問題［1］。路徑規(guī)劃算法是移動機器人實現(xiàn)自主導航的關鍵技術之一［2］，它主要解決機器人如何以最快的速度、最短的距離從起點到達目標點的問題。在機器人移動環(huán)境中，有可能存在各種各樣的障礙物，因此通過路徑規(guī)劃為機器人找到從起點到目標點的無碰撞最優(yōu)路徑［3］。

利用移動機器人中的傳感器，路徑規(guī)劃算法能夠?qū)崟r獲取機器人附近的環(huán)境信息，從而使機器人規(guī)避障礙物，如動態(tài)窗口法（DWA）。使用這種算法，能夠直接在速度空間上模擬機器人的移動軌跡，使移動機器人具有良好的避障能力［4］。然而隨著移動機器人面臨的環(huán)境越來越復雜且不可預測，動態(tài)窗口法并不能夠迅速適應這種復雜多變的環(huán)境［5］。面對復雜多變的環(huán)境，移動機器人路徑規(guī)劃算法需要具有自學習、自適應和魯棒的能力。

另一方面，智能體可以通過強化學習與環(huán)境進行動態(tài)的交互和試錯以獲得相應的獎勵反饋，從而找到最優(yōu)策略或者最大正獎勵［6］。因此，強化學習算法已經(jīng)開始應用于移動機器人路徑規(guī)劃問題［7～8］。Q-learning算法是強化學習算法中一種典型的無模型算法，不需要建立模型就能夠保持收斂性，但是需要建立一個Q值表來存儲信息。在復雜多變的環(huán)境下，這種方法需要建立一個巨大的Q值表，導致消耗大量時間和收斂速度慢，并且容易出現(xiàn)維數(shù)災難［9］。因此，Q-learning算法很難應用到大規(guī)模狀態(tài)-動作空間的移動機器人路徑規(guī)劃中。為了應對大規(guī)模狀態(tài)-動作空間集合，2013年Minh等提出將神經(jīng)網(wǎng)絡和強化學習相結合，通過神經(jīng)網(wǎng)絡的輸出近似計算Q值，然后訓練該神經(jīng)網(wǎng)絡來逼近狀態(tài)-動作值函數(shù)，該算法被稱為深度Q網(wǎng)絡（DQN）［10～11］。但DQN算法應用于路徑規(guī)劃問題時，仍舊存在很多問題，比如，如何保證機器人通過障礙物時保持安全的速度；此外，如果地圖的探索空間過大，智能體仍然需要大量時間和計算量來獲得所需經(jīng)驗。

本文在現(xiàn)有的路徑規(guī)劃算法和深度Q網(wǎng)絡基礎上，提出一種基于深度強化學習和動態(tài)窗口法的融合路徑規(guī)劃算法。該融合路徑規(guī)劃算法具備以下優(yōu)點。

1）具備“動態(tài)窗口”特性，將機器人的運動直接作用在速度空間上，通過機器人的線速度、角速度和旋轉(zhuǎn)方向來控制機器人的移動，使機器人能夠保持安全的速度行駛，避免速度過快發(fā)生碰撞、速度過慢耗時過高。

2）在卷積神經(jīng)網(wǎng)絡模型上對狀態(tài)-動作空間過大的地圖環(huán)境進行處理，同時對ε-greedy策略進行改進，然后訓練這個神經(jīng)網(wǎng)絡。仿真實驗結果表明，使用該融合算法能夠有效避免維數(shù)災難和收斂慢的問題，而且能夠保證機器人對復雜多變的環(huán)境也具有很強的魯棒性和實時性。

2 基于動態(tài)窗口法的傳統(tǒng)路徑規(guī)劃方法

動態(tài)窗口法（DWA）［12］的實現(xiàn)分為三部分：建立模型、速度采樣和軌跡評價。通過這三部分的實現(xiàn)，移動機器人的驅(qū)動能夠直接作用在速度空間（v，ω）上，并限制在可行的動態(tài)空間中。

首先，要想模擬機器人的移動軌跡，需要知道機器人的運動模型。設定機器人不是全向移動，即只能前進、左轉(zhuǎn)和右轉(zhuǎn)。利用模擬速度將機器人相鄰時刻的運動映射到機器人坐標系的x軸和y軸后，可以得到機器人在時間t+1時刻的坐標。因此，移動機器人的軌跡推導公式為

其中，x和y是機器人在坐標系上x軸和y軸的坐標；Δt是機器人相鄰動作的時間間隔；v是機器人的線速度，ω是機器人的角速度；φ是機器人與x軸的夾角。

然后，對機器人速度采樣。在速度空間（v，ω）中存在多組速度，但是由于機器人本身性能以及環(huán)境的限制，可以將采樣速度限制在允許的范圍內(nèi)?？紤]三方面的速度限制。

1）考慮機器人本身最大速度最小速度的限制：

2）考慮機器人本身受電機性能的影響，存在最大加減速的限制：

其中，νa和νb分別是機器人的最大加、減線速度；ωa和ωb分別是機器人的最大加、減角速度。

3）為了使機器人始終能夠保持安全的距離行駛，避免與障礙物發(fā)生碰撞。因此，在最大減速度的約束下，速度也存在一個限制范圍：

其中，dist(ν，ω)是速度所對應軌跡離障礙物最近的距離。

所以，機器人速度的實際采樣范圍是上述三種速度之間的交集：

最后，利用評價函數(shù)在若干組軌跡中選出最優(yōu)軌跡。評價函數(shù)如下：

其中，heading(ν，ω)是機器人在當前設定的采樣速度下，到達模擬軌跡末端的朝向與目標之間的角度差距。公式如下：

νelοcity(ν，ω)用來評價當前軌跡速度的大小，能夠促進機器人快速到達目標。

在計算軌跡的評價函數(shù)時，上述三個部分不是直接相加，而是先對它們進行平滑處理之后，再相加。以heading(ν，ω)為例，公式如下：

其中，i為待評價的當前軌跡；n為所有采樣軌跡的總數(shù)。

3 Q-learning算法

1989年，Watkins等提出了一種典型的無模型強化學習算法，即Q-learning算法［13］。該算法不需要建立模型，而是通過與環(huán)境不斷“試錯”來找到最優(yōu)策略。在強化學習中，各類決策問題通常建立在馬爾科夫決策過程（MDP）中進行，最終通過一系列的決策使得整體獲得的獎勵最大化。馬爾科夫決策過程包含五個關鍵因素：狀態(tài)空間S，動作空間A，狀態(tài)轉(zhuǎn)移函數(shù)P，折扣因子γ，獎勵函數(shù)R。

Learning算法利用迭代［8］的方法來使狀態(tài)-動作價值函數(shù)逼近目標函數(shù)。首先，將每個狀態(tài)下選擇的動作所得到的狀態(tài)-動作值函數(shù)存儲在一個Q值表中；然后，通過機器人與環(huán)境不斷交互來得到獎勵函數(shù)R；最后迭代更新Q值表，以此來獲得每個狀態(tài)下動作的Q值。Q-learning算法的更新迭代方式為

其中，α為學習率，s為當前狀態(tài)，s'為下一狀態(tài)。

4 卷積神經(jīng)網(wǎng)絡

在機器人路徑規(guī)劃中，障礙物檢測和識別是實現(xiàn)機器人避障的關鍵部分。隨著深度學習的快速發(fā)展，卷積神經(jīng)網(wǎng)絡（CNN）［14］在目標檢測和識別領域取得了重大成果。

在機器人學方面，卷積神經(jīng)網(wǎng)絡用來感知視覺導航的環(huán)境信息［15］。卷積神經(jīng)網(wǎng)絡將圖像作為輸入數(shù)據(jù)，經(jīng)過連續(xù)的卷積層、池化層的處理來獲取圖像的特征圖；然后，對特征圖進行特征檢測和提取，得到所需的圖像特征；最后，通過全連接層得到輸出結果。卷積神經(jīng)網(wǎng)絡作為一種經(jīng)典的視覺學習方法，能夠通過自學習［1］來提取特征模型。

圖1顯示了卷積神經(jīng)網(wǎng)絡的結構。假設機器人的運動方向有三種，其中a0表示前進，a1表示左轉(zhuǎn)，a2表示右轉(zhuǎn)，則動作空間就可以表示為A=［a0，a1，a2］。當機器人的當前狀態(tài)s輸入到卷積神經(jīng)網(wǎng)絡后，經(jīng)過兩個卷積層、兩個池化層，將600×600×3大小的圖像變成28×28×24大小的特征圖；然后，經(jīng)過兩個全連接層，最終得到一個1×3向量的輸出，這三個向量分別對應了機器人移動的三種動作。

圖1 卷積神經(jīng)網(wǎng)絡的結構示意圖

5 基于深度強化學習和動態(tài)窗口法的融合路徑規(guī)劃方法

深度強化學習（DRL）［16］就是將強化學習和神經(jīng)網(wǎng)絡相結合的一種算法，DQN算法［11］就是深度強化學習中一種使用較為廣泛的算法之一。DQN算法不使用迭代更新的方式來優(yōu)化方程，而是使用函數(shù)逼近器來估計方程［6］。DQN算法通過深度學習卷積神經(jīng)網(wǎng)絡去逼近Q值，其Q值的估計可近似為公式：

式中，θ為DQN中Q網(wǎng)絡的加權參數(shù)。DQN的優(yōu)點就是在狀態(tài)-動作空間對的數(shù)量有很多的情況下，Q值都可以快速求解，不需要進行大量的實驗就可以使算法收斂。

5.1 基于深度強化學習和動態(tài)窗口法的融合路徑規(guī)劃框架

為了使機器人能夠在復雜多變的環(huán)境下完成路徑規(guī)劃的任務，同時使機器人的移動具備動態(tài)窗口的特性，因此將深度強化學習和動態(tài)窗口法相融合來進行移動機器人路徑規(guī)劃。

圖2顯示了基于深度強化學習和動態(tài)窗口法的融合路徑規(guī)劃框架示意圖。首先，將機器人的運動環(huán)境以RGB圖像的形式輸入，通過卷積神經(jīng)網(wǎng)絡來處理圖像以降低計算復雜度；然后，機器人在當前狀態(tài)s，通過與環(huán)境（動態(tài)窗口部分）的交互，利用ε-greedy策略來選擇動作，之后，機器人會進入下一狀態(tài)s'，而且在交互過程中會產(chǎn)生一個獎勵r；最終，機器人通過選擇最大Q值所對應的動作進行移動。訓練樣本可以通過經(jīng)驗存放的機制來獲得，之后使用隨機梯度下降和反向傳播算法來更新網(wǎng)絡參數(shù)。經(jīng)驗存放機制的主要思想就是，在訓練期間，機器人在每個時間點t的運動信息都保存在一個經(jīng)驗元祖U中，U=（s，s'，a，r）。然后，將這些經(jīng)驗元祖都保存在經(jīng)驗存放池中以更新DQN的權重來訓練數(shù)據(jù)。

圖2 基于DQN和DWA的融合路徑規(guī)劃框架示意圖

5.2 獎懲功能設置

獎勵函數(shù)設置為式（11）：

當機器人到達目標點時，獎勵值設為200，使機器人能夠在不斷學習過程中盡可能快速到達目標點。設立一個距離閾值τ，當dist（v，ω）<τ時，獎勵值設為-1000，表示障礙物與機器人的距離過近，有可能與障礙物發(fā)生碰撞；同理，當dist（v，ω）>τ時，獎勵值設為100，使機器人能夠保持安全恰當?shù)乃俣刃旭偂?/p>

5.3 ε-greedy策略設置

為了驗證基于深度強化學習和動態(tài)窗口法的融合算法進行移動機器人路徑規(guī)劃的性能，我們在200輪起點、目標點隨機選擇的路徑規(guī)劃訓練過程中對機器人以ε-greedy策略進行評估。因此，對于ε-greedy策略，創(chuàng)建了一個獨特的函數(shù)來優(yōu)化性能，以更好地去適應每個參數(shù)。公式如下：

其中，ε_ini代表最初的ε-greedy策略；E代表機器人路徑規(guī)劃所經(jīng)歷的輪數(shù)。這個函數(shù)呈指數(shù)下降的趨勢，使機器人到最后訓練過程選擇最優(yōu)動作的概率大大增加。

6 仿真實驗與結果分析

6.1 RGB實驗環(huán)境與基本設置

本文設置了一個RGB圖像作為機器人路徑規(guī)劃的實驗環(huán)境，如圖3所示。該RGB圖像尺寸大小為600×600，圖中白色部分為障礙物，黑色部分為機器人可通行區(qū)域。本文在該環(huán)境下進行路徑規(guī)劃實驗，狀態(tài)空間包括RGB圖像中所有可能的位置，動作空間為三個可能的動作（左轉(zhuǎn)、右轉(zhuǎn)和前進）。在訓練過程中，每一輪路徑規(guī)劃任務的起點、目標點都是隨機分布的（要求：起點和目標點不能選擇在障礙物內(nèi)部）。

圖3 機器人路徑規(guī)劃實驗環(huán)境

6.2 實驗參數(shù)設置

本文在自定義的RGB圖像上進行移動機器人路徑規(guī)劃實驗，實驗中所使用的參數(shù)如表1所示。

表1 論文實驗中所使用的參數(shù)列表

6.3 實驗結果及分析

在本節(jié)中，我們通過對機器人路徑規(guī)劃的訓練結果、成功率和平均Qmax值變化這三個方面來衡量該融合路徑規(guī)劃算法的性能，這些訓練都是實時進行的。

圖4展示了機器人路徑規(guī)劃的訓練結果。為了實現(xiàn)機器人從起點到目標點的無碰撞路徑規(guī)劃，機器人需要通過與環(huán)境不斷地交互進行訓練，才能從當前狀態(tài)轉(zhuǎn)移到下一狀態(tài)，進而到達目標點。在訓練的過程中，可能會出現(xiàn)機器人距離障礙物過近的狀況，這時機器人可能與障礙物發(fā)生碰撞，機器人需要在該位置調(diào)整方向以保持安全距離行駛。因此，我們認定該狀態(tài)為訓練失敗的狀態(tài)。觀察圖4可知，在訓練前期，機器人對于訓練環(huán)境是未知的，處于探索階段，從而導致機器人的訓練波動較大。因此，機器人每輪路徑規(guī)劃的訓練總次數(shù)和訓練失敗次數(shù)無規(guī)則變化。隨著訓練輪數(shù)的增加，機器人對環(huán)境有了充分的了解，訓練能夠維持在穩(wěn)定的狀態(tài)，這表明該融合算法能夠使機器人在復雜多變的環(huán)境中也具有很強的泛化能力。

圖4 機器人路徑規(guī)劃的訓練結果圖

此外，圖5繪制了機器人在訓練過程中每輪路徑規(guī)劃成功率的變化曲線圖。從圖5中可以看出，使用該融合算法進行機器人路徑規(guī)劃，成功率可以維持在99.20%左右。同時，成功率的變化與機器人訓練總次數(shù)和訓練失敗次數(shù)密切相關。

圖5 機器人在訓練過程中成功率的變化曲線圖

圖6示出了在訓練過程中機器人的平均Qmax值變化曲線。從圖6可以看出，在前期探索階段，機器人所處環(huán)境是未知的，選擇動作的隨機概率比較大，導致機器人在當前狀態(tài)下執(zhí)行的動作可能并非Q值最大的動作，因此，在前期訓練過程中平均Qmax值較低。隨著訓練輪數(shù)的增加，機器人對環(huán)境有了充分的了解，從而進入了利用先驗知識的階段，機器人能夠選擇當前狀態(tài)下Q值最大的動作執(zhí)行，所以平均Qmax值呈現(xiàn)上升的變化趨勢。最終，平均Qmax值能夠穩(wěn)定在67左右，算法收斂。因此，使用該融合算法，機器人進行路徑規(guī)劃時具有平滑的學習能力，在復雜多變的環(huán)境下也具有魯棒性。

圖6 訓練過程中機器人平均Qmax值的變化曲線圖

7 結語

本文提出一種基于深度強化學習和動態(tài)窗口法的融合路徑規(guī)劃算法。針對現(xiàn)有路徑規(guī)劃算法中存在的不足之處，將深度強化學習和動態(tài)窗口法相融合，使機器人在復雜多變的環(huán)境下也具有動態(tài)窗口的特性，從而將機器人的驅(qū)動直接控制在速度空間上，保證機器人能夠保持安全的速度行駛，縮減耗時。然后，通過訓練這個新的深度Q網(wǎng)絡來近似逼近狀態(tài)-動作值函數(shù)。實驗結果表明，在復雜多變、動態(tài)未知的環(huán)境下，使用該融合算法可使機器人能夠通過實時調(diào)整機器人的速度和方向來獲得卓越的路徑規(guī)劃性能，具有很好的魯棒性和實時性。