李子怡,胡祥濤,張勇樂,許建軍

(安徽大學(xué) 電氣工程與自動化學(xué)院,安徽 合肥 230601)

0 引言

作為智能移動機(jī)器人關(guān)鍵技術(shù)之一,路徑規(guī)劃長期以來一直是十分活躍的研究領(lǐng)域,被國內(nèi)外學(xué)者廣泛關(guān)注[1-4]。路徑規(guī)劃問題描述為:在路徑長度、連續(xù)性以及實時性等約束條件下,找到一條從當(dāng)前位置移動到目標(biāo)位置的最優(yōu)無碰撞路徑[5-6]。根據(jù)移動機(jī)器人已知工作環(huán)境信息的程度,路徑規(guī)劃問題分為[7-8]全局路徑規(guī)劃和局部路徑規(guī)劃。全局路徑規(guī)劃也稱為離線規(guī)劃,指根據(jù)完全已知的環(huán)境先驗信息建立靜態(tài)全局地圖,再基于全局地圖從起始位置到目標(biāo)位置規(guī)劃出最優(yōu)路徑[9]。常見的全局路徑規(guī)劃方法可以分為4類[10],即基于圖搜索的規(guī)劃方法(以A*及D*[11]和可視圖方法[12]為代表)、基于隨機(jī)采樣的規(guī)劃方法(以快速搜索隨機(jī)樹(Rapidly-Exploring Random Trees,RRT)及其改進(jìn)方法[13-15]為代表)、智能搜索方法(以遺傳算法[16]、蟻群算法[17-18]為代表)、人工勢場法[19-20]。全局規(guī)劃方法對環(huán)境先驗信息的依賴性較強(qiáng),在實際任務(wù)中,機(jī)器人更多面對的是未知環(huán)境,常規(guī)全局路徑規(guī)劃方法不適用,因此越來越多的學(xué)者關(guān)注局部路徑規(guī)劃方法。

局部路徑規(guī)劃描述為移動機(jī)器人在探索未知環(huán)境過程中,通過傳感器獲取周圍環(huán)境信息,進(jìn)行增量計算后得出下一節(jié)點,從而逐步獲得一條無碰撞最優(yōu)路徑[7]。局部路徑規(guī)劃不受環(huán)境先驗信息影響,對未知環(huán)境具有更強(qiáng)的適應(yīng)性和實時性,在智能移動機(jī)器人路徑規(guī)劃中更被青睞[21-22]。局部路徑規(guī)劃算法主要分為避障規(guī)劃類算法(動態(tài)窗口法[23]、BUG類方法[24])和強(qiáng)化學(xué)習(xí)方法[25-27]。不同于避障規(guī)劃類算法,強(qiáng)化學(xué)習(xí)算法通過對環(huán)境進(jìn)行交互式試錯學(xué)習(xí),得到一個從初始狀態(tài)到目標(biāo)狀態(tài)最優(yōu)的行動策略[28-30]。因此,面對復(fù)雜未知環(huán)境,強(qiáng)化學(xué)習(xí)算法的適應(yīng)性最好,在移動機(jī)器人路徑規(guī)劃中表現(xiàn)優(yōu)異[7,31]。

