基于改進(jìn)Q-Learning的路徑規(guī)劃算法

張小月，韓尚君，陶青川，余艷梅

（四川大學(xué)電子信息學(xué)院，成都 610065）

0 引言

路徑規(guī)劃一直是機(jī)器人領(lǐng)域的重點(diǎn)問題，也是未來研究的熱點(diǎn)。常見的路徑規(guī)劃算法有Dijskra、RRT、A*、蟻群算法，可以在連續(xù)或是離散的空間中實(shí)現(xiàn)尋路。近年來機(jī)器學(xué)習(xí)興起，由Watkins提出的Q-Learning算法又重新回歸人們的視野，該方法在數(shù)字動(dòng)畫、游戲、個(gè)性化推薦、無人駕駛等眾多領(lǐng)域有著廣泛的應(yīng)用。而RRT、A*等方法有著計(jì)算量大、實(shí)時(shí)性差的缺點(diǎn)，Q-Learning通過訓(xùn)練能快速尋找到最短路徑，它在路徑規(guī)劃上有著天然的優(yōu)勢(shì)。

強(qiáng)化學(xué)習(xí)的靈感來源于心理學(xué)，智能體從與環(huán)境的交互中學(xué)習(xí)來獲取經(jīng)驗(yàn)，這個(gè)經(jīng)驗(yàn)會(huì)指導(dǎo)智能體根據(jù)環(huán)境的狀態(tài)執(zhí)行動(dòng)作，并根據(jù)環(huán)境的反饋增加新的經(jīng)驗(yàn)。本文對(duì)經(jīng)典的強(qiáng)化學(xué)習(xí)算法Q-Learning算法進(jìn)行改進(jìn)，優(yōu)化Q表格初始值，使用“探索引導(dǎo)”，解決了Q-Learning收斂速度慢的問題。

1 Q-Learning算法理論

1.1 強(qiáng)化學(xué)習(xí)組成結(jié)構(gòu)

強(qiáng)化學(xué)習(xí)主要是由智能體和環(huán)境構(gòu)成，其通信渠道有獎(jiǎng)勵(lì)、狀態(tài)和動(dòng)作。強(qiáng)化學(xué)習(xí)的框架如圖1所示，S是環(huán)境在t時(shí)刻的狀態(tài)，A是智能體在環(huán)境中t時(shí)刻執(zhí)行的動(dòng)作，A使得環(huán)境的狀態(tài)變?yōu)镾，在新狀態(tài)下環(huán)境產(chǎn)生了新的反饋R，智能體根據(jù)S和R執(zhí)行新的動(dòng)作A，如此循環(huán)往復(fù)直到迭代結(jié)束。

圖1 強(qiáng)化學(xué)習(xí)的框架

1.2 馬爾科夫決策

假設(shè)強(qiáng)化學(xué)習(xí)的求解過程滿足馬爾科夫?qū)傩约礋o后效性，系統(tǒng)的下一個(gè)狀態(tài)只與當(dāng)前的狀態(tài)有關(guān)，與之前的更早的狀態(tài)無關(guān)。馬爾科夫決策過程（MDP）的四元組是，S是狀態(tài)集合，S表示t時(shí)刻的狀態(tài)，A是動(dòng)作集，A表示t時(shí)刻的動(dòng)作，R是獎(jiǎng)勵(lì)函數(shù)，R=R（S，A）表示在狀態(tài)S下執(zhí)行A后智能體獲得的獎(jiǎng)勵(lì)，P是狀態(tài)轉(zhuǎn)移概率，記作P（S,R|S,A），表示t時(shí)刻狀態(tài)為S執(zhí)行動(dòng)作A后，獲得獎(jiǎng)勵(lì)R且下一個(gè)狀態(tài)為S的概率分布。完整的馬爾科夫決策模型如圖2所示。

圖2 馬爾科夫決策鏈

因?yàn)楝F(xiàn)實(shí)生活中，獎(jiǎng)勵(lì)往往是延遲的，不能只考慮當(dāng)前的單步收益，并且還需要考慮未來的獎(jiǎng)勵(lì)。想要使未來收益之和更加合理，距離當(dāng)前越遠(yuǎn)的收益，對(duì)現(xiàn)在的影響越小，引入折扣因子γ，是一個(gè)介于［0,1］的常數(shù)。使用G來表示未來累積獎(jiǎng)勵(lì)，表達(dá)式如下：

1.3 探索與利用

