基于啟發式強化學習的移動機器人路徑規劃算法研究

潘國倩，周新志

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

0 引言

路徑規劃是移動機器人完成各種任務的必要前提，也是其進入現實生活的重要環節，還是研究智能機器人的重要組成部分，其主要目的就是要在機器人的運行環境中找到一條從起點到終點的無碰撞路徑。根據機器人對環境的已知程度，目前的路徑規劃方法可以分為環境已知的全局路徑規劃和環境未知的局部路徑規劃，如人工勢場法、模糊邏輯算法、蟻群算法、粒子群算法、神經網絡算法等。由于移動機器人在實際應用中需要應對一些突發情況，因此有必要引入一種自學習的機制使得機器人能夠通過學習來實現自主避障。

強化學習是一種基于“試錯”方式的學習算法，機器人通過不斷嘗試動作來與環境進行交互，獲得環境反饋的“獎勵”，進而選擇最佳動作規劃路徑。其不僅通過結合神經網絡、智能控制及運籌學等算法或理論知識在理論和應用方面發展迅速，而且也被越來越多地運用在機器人的自動控制、運動以及智能調度等領域，在人工智能方面成為了學者們研究的熱點。其中，Q-learning算法是目前使用最為廣泛的強化學習算法。Q-learning算法被應用于機器人路徑規劃時，由于其不具先驗知識，一般會直接將Q值表初始化為全零的矩陣，故往往存在學習時間長、收斂速度慢等問題。目前，已有研究來解決此類問題，文獻［7］使用人工勢能場虛擬化環境，并通過勢能值引入先驗知識初始化Q值，進而提高Q-learning算法的收斂速度；文獻［8］結合人工勢場法，通過重新定義機器人的動作及步長來改進Q-learning算法，提高了算法收斂速度；文獻［9］提出部分的Q學習概念，使用花授粉算法改善Q-learning算法的初始化，加快Q-learning算法的學習；文獻［10］在傳統的Q-learning算法基礎上增加一層學習，使得機器人能夠提前了解環境，進而加快路徑規劃效率；文獻［11］為了加快Q-learning的學習速度，提出了一種集成學習策略；文獻［12］限制了狀態數，進而通過減小Q值表的大小提高了算法尋優速度；文獻［13］研究了連續的報酬函數，使得機器人采取的每個動作都能獲得相應的報酬，提高算法的學習效率。

雖然目前已有許多方法被提出來優化Qlearning算法，但是移動機器人尋找最佳路徑依舊是一個值得研究的問題。本文主要針對Qlearning算法進行路徑規劃時所面臨的學習效率低、收斂慢的問題，提出一種基于Q-learning算法的啟發式算法（HQL）。首先根據移動機器人在工作環境中當前點和終點的相對位置來選擇當前狀態下的動作集，使機器人始終朝目標點前進，來提高學習速度；然后，在算法中引入啟發式獎勵機制，使得機器人在選擇靠近終點的動作時收獲更多的獎勵，進而減少機器人盲目學習。最后在柵格環境中進行仿真實驗，驗證該算法的性能。

1 Q-learning算法

Q-learning算法是Watkins等提出的一種強化學習算法，也是時序差分算法中最常用的算法之一。其主要采用異策略評價估值的方法，這種方式也在很大程度上促進了Q值的迭代更新。Q-learning算法會根據機器人上一次所處的狀態信息和當前學習所獲得的獎勵，通過式（1）來不斷地更新自身維護的Q值表，進而當Q值表收斂時，機器人能從中選出最佳的狀態-動作對，得到最優策略。

式（1）中，為學習率，表示學習新知識的程度，取值在0到1之間；是狀態下采取行動時的獎勵；為折扣率，表示考慮未來獎勵的程度，取值在0到1之間；為下一個狀態，為下一個動作。

2 HQL算法

傳統的Q-learning算法在初始化過程中會將值設為均等值或隨機值，也就是說，算法在初始階段屬于盲目學習，這在一定程度上降低了算法的學習效率。同樣地，傳統算法會在固定的動作集中選擇動作，由于算法的動作選擇策略存在一定的隨機性，因此機器人會存在冗余學習，進而出現規劃路徑不佳的情況。針對這些問題，本文在傳統的Q-learning算法的基礎上做出如下兩種改進，提出了改進的Q-learning算法。

2.1 動態動作集策略

傳統的Q-learning算法的動作集是固定的，一般是上、下、左、右四個動作或是增加四個斜向動作的八個動作。根據算法的動作選擇策略，機器人在選擇動作時，存在一定的概率會隨機選擇動作集中的動作，故機器人所選的動作可能會使其遠離終點，進而影響機器人的學習效率。鑒于常識，當我們出發去目的地時，一般會有意識地朝著目的地前進，這樣才會使我們盡快到達。由此，提出動態動作集策略，使得機器人的每一步都能朝著終點前進。

動作集選擇策略的主要思想是根據機器人當前所處的位置與終點的相對位置來給機器人分配動作集。本文以移動機器人的終點為參照，將算法的動作集分為如圖1所示的八種情況，然后根據式（2）判斷，此時機器人應該選擇哪一個動作集。

