基于探索-利用權衡優化的Q學習路徑規劃

彭云建，梁 進

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

0 引 言

隨著人工智能的發展，能自主移動的智能體機器人在工業、軍事以及醫療領域得到廣泛使用[1]，路徑規劃要求智能體避開障礙物，找到從出發點到目標點的最佳或次優路徑[2]，是移動智能體被廣泛使用和發揮價值的基礎。其中未知環境下的路徑規劃是研究的難點和熱點，目前主要的方法有人工勢場法[3]、神經網絡、遺傳算法、粒子群等智能算法[4]。

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

該文根據優化ε值的改變方式和利用動作價值來動態選擇采取的動作的思想，提出了基于探索-利用權衡優化的Q學習路徑規劃方法，解決移動智能體在未知環境下的路徑規劃問題。

1 探索-利用權衡優化的Q學習算法

為了實現智能體在未知環境下的路徑規劃，基于探索-利用權衡優化的Q學習路徑規劃可以分為兩個部分，一是利用強化學習中Q學習不需要事先知道環境，智能體依然能與未知環境的互動中學習的特點，通過獲得足夠的幕數學習經驗，不斷更新Q表的動作價值，進而不斷更新優化路徑規劃策略，實現路徑規劃；二是利用提出的εDBE方法和AεBS，權衡強化學習中固有的探索-利用問題，提高未知環境下路徑規劃的快速性。

基于探索-利用權衡優化的Q學習路徑規劃如圖1所示。提出改進探索-利用權衡問題的εDBE方法和AεBS方法，著重優化ε值的改變方式和利用Q表中的動作價值來動態選擇采取的動作，通過智能體與環境互動產生每幕學習經驗來影響Q表動作價值的評估，進而獲得更優動作行為、更新獲得更優路徑規劃策略。

圖1 探索-利用權衡優化的Q學習路徑規劃

圖2 智能體與環境交互圖

智能體與環境交互如圖2所示，每幕學習經驗定義如下：在t時刻，智能體處于狀態st，采取動作at，因此在t+1時刻，智能體獲得來自環境的獎勵rt+1，并在環境中發生了狀態轉移，到達了狀態st+1。在智能體與環境的不斷交互過程中可獲得一個狀態、行動、獎勵的序列：s0，a0，r1，s1，a1，r2，s2，a2，r3，s3，…，sT,其中T是終止時刻，這樣有終止狀態的一個序列也稱為一幕(episode)學習經驗。

2 改進探索-利用權衡問題的εDBE方法和AεBS方法

2.1 權衡探索-利用問題的基本方法

為了解決強化學習固有的探索-利用問題，經典的Q學習算法中采用了ε-貪婪方法。之后有研究人員提出了改進ε-貪婪方法的ε-first方法、ε-decreasing方法，都是為了更好權衡探索-利用問題，提高Q學習算法解決問題的能力。

2.1.1ε-貪婪方法

ε-貪婪方法的思想是設定一個小的貪婪探索系數，0<ε≤1,在選擇要采取哪個動作時，有ε的概率從所有可選的動作中隨機選擇，有1-ε的概率選擇目前能獲得最大回報的動作。可用式(1)表示：

(1)

其中，π(a|s)為在狀態s下選擇動作a的概率，m為狀態s下動作集合A(s)中動作a的總個數,a∈A(s),a*為狀態s下的最優動作。

2.1.2ε-first方法

ε-first方法[9]的思想是一開始將ε的值設為1，讓智能體處于完全探索狀態，一段訓練幕數(episode)之后，將ε的值設為0，讓智能體處于完全利用環境狀態。可用式(2)表示：

(2)

其中，episode為幕數變量，preset_episo為預先設定的幕數值。

2.1.3ε-decreasing方法

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

(3)

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

2.2 εDBE方法和AεBS方法

針對Q學習中固有的探索-利用問題，該文提出隨幕數(episodes)平滑衰減ε-值的ε-decreasing based episodes(εDBE)方法，以及根據Q表中的狀態動作值判斷到達狀態的陌生/熟悉程度、做出探索或利用選擇的adaptiveεbased state (AεBS)方法。

2.2.1εDBE方法

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

(4)

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

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

2.2.2 AεBS方法

根據到達位置的陌生/熟悉程度和動作價值，從而做出探索/利用的動態動作選擇AεBS方法。引入不斷學習更新的Q表中動作價值作為陌生/熟悉程度的指標，當狀態s下所對應的所有動作價值全為0時，認為該狀態對于智能體來說是陌生的；當狀態s下所對應的所有動作價值不全為0時，認為該狀態對于智能體來說是熟悉的。在每幕學習的每一個步(step)中，遇到陌生的位置狀態，ε值變為1，采取探索模式隨機選擇動作集中的任一動作；遇到熟悉的位置狀態，ε值變為0，采取利用模式選擇狀態動作價值最大的動作。另外融合ε-first方法的思想，根據未知環境情況的不同，在幕數段中加入很小的ε值對Q表更新進行微調整。可用式(6)表示：

(6)

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

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

3 引入εDBE方法和AεBS方法的Q學習路徑規劃

在未知環境路徑規劃下，移動智能體在不同的狀態s下通過策略π選擇要采取的動作a，與環境進行交互獲得獎勵r，并到達下一狀態s'。重復上述過程不斷迭代探索，更新Q表中的動作價值，找到更好的動作，直至找到最優策略π*，完成未知環境下的路徑規劃。時序差分方法是評估價值函數和尋找最優策略的實用方法。時序差分方法可以使智能體能直接與環境互動的經驗中學習，不需要構建關于環境的動態特性。

