基于梯度獎勵的深度強化學(xué)習(xí)移動機器人路徑規(guī)劃

喻凱旋，林富生，宋志峰，余聯(lián)慶

(1.武漢紡織大學(xué)機械工程與自動化學(xué)院，湖北武漢 430200；2.三維紡織湖北省工程研究中心，湖北武漢 430200；3.湖北省數(shù)字化紡織裝備重點實驗室，湖北武漢 430200)

0 前言

路徑規(guī)劃是當(dāng)今移動機器人研究的一大熱點，同時也是一大難點。路徑規(guī)劃是指在起始點與終點之間尋找出一條合適的無碰撞路徑[1]，在移動機器人導(dǎo)航中起到重要作用。隨著使用場景逐漸復(fù)雜以及安全要求不斷提高，如何快速、準(zhǔn)確地規(guī)劃行駛路徑是一個難題。傳統(tǒng)路徑規(guī)劃算法有快速搜索隨機數(shù)[2](Rapidly-exploring Random Trees，RRT)、蟻群算法[3](Ant Colony Optimization，ACO)和遺傳算法[4](Genetic Algorithm，GA)等。以上算法經(jīng)多次改進均有廣泛應(yīng)用，但都存在相應(yīng)缺陷，例如模型建造困難、搜索能力不足、容易陷入局部最優(yōu)等。

機器學(xué)習(xí)的相關(guān)研究最近突飛猛進，機器人打敗人類精英將不再是夢想。針對機器學(xué)習(xí)的學(xué)習(xí)能力，許多研究者嘗試將機器學(xué)習(xí)應(yīng)用到路徑規(guī)劃中。深度強化學(xué)習(xí)在路徑規(guī)劃上應(yīng)用最廣的是DQN(Deep Q-Network，DQN)[5]算法，它結(jié)合了深度學(xué)習(xí)的感知能力和強化學(xué)習(xí)的決策能力。DQN使用神經(jīng)網(wǎng)絡(luò)代替了Q-learning的Q表，解決了狀態(tài)過多時Q表的“維度災(zāi)難”問題，同時增加了經(jīng)驗回放和目標(biāo)網(wǎng)絡(luò)，提高經(jīng)驗利用率的同時改善了數(shù)據(jù)時序關(guān)聯(lián)的問題，但傳統(tǒng)的DQN算法存在過估計、收斂慢、稀疏獎勵等問題。

對于深度強化學(xué)習(xí)算法中的問題，徐志雄等[6]采用目標(biāo)動態(tài)融合機制，將DQN與Sarsa算法融合，提出了DTDQN算法，既提高了訓(xùn)練效率，也緩解了過估計問題。王軍等人[7]將后見經(jīng)驗回放(Hindsight Experience Replay，HER)算法與DQN結(jié)合，采用置信區(qū)上界的方式選擇下一步的運動方向，輸入原始RGB圖像，輸出4個動作的Q值，一定程度上緩解了稀疏獎勵帶來的難以收斂問題。袁帥等人[8]提出了D3QN的路徑規(guī)劃算法，引入長短時記憶網(wǎng)絡(luò)(Long Short-Term Memory，LSTM)，提高記憶和認知障礙物的能力，采用優(yōu)先經(jīng)驗回放機制(Prioritized Experience Replay，PER)提高重要樣本的利用率，明顯提升了神經(jīng)網(wǎng)絡(luò)的收斂速度。

針對深度強化學(xué)習(xí)在路徑規(guī)劃上收斂過慢以及稀疏獎勵問題，本文作者提出了梯度獎勵機制，全新設(shè)計的獎勵函數(shù)提高了環(huán)境對機器人的反饋，結(jié)合去首動態(tài)貪婪策略以及基于均方誤差的優(yōu)先經(jīng)驗回放可有效緩解以上問題。

1 強化學(xué)習(xí)