對(duì)于免模型的環(huán)境，探索和利用是相輔相成的，想要獲取更多的環(huán)境信息就需要探索，想要提高獎(jiǎng)勵(lì)、制定最優(yōu)策略需要進(jìn)行利用，兩者同樣重要。強(qiáng)化學(xué)習(xí)算法訓(xùn)練時(shí)的輪數(shù)是有限的，探索的占比增加會(huì)導(dǎo)致利用的次數(shù)減少，所以需要權(quán)衡探索與利用的使用比例。

ε-貪婪算法用于表示探索與利用的行為，以ε概率進(jìn)行“探索”，即智能體隨機(jī)選擇一個(gè)動(dòng)作，以1-ε概率進(jìn)行“利用”，選擇獎(jiǎng)勵(lì)最大的動(dòng)作作為下一個(gè)要執(zhí)行的動(dòng)作，這時(shí)會(huì)利用已知的環(huán)境和獎(jiǎng)勵(lì)信息。數(shù)學(xué)表達(dá)式如下：

ε參數(shù)的選擇會(huì)影響收斂速度，當(dāng)ε的值較大時(shí)，探索的機(jī)會(huì)更多，模型的收斂速度快；當(dāng)ε的值較小時(shí)，利用的機(jī)會(huì)更多，模型會(huì)更加穩(wěn)定，但收斂速度比較慢。若動(dòng)作對(duì)應(yīng)的獎(jiǎng)勵(lì)不確定性較小、概率分布較寬時(shí)，建議使用較大的ε值；若動(dòng)作對(duì)應(yīng)的獎(jiǎng)勵(lì)不確定性較小、概率分布較集中時(shí)，少量嘗試就能接近真實(shí)的獎(jiǎng)勵(lì)，可以使用較小的ε值。ε的值通常取一個(gè)常數(shù)，比如0.1或0.01。

1.4 Q-Lear ni ng算法

時(shí)序差分算法Q-Learning使用Q表格記錄動(dòng)作價(jià)值，下一個(gè)時(shí)刻的Q值會(huì)影響當(dāng)前時(shí)刻的Q值，使得Q逼近未來總收益G。Q-Learning在選擇動(dòng)作時(shí)會(huì)默認(rèn)選擇最優(yōu)策略，即最大Q值對(duì)應(yīng)的動(dòng)作，但這可能與下一時(shí)刻的實(shí)際執(zhí)行動(dòng)作不一致，所以說Q-Learning是一種偏向最優(yōu)Q的策略。動(dòng)作值函數(shù)Q（S，A）如下：

根據(jù)ε-貪婪算法來決定使用哪一個(gè)動(dòng)作，1-ε的概率執(zhí)行最大Q值對(duì)應(yīng)的動(dòng)作，ε的概率隨機(jī)執(zhí)行一個(gè)動(dòng)作。執(zhí)行完動(dòng)作A后，智能體與環(huán)境交互，獲得下一個(gè)狀態(tài)S和獎(jiǎng)勵(lì)R。在更新Q值時(shí)，時(shí)序差分目標(biāo)使用動(dòng)作值函數(shù)的最大值對(duì)應(yīng)的動(dòng)作a，在策略上想要獲得最大收益，但實(shí)際上會(huì)執(zhí)行動(dòng)作A。

2 基于改進(jìn)Q-Learning的路徑規(guī)劃算法

2.1 經(jīng)典Q-Lear ni ng實(shí)例

本文借用百度飛槳（PaddlePaddle）的開源Q-Learning項(xiàng)目，對(duì)該項(xiàng)目中的Q-Learning算法進(jìn)行改進(jìn)。如圖3的柵格模型所示，智能體是烏龜，起點(diǎn)為左下角烏龜所在位置，終點(diǎn)為右下角格子。OpenAI的gym庫提供了常用的強(qiáng)化學(xué)習(xí)環(huán)境，這里解決的是Gym庫中的懸崖尋路問題，黑色區(qū)域是懸崖，每次烏龜?shù)袈鋺已潞髸?huì)重新回到上一步的位置。Q表格是一個(gè)大小為12×4且初始值為0的矩陣，隨后使用ε-貪婪算法執(zhí)行動(dòng)作，更新狀態(tài)和獎(jiǎng)勵(lì)，使用動(dòng)作值函數(shù)（公式3）更新Q表格。訓(xùn)練次數(shù)設(shè)置為1500次，每次烏龜?shù)竭_(dá)終點(diǎn)就會(huì)重回起點(diǎn)開始新一輪的訓(xùn)練，測(cè)試結(jié)果如圖3的路線所示，智能體會(huì)根據(jù)Q值選擇最優(yōu)路徑。