Q學習是off-policy下的時序差分控制方法，是強化學習的一個重要突破[14]。Q學習更新的是動作價值函數，更新方法如式(7)所示：

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

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

(7)

其中，α為學習率，0<α<1；γ稱為折扣因子，表示未來獎勵對當前狀態的影響程度[15]，0≤γ≤1。

在t時刻智能體處于狀態st，動作狀態價值為Q(st,at)，當智能體采取動作at后在t+1時刻到達狀態st+1并獲得獎勵rt+1，此時智能體將在Q表中找到能夠使在狀態st+1下動作價值最大的動作a,以此來獲得Q(st+1,a)，從而對Q(st,at)進行更新。

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

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

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

(8)

假設st+1所對應的maxaQ(st+1,a)恒定，通過式(8)可迭代求得穩定的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)

以此類推，n次迭代：

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

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

(11)

因為0<α<1，所以0<1-α<1，當n→∞時，Q(st,at)將以概率1收斂到最優值，即：

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

(12)

當Q表更新后，根據式(13)即可選出狀態下具有最大動作狀態價值的動作，從而獲得路徑規劃更優策略π'的更新。

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

(13)

該文以稀疏獎勵的形式定義獎勵函數r，如式(14)所示，將狀態分為障礙狀態、路徑狀態和目標終點狀態，分別用狀態集合O(s)、P(s)、G(s)表示。其中到達障礙狀態獲得-1獎勵值，到達目標終點狀態獲得+1獎勵值，到達路徑狀態獲得0獎勵值，促使智能體避開障礙物快速到達目標終點。

(14)

每個狀態有上、下、左、右四個動作可選擇，訓練的過程為輸入當前狀態后，根據(εDBE)方法或根據(AεBS)方法從Q表中選出當前狀態的相應動作，與未知環境交互后獲得獎勵，進入下一狀態并判斷是否撞到障礙物。

若判定會撞到障礙物,則根據式(8)更新Q表后結束本幕學習，開始下一個幕的學習;若判定不會撞到障礙物,則根據式(8)更新Q表后進入下一狀態,本幕學習直至到達終點或判定會發生碰撞障礙物后結束。重復學習過程,不斷更新Q表中各個狀態的動作價值，直至找到最優策略，實現路徑規劃。

4 實驗結果及分析

4.1 實驗設計

該文在10*10的地圖上進行Q學習路徑規劃，設定了兩種智能體未知的不同環境，對提出的基于探索-利用權衡優化的Q學習路徑規劃與基于經典的ε-貪婪方法、ε-first方法、ε-decreasing方法的Q學習路徑規劃進行比較，驗證提出方法的可行性和高效快速性。

其中每個網格對應一個狀態，用不同的狀態標號表示[16]。即在位置(x,y)處的網格對應的狀態標號stateno可用式(15)表示。

stateno=10(x-1)+y

(15)

圖3所示為兩種智能體未知的情況地圖，狀態SS為起點位置，GS為終點位置，起始位置和路徑均用深灰色表示，黑色為障礙物。智能體在每個無障礙物的淺灰色位置狀態下，有上、下、左、右四個動作可以選擇，碰到障礙物意味著一幕學習以失敗結束，獲得-1獎勵值，并返回起點位置；到達終點意味著一幕學習以成功結束，獲得+1獎勵值，并返回起點位置；到達其余狀態均獲得0獎勵值。

圖3 兩種智能體未知的環境地圖

4.2 結果分析

通過Q學習路徑規劃可以得到以下仿真實驗結果：圖4所示為未知環境地圖1下的仿真實驗結果，其中折扣因子γ=0.8，學習率α=0.2，ε-貪婪方法的ε值為0.1，ε-decreasing方法的ε初始值為0.8，εDBE的ε初始值為0.2，AεBS方法在30幕前的ε值為0.05。從圖4(b)可以發現，Q學習可以實現路徑規劃，找到從起點到終點的最優路徑，狀態轉移步數為11步。

圖4 未知環境地圖1中的仿真實驗結果

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

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

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

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

為了檢驗不同未知復雜環境下基于探索-利用權衡優化的Q學習路徑規劃方法的適應性，在未知環境地圖2下繼續進行仿真實驗，其中折扣因子γ=0.8，學習率α=0.2，ε-decreasing方法的ε初始值為0.8，εDBE的ε初始值為0.2，AεBS方法在100幕到300間的ε值為0.1。

圖5所示為未知環境地圖2下的仿真實驗結果。實驗結果表明，提出的(εDBE)方法和(AεBS)方法較ε-first方法、ε-decreasing方法，在Q學習路徑規劃中依然能更有效快速找到最優路徑，狀態轉移步數為20步，最優路徑收斂所需的學習幕數更少，找到路徑的成功率更高。

圖5 未知環境地圖2中的仿真實驗結果

5 結束語

針對移動智能體在未知環境下的路徑規劃問題，提出了基于探索-利用權衡優化的Q學習路徑規劃。實驗結果表明，該方法具有可行性和高效性：提出方法能找到最優路徑，實現路徑規劃；與現有的權衡探索-利用的ε-貪婪方法、ε-first方法、ε-decreasing方法比較，提出的(εDBE)方法和(AεBS)方法能更好權衡探索-利用問題，在未知障礙環境情況下具有快速學習適應的特性，最優路徑步數收斂速度更快，能高效可行地解決未知環境下的路徑規劃問題。