強化學(xué)習(xí)可以看作是一個剛出生的“嬰兒”通過不斷學(xué)習(xí)，逐漸成長為一個“成人”的過程[9]。智能體通過與環(huán)境互動，通過環(huán)境給予的獎勵來判斷當(dāng)前動作的好壞。強化學(xué)習(xí)的過程如圖1所示，智能體根據(jù)當(dāng)前狀態(tài)st做出動作at，環(huán)境根據(jù)動作給出當(dāng)前動作的獎勵rt和下一時刻的狀態(tài)st+1，強化學(xué)習(xí)的目標(biāo)就是最大化期望累計獎勵。

圖1 強化學(xué)習(xí)過程

1.1 傳統(tǒng)強化學(xué)習(xí)

貝爾曼方程是用來估計從當(dāng)前時刻開始未來的所有累計獎勵總和，記為回報值Ut，如公式(1)所示：

Ut=Rt+γRt+1+γ2Rt+2+γ3Rt+3+……

(1)

式中：γ為折扣率，值介于0和1之間，γ值越大代表未來獎勵的權(quán)重越大。

Q-learning采用時序差分(Temporal Difference，TD)算法，利用貝爾曼方程估計未來所有獎勵的總和，是一種動態(tài)迭代的強化學(xué)習(xí)算法。迭代公式可以寫為公式(2)：

(2)

式中：α為學(xué)習(xí)率，表示更新Q值時，TD-error所占比重的大小。

1.2 深度強化學(xué)習(xí)算法

DQN使用神經(jīng)網(wǎng)絡(luò)代替Q表，解決了狀態(tài)過多時的維度災(zāi)難問題。傳統(tǒng)DQN在尋找最優(yōu)動作時都是根據(jù)最大Q值選擇，在網(wǎng)絡(luò)更新時容易產(chǎn)生過估計問題，對4個動作不均勻的過估計會影響動作決策。解決過估計問題常用的優(yōu)化方式有DDQN[10](Double DQN，DDQN)和 Dueling DQN[11]。DDQN的目標(biāo)值計算如公式(3)所示，利用當(dāng)前網(wǎng)絡(luò)計算下一狀態(tài)的最優(yōu)動作，然后將這個動作代入目標(biāo)網(wǎng)絡(luò)重新計算Q值。目標(biāo)網(wǎng)絡(luò)具有一定的遲緩性，因此DDQN可以在一定程度上降低DQN的高估問題。

(3)

argmax為當(dāng)前集合對應(yīng)值最大的動作序號。

Dueling DQN的優(yōu)化方式在神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)上，如圖2所示，將DQN輸出的Q值變?yōu)闋顟B(tài)價值函數(shù)V(s)與動作優(yōu)勢函數(shù)A(s，a)的和，如公式(4)所示：

Q(s，a；ω，α，β)=V(s；ω，β)+A(s，a；ω，α)

(4)

Dueling DQN存在一種特殊情況，如果狀態(tài)價值函數(shù)V(s)為0時，此時動作優(yōu)勢函數(shù)A(s，a)就等于Q值[12]。所以通常使用預(yù)測動作的A值減去其平均值作為動作優(yōu)勢函數(shù)，使所有動作的A值相加和為零，如公式(5)所示：

(5)

相較于DQN，Dueling DQN在網(wǎng)絡(luò)參數(shù)更新時，可以學(xué)習(xí)到當(dāng)前狀態(tài)對應(yīng)的狀態(tài)價值函數(shù)V(s)的值，普通DQN只能學(xué)習(xí)到當(dāng)前狀態(tài)下對應(yīng)的動作大的Q值，在一些特殊情況下，狀態(tài)的選擇優(yōu)于動作選擇時，例如路徑規(guī)劃中靠近終點的一些位置，這些位置上的獎勵值顯然需要優(yōu)于距離目標(biāo)點較遠位置的獎勵值，此時Dueling DQN在Q值估計的精準(zhǔn)度上有更好的效果。

Dueling DQN網(wǎng)絡(luò)更新如公式(6)所示：

(6)

2 改進深度強化學(xué)習(xí)算法

