彭云建，梁 進(jìn)

(華南理工大學(xué) 自動(dòng)化科學(xué)與工程學(xué)院，廣東 廣州 510640)

0 引 言

隨著人工智能的發(fā)展，能自主移動(dòng)的智能體機(jī)器人在工業(yè)、軍事以及醫(yī)療領(lǐng)域得到廣泛使用[1]，路徑規(guī)劃要求智能體避開(kāi)障礙物，找到從出發(fā)點(diǎn)到目標(biāo)點(diǎn)的最佳或次優(yōu)路徑[2]，是移動(dòng)智能體被廣泛使用和發(fā)揮價(jià)值的基礎(chǔ)。其中未知環(huán)境下的路徑規(guī)劃是研究的難點(diǎn)和熱點(diǎn)，目前主要的方法有人工勢(shì)場(chǎng)法[3]、神經(jīng)網(wǎng)絡(luò)、遺傳算法、粒子群等智能算法[4]。

在利用強(qiáng)化學(xué)習(xí)解決未知情況下的路徑規(guī)劃方面，M.C. Su等人提出在路徑規(guī)劃的理論中增加強(qiáng)化學(xué)習(xí)方法[5]。沈晶等人提出基于分層強(qiáng)化學(xué)習(xí)的路徑規(guī)劃的方法[6]。Y. Song 等人提出一種有效的移動(dòng)機(jī)器人Q學(xué)習(xí)方法[7]。然而，在利用強(qiáng)化學(xué)習(xí)解決路徑規(guī)劃時(shí)，都會(huì)遇到強(qiáng)化學(xué)習(xí)本身固有的問(wèn)題，即探索-利用問(wèn)題[8]。為了解決探索-利用問(wèn)題，目前提出的方法有ε貪婪方法和對(duì)其改進(jìn)的ε-first方法[9]、ε-decreasing方法[10]，還有梯度算法[11]、value difference based exploration(VDBE)方法[12]等，但各有優(yōu)點(diǎn)和不足，仍然有優(yōu)化的空間。

該文根據(jù)優(yōu)化ε值的改變方式和利用動(dòng)作價(jià)值來(lái)動(dòng)態(tài)選擇采取的動(dòng)作的思想，提出了基于探索-利用權(quán)衡優(yōu)化的Q學(xué)習(xí)路徑規(guī)劃方法，解決移動(dòng)智能體在未知環(huán)境下的路徑規(guī)劃問(wèn)題。

1 探索-利用權(quán)衡優(yōu)化的Q學(xué)習(xí)算法

為了實(shí)現(xiàn)智能體在未知環(huán)境下的路徑規(guī)劃，基于探索-利用權(quán)衡優(yōu)化的Q學(xué)習(xí)路徑規(guī)劃可以分為兩個(gè)部分，一是利用強(qiáng)化學(xué)習(xí)中Q學(xué)習(xí)不需要事先知道環(huán)境，智能體依然能與未知環(huán)境的互動(dòng)中學(xué)習(xí)的特點(diǎn)，通過(guò)獲得足夠的幕數(shù)學(xué)習(xí)經(jīng)驗(yàn)，不斷更新Q表的動(dòng)作價(jià)值，進(jìn)而不斷更新優(yōu)化路徑規(guī)劃策略，實(shí)現(xiàn)路徑規(guī)劃；二是利用提出的εDBE方法和AεBS，權(quán)衡強(qiáng)化學(xué)習(xí)中固有的探索-利用問(wèn)題，提高未知環(huán)境下路徑規(guī)劃的快速性。

基于探索-利用權(quán)衡優(yōu)化的Q學(xué)習(xí)路徑規(guī)劃如圖1所示。提出改進(jìn)探索-利用權(quán)衡問(wèn)題的εDBE方法和AεBS方法，著重優(yōu)化ε值的改變方式和利用Q表中的動(dòng)作價(jià)值來(lái)動(dòng)態(tài)選擇采取的動(dòng)作，通過(guò)智能體與環(huán)境互動(dòng)產(chǎn)生每幕學(xué)習(xí)經(jīng)驗(yàn)來(lái)影響Q表動(dòng)作價(jià)值的評(píng)估，進(jìn)而獲得更優(yōu)動(dòng)作行為、更新獲得更優(yōu)路徑規(guī)劃策略。