在移動機(jī)器人路徑規(guī)劃算法中常采用的強(qiáng)化學(xué)習(xí)方法是Q學(xué)習(xí)(Q-learning)算法[8,21]。宋勇等[20]提出將人工勢場引入經(jīng)典Q學(xué)習(xí),根據(jù)先驗信息構(gòu)造勢能場初始化Q表,提高了Q學(xué)習(xí)的收斂速度,但對初始化Q-Table需要環(huán)境先驗信息,不適用于未知環(huán)境;LOW等[1]將花授粉算法(Flower Pollination Algorithm, FPA)引入Q學(xué)習(xí),由FPA取得先驗知識初始化Q表,加快了Q學(xué)習(xí)算法收斂,但不適用于未知環(huán)境;田曉航等[32]將蟻群算法引入Q學(xué)習(xí),提出一種尋優(yōu)范圍優(yōu)化方法,減少了智能體的無效探索次數(shù),然而算法中信息素機(jī)制對Q表的編碼方案需要環(huán)境先驗信息,不適用于未知環(huán)境;CHEN等[33]針對凹形地形問題提出融入障礙區(qū)擴(kuò)展思想的改進(jìn)算法,避免智能體因進(jìn)入凹形障礙物區(qū)域而產(chǎn)生無效迭代,然而算法仍需對凹形障礙區(qū)進(jìn)行大量探索,以分辨障礙物和智能體的位置關(guān)系;GUO等[34]提出將模擬退火(Simulated Annealing,SA)算法引入Q學(xué)習(xí)平衡探索和利用的關(guān)系,加快了算法的收斂速度,雖然SA算法不完全拒絕惡化解的特性能夠避免移動機(jī)器人陷入局部最優(yōu)區(qū)域,但是其自身存在超參數(shù)設(shè)置問題,增加了計算的負(fù)擔(dān);LI等[10]在Boltzmann Q學(xué)習(xí)的基礎(chǔ)上引入啟發(fā)搜索策略,避免了局部最優(yōu)的情況,提高了算法收斂速度,然而玻爾茲曼策略在每一次選擇動作后都需要進(jìn)行大量計算,當(dāng)狀態(tài)集較大時會帶來更多計算量,影響收斂速度;LI等[35]在Q學(xué)習(xí)基礎(chǔ)上引入自適應(yīng)探索策略,提出AE Q-learning算法,在一定程度上緩解了探索和利用的沖突,加快了算法收斂速度,然而該方法有較多超參數(shù),不利于方法遷移,具有較強(qiáng)的主觀性;WANG等[36]在Boltzmann Q學(xué)習(xí)的基礎(chǔ)上引入經(jīng)驗重載,提出Backward Q-learning算法,該方法在每次成功達(dá)到終點后重新計算成功路徑的Q值,每次重載路徑并計算的代價較大,算法在極大提高收斂性和算法穩(wěn)定性的同時犧牲了效率,而且算法受狀態(tài)—動作空間維度的影響極大。

綜上所述,在經(jīng)典強(qiáng)化學(xué)習(xí)領(lǐng)域內(nèi),學(xué)者們主要從融合智能算法、探索策略改進(jìn)[37-39]兩方面對Q learning進(jìn)行改進(jìn)。融合智能算法類表現(xiàn)在對狀態(tài)集進(jìn)行編碼及對Q表初始化的改進(jìn)上,使算法盡量掌握環(huán)境的完備信息,縮小了Q學(xué)習(xí)的適用范圍,該改進(jìn)方法不適用于環(huán)境信息不完備的未知環(huán)境;探索策略改進(jìn)類主要表現(xiàn)在引導(dǎo)策略方法對獎勵值設(shè)置的改進(jìn)和對智能體動作選擇策略上的改進(jìn),這類改進(jìn)加快了算法收斂效率且未增加對先驗信息的要求。這些改進(jìn)雖然成功應(yīng)用于路徑規(guī)劃并表現(xiàn)優(yōu)異,但是仍然存在3個局限性:①收斂速度慢,且隨著地圖規(guī)模的增大,狀態(tài)變量增多,計算效率下降;②算法魯棒性有待進(jìn)一步提升;③面臨特殊環(huán)境時,機(jī)器人容易陷入地形陷阱。針對上述問題,本文在經(jīng)典Q學(xué)習(xí)算法基礎(chǔ)上,設(shè)計了雙重記憶機(jī)制、虛擬目標(biāo)引導(dǎo)方法、自適應(yīng)貪婪因子,提出基于虛擬目標(biāo)制導(dǎo)的自適應(yīng)Q學(xué)習(xí)算法(Adaptive Q-learning algorithm based on Virtual Target Guidance,VTGA-Q-Learning),并通過對比實驗驗證了算法的有效性,實現(xiàn)了移動機(jī)器人在未知環(huán)境下的路徑規(guī)劃。

1 虛擬目標(biāo)制導(dǎo)的路徑規(guī)劃問題與描述

1.1 學(xué)習(xí)算法

Q學(xué)習(xí)算法是一種基于值函數(shù)的強(qiáng)化學(xué)習(xí)算法,其核心是Q表的設(shè)計與更新。Q表建立了“狀態(tài)動作對”(s,a)與Q(s,a)的映射。按照Q學(xué)習(xí)算法,智能體基于當(dāng)前狀態(tài)st從Q表中選擇動作at,然后環(huán)境反饋相應(yīng)回報Rt+1,利用式(1)計算該狀態(tài)動作對的價值Q(st,at),并更新Q表中的Q(st,at)值,以此作為下一狀態(tài)選擇最優(yōu)動作的依據(jù)。

Q(st,at)←Q(st,at)+

(1)

式中:st為t時刻智能體的狀態(tài),st∈S,S為智能體有限狀態(tài)集合;at為t時刻智能體的動作,at∈A,A為智能體有限動作集合;Rt+1為智能體在狀態(tài)s下選擇動作a所獲的即時獎勵;α為學(xué)習(xí)率,α∈(0,1);γ為折扣率,γ∈(0,1)。