深度強化學(xué)習(xí)在簡單環(huán)境下經(jīng)過多次訓(xùn)練，可以達到較好的成功率，但效率低。而在復(fù)雜環(huán)境下，由于狀態(tài)數(shù)量多，模型復(fù)雜，可能出現(xiàn)無法收斂的情況。在多次實驗中發(fā)現(xiàn)深度強化學(xué)習(xí)在小范圍地圖下的路徑規(guī)劃效果遠遠優(yōu)于大范圍地圖?；谶@一特性，本文作者從獎勵機制入手，劃分獎勵區(qū)域縮小探索范圍，同時在探索策略和經(jīng)驗回放上做相應(yīng)的優(yōu)化設(shè)計。具體方法如下：

2.1 改進獎勵函數(shù)

獎懲政策是強化學(xué)習(xí)里面一個非常重要的參數(shù)，合適的獎勵函數(shù)可以使智能體與環(huán)境獲得更多的交互[13]。在路徑規(guī)劃中，傳統(tǒng)的二分獎勵函數(shù)設(shè)置為：到達目標(biāo)點獎勵為1，碰到障礙物或超出邊界獎勵為-1，其余情況下為0。

傳統(tǒng)獎勵函數(shù)將目標(biāo)點與障礙物區(qū)分，可以讓機器人明確自己的目標(biāo)，此方法只有當(dāng)機器人首次探索到目標(biāo)點后，機器人才會學(xué)到正向的獎勵。對于復(fù)雜的大尺寸環(huán)境，機器人只能在安全區(qū)域隨機探索，探索時間長、樣本利用率低，可能造成無法收斂的情況。針對傳統(tǒng)獎勵函數(shù)的弊端，本文作者重新設(shè)計獎勵函數(shù)，提出一種梯度獎勵機制，劃分獎勵分布區(qū)域，誘導(dǎo)機器人逐步縮小探索范圍，同時讓機器人在安全區(qū)域內(nèi)可以獲得正向獎勵。獎勵分布如圖3所示。

根據(jù)起始點與目標(biāo)點的位置，可將環(huán)境劃分為4個區(qū)域，包括緩沖區(qū)、探索區(qū)、臨近區(qū)以及目標(biāo)區(qū)。緩沖區(qū)為最外層區(qū)域，此區(qū)域被視為遠離目標(biāo)點，用于起始點附近有障礙物的情況，此時可以起緩沖作用。探索區(qū)為起始點向目標(biāo)點移動的開始區(qū)域，此時移動機器人以探索為主，搜索障礙物區(qū)域并向內(nèi)層靠近。臨近區(qū)為路徑總長的中部區(qū)域，距離目標(biāo)點的距離約為總長的一半。目標(biāo)區(qū)為最接近目標(biāo)點的區(qū)域，搜索到目標(biāo)點所需時間最短。

獎勵函數(shù)如公式(7)所示：

(7)

式中：Δht為t時刻機器人距離目標(biāo)點的歐幾里得距離；G為目標(biāo)點；T為安全區(qū)域集合；H為障礙物集合；η為獎勵系數(shù)，值與Δht有關(guān)，如公式(8)所示：

(8)

式中：H為起始點距離終點的總長度。

在距離目標(biāo)點越近的范圍，所對應(yīng)的η值會越大，同時采用突變的更新方式，改變不同區(qū)域內(nèi)獎勵值的大小，打破了邊緣位置上數(shù)據(jù)關(guān)聯(lián)性。突出強調(diào)4種不同的區(qū)域帶來的獎勵梯度，讓探索的范圍逐次減小，改善其盲目探索的特點，對移動機器人的運動起到指引的作用。

2.2 改進探索策略

