基于DE-Q 學習算法的移動機器人路徑規(guī)劃*

馬澤倫，袁 亮，2*，肖文東，何 麗

（1.新疆大學機械工程學院，烏魯木齊 830047；2.北京化工大學信息科學與技術(shù)學院，北京 100029）

0 引言

路徑規(guī)劃是移動機器人的重要研究方向，它在一定程度上反映了移動機器人的智能水平。移動機器人的導航已經(jīng)廣泛應用于工業(yè)、農(nóng)業(yè)、服務等領(lǐng)域［1］。在移動之前進行路徑規(guī)劃，可以提高移動機器人的精度和效率［2］。路徑規(guī)劃的目的是根據(jù)評估標準，幫助移動機器人獲得從初始點到目標點所需的運動路徑［3］。并且機器人在這條路徑上運動時不會相互碰撞，同時也會嘗試優(yōu)化路徑［4］。當移動機器人完成各種任務時，還必須能夠處理各種突發(fā)事件［5］。

路徑規(guī)劃算法有蟻群算法、粒子群優(yōu)化算法和遺傳算法［6-8］，使用上述算法進行路徑必須事先知道完整的環(huán)境信息［9］，而強化學習不同，其學習過程是動態(tài)的，是不斷與環(huán)境相互作用的，故使用強化學習進行路徑規(guī)劃不需要事先知道完整的環(huán)境信息。因此，強化學習涉及許多對象，如動作、環(huán)境、狀態(tài)轉(zhuǎn)移概率和獎勵函數(shù)。強化學習中最廣為人知的算法是時間差分（TD）算法［10］。時間差分算法在動態(tài)規(guī)劃中借鑒了自舉法，在實驗結(jié)束前估計出值函數(shù)，以加快學習速度，提高學習效率。TD 算法主要包括異策略的Q 學習和同策略的Sarsa 算法［4］。

2017 年，SHARMA A 等提出了一種利用Q學習算法的多機器人路徑規(guī)劃協(xié)作方法［11］。在Holonic 多智能體系統(tǒng)上，對原有的Q 值表進行改進，添加協(xié)同更新策略，使環(huán)境中的機器人可以通過自身經(jīng)驗學習，同時也可以學習其他機器人的經(jīng)驗。實驗結(jié)果表明，該算法能夠利用多機器人協(xié)作解決未完成或未知環(huán)境下的路徑規(guī)劃問題。Q 學習算法能適用于未知環(huán)境地圖下的路徑規(guī)劃，是因為其迭代過程是一個試錯和探索的過程。

雖然Q 學習具有這些優(yōu)越的特性，但它仍然存在收斂速度慢的缺點［12］。以上研究并沒有提高Q 學習算法的收斂性。為了加快Q 學習算法的收斂速度，本文引入了方向獎懲機制和估價函數(shù)，以優(yōu)化Q學習算法的獎勵機制。

1 強化學習算法簡述

1.1 強化學習模型

智能體通過選擇動作與未知環(huán)境進行交互，完成路徑規(guī)劃。智能體在動作和環(huán)境的影響下會獲得一個新的狀態(tài)。同時，環(huán)境也會給智能體一個獎勵值。智能體在使用不斷更新的數(shù)據(jù)優(yōu)化動作策略后，繼續(xù)與環(huán)境交互以獲取新的數(shù)據(jù)。之后，智能體使用新數(shù)據(jù)進一步優(yōu)化行為策略［4］。強化學習模型如圖1 所示。

圖1 強化學習模型Fig.1 Reinforcement learning model

強化學習算法可以分為基于值函數(shù)的、基于策略的和基于模型的3 種算法，Q 學習算法是一種基于值函數(shù)的算法［4］。

基于值函數(shù)的算法從如何評估策略的質(zhì)量開始。為了更簡潔、更方便地評估策略的質(zhì)量，引入了獎勵機制。在智能體選擇每一個動作后，都會獲得獎勵。其過程如下：在初始狀態(tài)下，智能體選擇一個動作，然后智能體從環(huán)境中獲得一個獎勵值，在完成此操作后，智能體將獲得一個新的狀態(tài)。在這種狀態(tài)下，智能體選擇下一個動作，并將從環(huán)境中獲得獎勵值。完成移動后智能體將獲得一個新的狀態(tài)。這個過程依次循環(huán)，直到智能體到達最終狀態(tài)［4］。

1.2 馬爾科夫決策過程

1.3 經(jīng)典Q 學習算法