1.2 路徑規(guī)劃模型

將Q學(xué)習(xí)算法用于移動機(jī)器人路徑規(guī)劃問題,需要分別對機(jī)器人所處的環(huán)境、狀態(tài)集、動作集、價值函數(shù)進(jìn)行定義和建模。

1.2.1 環(huán)境建模

本文采用格柵法建立移動機(jī)器人環(huán)境模型。格柵法用網(wǎng)格等分整個環(huán)境,將自由區(qū)域標(biāo)記為0,障礙物標(biāo)記為1,格柵圖中的障礙物(obstacle)、智能體起點位置(start)、智能體終點位置(goal)、自由空間(freedom)如圖1所示。

1.2.2 狀態(tài)集和動作集

本文將移動機(jī)器人的狀態(tài)描述為格柵中心坐標(biāo)(x,y),每個柵格為一個狀態(tài)。由于為未知環(huán)境,狀態(tài)集的大小依賴機(jī)器人探索得到。隨著地圖規(guī)模的增大,狀態(tài)集的規(guī)模隨之增大,導(dǎo)致Q表的維護(hù)成本增加。

動作集的設(shè)置方式一般有四鄰域和八鄰域兩種,如圖2所示。四領(lǐng)域只有上、下、左、右4個動作,移動機(jī)器人在每個狀態(tài)下選擇其中一個動作執(zhí)行;八領(lǐng)域有8個動作,規(guī)劃出的路徑相對平滑,但會降低算法收斂速度。本文所有Q學(xué)習(xí)算法都采用四鄰域狀態(tài)集,不影響本文的算法性能驗證和對比分析。

1.2.3 獎勵函數(shù)

獎勵函數(shù)會影響智能體的收斂和探索周期,在常規(guī)Q學(xué)習(xí)算法中,設(shè)置獎勵函數(shù)

(2)

式中將智能體所處的狀態(tài)分為Sgoal,Sobstacle,Sfreedom3類,分別對應(yīng)目標(biāo)點、障礙物、自由空間,Q學(xué)習(xí)算法根據(jù)狀態(tài)分類給予相應(yīng)獎勵。

2 算法改進(jìn)設(shè)計

常規(guī)Q學(xué)習(xí)算法在處理未知環(huán)境下移動機(jī)器人路徑規(guī)劃問題時,存在收斂速度慢、魯棒性差、盲目性和地圖陷阱等問題,本文設(shè)計了3種機(jī)制以改善Q學(xué)習(xí)算法性能。

2.1 雙重記憶機(jī)制

2.1.1 障礙物記憶機(jī)制

在Q學(xué)習(xí)中,智能體需要不斷同環(huán)境進(jìn)行交互學(xué)習(xí),經(jīng)過一段時間學(xué)習(xí)后,Q表中指向障礙物的動作的獎勵值會小于其他動作的獎勵值,因此智能體可以根據(jù)Q表選擇最佳動作避開障礙物。然而在學(xué)習(xí)過程中,智能體需要平衡探索和利用的關(guān)系,即智能體的動作選擇不完全依賴Q表,而是以一定概率隨機(jī)選擇一個動作,以加強(qiáng)對未知地圖的探索開發(fā)。因此在探索期間,智能體仍會高頻選擇指向障礙物的動作,從而產(chǎn)生無效迭代,降低了探索效率。為此,本文設(shè)計了障礙記憶機(jī)制對障礙物進(jìn)行一次學(xué)習(xí),克服了Classic-Q-Learning對障礙物迭代學(xué)習(xí)過程中因隨機(jī)策略而產(chǎn)生無效迭代的問題。

如圖3所示,障礙記憶機(jī)制設(shè)計可描述為:智能體在狀態(tài)st采取動作at時,如果觀測到下一位置為障礙物,則將動作狀態(tài)對(st,at)存儲到障礙物記憶區(qū)中,并將障礙物記憶區(qū)內(nèi)的動作狀態(tài)對被選擇的概率置0,以杜絕智能體隨機(jī)探索時的無效迭代,提高探索的有效性;另外,因為本文算法面對的是未知環(huán)境,所以將Q表設(shè)置為動態(tài)創(chuàng)建而不是初始化為固定大小的Q表。

2.1.2 短時記憶機(jī)制

