馬澤倫,袁 亮,2*,肖文東,何 麗
(1.新疆大學(xué)機(jī)械工程學(xué)院,烏魯木齊 830047;2.北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院,北京 100029)
路徑規(guī)劃是移動(dòng)機(jī)器人的重要研究方向,它在一定程度上反映了移動(dòng)機(jī)器人的智能水平。移動(dòng)機(jī)器人的導(dǎo)航已經(jīng)廣泛應(yīng)用于工業(yè)、農(nóng)業(yè)、服務(wù)等領(lǐng)域[1]。在移動(dòng)之前進(jìn)行路徑規(guī)劃,可以提高移動(dòng)機(jī)器人的精度和效率[2]。路徑規(guī)劃的目的是根據(jù)評估標(biāo)準(zhǔn),幫助移動(dòng)機(jī)器人獲得從初始點(diǎn)到目標(biāo)點(diǎn)所需的運(yùn)動(dòng)路徑[3]。并且機(jī)器人在這條路徑上運(yùn)動(dòng)時(shí)不會(huì)相互碰撞,同時(shí)也會(huì)嘗試優(yōu)化路徑[4]。當(dāng)移動(dòng)機(jī)器人完成各種任務(wù)時(shí),還必須能夠處理各種突發(fā)事件[5]。
路徑規(guī)劃算法有蟻群算法、粒子群優(yōu)化算法和遺傳算法[6-8],使用上述算法進(jìn)行路徑必須事先知道完整的環(huán)境信息[9],而強(qiáng)化學(xué)習(xí)不同,其學(xué)習(xí)過程是動(dòng)態(tài)的,是不斷與環(huán)境相互作用的,故使用強(qiáng)化學(xué)習(xí)進(jìn)行路徑規(guī)劃不需要事先知道完整的環(huán)境信息。因此,強(qiáng)化學(xué)習(xí)涉及許多對象,如動(dòng)作、環(huán)境、狀態(tài)轉(zhuǎn)移概率和獎(jiǎng)勵(lì)函數(shù)。強(qiáng)化學(xué)習(xí)中最廣為人知的算法是時(shí)間差分(TD)算法[10]。時(shí)間差分算法在動(dòng)態(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í),同時(shí)也可以學(xué)習(xí)其他機(jī)器人的經(jīng)驗(yàn)。實(shí)驗(yàn)結(jié)果表明,該算法能夠利用多機(jī)器人協(xié)作解決未完成或未知環(huán)境下的路徑規(guī)劃問題。Q 學(xué)習(xí)算法能適用于未知環(huán)境地圖下的路徑規(guī)劃,是因?yàn)槠涞^程是一個(gè)試錯(cuò)和探索的過程。
雖然Q 學(xué)習(xí)具有這些優(yōu)越的特性,但它仍然存在收斂速度慢的缺點(diǎn)[12]。以上研究并沒有提高Q 學(xué)習(xí)算法的收斂性。為了加快Q 學(xué)習(xí)算法的收斂速度,本文引入了方向獎(jiǎng)懲機(jī)制和估價(jià)函數(shù),以優(yōu)化Q學(xué)習(xí)算法的獎(jiǎng)勵(lì)機(jī)制。
智能體通過選擇動(dòng)作與未知環(huán)境進(jìn)行交互,完成路徑規(guī)劃。智能體在動(dòng)作和環(huán)境的影響下會(huì)獲得一個(gè)新的狀態(tài)。同時(shí),環(huán)境也會(huì)給智能體一個(gè)獎(jiǎng)勵(lì)值。智能體在使用不斷更新的數(shù)據(jù)優(yōu)化動(dòng)作策略后,繼續(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ì)量,引入了獎(jiǎng)勵(lì)機(jī)制。在智能體選擇每一個(gè)動(dòng)作后,都會(huì)獲得獎(jiǎng)勵(lì)。其過程如下:在初始狀態(tài)下,智能體選擇一個(gè)動(dòng)作,然后智能體從環(huán)境中獲得一個(gè)獎(jiǎng)勵(lì)值,在完成此操作后,智能體將獲得一個(gè)新的狀態(tài)。在這種狀態(tài)下,智能體選擇下一個(gè)動(dòng)作,并將從環(huán)境中獲得獎(jiǎng)勵(lì)值。完成移動(dòng)后智能體將獲得一個(gè)新的狀態(tài)。這個(gè)過程依次循環(huán),直到智能體到達(dá)最終狀態(tài)[4]。
Q 學(xué)習(xí)算法是馬爾科夫決策過程的一種表達(dá)形式,Q 學(xué)習(xí)算法會(huì)學(xué)習(xí)特定狀態(tài)下特定動(dòng)作的值。利用Q 學(xué)習(xí)算法構(gòu)建一個(gè)Q 表,以狀態(tài)為行,動(dòng)作為列,Q 學(xué)習(xí)算法根據(jù)每個(gè)動(dòng)作的獎(jiǎng)勵(lì)值更新Q表[4]。Q 學(xué)習(xí)算法是一個(gè)異策略算法,這意味著行動(dòng)策略和評價(jià)策略是不同的。Q 學(xué)習(xí)中的動(dòng)作策略為ε-greedy 策略,而更新Q 表的策略為貪婪策略[4]:
貪婪策略:
Q 學(xué)習(xí)算法輸出的是所有的狀態(tài)-動(dòng)作的值函數(shù)Q(St,At),Q(St,At)的值由式(3)進(jìn)行更新:
式中,St為當(dāng)前狀態(tài),At為在St狀態(tài)下執(zhí)行的動(dòng)作,Rt+1為通過狀態(tài)St執(zhí)行動(dòng)作At獲得的獎(jiǎng)勵(lì),St+1為下一個(gè)狀態(tài),a 為能選擇的動(dòng)作集。α 為學(xué)習(xí)因子,控制Q 學(xué)習(xí)算法的學(xué)習(xí)速度,0<α<1。γ 表示折現(xiàn)系數(shù),表示后一行為對當(dāng)前狀態(tài)獎(jiǎng)勵(lì)的影響較小,且0<γ<1。經(jīng)典Q 學(xué)習(xí)算法如表1 所示。
表1 經(jīng)典Q 學(xué)習(xí)算法Table 1 Classical Q-learning algorithm
Q 學(xué)習(xí)算法的優(yōu)點(diǎn)在于不需要先驗(yàn)地圖,缺點(diǎn)在于收斂速度過慢,為了加快Q 學(xué)習(xí)算法的收斂速度,本文提出在經(jīng)典Q 學(xué)習(xí)算法的基礎(chǔ)上,加入方向獎(jiǎng)懲機(jī)制,同時(shí)引入估價(jià)函數(shù)以優(yōu)化Q 學(xué)習(xí)的獎(jiǎng)懲機(jī)制。
使用Q 學(xué)習(xí)算法進(jìn)行路徑規(guī)劃時(shí),為了加快Q學(xué)習(xí)算法的收斂速度,引入方向獎(jiǎng)懲機(jī)制以改進(jìn)Q學(xué)習(xí)算法的獎(jiǎng)勵(lì)矩陣。以移動(dòng)機(jī)器人運(yùn)動(dòng)的起始點(diǎn)在柵格地圖的西北角,目標(biāo)點(diǎn)在柵格地圖的東南角為例,改進(jìn)后的方向獎(jiǎng)懲機(jī)制如式(4)所示:
rewarddirection表示移動(dòng)機(jī)器人在進(jìn)行動(dòng)作選擇時(shí)的方向獎(jiǎng)勵(lì)值,通過設(shè)置rewarddirection使得移動(dòng)機(jī)器人選擇趨向于目標(biāo)點(diǎn)的動(dòng)作。
在傳統(tǒng)的Q 學(xué)習(xí)算法的基礎(chǔ)上,引入估價(jià)函數(shù),以加快Q 學(xué)習(xí)算法的收斂效率。估價(jià)函數(shù)的主要作用是建立移動(dòng)機(jī)器人的動(dòng)態(tài)位置和起點(diǎn)、終點(diǎn)的位置之間的關(guān)系,如式(5)所示:
式(5)中,f(N)表示估價(jià)函數(shù)的值,將其作為Q 學(xué)習(xí)算法的獎(jiǎng)勵(lì)值,N 表示移動(dòng)機(jī)器人當(dāng)前位置的柵格編號,αe和βe為估價(jià)函數(shù)的權(quán)重因數(shù),ps 表示移動(dòng)機(jī)器人在當(dāng)前位置到起始點(diǎn)的歐式距離,pe 表示移動(dòng)機(jī)器人在當(dāng)前位置到終點(diǎn)的歐式距離。nx和ny分別表示移動(dòng)機(jī)器人當(dāng)前位置的橫、縱坐標(biāo),Sx和Sy分別表示移動(dòng)機(jī)器人運(yùn)動(dòng)軌跡起始點(diǎn)的橫、縱坐標(biāo),Ex和Ey分別表示移動(dòng)機(jī)器人運(yùn)動(dòng)軌跡終點(diǎn)的橫、縱坐標(biāo)。
在使用Q 學(xué)習(xí)算法對移動(dòng)機(jī)器人進(jìn)行路徑規(guī)劃時(shí),移動(dòng)機(jī)器人的動(dòng)作選擇為離散的8 個(gè)可行方向,ps 計(jì)算了移動(dòng)機(jī)器人沿可行方向到達(dá)的位置與移動(dòng)機(jī)器人路徑起點(diǎn)位置的歐氏距離,ps 的值越大說明移動(dòng)機(jī)器人距離目標(biāo)點(diǎn)越近。pe 計(jì)算了移動(dòng)機(jī)器人沿可行方向到達(dá)的位置與移動(dòng)機(jī)器人路徑終點(diǎn)位置的歐氏距離,pe 的值越小說明移動(dòng)機(jī)器人距離目標(biāo)點(diǎn)越近。為了防止pe 對于估價(jià)函數(shù)的影響過大,引入了權(quán)重系數(shù)αe與βe。
文獻(xiàn)[9]中提出的激勵(lì)函數(shù)僅使移動(dòng)機(jī)器人接近目標(biāo)點(diǎn),即僅連接智能體與目標(biāo)點(diǎn)的位置信息,估價(jià)函數(shù)在此基礎(chǔ)上不僅能使移動(dòng)機(jī)器人接近目標(biāo)點(diǎn),還能使移動(dòng)機(jī)器人遠(yuǎn)離起始點(diǎn)。
移動(dòng)機(jī)器人在運(yùn)動(dòng)環(huán)境中運(yùn)動(dòng)時(shí),如果區(qū)域可行環(huán)境獎(jiǎng)勵(lì)值為1,如果區(qū)域不可行則環(huán)境獎(jiǎng)勵(lì)值為-100,到達(dá)目標(biāo)點(diǎn)則環(huán)境獎(jiǎng)勵(lì)值為20,如式(6)所示:
圖2 DE-Q 學(xué)習(xí)算法流程圖Fig.2 The flowchart of DE-Q-learning algorithm
移動(dòng)機(jī)器人在使用Q 學(xué)習(xí)算法時(shí)優(yōu)選獎(jiǎng)勵(lì)值更大的動(dòng)作,DE-Q 學(xué)習(xí)算法優(yōu)化了Q 學(xué)習(xí)算法動(dòng)作選擇的獎(jiǎng)勵(lì)機(jī)制,使得移動(dòng)機(jī)器人趨向于目標(biāo)點(diǎn)的動(dòng)作獎(jiǎng)勵(lì)值增大,從而提高了Q 學(xué)習(xí)的收斂效率。
為了說明改進(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í)算法為僅通過方向獎(jiǎng)懲機(jī)制改進(jìn)Q學(xué)習(xí)的獎(jiǎng)勵(lì)機(jī)制,Eva-Q 學(xué)習(xí)算法為僅通過估價(jià)函數(shù)改進(jìn)Q 學(xué)習(xí)的獎(jiǎng)勵(lì)機(jī)制,DE-Q 學(xué)習(xí)算法為同時(shí)通過方向獎(jiǎng)懲機(jī)制與估價(jià)函數(shù)改進(jìn)Q-學(xué)習(xí)的獎(jiǎng)勵(lì)機(jī)制?,F(xiàn)對兩種復(fù)雜程度不一的地圖進(jìn)行仿真模擬。
現(xiàn)對如圖3 所示的移動(dòng)機(jī)器人運(yùn)動(dòng)環(huán)境進(jìn)行仿真實(shí)驗(yàn)。
圖3 移動(dòng)機(jī)器人運(yùn)動(dòng)環(huán)境與最短路徑Fig.3 Motion environment and shortest path of mobile robots
對圖3 進(jìn)行50 次路徑規(guī)劃算法模擬仿真實(shí)驗(yàn)時(shí),其達(dá)到收斂時(shí)的次數(shù)如表2 所示。
表2 中,Num 即為50 次實(shí)驗(yàn)中算法達(dá)到收斂時(shí)的學(xué)習(xí)次數(shù)。方向獎(jiǎng)懲機(jī)制與估價(jià)函數(shù)提高了Q學(xué)習(xí)算法的收斂速度。DE-Q 學(xué)習(xí)算法在圖3中的收斂效率較經(jīng)典Q 學(xué)習(xí)算法提升了24%以上。
表2 Q 學(xué)習(xí)算法達(dá)到收斂時(shí)的次數(shù)Table 2 The number of times when Q-learning algorithm reaches convergence
由于移動(dòng)機(jī)器人需要對環(huán)境進(jìn)行探索,因此,Q學(xué)習(xí)算法在進(jìn)行動(dòng)作選擇時(shí)的策略為ε-greedy 策略,這說明移動(dòng)機(jī)器人在進(jìn)行動(dòng)作選擇時(shí)不總是選擇獎(jiǎng)勵(lì)值最大的方向進(jìn)行動(dòng)作,為了探索環(huán)境,移動(dòng)機(jī)器人也會(huì)選擇其他方向進(jìn)行移動(dòng),這就導(dǎo)致使用Q學(xué)習(xí)算法進(jìn)行移動(dòng)機(jī)器人路徑規(guī)劃任務(wù)時(shí),最終路徑趨近于最優(yōu)路徑。如圖4 所示,在圖3 中使用Q 學(xué)習(xí)算法,Dir-Q 學(xué)習(xí)算法,Eva-Q 學(xué)習(xí)算法,DE-Q 學(xué)習(xí)算法進(jìn)行路徑規(guī)劃時(shí),最優(yōu)路徑的長度為31.4,為了更好地說明Q 學(xué)習(xí)及其改進(jìn)算法的收斂效果,設(shè)置移動(dòng)機(jī)器人最優(yōu)路徑的收斂區(qū)間為len∈[31.4,35]。現(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í)算法即為僅通過方向獎(jiǎng)懲機(jī)制改進(jìn)Q 學(xué)習(xí)的算法,Eva-Q 學(xué)習(xí)算法即為僅通過估價(jià)函數(shù)改進(jìn)Q 學(xué)習(xí)的算法,DE-Q 學(xué)習(xí)算法即為同時(shí)通過方向獎(jiǎng)懲機(jī)制與估價(jià)函數(shù)改進(jìn)Q學(xué)習(xí)的算法。其中,使用DE-Q 學(xué)習(xí)算法進(jìn)行路徑規(guī)劃時(shí)的收斂效果最優(yōu)。
為了證明地圖的非特殊性,現(xiàn)對如圖5 所示的移動(dòng)機(jī)器人運(yùn)動(dòng)環(huán)境進(jìn)行仿真實(shí)驗(yàn)。
圖5 移動(dòng)機(jī)器人運(yùn)動(dòng)環(huán)境與最短路徑Fig.5 Motion environment and shortest path of mobile robots
對圖5 進(jìn)行50 次路徑規(guī)劃算法模擬仿真實(shí)驗(yàn)時(shí),其達(dá)到收斂時(shí)的次數(shù)如表3 所示。
表3 Q 學(xué)習(xí)算法達(dá)到收斂時(shí)的次數(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 算法的收斂速度最快,同時(shí)相較于Dir-Q 學(xué)習(xí)與Eva-Q 學(xué)習(xí)而言,DE-Q 學(xué)習(xí)算法的魯棒性更優(yōu)。
文中針對Q 學(xué)習(xí)算法收斂速度過慢的情況,提出了方向獎(jiǎng)懲機(jī)制與估價(jià)函數(shù)以改進(jìn)獎(jiǎng)勵(lì)機(jī)制,從而達(dá)到加快Q 學(xué)習(xí)算法收斂的目標(biāo)。同時(shí)使用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)境中,方向獎(jiǎng)懲機(jī)制與估價(jià)函數(shù)都加快了Q 學(xué)習(xí)算法的收斂效率。DE-Q 學(xué)習(xí)算法具有更快的收斂速度和更優(yōu)的魯棒性。