圖1 八種動作集

式（2）中，，分別為移動機器人當前位置的橫、縱坐標，x，y分別為終點的橫、縱坐標。機器人在某一狀態進行學習之前，會先將機器人當前坐標與終點坐標進行運算，當（xx )*(-y ）＞0且-x ＜0時，即d *d ＞0,d ＜0，機器人選擇第一種動作集，即圖1（a）所示動作集進行學習；當（-x )*(-y ）=0且-x ＜0時，即d *d =0,d ＜0，機器人選擇第二種動作集，即圖1（b）所示動作集；以此類推，式（2）中第3至第8條距離條件依次對應圖1（c）至圖1（h）所示的動作集。

2.2 啟發式獎懲函數

Q-learning算法是無模型的學習算法，存在盲目學習的問題。為使機器人剛開始學習的時候就有意識地朝著終點的方向學習，在一定程度上減少盲目學習，進一步加快算法的學習速度，本文從算法的獎懲函數出發，通過使機器人采取不同的動作獲得不同的獎勵來指導機器人學習環境。若機器人采取的動作使其更接近終點，則獲得更多的獎勵；反之，則獲得的獎勵會減少。

本文中傳統的Q-learning算法獎懲函數設置如式（3）所示。

引入啟發式獎勵后的獎懲函數設置如式（4）所示。

其中，r 為Q-learning算法設置的獎懲函數，，分別為移動機器人當前位置的橫、縱坐標，x，y分別為終點的橫、縱坐標。

2.3 流程設計

運用HQL算法進行路徑規劃步驟如下：

（1）初始化算法的值表；

（2）判斷機器人總的學習次數是否小于5000，若是，進入（3），若否，則結束學習；

（3）初始化狀態；

（4）根據策略選擇動作集；

（5）從動作集中選出下一步動作并執行；

（6）根據執行動作后的狀態得到相應的獎勵r；

（7）根據式（1）計算并更新值表；

（8）進入下一個狀態；

（9）判斷此時機器人所處的狀態是否為終點，若是，則返回（2）進入下一次學習，若否，則返回（4）。

3 實驗及結果分析

本文實驗使用Python進行編譯，實驗采用30×30的二維柵格地圖來表示整個環境信息。其中，左下圓點代表機器人的起點，右上圓點代表終點，實心方格表示障礙物，白色區域表示可移動區域。在仿真實驗中，傳統Q學習算法和本文算法學習過程中的實驗參數值設置如下。折扣因子表示考慮未來獎勵的程度，本文采取一個折中的方式，設為0.5。同時經過多次嘗試與試驗，將嘗試次數即機器人總的學習次數設為5000，學習率和探索因子的初始值分別設為0.8和0.3，使機器人能夠得到更加充分的學習且算法性能更加穩定。

在柵格地圖中對本文所提的改進算法與兩種傳統Q-learning算法進行驗證，證明本文的改進算法在規劃路徑的長度和學習效率方面的優勢。圖2（a）、（b）分別為表1中傳統Q-learning算法（QL_0）和本文算法（QL_2）在柵格地圖中生成的最優路徑。

表1 學習算法在路徑規劃中的性能比較

圖2 算法規劃的路徑圖

表1中算法的收斂回合、收斂時間和路徑長度均為30次實驗數據的平均值，QL_0算法表示動作集為上、下、左、右的傳統Q-learning算法；QL_1算法表示動作集為上、下、左、右、右上、右下、左上、左下的傳統Q-learning算法；QL_2為本文所提算法。在算法收斂的判斷中，本文主要根據連續10次嘗試回合路徑長度標準差小于0.25即視為算法收斂。

從表1可知，將本文所提算法即QL_2與傳統的四個動作的Q-learning算法即QL_0進行對比，算法的收斂回合提前了75.8%，收斂時間減少了45.3%，規劃的最終路徑長度縮短了24.5%。對比QL_1和QL_0可知，僅僅增加算法的動作數，雖然很大程度上縮短規劃路徑的長度，但是并沒有明顯加快算法的收斂速度。根據表1的數據，相較于QL_0和QL_1這兩種傳統學習算法，本文所提算法在不增加動作數的情況下不僅能夠縮短規劃的路徑長度，同時也能達到使算法更快收斂的目的。

4 結語

基于馬爾可夫決策過程的Q-learning算法在路徑規劃應用中一般可以找到到達終點的路徑，但是其在復雜環境下進行路徑規劃時學習效率低、收斂速度慢，由此提出了基于Q_learning算法的啟發式算法（HQL）。首先，學習算法是通過選擇每個狀態下最優動作的方式來完成路徑規劃，每一次的動作選擇都在一定程度上影響機器人的學習效果，故本文從源頭出發，通過控制動作集來使機器人進行更有效的學習，提高學習效率；其次，通過在算法中加入啟發式獎勵，機器人的每一個動作都能得到不同的獎勵，使得機器人能夠朝著終點運動，進一步加快其學習。最后從仿真實驗結果可以看出，相較于傳統的學習算法，本文所提算法性能更優。