基于深度強(qiáng)化學(xué)習(xí)和動態(tài)窗口法的移動機(jī)器人路徑規(guī)劃?

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

（長安大學(xué) 西安 710064）

1 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

νelοcity(ν，ω)用來評價當(dāng)前軌跡速度的大小，能夠促進(jìn)機(jī)器人快速到達(dá)目標(biāo)。

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

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

3 Q-learning算法

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

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

其中，α為學(xué)習(xí)率，s為當(dāng)前狀態(tài)，s'為下一狀態(tài)。

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

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

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

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

圖1 卷積神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)示意圖

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

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

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

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

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

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

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

5.2 獎懲功能設(shè)置

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

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

5.3 ε-greedy策略設(shè)置

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

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

6 仿真實驗與結(jié)果分析

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

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

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

6.2 實驗參數(shù)設(shè)置

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

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

6.3 實驗結(jié)果及分析

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

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

圖4 機(jī)器人路徑規(guī)劃的訓(xùn)練結(jié)果圖

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

圖5 機(jī)器人在訓(xùn)練過程中成功率的變化曲線圖

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

圖6 訓(xùn)練過程中機(jī)器人平均Qmax值的變化曲線圖

7 結(jié)語

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