在DQN中，通常以當(dāng)前狀態(tài)的最大Q值的動作作為下一步的動作，在網(wǎng)絡(luò)訓(xùn)練不完全時，容易出現(xiàn)探索區(qū)域過小或陷入局部最優(yōu)等情況。貪婪策略利用隨機數(shù)n和探索因子ε可以實現(xiàn)探索與利用的平衡。首先生成一個隨意數(shù)n，若n>ε，則選擇Q值最大的動作；反之，隨機選擇一個動作。在隨機選擇動作的時候，仍有概率會選擇最大Q值的動作，未達到探索的效果。因此，本文作者提出一種去首動態(tài)貪婪策略，在探索階段，先排除最大Q值的動作，然后在剩余動作里面隨機選擇，所有動作的集合表示為A，去除最大Q值的動作集合為A-，動作選擇函數(shù)如公式(9)所示：

(9)

探索因子ε代表隨機探索環(huán)境的程度，陌生環(huán)境下，探索因子可認為隨著探索次數(shù)增加而逐漸減小，可加速網(wǎng)絡(luò)模型訓(xùn)練。對此，本文作者采用變化率調(diào)節(jié)策略，ε遵循二次函數(shù)分布，如式(10)所示：

εt=k(x-αmax)2+αmin

(10)

式中：x為當(dāng)前的回合數(shù)；αmax為最大探索率；αmin為最小探索率。

2.3 改進經(jīng)驗回放

優(yōu)先經(jīng)驗回放使用sum tree的結(jié)構(gòu)形式儲存數(shù)據(jù)，數(shù)據(jù)抽取的概率與優(yōu)先級的大小成正比[14]。優(yōu)先級大的數(shù)據(jù)有更高的抽取概率，同時優(yōu)先級小的數(shù)據(jù)也有被抽取的可能，保證樣本多樣性的同時達到重要樣本的最大利用率。本文作者提出基于均方誤差的改進優(yōu)先經(jīng)驗回放機制，如公式(11)所示：

(11)

數(shù)據(jù)抽取的過程類似于蒙特卡洛積分，不同的數(shù)據(jù)估計的精準(zhǔn)度不同。重要性采樣(Importance Sampling)是一種人為干預(yù)抽樣分布的方法[15]，對重要性高的數(shù)據(jù)加權(quán)一個重要性權(quán)重，使其重要性在整體上達到平均。樣本概率分布和重要性采樣權(quán)重如公式(12)，(13)所示：

(12)

(13)

式中：α和β介于0和1之間，用于適當(dāng)調(diào)整優(yōu)先級的大小，不改變優(yōu)先級分布。

2.4 總體流程

整體流程如圖4所示。首先通過Dueling DQN結(jié)構(gòu)生成當(dāng)前網(wǎng)絡(luò)和目標(biāo)網(wǎng)絡(luò)，其中隱藏層為4層，每層包含64個神經(jīng)元，激活函數(shù)為ReLU函數(shù)。網(wǎng)絡(luò)參數(shù)分別為ω和ω-，然后利用去首動態(tài)貪婪策略得到基于狀態(tài)s的動作a，與環(huán)境交互獲得下一個狀態(tài)s-和獎勵r，并將四元組儲存到經(jīng)驗回放池，使用優(yōu)先經(jīng)驗回放抽取Batch組數(shù)據(jù)，利用當(dāng)前網(wǎng)絡(luò)和目標(biāo)網(wǎng)絡(luò)生成預(yù)測值和TD目標(biāo)值，計算均方誤差后采用梯度下降更新當(dāng)前網(wǎng)絡(luò)參數(shù)ω，最后每隔C步更新目標(biāo)網(wǎng)絡(luò)參數(shù)ω-。

圖4 整體流程

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

實驗環(huán)境為CPU i5-12500H、GPU RTX 3050Ti、Python3.9、Tensorflow2.6.0、Cuda11.5，利用Python-Tkinter圖形化界面構(gòu)建仿真地圖環(huán)境。其中黑色方塊代表障礙物，紅色方塊代表移動機器人，黃色圓圈代表終點。機器人有“上”“下”“左”“右”4種移動方式，遇到障礙物、超出邊界和到達終點代表回合結(jié)束。本文作者設(shè)置了小范圍地圖和大范圍地圖，分別如圖5和圖6所示。比較不同地圖下原始算法和改進算法的結(jié)果，驗證了改進算法的有效性。超參數(shù)設(shè)置如表1所示。