圖1 探索-利用權(quán)衡優(yōu)化的Q學(xué)習(xí)路徑規(guī)劃

圖2 智能體與環(huán)境交互圖

智能體與環(huán)境交互如圖2所示，每幕學(xué)習(xí)經(jīng)驗(yàn)定義如下：在t時(shí)刻，智能體處于狀態(tài)st，采取動(dòng)作at，因此在t+1時(shí)刻，智能體獲得來(lái)自環(huán)境的獎(jiǎng)勵(lì)rt+1，并在環(huán)境中發(fā)生了狀態(tài)轉(zhuǎn)移，到達(dá)了狀態(tài)st+1。在智能體與環(huán)境的不斷交互過(guò)程中可獲得一個(gè)狀態(tài)、行動(dòng)、獎(jiǎng)勵(lì)的序列：s0，a0，r1，s1，a1，r2，s2，a2，r3，s3，…，sT,其中T是終止時(shí)刻，這樣有終止?fàn)顟B(tài)的一個(gè)序列也稱(chēng)為一幕(episode)學(xué)習(xí)經(jīng)驗(yàn)。

2 改進(jìn)探索-利用權(quán)衡問(wèn)題的εDBE方法和AεBS方法

2.1 權(quán)衡探索-利用問(wèn)題的基本方法

為了解決強(qiáng)化學(xué)習(xí)固有的探索-利用問(wèn)題，經(jīng)典的Q學(xué)習(xí)算法中采用了ε-貪婪方法。之后有研究人員提出了改進(jìn)ε-貪婪方法的ε-first方法、ε-decreasing方法，都是為了更好權(quán)衡探索-利用問(wèn)題，提高Q學(xué)習(xí)算法解決問(wèn)題的能力。

2.1.1ε-貪婪方法

ε-貪婪方法的思想是設(shè)定一個(gè)小的貪婪探索系數(shù)，0<ε≤1,在選擇要采取哪個(gè)動(dòng)作時(shí)，有ε的概率從所有可選的動(dòng)作中隨機(jī)選擇，有1-ε的概率選擇目前能獲得最大回報(bào)的動(dòng)作?？捎檬?1)表示：

(1)

其中，π(a|s)為在狀態(tài)s下選擇動(dòng)作a的概率，m為狀態(tài)s下動(dòng)作集合A(s)中動(dòng)作a的總個(gè)數(shù),a∈A(s),a*為狀態(tài)s下的最優(yōu)動(dòng)作。

2.1.2ε-first方法

ε-first方法[9]的思想是一開(kāi)始將ε的值設(shè)為1，讓智能體處于完全探索狀態(tài)，一段訓(xùn)練幕數(shù)(episode)之后，將ε的值設(shè)為0，讓智能體處于完全利用環(huán)境狀態(tài)?？捎檬?2)表示：

(2)

其中，episode為幕數(shù)變量，preset_episo為預(yù)先設(shè)定的幕數(shù)值。

2.1.3ε-decreasing方法

改進(jìn)的ε-decreasing方法[10]是ε-貪婪方法和ε-first方法的折中，思想是初始將ε設(shè)為一個(gè)較大的值，從訓(xùn)練幕數(shù)來(lái)看，ε隨著訓(xùn)練幕數(shù)增加不斷減少；從單幕的步數(shù)來(lái)看，ε隨者步數(shù)增加而增大。可用式(3)表示：

(3)

其中，ε0為貪婪系數(shù)的初始設(shè)定值，episode為幕數(shù)變量，step為每幕的步數(shù)變量。

2.2 εDBE方法和AεBS方法