圖3 懸崖環(huán)境（CliffWalking-v0）

對(duì)于每輪的獎(jiǎng)勵(lì)，初始值是0，烏龜每走一個(gè)白格子，獎(jiǎng)勵(lì)減1，每走一個(gè)黑格子，獎(jiǎng)勵(lì)減100。如果走最短的路徑，需要走13步，得到的獎(jiǎng)勵(lì)是-13，也是所有路徑中收益最大的情況。

圖4是訓(xùn)練迭代次數(shù)-步數(shù)曲線圖，縱坐標(biāo)表示步數(shù)，橫坐標(biāo)表示為訓(xùn)練迭代次數(shù)。隨著訓(xùn)練次數(shù)的增加，步數(shù)會(huì)逐漸減少到40以下。曲線一直都沒有收斂，因?yàn)楦鶕?jù)ε-貪婪算法有ε概率隨機(jī)選擇動(dòng)作的情況，這里ε設(shè)置了0.1，所以智能體有90%的情況進(jìn)行利用，10%的情況進(jìn)行探索。

圖4 原始的訓(xùn)練次數(shù)-步數(shù)曲線圖

為了方便觀察，圖5還繪制了訓(xùn)練次數(shù)-獎(jiǎng)勵(lì)（相反數(shù)）曲線圖，Q-Learning算法訓(xùn)練1500次，由于獎(jiǎng)勵(lì)是負(fù)數(shù)，所以獎(jiǎng)勵(lì)的相反數(shù)越小說明實(shí)際的獎(jiǎng)勵(lì)越大。圖5作為圖4的補(bǔ)充，因?yàn)橹悄荏w無論是走黑格子還是白格子，步數(shù)都是增加1，而白格子的獎(jiǎng)勵(lì)是-1，黑格子的獎(jiǎng)勵(lì)是-100，所以使用獎(jiǎng)勵(lì)的相反數(shù)作為縱坐標(biāo)能區(qū)分智能體走不同格子的情況。

圖5 原始的訓(xùn)練迭代次數(shù)-獎(jiǎng)勵(lì)（相反數(shù)）曲線

2.2 改進(jìn)Q-Lear ni ng的方法

本文分別從Q表格的初始值和探索訓(xùn)練過程兩個(gè)不同的角度來改進(jìn)Q-Learning，以此來減少訓(xùn)練次數(shù)。對(duì)Q-Learning的具體改進(jìn)如下：一是引入初始化Q表格的方法并使用歐氏距離或曼哈頓距離修改Q表格的初始值，二是提出使用“探索引導(dǎo)”來避開障礙物。

2.2.1 初始化Q表格

傳統(tǒng)的Q-Learning會(huì)將Q值初始化為0，想要智能體選擇最短路徑，可以初始化Q值為當(dāng)前位置到目標(biāo)位置的距離的倒數(shù)或相反數(shù)。離目標(biāo)越近Q值就越大，智能體在訓(xùn)練初期更容易朝著目標(biāo)位置的方向前進(jìn)。

2.2.2 探索引導(dǎo)

針對(duì)10%的探索的情況，智能體有可能會(huì)多次選擇掉入懸崖（黑格子）的動(dòng)作，這種情況應(yīng)當(dāng)避免。本文提出的“探索引導(dǎo)”目的是在探索的時(shí)候引導(dǎo)智能體盡量選擇無障礙的路線，方法具體內(nèi)容如下：當(dāng)智能體在前幾次掉入懸崖后，當(dāng)前位置對(duì)應(yīng)的Q值會(huì)遠(yuǎn)小于Q表格中的其他Q值。在10%隨機(jī)動(dòng)作之前加一個(gè)判斷，排除Q值較小即容易掉入懸崖的動(dòng)作，這樣就可以加快獎(jiǎng)勵(lì)收斂的速度。

2.3 實(shí)驗(yàn)結(jié)果

2.3.1 初始化Q表格的實(shí)驗(yàn)結(jié)果

2.2.1設(shè)計(jì)的三組實(shí)驗(yàn)的訓(xùn)練迭代次數(shù)-步數(shù)曲線圖如圖6所示?？梢灾庇^地看出圖6（c）即Q表格初始值為-d的情況表現(xiàn)最好，基本上訓(xùn)練幾次，步數(shù)就減少到25以下了。另外實(shí)驗(yàn)兩組都是在訓(xùn)練次數(shù)快到400的時(shí)候步數(shù)才減到40以下，（a）比（b）稍微好一點(diǎn)，但不明顯。