為了解決地圖陷阱問題,本文提出短時記憶機(jī)制。該機(jī)制首先定義短時記憶區(qū)間T-M(如圖5),用于存儲智能體連續(xù)的5個狀態(tài)行為對,然后通過查詢T-M內(nèi)是否存在{st,st+1}∈{st-3,st-2,st-1}來判斷智能體是否陷入地圖陷阱。當(dāng)陷入地圖陷阱時,禁止選擇鏈接st,st+1的動作,智能體隨機(jī)選擇其他動作,從而跳出地圖陷阱。

2.2 虛擬目標(biāo)引導(dǎo)方法

不同于蒙特卡洛方法利用一次實驗的經(jīng)驗平均來估計當(dāng)前值函數(shù),Q學(xué)習(xí)利用策略采樣獲得后繼狀態(tài)的值函數(shù)來估計當(dāng)前狀態(tài)的值函數(shù)。對采樣數(shù)據(jù)的利用效率深刻影響著值函數(shù)迭代,而且Q學(xué)習(xí)存在探索效率低下的問題。虛擬目標(biāo)引導(dǎo)方法從經(jīng)驗區(qū)M中篩選出不同重要程度的狀態(tài)集,再從該狀態(tài)集中獲取狀態(tài)作為階段性虛擬目標(biāo),并設(shè)置虛擬獎勵,通過虛擬獎勵使智能體學(xué)習(xí)到虛擬目標(biāo)作為輔助節(jié)點的價值,引導(dǎo)機(jī)器人更高效地到達(dá)真實目標(biāo)。

通過虛擬目標(biāo)引導(dǎo)方法從經(jīng)驗區(qū)M中篩選出3級重要數(shù)據(jù)表層經(jīng)驗(Surface Experience,SE)、深層經(jīng)驗(Deep Experience,DE)、貪婪經(jīng)驗(Greedy Experience,GE),如圖6所示。表層經(jīng)驗指在歷史實驗數(shù)據(jù)中,根據(jù)式(3)篩選出比序列整體優(yōu)秀的狀態(tài)—動作對;深層經(jīng)驗指在表層經(jīng)驗中,根據(jù)式(4),通過加權(quán)平均的方法求出截止當(dāng)前實驗序列確定的狀態(tài)價值,反映了過往經(jīng)驗中該狀態(tài)的相對價值隨實驗數(shù)據(jù)的增加而趨近于真實狀態(tài)價值;貪婪經(jīng)驗指在深層經(jīng)驗中,根據(jù)式(5)貪婪選取深層經(jīng)驗中狀態(tài)價值最大的狀態(tài),從而篩選出歷史數(shù)據(jù)中較為重要的序列節(jié)點。

(3)

(4)

(5)

式(2)給出了常規(guī)Q學(xué)習(xí)算法的價值函數(shù)計算方法,這種設(shè)置方法在地圖規(guī)模不大時相對適用。當(dāng)?shù)貓D規(guī)模較大時存在稀疏獎勵問題,導(dǎo)致智能體盲目探索,算法難以收斂。同時,為了改善強(qiáng)化學(xué)習(xí)存在的稀疏獎勵問題,在完成虛擬目標(biāo)選擇后,分別賦予不同分區(qū)中的狀態(tài)不同的動態(tài)價值,該思路可描述為:對貪婪經(jīng)驗中的狀態(tài)給予高激勵,深層經(jīng)驗中的狀態(tài)給予中激勵,淺層經(jīng)驗中的狀態(tài)給予較低激勵。本文的動態(tài)獎勵函數(shù)設(shè)置如下:

(6)

Dy_R(st)=

J(st)·F(st)+w·E(st)+R1;

(7)

(8)

(9)

式中:Dy_R(st)為動態(tài)獎勵函數(shù);J(st)為一個二值函數(shù),用于限制在{表層經(jīng)驗;深層經(jīng)驗;貪婪經(jīng)驗}中的狀態(tài)只能被動態(tài)獎勵額外獎勵一次,以防過度獎勵造成收斂彌散;count[st]為標(biāo)志數(shù)組,用于存儲被動態(tài)獎勵附加獎勵的狀態(tài);w∈(0,0.1)為常權(quán)重參數(shù);E(st)為歷次實驗中,狀態(tài)st到{表層經(jīng)驗;深層經(jīng)驗;貪婪經(jīng)驗}中的次數(shù)。

2.3 自適應(yīng)貪婪因子