針對(duì)Q學(xué)習(xí)中固有的探索-利用問(wèn)題，該文提出隨幕數(shù)(episodes)平滑衰減ε-值的ε-decreasing based episodes(εDBE)方法，以及根據(jù)Q表中的狀態(tài)動(dòng)作值判斷到達(dá)狀態(tài)的陌生/熟悉程度、做出探索或利用選擇的adaptiveεbased state (AεBS)方法。

2.2.1εDBE方法

隨幕數(shù)(episodes)平滑衰減ε值的εDBE方法結(jié)合了ε-decreasing方法和ε-貪婪方法的特點(diǎn)，即將初始ε設(shè)為一個(gè)較小的值，從訓(xùn)練幕數(shù)的角度來(lái)看，隨著訓(xùn)練幕數(shù)增加而不斷衰減；從單幕的步數(shù)角度來(lái)看ε保持不變，結(jié)合了ε-decreasing方法中ε衰減的特點(diǎn)，同時(shí)也具有ε-貪婪方法在每一幕步數(shù)中ε保持不變的特點(diǎn)。在選擇同時(shí)滿(mǎn)足上述兩個(gè)特點(diǎn)的ε衰減函數(shù)上，采用式(4)控制ε值的衰減。

(4)

其中，ε0為貪婪系數(shù)的初始設(shè)定值，0<ε0≤1，episode為幕數(shù)變量。

將式(4)與式(1)結(jié)合可得式(5)。

2.2.2 AεBS方法

根據(jù)到達(dá)位置的陌生/熟悉程度和動(dòng)作價(jià)值，從而做出探索/利用的動(dòng)態(tài)動(dòng)作選擇AεBS方法。引入不斷學(xué)習(xí)更新的Q表中動(dòng)作價(jià)值作為陌生/熟悉程度的指標(biāo)，當(dāng)狀態(tài)s下所對(duì)應(yīng)的所有動(dòng)作價(jià)值全為0時(shí)，認(rèn)為該狀態(tài)對(duì)于智能體來(lái)說(shuō)是陌生的；當(dāng)狀態(tài)s下所對(duì)應(yīng)的所有動(dòng)作價(jià)值不全為0時(shí)，認(rèn)為該狀態(tài)對(duì)于智能體來(lái)說(shuō)是熟悉的。在每幕學(xué)習(xí)的每一個(gè)步(step)中，遇到陌生的位置狀態(tài)，ε值變?yōu)?，采取探索模式隨機(jī)選擇動(dòng)作集中的任一動(dòng)作；遇到熟悉的位置狀態(tài)，ε值變?yōu)?，采取利用模式選擇狀態(tài)動(dòng)作價(jià)值最大的動(dòng)作。另外融合ε-first方法的思想，根據(jù)未知環(huán)境情況的不同，在幕數(shù)段中加入很小的ε值對(duì)Q表更新進(jìn)行微調(diào)整?？捎檬?6)表示：

(6)

其中，episode為幕數(shù)變量,episo1和episo2為設(shè)定的幕數(shù)值，ε0為貪婪系數(shù)的初始設(shè)定值，0<ε0≤1，A(s)為狀態(tài)s下的動(dòng)作集合。

由于初始階段中Q表的動(dòng)作價(jià)值均初始化為零，因此采用AεBS方法的智能體可以充分探索環(huán)境，即每當(dāng)遇到動(dòng)作價(jià)值為零時(shí)智能體會(huì)判斷出自身處于陌生環(huán)境，更傾向于隨機(jī)選擇不同的動(dòng)作進(jìn)行探索，更有可能不斷遇到陌生情況，探索更為充分。同時(shí)在與環(huán)境的交互中不斷更新Q表的動(dòng)作價(jià)值，增加環(huán)境熟悉程度，從而利用Q表的動(dòng)作價(jià)值的大小比較選擇最優(yōu)動(dòng)作，進(jìn)而不斷更新路徑策略。

3 引入εDBE方法和AεBS方法的Q學(xué)習(xí)路徑規(guī)劃