圖6 Q表格不同初始中對(duì)應(yīng)的訓(xùn)練迭代次數(shù)-步數(shù)曲線

手動(dòng)設(shè)置訓(xùn)練次數(shù)，在減少訓(xùn)練次數(shù)后，可以得到獲取最優(yōu)路徑的最少訓(xùn)練次數(shù)，Q表格初始化為0時(shí)，至少需要訓(xùn)練280次；Q表格初始化為1/d時(shí)至少需要訓(xùn)練260次；Q表格初始化為1/d時(shí)至少需要訓(xùn)練310次；Q表格初始化為-d時(shí)至少需要訓(xùn)練20次。由于存在10%的概率探索，最少訓(xùn)練次數(shù)具有偶然性，但無論如何，使用-d來初始化Q表格可以減少訓(xùn)練次數(shù)是毋庸置疑的。由于Q值初始化為曼哈頓距離的情況表現(xiàn)不佳，后面的實(shí)驗(yàn)只會(huì)用到歐式距離。

2.3.2 探索引導(dǎo)的實(shí)驗(yàn)結(jié)果

本文設(shè)置“探索引導(dǎo)”的閾值為-50，即智能體不會(huì)探索Q值小于-50的格子。圖8記錄了使用“探索引導(dǎo)”后，Q表格不同初始值對(duì)應(yīng)的訓(xùn)練迭代次數(shù)-步數(shù)曲線圖。這一次Q值初始為-d時(shí)，步數(shù)在剛開始就收斂到了一個(gè)很低的數(shù)。只看圖7的（a）（b）即Q值初始值分別為0和1/d時(shí)，“探索引導(dǎo)”好像并沒有改善的作用，但是從獎(jiǎng)勵(lì)的角度來看，“探索引導(dǎo)”可以減少走黑格子即獎(jiǎng)勵(lì)值為-100的情況。

圖7 使用“探索引導(dǎo)”后，Q表格不同初始值對(duì)應(yīng)的訓(xùn)練迭代次數(shù)-步數(shù)曲線

如圖8所示，加入了探索引導(dǎo)后，隨著訓(xùn)練次數(shù)的增加，獎(jiǎng)勵(lì)能夠快速收斂。（a）圖是Q值初始化為0的時(shí)候，“探索引導(dǎo)”使得獎(jiǎng)勵(lì)在訓(xùn)練了450次左右就收斂了。這里收斂的訓(xùn)練次數(shù)跟2.3.1中最少訓(xùn)練次數(shù)是不一樣的，獎(jiǎng)勵(lì)收斂后，進(jìn)行測(cè)試的時(shí)候，智能體一定會(huì)走最優(yōu)路徑，而最少訓(xùn)練次數(shù)是一個(gè)不穩(wěn)定的值，運(yùn)氣好的情況下，在訓(xùn)練次數(shù)等于最少訓(xùn)練次數(shù)的時(shí)候智能體會(huì)選擇最優(yōu)路徑，但并不是每次都能成功。圖8分別是Q初始化為0、1/d和-d的情況下，使用了“探索引導(dǎo)”的訓(xùn)練次數(shù)-獎(jiǎng)勵(lì)（相反數(shù)）曲線圖，（b）中獎(jiǎng)勵(lì)收斂速度更快，大概訓(xùn)練300次左右就收斂了，比Q值初始為0的情況訓(xùn)練次數(shù)少了30%，（c）圖中，獎(jiǎng)勵(lì)的初始值更小。

圖8 使用“探索引導(dǎo)”后，Q表格不同初始值對(duì)應(yīng)的訓(xùn)練迭代次數(shù)-獎(jiǎng)勵(lì)（相反數(shù)）曲線

3 結(jié)語

實(shí)驗(yàn)結(jié)果顯示，可以從兩個(gè)方面來改善QLearning：一是Q表格的初始值，使用-d可以減少訓(xùn)練次數(shù)，利用目標(biāo)點(diǎn)與當(dāng)前位置的距離作為先驗(yàn)知識(shí)，智能體會(huì)選擇執(zhí)行離目標(biāo)點(diǎn)更近的動(dòng)作；二是使用了“探索引導(dǎo)”，讓智能體在多次“碰壁”后能夠?qū)W習(xí)避開障礙的經(jīng)驗(yàn)，下次探索的時(shí)候排除掉落懸崖的動(dòng)作，從剩下的動(dòng)作中隨機(jī)選擇。這兩個(gè)方法能夠均能減少訓(xùn)練次數(shù)，不僅減少了時(shí)間和計(jì)算的成本，還提高Q-Learning的效率。