常規(guī)Q學(xué)習(xí)算法采用貪婪策略雖然在一定程度上平衡了探索和利用,但是貪婪因子ε為固定值,ε值的設(shè)計極大影響了對未知地圖的探索利用能力,固定的貪婪因子使智能體的探索性始終保持不變,這不利于算法收斂,使算法存在較大波動,且使超參數(shù)設(shè)計存在主觀性;調(diào)整貪婪因子應(yīng)隨探索程度的提高而衰減,合理的貪婪因子應(yīng)隨智能體的探索經(jīng)驗動態(tài)調(diào)整。針對以上問題,本文提出自適應(yīng)貪婪因子。

自適應(yīng)貪婪因子根據(jù)智能體同環(huán)境的交互程度以及由探索經(jīng)驗估計的環(huán)境復(fù)雜程度進(jìn)行自行調(diào)整,并將學(xué)習(xí)階段分為探索階段、隨機(jī)探索利用階段、利用階段3個階段,從而提高算法的收斂速度和穩(wěn)定性,更好地平衡探索和利用的矛盾,同時擺脫了超參數(shù)設(shè)計的困擾。本文定義自適應(yīng)貪婪因子

ε=tanh((|xstart-xgoal|+|ystart-ygoal|)·

(10)

自適應(yīng)貪婪因子根據(jù)智能體與環(huán)境的交互程度主動調(diào)整貪婪因子,對學(xué)習(xí)階段進(jìn)行劃分,逐步增加智能體對已有知識的利用,從而提高算法的收斂性和穩(wěn)定性,更好地平衡探索和利用的矛盾。

3 基于雙重記憶機(jī)制的自適應(yīng)Q學(xué)習(xí)算法流程

基于上述改進(jìn),將雙重記憶機(jī)制、虛擬目標(biāo)引導(dǎo)方法、自適應(yīng)貪婪因子融入常規(guī)Q學(xué)習(xí)算法,提出VTGA-Q-Learning,其流程如圖7所示,具體步驟如下:

步驟1初始化學(xué)習(xí)率α、衰減系數(shù)γ、貪婪因子ε;設(shè)置最大幕數(shù)episode、常權(quán)重參數(shù)w、障礙物記憶區(qū)、短時記憶區(qū)、虛擬獎勵學(xué)習(xí)步長C、經(jīng)驗池容量M,以及起點和終點。

步驟2設(shè)置初始化參數(shù)后,智能體同環(huán)境進(jìn)行交互(超過最大幕數(shù)則終止),用自適應(yīng)貪婪因子(式(10))對ε調(diào)整后,根據(jù)動作選擇機(jī)制獲得下一時刻的狀態(tài)觀測值(observation)、獎勵值(reward)和結(jié)束標(biāo)志位(done)。

步驟3判斷是否陷入地圖陷阱,是則返回步驟2,否則執(zhí)行步驟4。

步驟4每隔C步從經(jīng)驗區(qū)M中抽取虛擬目標(biāo),并由式(7)設(shè)置虛擬目標(biāo)獎勵。

步驟5根據(jù)式(1)更新Q表,將[st,at,r,observation]加入M中。

步驟6更新幕數(shù)并對done進(jìn)行判斷。如果done=goal,則更新到達(dá)目標(biāo)點的次數(shù),轉(zhuǎn)步驟2;如果done=obstacle,則將狀態(tài)observation加入障礙物記憶區(qū)間,轉(zhuǎn)步驟2;如果done=free,則執(zhí)行步驟7。

步驟7更新狀態(tài)s=observation,轉(zhuǎn)步驟2。

因為VTGA-Q-Learning面對未知環(huán)境,所以狀態(tài)集未知。因此在Q表的創(chuàng)建上,動態(tài)創(chuàng)建Q表而非創(chuàng)建固定維度的Q表(智能體同環(huán)境交互獲得觀測數(shù)據(jù)后查詢Q表,判斷當(dāng)前狀態(tài)是否為新狀態(tài),是則擴(kuò)展Q表)。圖7中的動作選擇機(jī)制的步驟描述如下:

步驟1輸入st,at-1,ε。

步驟2判斷當(dāng)前狀態(tài)是否存在Q表中,是則執(zhí)行步驟3,否則在Q表中創(chuàng)建新行后執(zhí)行步驟3。

步驟3判斷當(dāng)前狀態(tài)是否在障礙物記憶中,是則根據(jù)式(11)選擇動作,否則根據(jù)式(12)選擇動作。

(11)

(12)

4 算法性能測試與分析

4.1 測試環(huán)境

為驗證所提VTGA-Q-Learning算法的可行性和有效性,本文在Python 3.8+Open AI Gym和Pybullet中搭建環(huán)境地圖,操作系統(tǒng)為Windows10 x64,硬件信息為Intel i5-11400F,DDR4 8 GB。

本文針對未知環(huán)境下的路徑規(guī)劃問題設(shè)置了4種環(huán)境格柵地圖(如圖8)用于測試驗證算法。其中紅色方格表示智能體起點位置,黃色圓圈表示終點位置。圖8a為16×16維地圖,用于對比測試算法性能;圖8b～圖8d為25×25維復(fù)雜地圖,其中設(shè)計了大量地圖陷阱,用于測試本文算法的泛化性能以及規(guī)避地圖陷阱的能力。算法的參數(shù)設(shè)置如表1所示。

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

表中,C的取值對算法優(yōu)化影響較大,現(xiàn)在圖8a環(huán)境地圖中對參數(shù)C進(jìn)行研究,令C∈[0,600],按間隔50離散取值,每個C分別進(jìn)行10次實驗,計算其獎勵值,C=0時表示不使用虛擬獎勵。按式(13)對實驗數(shù)據(jù)進(jìn)行處理,給出10次實驗的平均獎勵步長比。如圖9所示,橫坐標(biāo)為實驗?zāi)粩?shù),共1 000幕;縱坐標(biāo)為10次實驗每幕獎勵值與步長比值的平均值,可見C=200時虛擬獎勵最大。因此,后文均取C=200。