Q 學習算法是馬爾科夫決策過程的一種表達形式，Q 學習算法會學習特定狀態(tài)下特定動作的值。利用Q 學習算法構(gòu)建一個Q 表，以狀態(tài)為行，動作為列，Q 學習算法根據(jù)每個動作的獎勵值更新Q表［4］。Q 學習算法是一個異策略算法，這意味著行動策略和評價策略是不同的。Q 學習中的動作策略為ε-greedy 策略，而更新Q 表的策略為貪婪策略［4］：

貪婪策略：

Q 學習算法輸出的是所有的狀態(tài)-動作的值函數(shù)Q（St，At），Q（St，At）的值由式（3）進行更新：

式中，St為當前狀態(tài)，At為在St狀態(tài)下執(zhí)行的動作，Rt+1為通過狀態(tài)St執(zhí)行動作At獲得的獎勵，St+1為下一個狀態(tài)，a 為能選擇的動作集。α 為學習因子，控制Q 學習算法的學習速度，0＜α＜1。γ 表示折現(xiàn)系數(shù)，表示后一行為對當前狀態(tài)獎勵的影響較小，且0＜γ＜1。經(jīng)典Q 學習算法如表1 所示。

表1 經(jīng)典Q 學習算法Table 1 Classical Q-learning algorithm

2 DE-Q 學習算法

Q 學習算法的優(yōu)點在于不需要先驗地圖，缺點在于收斂速度過慢，為了加快Q 學習算法的收斂速度，本文提出在經(jīng)典Q 學習算法的基礎上，加入方向獎懲機制，同時引入估價函數(shù)以優(yōu)化Q 學習的獎懲機制。

2.1 方向獎懲機制

使用Q 學習算法進行路徑規(guī)劃時，為了加快Q學習算法的收斂速度，引入方向獎懲機制以改進Q學習算法的獎勵矩陣。以移動機器人運動的起始點在柵格地圖的西北角，目標點在柵格地圖的東南角為例，改進后的方向獎懲機制如式（4）所示：

rewarddirection表示移動機器人在進行動作選擇時的方向獎勵值，通過設置rewarddirection使得移動機器人選擇趨向于目標點的動作。

2.2 估價函數(shù)

在傳統(tǒng)的Q 學習算法的基礎上，引入估價函數(shù)，以加快Q 學習算法的收斂效率。估價函數(shù)的主要作用是建立移動機器人的動態(tài)位置和起點、終點的位置之間的關(guān)系，如式（5）所示：

式（5）中，f（N）表示估價函數(shù)的值，將其作為Q 學習算法的獎勵值，N 表示移動機器人當前位置的柵格編號，αe和βe為估價函數(shù)的權(quán)重因數(shù)，ps 表示移動機器人在當前位置到起始點的歐式距離，pe 表示移動機器人在當前位置到終點的歐式距離。nx和ny分別表示移動機器人當前位置的橫、縱坐標，Sx和Sy分別表示移動機器人運動軌跡起始點的橫、縱坐標，Ex和Ey分別表示移動機器人運動軌跡終點的橫、縱坐標。

在使用Q 學習算法對移動機器人進行路徑規(guī)劃時，移動機器人的動作選擇為離散的8 個可行方向，ps 計算了移動機器人沿可行方向到達的位置與移動機器人路徑起點位置的歐氏距離，ps 的值越大說明移動機器人距離目標點越近。pe 計算了移動機器人沿可行方向到達的位置與移動機器人路徑終點位置的歐氏距離，pe 的值越小說明移動機器人距離目標點越近。為了防止pe 對于估價函數(shù)的影響過大，引入了權(quán)重系數(shù)αe與βe。

文獻［9］中提出的激勵函數(shù)僅使移動機器人接近目標點，即僅連接智能體與目標點的位置信息，估價函數(shù)在此基礎上不僅能使移動機器人接近目標點，還能使移動機器人遠離起始點。

2.3 DE-Q 學習算法

移動機器人在運動環(huán)境中運動時，如果區(qū)域可行環(huán)境獎勵值為1，如果區(qū)域不可行則環(huán)境獎勵值為-100，到達目標點則環(huán)境獎勵值為20，如式（6）所示：

圖2 DE-Q 學習算法流程圖Fig.2 The flowchart of DE-Q-learning algorithm

移動機器人在使用Q 學習算法時優(yōu)選獎勵值更大的動作，DE-Q 學習算法優(yōu)化了Q 學習算法動作選擇的獎勵機制，使得移動機器人趨向于目標點的動作獎勵值增大，從而提高了Q 學習的收斂效率。

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