表1 超參數(shù)設(shè)置

圖5 小范圍地圖 圖6 大范圍地圖

3.1 小范圍地圖對比

由于環(huán)境尺寸不同，狀態(tài)信息數(shù)量有所差距，因此小范圍下經(jīng)驗回放池容量和單次抽取樣本數(shù)量分別選擇10 000和32。首先使用隨機抽樣對梯度獎勵算法和普通二分獎勵的Dueling DQN算法比對，訓(xùn)練回合為5 000次，規(guī)劃的路徑如圖7所示。

圖7 小范圍路徑規(guī)劃

無論是普通獎勵還是梯度獎勵，在小范圍環(huán)境下均可規(guī)劃出同樣的最短路徑，說明在路徑結(jié)果方面梯度獎勵所占優(yōu)勢并不顯著，然而在路徑規(guī)劃的成功率上兩者有較大差距，成功率曲線如圖8所示。

圖8 小范圍成功率對比

由圖8可知：兩者在初次探索到目標(biāo)點后均有一較大突變，隨后呈現(xiàn)逐漸上升的趨勢，說明強化學(xué)習(xí)中首次獲得目標(biāo)點獎勵對網(wǎng)絡(luò)收斂起到非常重要的作用。對比可知：在梯度獎勵下，機器人首次到達目標(biāo)點只需1 698回合，而傳統(tǒng)二分獎勵需要2 746回合，在探索效率上提升了約38%。梯度獎勵下機器人在3 000回合可達到0.8的成功率，總體成功次數(shù)2 493次；普通獎勵下機器人在3 900回合才能達到0.8的成功率，總體成功次數(shù)1 771次，成功率提升約40%。結(jié)果表明，梯度獎勵在小范圍環(huán)境下相比普通獎勵總體優(yōu)化接近40%。

3.2 大范圍地圖對比

地圖尺寸增大，狀態(tài)數(shù)量因此增多，因此經(jīng)驗回放池容量選擇16 000，單次抽取數(shù)據(jù)為64組。測試方式首先使用優(yōu)先經(jīng)驗回放、梯度獎勵和普通獎勵進行組合測試，然后與文獻[7]所使用的HERDQN算法進行比較測試，探索策略均為去首動態(tài)貪婪策略，訓(xùn)練回合為10 000次。經(jīng)多次重復(fù)實驗，累計成功次數(shù)如表2所示。

表2 累計成功次數(shù)

由表2可知：在10 000回合的訓(xùn)練中，整體成功率最高的組合為梯度獎勵加上優(yōu)先經(jīng)驗回放的方式，達到56.19%；其次為未加優(yōu)先經(jīng)驗回放的梯度獎勵50.07%；而普通的Dueling DQN整體成功次數(shù)僅為4.48%。整體成功率上，梯度獎勵占據(jù)較大優(yōu)勢。

同時從每千次的累計成功次數(shù)中可以看出：梯度獎勵優(yōu)勢明顯，成功次數(shù)逐漸增加，而普通獎勵成功次數(shù)卻停滯不前；相同梯度獎勵下，優(yōu)先經(jīng)驗回放成功次數(shù)大于隨機抽樣約400次，因此優(yōu)先經(jīng)驗回放可顯著減少初次探索到目標(biāo)點的次數(shù)，但在后期的探索上，兩者提升效率趨于相等。

從圖9所示的成功率曲線得知，整體趨勢上增加梯度獎勵的算法呈現(xiàn)上升趨勢，而普通獎勵在6 500次以后成功率降為0；在初次探索到目標(biāo)點的時間上，梯度獎勵比普通獎勵時間縮短近50%，同時增加梯度獎勵的優(yōu)先經(jīng)驗回放比隨機抽樣時間縮短約15%，隨機抽樣梯度獎勵在2 100次訓(xùn)練會初次達到終點，增加優(yōu)先經(jīng)驗回放后縮短為1 800次；6 000回合以上，增加梯度獎勵的算法趨近于收斂，其中優(yōu)先經(jīng)驗回放相比隨機抽樣的成功率波動明顯減少，成功率穩(wěn)定在80%以上；對于普通獎勵，成功率一直為0，它陷入了局部最優(yōu)解。