在未知環(huán)境路徑規(guī)劃下，移動(dòng)智能體在不同的狀態(tài)s下通過(guò)策略π選擇要采取的動(dòng)作a，與環(huán)境進(jìn)行交互獲得獎(jiǎng)勵(lì)r，并到達(dá)下一狀態(tài)s'。重復(fù)上述過(guò)程不斷迭代探索，更新Q表中的動(dòng)作價(jià)值，找到更好的動(dòng)作，直至找到最優(yōu)策略π*，完成未知環(huán)境下的路徑規(guī)劃。時(shí)序差分方法是評(píng)估價(jià)值函數(shù)和尋找最優(yōu)策略的實(shí)用方法。時(shí)序差分方法可以使智能體能直接與環(huán)境互動(dòng)的經(jīng)驗(yàn)中學(xué)習(xí)，不需要構(gòu)建關(guān)于環(huán)境的動(dòng)態(tài)特性。

Q學(xué)習(xí)是off-policy下的時(shí)序差分控制方法，是強(qiáng)化學(xué)習(xí)的一個(gè)重要突破[14]。Q學(xué)習(xí)更新的是動(dòng)作價(jià)值函數(shù)，更新方法如式(7)所示：

Q(st,at)←Q(st,at)+α[rt+1+

γmaxaQ(st+1,a)-Q(st,at)]

(7)

其中，α為學(xué)習(xí)率，0<α<1；γ稱(chēng)為折扣因子，表示未來(lái)獎(jiǎng)勵(lì)對(duì)當(dāng)前狀態(tài)的影響程度[15]，0≤γ≤1。

在t時(shí)刻智能體處于狀態(tài)st，動(dòng)作狀態(tài)價(jià)值為Q(st,at)，當(dāng)智能體采取動(dòng)作at后在t+1時(shí)刻到達(dá)狀態(tài)st+1并獲得獎(jiǎng)勵(lì)rt+1，此時(shí)智能體將在Q表中找到能夠使在狀態(tài)st+1下動(dòng)作價(jià)值最大的動(dòng)作a,以此來(lái)獲得Q(st+1,a)，從而對(duì)Q(st,at)進(jìn)行更新。

可將式(7)改寫(xiě)成式(8)。

Q(st,at)←(1-α)Q(st,at)+

α[rt+1+γmaxaQ(st+1,a)]

(8)

假設(shè)st+1所對(duì)應(yīng)的maxaQ(st+1,a)恒定，通過(guò)式(8)可迭代求得穩(wěn)定的Q(st,at)。

一次迭代：

Q(st,at)←(1-α)Q(st,at)+

α[rt+1+γmaxaQ(st+1,a)]

(9)

二次迭代：

Q(st,at)←(1-α)[(1-α)Q(st,at)+

α[rt+1+γmaxaQ(st+1,a)]]+

α[rt+1+γmaxaQ(st+1,a)]

←(1-α)2Q(st,at)+

[1-(1-α)2][rt+1+γmaxaQ(st+1,a)]

(10)

以此類(lèi)推，n次迭代：

Q(st,at)←(1-α)nQ(st,at)+

[1-(1-α)n][rt+1+γmaxaQ(st+1,a)]

(11)

因?yàn)?<α<1，所以0<1-α<1，當(dāng)n→∞時(shí)，Q(st,at)將以概率1收斂到最優(yōu)值，即：

Q(st,at)←rt+1+γmaxaQ(st+1,a)

(12)

當(dāng)Q表更新后，根據(jù)式(13)即可選出狀態(tài)下具有最大動(dòng)作狀態(tài)價(jià)值的動(dòng)作，從而獲得路徑規(guī)劃更優(yōu)策略π'的更新。

π'(s)=argmaxaQ(s,a)

(13)