(13)

式中:j為實驗次數(shù),j=1,…,10;rewardepisode,num_stepepisode分別為每一幕的總獎勵與總步長;episode為當(dāng)前幕數(shù),episode∈[0,max_episode]。

4.2 實驗結(jié)果分析

4.2.1 算法對比測試結(jié)果

圖10所示分別為Classic-Q-Learning,Dynamic-Q-Learning[40],AE-Q-learning[35],SA-Q-learning[34],Backward-Q-learning[36]和本文VTGA-Q-Learning在圖8a上的實驗數(shù)據(jù),包括episode-reward圖(左列)和episode-stepnum圖(右列)兩類數(shù)據(jù)。圖10中左右兩列的橫坐標(biāo)均為強(qiáng)化學(xué)習(xí)幕數(shù)(episode),左圖(episode-reward圖)縱坐標(biāo)為智能體每一幕的總獎勵值,右圖(episode-stepnum圖)縱坐標(biāo)為智能體在該幕下的累計步長。表2所示為各算法在圖8a上進(jìn)行10次實驗的平均數(shù)據(jù)。從圖10和表2可以發(fā)現(xiàn):

表2 各算法在圖8a上的實驗數(shù)據(jù)

(1)在10 000幕內(nèi),Classic-Q-Learning中智能體到達(dá)目標(biāo)點的總幕數(shù)為5 833幕;Dynamic-Q-Learning中智能體到達(dá)目標(biāo)點的總幕數(shù)為8 530幕;同時從圖10a和圖10c可見,兩種算法都不能穩(wěn)定收斂,獎勵值存在較大波動,收斂性較差;從圖10b和圖10d可見,智能體每幕的步長存在較大波動,表明智能體存在受ε影響而導(dǎo)致的隨機(jī)收斂問題,Classic-Q-Learning和Dynamic-Q-Learning在收斂階段仍存在因障礙物而提前終止的情況,降低了算法的效率。

(2)從圖10e和圖10f觀察到,AE-Q-learning在1 000幕內(nèi),智能體到達(dá)目標(biāo)點的總幕數(shù)為618幕;在197幕以后,智能體就能穩(wěn)定到達(dá)目標(biāo)點。表明該算法的收斂速度和穩(wěn)定性都有很大改進(jìn)。但對比Dynamic-Q-Learning可見,AE-Q-learning雖然提升了算法的收斂性,但是不能穩(wěn)定收斂,仍為隨機(jī)收斂。

(3)從圖10g和圖10h觀察到,SA-Q-learning在1 000幕內(nèi),智能體到達(dá)目標(biāo)點的總幕數(shù)為872幕;在188幕以后,智能體就能穩(wěn)定收斂到達(dá)目標(biāo)點。表明該算法的收斂速度和穩(wěn)定性都有很大改進(jìn),但從實驗數(shù)據(jù)可見其步長峰值較高,平均用時為155.631 s,對比Dynamic-Q-Learning法10 000幕的用時,可見SA-Q-learning在提升算法收斂性的同時降低了收斂速度。