為了說明改進算法的優(yōu)越性，使用MATLAB 對經(jīng)典Q 學習算法，Dir-Q 學習算法，Eva-Q 學習算法以及DE-Q 學習算法進行仿真模擬，并進行對比，其中，Dir-Q 學習算法為僅通過方向獎懲機制改進Q學習的獎勵機制，Eva-Q 學習算法為僅通過估價函數(shù)改進Q 學習的獎勵機制，DE-Q 學習算法為同時通過方向獎懲機制與估價函數(shù)改進Q-學習的獎勵機制?，F(xiàn)對兩種復雜程度不一的地圖進行仿真模擬。

現(xiàn)對如圖3 所示的移動機器人運動環(huán)境進行仿真實驗。

圖3 移動機器人運動環(huán)境與最短路徑Fig.3 Motion environment and shortest path of mobile robots

對圖3 進行50 次路徑規(guī)劃算法模擬仿真實驗時，其達到收斂時的次數(shù)如表2 所示。

表2 中，Num 即為50 次實驗中算法達到收斂時的學習次數(shù)。方向獎懲機制與估價函數(shù)提高了Q學習算法的收斂速度。DE-Q 學習算法在圖3中的收斂效率較經(jīng)典Q 學習算法提升了24%以上。

表2 Q 學習算法達到收斂時的次數(shù)Table 2 The number of times when Q-learning algorithm reaches convergence

由于移動機器人需要對環(huán)境進行探索，因此，Q學習算法在進行動作選擇時的策略為ε-greedy 策略，這說明移動機器人在進行動作選擇時不總是選擇獎勵值最大的方向進行動作，為了探索環(huán)境，移動機器人也會選擇其他方向進行移動，這就導致使用Q學習算法進行移動機器人路徑規(guī)劃任務時，最終路徑趨近于最優(yōu)路徑。如圖4 所示，在圖3 中使用Q 學習算法，Dir-Q 學習算法，Eva-Q 學習算法，DE-Q 學習算法進行路徑規(guī)劃時，最優(yōu)路徑的長度為31.4，為了更好地說明Q 學習及其改進算法的收斂效果，設置移動機器人最優(yōu)路徑的收斂區(qū)間為len∈［31.4，35］?，F(xiàn)從50 次重復實驗中，隨機挑選一次仿真實驗的結(jié)果，如圖4 所示，該次實驗收斂效率提升了60%。

圖4 規(guī)劃路徑長度變化趨勢Fig.4 Changing trend of planned path length

如圖4 所示，Dir-Q 學習算法即為僅通過方向獎懲機制改進Q 學習的算法，Eva-Q 學習算法即為僅通過估價函數(shù)改進Q 學習的算法，DE-Q 學習算法即為同時通過方向獎懲機制與估價函數(shù)改進Q學習的算法。其中，使用DE-Q 學習算法進行路徑規(guī)劃時的收斂效果最優(yōu)。

為了證明地圖的非特殊性，現(xiàn)對如圖5 所示的移動機器人運動環(huán)境進行仿真實驗。

圖5 移動機器人運動環(huán)境與最短路徑Fig.5 Motion environment and shortest path of mobile robots

對圖5 進行50 次路徑規(guī)劃算法模擬仿真實驗時，其達到收斂時的次數(shù)如表3 所示。

表3 Q 學習算法達到收斂時的次數(shù)Table 3 The number of times when Q-learning algorithm reaches convergence

圖6 規(guī)劃路徑長度變化趨勢Fig.6 Changing trend of planned path length

上述實驗說明對于障礙物較規(guī)整的地圖與障礙物較隨機的地圖而言，DE-Q 學習算法均提高了Q 學習算法收斂效率，并且DE-Q 算法的收斂速度最快，同時相較于Dir-Q 學習與Eva-Q 學習而言，DE-Q 學習算法的魯棒性更優(yōu)。

4 結(jié)論

文中針對Q 學習算法收斂速度過慢的情況，提出了方向獎懲機制與估價函數(shù)以改進獎勵機制，從而達到加快Q 學習算法收斂的目標。同時使用MATLAB 進行仿真分析，在兩種復雜程度不一的地圖中，對Q 學習算法，Dir-Q 學習算法，Eva-Q 學習算法，DE-Q 學習算法進行仿真模擬實驗，實驗結(jié)果表明在不同的環(huán)境中，方向獎懲機制與估價函數(shù)都加快了Q 學習算法的收斂效率。DE-Q 學習算法具有更快的收斂速度和更優(yōu)的魯棒性。