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

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

（長安大學 西安 710064）

1 引言

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

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

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

本文在現有的路徑規劃算法和深度Q網絡基礎上，提出一種基于深度強化學習和動態窗口法的融合路徑規劃算法。該融合路徑規劃算法具備以下優點。

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

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

2 基于動態窗口法的傳統路徑規劃方法

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

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

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

然后，對機器人速度采樣。在速度空間（v，ω）中存在多組速度，但是由于機器人本身性能以及環境的限制，可以將采樣速度限制在允許的范圍內。考慮三方面的速度限制。

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

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

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

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

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

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

最后，利用評價函數在若干組軌跡中選出最優軌跡。評價函數如下：

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

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

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

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

3 Q-learning算法

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

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

其中，α為學習率，s為當前狀態，s'為下一狀態。

4 卷積神經網絡

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

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

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

圖1 卷積神經網絡的結構示意圖

5 基于深度強化學習和動態窗口法的融合路徑規劃方法

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

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

5.1 基于深度強化學習和動態窗口法的融合路徑規劃框架

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

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

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

5.2 獎懲功能設置

獎勵函數設置為式（11）：

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

5.3 ε-greedy策略設置

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

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

6 仿真實驗與結果分析

6.1 RGB實驗環境與基本設置

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

圖3 機器人路徑規劃實驗環境

6.2 實驗參數設置

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

表1 論文實驗中所使用的參數列表

6.3 實驗結果及分析

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

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

圖4 機器人路徑規劃的訓練結果圖

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

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

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

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

7 結語

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