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

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

0 引言

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

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

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

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

1 強(qiáng)化學(xué)習(xí)算法簡述

1.1 強(qiáng)化學(xué)習(xí)模型

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

圖1 強(qiáng)化學(xué)習(xí)模型Fig.1 Reinforcement learning model

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

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

1.2 馬爾科夫決策過程

1.3 經(jīng)典Q 學(xué)習(xí)算法

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

貪婪策略：

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

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

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

2 DE-Q 學(xué)習(xí)算法

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

2.1 方向獎懲機(jī)制

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

rewarddirection表示移動機(jī)器人在進(jìn)行動作選擇時的方向獎勵值，通過設(shè)置rewarddirection使得移動機(jī)器人選擇趨向于目標(biāo)點(diǎn)的動作。

2.2 估價函數(shù)

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

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

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

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

2.3 DE-Q 學(xué)習(xí)算法

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

圖2 DE-Q 學(xué)習(xí)算法流程圖Fig.2 The flowchart of DE-Q-learning algorithm

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

3 仿真實(shí)驗(yàn)及結(jié)果分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)論

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