該文以稀疏獎(jiǎng)勵(lì)的形式定義獎(jiǎng)勵(lì)函數(shù)r，如式(14)所示，將狀態(tài)分為障礙狀態(tài)、路徑狀態(tài)和目標(biāo)終點(diǎn)狀態(tài)，分別用狀態(tài)集合O(s)、P(s)、G(s)表示。其中到達(dá)障礙狀態(tài)獲得-1獎(jiǎng)勵(lì)值，到達(dá)目標(biāo)終點(diǎn)狀態(tài)獲得+1獎(jiǎng)勵(lì)值，到達(dá)路徑狀態(tài)獲得0獎(jiǎng)勵(lì)值，促使智能體避開(kāi)障礙物快速到達(dá)目標(biāo)終點(diǎn)。

(14)

每個(gè)狀態(tài)有上、下、左、右四個(gè)動(dòng)作可選擇，訓(xùn)練的過(guò)程為輸入當(dāng)前狀態(tài)后，根據(jù)(εDBE)方法或根據(jù)(AεBS)方法從Q表中選出當(dāng)前狀態(tài)的相應(yīng)動(dòng)作，與未知環(huán)境交互后獲得獎(jiǎng)勵(lì)，進(jìn)入下一狀態(tài)并判斷是否撞到障礙物。

若判定會(huì)撞到障礙物,則根據(jù)式(8)更新Q表后結(jié)束本幕學(xué)習(xí)，開(kāi)始下一個(gè)幕的學(xué)習(xí);若判定不會(huì)撞到障礙物,則根據(jù)式(8)更新Q表后進(jìn)入下一狀態(tài),本幕學(xué)習(xí)直至到達(dá)終點(diǎn)或判定會(huì)發(fā)生碰撞障礙物后結(jié)束。重復(fù)學(xué)習(xí)過(guò)程,不斷更新Q表中各個(gè)狀態(tài)的動(dòng)作價(jià)值，直至找到最優(yōu)策略，實(shí)現(xiàn)路徑規(guī)劃。

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

4.1 實(shí)驗(yàn)設(shè)計(jì)

該文在10*10的地圖上進(jìn)行Q學(xué)習(xí)路徑規(guī)劃，設(shè)定了兩種智能體未知的不同環(huán)境，對(duì)提出的基于探索-利用權(quán)衡優(yōu)化的Q學(xué)習(xí)路徑規(guī)劃與基于經(jīng)典的ε-貪婪方法、ε-first方法、ε-decreasing方法的Q學(xué)習(xí)路徑規(guī)劃進(jìn)行比較，驗(yàn)證提出方法的可行性和高效快速性。

其中每個(gè)網(wǎng)格對(duì)應(yīng)一個(gè)狀態(tài)，用不同的狀態(tài)標(biāo)號(hào)表示[16]。即在位置(x,y)處的網(wǎng)格對(duì)應(yīng)的狀態(tài)標(biāo)號(hào)stateno可用式(15)表示。

stateno=10(x-1)+y

(15)

圖3所示為兩種智能體未知的情況地圖，狀態(tài)SS為起點(diǎn)位置，GS為終點(diǎn)位置，起始位置和路徑均用深灰色表示，黑色為障礙物。智能體在每個(gè)無(wú)障礙物的淺灰色位置狀態(tài)下，有上、下、左、右四個(gè)動(dòng)作可以選擇，碰到障礙物意味著一幕學(xué)習(xí)以失敗結(jié)束，獲得-1獎(jiǎng)勵(lì)值，并返回起點(diǎn)位置；到達(dá)終點(diǎn)意味著一幕學(xué)習(xí)以成功結(jié)束，獲得+1獎(jiǎng)勵(lì)值，并返回起點(diǎn)位置；到達(dá)其余狀態(tài)均獲得0獎(jiǎng)勵(lì)值。

圖3 兩種智能體未知的環(huán)境地圖

4.2 結(jié)果分析

通過(guò)Q學(xué)習(xí)路徑規(guī)劃可以得到以下仿真實(shí)驗(yàn)結(jié)果：圖4所示為未知環(huán)境地圖1下的仿真實(shí)驗(yàn)結(jié)果，其中折扣因子γ=0.8，學(xué)習(xí)率α=0.2，ε-貪婪方法的ε值為0.1，ε-decreasing方法的ε初始值為0.8，εDBE的ε初始值為0.2，AεBS方法在30幕前的ε值為0.05。從圖4(b)可以發(fā)現(xiàn)，Q學(xué)習(xí)可以實(shí)現(xiàn)路徑規(guī)劃，找到從起點(diǎn)到終點(diǎn)的最優(yōu)路徑，狀態(tài)轉(zhuǎn)移步數(shù)為11步。