(4)從圖10i和圖10j觀察到,Backward-Q-learning在1 000幕內(nèi),智能體到達(dá)目標(biāo)點的總幕數(shù)為892幕;在124幕以后,智能體穩(wěn)定收斂到達(dá)目標(biāo)點。從表2的實驗數(shù)據(jù)可見其平均用時為201.423 s,對比Dynamic-Q-Learning和SA-Q-learning可知,Backward-Q-learning在提升收斂性的同時,也因Backward模塊降低了算法效率。

(5)從圖10k和圖10l觀察到,VTGA-Q-Learning在1 000幕內(nèi),智能體到達(dá)目標(biāo)點的總幕數(shù)為935幕;智能體在57幕就已準(zhǔn)確到達(dá)最終目標(biāo)點,并在82幕后穩(wěn)定到達(dá)目標(biāo)點,平均用時比AE-Q-learning降低42.322%,比SA-Q-learning降低63.471%,比Backward-Q-learning降低71.776%。表明所提改進(jìn)方法能有效提高算法的收斂速度和穩(wěn)定性,其次對比圖10的a,c,e,g,1 5張圖可見,VTGA-Q-Learning的獎勵值更為豐富。

4.2.2 魯棒性測試

魯棒性測試實驗用圖8b～圖8d進(jìn)行測試,實驗數(shù)據(jù)分別如表3～表5(10次實驗的平均數(shù)據(jù))、圖11～圖13所示,對比算法采用SA-Q-learning和Backward-Q-learning(Classic-Q-Learning,Dynamic-Q-Learning,AE-Q-learning算法在1 000幕內(nèi)不能收斂)。

表3 各算法在圖8b環(huán)境地圖上的實驗數(shù)據(jù)

表4 各算法在圖8c環(huán)境地圖上的實驗數(shù)據(jù)

表5 各算法在圖8d環(huán)境地圖上的實驗數(shù)據(jù)

從表3可見,在環(huán)境圖8b上,相比SA-Q-learning在286幕、Backward-Q-learning在307幕初次到達(dá)目標(biāo)點,VTGA-Q-Learning在253幕首次探尋到目標(biāo)點且收斂速度和成功率均較好,3種算法規(guī)劃的路徑長度相同;同時由圖11f對比可見,VTGA-Q-Learning在步長峰值和稀疏獎勵問題上都得到很大改善,緩解了盲目探索問題。

從表4可見,在圖8c上,VTGA-Q-Learning的收斂速度比對比算法有較大改善;從初次到達(dá)目標(biāo)點的幕數(shù)來看,VTGA-Q-Learning針對包含陷阱的地圖仍有較好的適應(yīng)性;從圖12f可見,VTGA-Q-Learning的步長峰值遠(yuǎn)低于對比算法,且成功率相對較高。

從表5可見,在面對包含較多凹型陷阱的復(fù)雜環(huán)境(如圖8d)時,VTGA-Q-Learning在263幕收斂時,對比算法還未找到目標(biāo)點;從收斂用時和成功率上看,VTGA-Q-Learning在提高收斂速度的同時,并未降低探索的有效性;從圖13可見,VTGA-Q-Learning步長得到明顯改善,且獎勵值更加密集。

4.2.3ε曲線分析

為體現(xiàn)自適應(yīng)貪婪因子中ε的變化,圖14給出了VTGA-Q-Learning在圖8a～圖8d中的自適應(yīng)貪婪因子的變化曲線。從圖14a～圖14d可見,起始階段智能體有一段完全探索時期(ε=1),期間智能體對環(huán)境進(jìn)行充分探索;在對環(huán)境信息有所掌握后,由探索經(jīng)驗估計地圖的復(fù)雜程度和交互程度來ε調(diào)整的變化速率;當(dāng)交互程度較高時,ε變化速率減緩,逐漸穩(wěn)定在較小值,使策略比較保守,更傾向于利用已有知識。對比圖14a和圖14b～圖14d可見,面對比較簡單的環(huán)境,ε的變化比較平滑;反觀圖14b～圖14d,面對復(fù)雜環(huán)境,ε隨交互程度和環(huán)境復(fù)雜程度主動調(diào)節(jié)變換速率,所提自適應(yīng)貪婪因子對環(huán)境具有較好的自適應(yīng)能力。

5 虛擬仿真實驗