圖9 大范圍成功率對比

圖10為局部最優(yōu)解路線，最終結(jié)果是機器人在圖中A和B兩點處一直進行無限循環(huán)。通過分析可得：在點A機器人認為最大回報為向下運動，即點B；在點B處機器人認為最大回報為向上運動，即點A，即使在貪婪策略下有少數(shù)情況可逃離循環(huán)，但后續(xù)仍會陷進局部最優(yōu)解。梯度獎勵因其指引作用，在得到獎勵對比后，機器人可很快逃離此局部最優(yōu)。從成功率可得到梯度獎勵對比普通獎勵規(guī)劃效率提升近50%，同時解決了局部最優(yōu)的難題。

圖10 局部最優(yōu)路徑示意

圖11為表示樣本偏差的代價函數(shù)(cost function)的數(shù)值，比較了在梯度獎勵下增加優(yōu)先經(jīng)驗回放與隨機抽樣的差別?？芍簝烧咴诔跏茧A段未探索到目標(biāo)點時均具有較小偏差，因為未達到目標(biāo)點，導(dǎo)致數(shù)值整體偏小，后續(xù)逐漸增加，隨后趨于收斂。在總體偏差上，將每回合的偏差值累加后求平均，可得到梯度獎勵的平均樣本偏差約為0.99，增加優(yōu)先經(jīng)驗回放的平均樣本偏差約為0.39，優(yōu)先經(jīng)驗回放與隨機抽樣對比，偏差值可減少約59.6%。實驗結(jié)果表明：優(yōu)先經(jīng)驗回放可顯著減少樣本估計的偏差，同時提高探索效率，增強算法的魯棒性。

圖11 樣本偏差比較

在大范圍地圖下，使用梯度獎勵與文獻[7]的方法規(guī)劃的路徑分別如圖12和圖13所示。對比路徑的長度、拐點的個數(shù)以及成功率達到60%時的次數(shù)，如表3所示。

表3 指標(biāo)對比

圖12 梯度獎勵規(guī)劃路徑 圖13 文獻[7]規(guī)劃路徑

可知：梯度獎勵與文獻[7]的HERDQN相比，路徑長度短兩格，兩者差距主要產(chǎn)生在圖13的C處，C處由于缺乏獎勵的引導(dǎo)，導(dǎo)致機器人認為向左走為最佳路徑，而后為了尋找到終點又不得不向右走，導(dǎo)致路徑變長；拐點次數(shù)兩者相等；在成功率的對比上，兩者達到60%成功率所需次數(shù)分別約為3 100次和4 050次，相差約1 000次。因此梯度獎勵在速率上，對比HERDQN提升約25%，可證實其優(yōu)越性。

4 結(jié)論

稀疏獎勵是深度強化學(xué)習(xí)中一個重大難題，在路徑規(guī)劃中體現(xiàn)出效率低、不易收斂等問題。本文作者提出一種梯度獎勵政策，劃分獎勵分布區(qū)域，讓機器人在安全區(qū)域也能得到正向獎勵，同時結(jié)合去首動態(tài)貪婪策略與優(yōu)先經(jīng)驗回放，實現(xiàn)探索程度最大化的同時提升對有效樣本的利用率。實驗結(jié)果表明：小范圍環(huán)境內(nèi)梯度獎勵機制探索效率提升38%，整體成功率提升40%；在大范圍環(huán)境內(nèi)，梯度獎勵可顯著增加探索效率，總體成功率可提升12倍以上，探索后期成功率穩(wěn)定在80%以上，也改善了稀疏獎勵中不易收斂等難題，具有較強的穩(wěn)定性。