圖4 未知環(huán)境地圖1中的仿真實(shí)驗(yàn)結(jié)果

從圖4(c)不同方法不同幕下ε變化比較中，ε-decreasing方法中ε衰減過(guò)程較為波動(dòng)，εDBE方法中ε衰減過(guò)程較為平緩。

從圖4(d)不同方法路徑成功率比較中可以看到，提出的(εDBE)方法和(AεBS)方法都比經(jīng)典的ε-貪婪方法、ε-first方法、ε-decreasing方法能更快找到最優(yōu)路徑，在相同的幕數(shù)經(jīng)驗(yàn)學(xué)習(xí)下成功率更高。

從圖4(e)不同方法路徑步數(shù)收斂變化比較中也可以看出，(εDBE)方法和(AεBS)方法最優(yōu)路徑收斂更快，ε-貪婪方法大約在170幕左右收斂、ε-first方法大約在110幕左右收斂、ε-decreasing方法大約在100幕左右收斂，(εDBE)方法和(AεBS)方法大約在60幕左右收斂。

在圖4(f)不同方法路徑步數(shù)收斂后方法特性比較中，由于(εDBE)方法和ε-貪婪方法中ε-值不為零，會(huì)出現(xiàn)一些細(xì)小的探索“尖刺”，但這些額外探索并不會(huì)妨礙智能體根據(jù)Q表中動(dòng)作價(jià)值函數(shù)找到最優(yōu)路徑。

為了檢驗(yàn)不同未知復(fù)雜環(huán)境下基于探索-利用權(quán)衡優(yōu)化的Q學(xué)習(xí)路徑規(guī)劃方法的適應(yīng)性，在未知環(huán)境地圖2下繼續(xù)進(jìn)行仿真實(shí)驗(yàn)，其中折扣因子γ=0.8，學(xué)習(xí)率α=0.2，ε-decreasing方法的ε初始值為0.8，εDBE的ε初始值為0.2，AεBS方法在100幕到300間的ε值為0.1。

圖5所示為未知環(huán)境地圖2下的仿真實(shí)驗(yàn)結(jié)果。實(shí)驗(yàn)結(jié)果表明，提出的(εDBE)方法和(AεBS)方法較ε-first方法、ε-decreasing方法，在Q學(xué)習(xí)路徑規(guī)劃中依然能更有效快速找到最優(yōu)路徑，狀態(tài)轉(zhuǎn)移步數(shù)為20步，最優(yōu)路徑收斂所需的學(xué)習(xí)幕數(shù)更少，找到路徑的成功率更高。

圖5 未知環(huán)境地圖2中的仿真實(shí)驗(yàn)結(jié)果

5 結(jié)束語(yǔ)

針對(duì)移動(dòng)智能體在未知環(huán)境下的路徑規(guī)劃問(wèn)題，提出了基于探索-利用權(quán)衡優(yōu)化的Q學(xué)習(xí)路徑規(guī)劃。實(shí)驗(yàn)結(jié)果表明，該方法具有可行性和高效性：提出方法能找到最優(yōu)路徑，實(shí)現(xiàn)路徑規(guī)劃；與現(xiàn)有的權(quán)衡探索-利用的ε-貪婪方法、ε-first方法、ε-decreasing方法比較，提出的(εDBE)方法和(AεBS)方法能更好權(quán)衡探索-利用問(wèn)題，在未知障礙環(huán)境情況下具有快速學(xué)習(xí)適應(yīng)的特性，最優(yōu)路徑步數(shù)收斂速度更快，能高效可行地解決未知環(huán)境下的路徑規(guī)劃問(wèn)題。