在第4章算法性能對比實驗的基礎(chǔ)上,本文進(jìn)一步開展虛擬仿真實驗,通過模擬真實環(huán)境,驗證機(jī)器人的自主路徑規(guī)劃能力和工程實用性。虛擬仿真實驗用四驅(qū)麥克納姆輪小車作為測試對象,在Pybullet軟件中模擬創(chuàng)建室內(nèi)環(huán)境地圖,如圖15所示,圖中黑色為障礙物,紅色為目標(biāo)點,紫色為四驅(qū)麥克納姆輪小車。四驅(qū)麥克納姆輪小車具有前后左右行走能力,搭載有高性能控制器、4個超聲波傳感器、里程計等;超聲波傳感器安裝在小車的4個邊(對應(yīng)小車4個動作的方向),每邊的感知范圍為±20°,距離為2 cm～450 cm;里程計定位精度≤0.15 m,能夠根據(jù)上位機(jī)發(fā)出的目標(biāo)位置自主探索路徑;小車模型與實物圖如圖16所示。根據(jù)小車尺寸、感知范圍和行走定位誤差,定義每個正方形柵格邊長為1 m,小車位于柵格中心。

在相同室內(nèi)環(huán)境下,本項目開展了兩組實驗,實驗1如圖15a所示,實驗2如圖15b所示,圖中紅色為目標(biāo)點,紫色為小車當(dāng)前起始位置,實驗1和實驗2的起點和終點相反,以表現(xiàn)算法的泛化性。為了驗證算法的穩(wěn)定性,每組實驗各做10次。按照算法設(shè)計,小車接到目的地位置指令后開始進(jìn)行探索,小車移動方向?qū)?yīng)的超聲波傳感器檢測到0.02 m內(nèi)有障礙物即視為碰撞,然后根據(jù)算法設(shè)置返回起點再次探索;當(dāng)小車定位在距目標(biāo)≤0.02 m,且小車移動方向所對應(yīng)的超聲波傳感器檢測到0.02 m內(nèi)有障礙物時,視為成功并輸出起點到終點的軌跡列表。

在本文強(qiáng)化學(xué)習(xí)算法驅(qū)動下,小車每次實驗都能準(zhǔn)確找到最優(yōu)路徑,其中兩組虛擬仿真實驗第10次路徑規(guī)劃結(jié)果如圖17所示,表明所提算法具有良好的泛化性。因為強(qiáng)化學(xué)習(xí)的特性,每組中10次實驗得到的最優(yōu)路徑并不完全相同,路徑探索時間和路徑長度的統(tǒng)計數(shù)據(jù)如表6所示。從表中可見,實驗1路徑長度均值為18.598 m,標(biāo)準(zhǔn)差為0.287 m,實驗2路徑長度均值為18.903 m,標(biāo)準(zhǔn)差為0.225 m,而且兩組實驗各自探索時間也非常接近,表明算法穩(wěn)定性較好。

表6 規(guī)劃路徑長度與探索時間統(tǒng)計分析

綜上所述,小車在兩組實驗中都能穩(wěn)定到達(dá)目標(biāo)點,而且每次實驗數(shù)據(jù)無較大波動,表明本文算法具有較好的穩(wěn)定性、泛化性和工程適用性。

6 結(jié)束語

本文針對環(huán)境信息未知的移動機(jī)器人路徑規(guī)劃問題,提出一種VTGA-Q-Learning,相對常規(guī)Q學(xué)習(xí)算法,其改進(jìn)如下:

(1)雙重記憶機(jī)制 在一定程度上減少了地圖維度帶來的維度災(zāi)難問題,而且引入障礙物記憶機(jī)制,避免探索時重復(fù)選擇無效動作,增強(qiáng)了對復(fù)雜地圖的適應(yīng)性,加快了收斂速度。

(2)虛擬目標(biāo)引導(dǎo)方法 通過從歷史經(jīng)驗中提取中間態(tài)信息,并將中間態(tài)反映在動態(tài)獎勵函數(shù)設(shè)置上,使智能體學(xué)習(xí)到比較重要的中間狀態(tài),從而改善稀疏獎勵,提高智能體的目標(biāo)趨向性。

(3)自適應(yīng)貪婪因子 自適應(yīng)動作選擇策略自適應(yīng)地平衡了探索和利用的關(guān)系,并根據(jù)機(jī)器人同環(huán)境的交互程度確定主要參數(shù);同時根據(jù)交互經(jīng)驗設(shè)置動作概率,避免了非貪婪時均勻動作選擇的弊端。

通過4種地圖進(jìn)行仿真測試表明,相對其他Q學(xué)習(xí)算法,本文VTGA-Q-Learning提高了Q學(xué)習(xí)的收斂性和收斂速度,具有很好的泛化性和障礙陷阱規(guī)避能力,并通過虛擬仿真實驗證明了本文算法的工程適用性。