基于改進Q-Learning的路徑規劃算法

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

（四川大學電子信息學院，成都 610065）

0 引言

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

強化學習的靈感來源于心理學，智能體從與環境的交互中學習來獲取經驗，這個經驗會指導智能體根據環境的狀態執行動作，并根據環境的反饋增加新的經驗。本文對經典的強化學習算法Q-Learning算法進行改進，優化Q表格初始值，使用“探索引導”，解決了Q-Learning收斂速度慢的問題。

1 Q-Learning算法理論

1.1 強化學習組成結構

強化學習主要是由智能體和環境構成，其通信渠道有獎勵、狀態和動作。強化學習的框架如圖1所示，S是環境在t時刻的狀態，A是智能體在環境中t時刻執行的動作，A使得環境的狀態變為S，在新狀態下環境產生了新的反饋R，智能體根據S和R執行新的動作A，如此循環往復直到迭代結束。

圖1 強化學習的框架

1.2 馬爾科夫決策

假設強化學習的求解過程滿足馬爾科夫屬性即無后效性，系統的下一個狀態只與當前的狀態有關，與之前的更早的狀態無關。馬爾科夫決策過程（MDP）的四元組是，S是狀態集合，S表示t時刻的狀態，A是動作集，A表示t時刻的動作，R是獎勵函數，R=R（S，A）表示在狀態S下執行A后智能體獲得的獎勵，P是狀態轉移概率，記作P（S,R|S,A），表示t時刻狀態為S執行動作A后，獲得獎勵R且下一個狀態為S的概率分布。完整的馬爾科夫決策模型如圖2所示。

圖2 馬爾科夫決策鏈

因為現實生活中，獎勵往往是延遲的，不能只考慮當前的單步收益，并且還需要考慮未來的獎勵。想要使未來收益之和更加合理，距離當前越遠的收益，對現在的影響越小，引入折扣因子γ，是一個介于［0,1］的常數。使用G來表示未來累積獎勵，表達式如下：

1.3 探索與利用

對于免模型的環境，探索和利用是相輔相成的，想要獲取更多的環境信息就需要探索，想要提高獎勵、制定最優策略需要進行利用，兩者同樣重要。強化學習算法訓練時的輪數是有限的，探索的占比增加會導致利用的次數減少，所以需要權衡探索與利用的使用比例。

ε-貪婪算法用于表示探索與利用的行為，以ε概率進行“探索”，即智能體隨機選擇一個動作，以1-ε概率進行“利用”，選擇獎勵最大的動作作為下一個要執行的動作，這時會利用已知的環境和獎勵信息。數學表達式如下：

ε參數的選擇會影響收斂速度，當ε的值較大時，探索的機會更多，模型的收斂速度快；當ε的值較小時，利用的機會更多，模型會更加穩定，但收斂速度比較慢。若動作對應的獎勵不確定性較小、概率分布較寬時，建議使用較大的ε值；若動作對應的獎勵不確定性較小、概率分布較集中時，少量嘗試就能接近真實的獎勵，可以使用較小的ε值。ε的值通常取一個常數，比如0.1或0.01。

1.4 Q-Lear ni ng算法

時序差分算法Q-Learning使用Q表格記錄動作價值，下一個時刻的Q值會影響當前時刻的Q值，使得Q逼近未來總收益G。Q-Learning在選擇動作時會默認選擇最優策略，即最大Q值對應的動作，但這可能與下一時刻的實際執行動作不一致，所以說Q-Learning是一種偏向最優Q的策略。動作值函數Q（S，A）如下：

根據ε-貪婪算法來決定使用哪一個動作，1-ε的概率執行最大Q值對應的動作，ε的概率隨機執行一個動作。執行完動作A后，智能體與環境交互，獲得下一個狀態S和獎勵R。在更新Q值時，時序差分目標使用動作值函數的最大值對應的動作a，在策略上想要獲得最大收益，但實際上會執行動作A。

2 基于改進Q-Learning的路徑規劃算法

2.1 經典Q-Lear ni ng實例

本文借用百度飛槳（PaddlePaddle）的開源Q-Learning項目，對該項目中的Q-Learning算法進行改進。如圖3的柵格模型所示，智能體是烏龜，起點為左下角烏龜所在位置，終點為右下角格子。OpenAI的gym庫提供了常用的強化學習環境，這里解決的是Gym庫中的懸崖尋路問題，黑色區域是懸崖，每次烏龜掉落懸崖后會重新回到上一步的位置。Q表格是一個大小為12×4且初始值為0的矩陣，隨后使用ε-貪婪算法執行動作，更新狀態和獎勵，使用動作值函數（公式3）更新Q表格。訓練次數設置為1500次，每次烏龜到達終點就會重回起點開始新一輪的訓練，測試結果如圖3的路線所示，智能體會根據Q值選擇最優路徑。

圖3 懸崖環境（CliffWalking-v0）

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

圖4是訓練迭代次數-步數曲線圖，縱坐標表示步數，橫坐標表示為訓練迭代次數。隨著訓練次數的增加，步數會逐漸減少到40以下。曲線一直都沒有收斂，因為根據ε-貪婪算法有ε概率隨機選擇動作的情況，這里ε設置了0.1，所以智能體有90%的情況進行利用，10%的情況進行探索。

圖4 原始的訓練次數-步數曲線圖

為了方便觀察，圖5還繪制了訓練次數-獎勵（相反數）曲線圖，Q-Learning算法訓練1500次，由于獎勵是負數，所以獎勵的相反數越小說明實際的獎勵越大。圖5作為圖4的補充，因為智能體無論是走黑格子還是白格子，步數都是增加1，而白格子的獎勵是-1，黑格子的獎勵是-100，所以使用獎勵的相反數作為縱坐標能區分智能體走不同格子的情況。

圖5 原始的訓練迭代次數-獎勵（相反數）曲線

2.2 改進Q-Lear ni ng的方法

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

2.2.1 初始化Q表格

傳統的Q-Learning會將Q值初始化為0，想要智能體選擇最短路徑，可以初始化Q值為當前位置到目標位置的距離的倒數或相反數。離目標越近Q值就越大，智能體在訓練初期更容易朝著目標位置的方向前進。

2.2.2 探索引導

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

2.3 實驗結果

2.3.1 初始化Q表格的實驗結果

2.2.1設計的三組實驗的訓練迭代次數-步數曲線圖如圖6所示。可以直觀地看出圖6（c）即Q表格初始值為-d的情況表現最好，基本上訓練幾次，步數就減少到25以下了。另外實驗兩組都是在訓練次數快到400的時候步數才減到40以下，（a）比（b）稍微好一點，但不明顯。

圖6 Q表格不同初始中對應的訓練迭代次數-步數曲線

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

2.3.2 探索引導的實驗結果

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

圖7 使用“探索引導”后，Q表格不同初始值對應的訓練迭代次數-步數曲線

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

圖8 使用“探索引導”后，Q表格不同初始值對應的訓練迭代次數-獎勵（相反數）曲線

3 結語

實驗結果顯示，可以從兩個方面來改善QLearning：一是Q表格的初始值，使用-d可以減少訓練次數，利用目標點與當前位置的距離作為先驗知識，智能體會選擇執行離目標點更近的動作；二是使用了“探索引導”，讓智能體在多次“碰壁”后能夠學習避開障礙的經驗，下次探索的時候排除掉落懸崖的動作，從剩下的動作中隨機選擇。這兩個方法能夠均能減少訓練次數，不僅減少了時間和計算的成本，還提高Q-Learning的效率。