基于改進Q-learning算法的移動機器人局部路徑規劃

張耀玉，李彩虹，張國勝，李永迪，梁振英

(山東理工大學 計算機科學與技術學院, 山東 淄博 255049)

隨著科學技術的快速發展，移動機器人的應用越來越廣泛。在移動機器人的研究中，機器人避障并且規劃有效路徑是至關重要的問題[1]。移動機器人的路徑規劃分為全局路徑規劃[2]和局部路徑規劃[3]。全局路徑規劃是在靜態已知環境信息下，尋找一條從起點到目標點的無碰撞最優路徑。局部路徑規劃是在未知或部分已知環境信息下，在移動過程中利用傳感器等檢測環境信息進行實時路徑規劃。

當前有效避障的路徑規劃方法有很多，傳統方法主要有A*算法[4]、Dijkstra算法[5]、模糊控制法[6]、遺傳算法[7]、人工勢場法[8]和神經網絡[9]等。而智能算法的應用在很大程度上解決了傳統算法效率低下、操作復雜等缺點。Q-learning算法是Watikins提出的一種強化學習算法[10]，在移動機器人路徑規劃領域中應用廣泛，具有不依賴環境先驗模型的特點；缺點是算法收斂速度較慢，在訓練次數不夠多時找不到最優路徑。因此，高樂等[11]在Q-learning算法的基礎上增加了一層學習過程，對環境進行了深度學習，提高了算法的收斂速度。毛國君等[12]引入了動態搜索因子ε，根據環境的反饋來動態調整貪婪因子ε，當探索路徑失敗時，增大ε使下一次探索的隨機性增大；反之，則通過減少ε來增加目的性，該方法有效地減少了迭代搜索的代價，能夠找到更優的路徑。Oh等[13]采用基于模糊規則的Q-learning算法指定Q值，然后與傳統的Q-learning算法相融合來加速算法的學習效率，以更少的迭代次數獲得良好的結果。Lillicrap等[14]以神經網絡來擬合Q-learning中的Q(s,a)，然后采用經驗回放和目標網絡的方法來改善Q-learning算法收斂穩定性。

本文針對傳統的Q-learning算法存在的學習速度慢、效率低等問題，提出一種改進的IQ-learning算法，實現移動機器人的局部路徑規劃。在傳統Q-learning算法的基礎上，增加對角線運動獎勵值，減少算法在初始階段盲目搜索問題，減少規劃路徑的長度，提高路徑的規劃效率，使移動機器人在更短時間內找到一條從起點到目標點的較優路徑。

1 Q-learning算法

強化學習是從環境狀態到動作映射的學習，使動作從環境中獲得的獎勵最大，其工作原理如圖1所示。強化學習基于馬爾可夫決策過程(Markov decisions process, MDP)[15]。馬爾可夫屬性是指系統的狀態只與當前狀態有關，而與更早之前的狀態無關。

圖1 強化學習工作原理

Q-learning算法是強化學習算法之一，是基于Q值迭代的無模型算法。通過不斷迭代，對每個可能的狀態動作進行多次嘗試，最終學到最優的控制策略[16]。迭代過程中不斷對Q值更新，Q值的更新公式為

newQ(s,a)=(1-α)Q(s,a)+α(R(s,a)+

γmaxQ'(s',a')),

(1)

式中：s和s'分別代表當前狀態和下一個狀態；a代表s到s'的有效動作；Q(s,a)代表當前狀態s和動作a的Q值；R(s,a)是指當前狀態s和動作a的獎勵；maxQ'(s',a')代表下一個狀態下所有動作中最大的Q值；α表示學習率，α越大，Q值收斂越快，但也越容易產生振蕩，本文α取0.6。根據式(1)，Q-learning算法在某個狀態下采取貪心策略對所有可能路徑進行探索，每前進一步都在尋找當前狀態下的局部最優解。

2 IQ-learning算法

本文所設計的IQ-learning算法在Q-learning算法基礎上，在獎懲函數中添加對角線運動獎勵值，使得移動機器人在路徑規劃時減少盲目搜索，提高算法的學習效率。

2.1 柵格地圖設計

本文基于柵格地圖構造機器人的運行環境。運行環境為20×20的八連通柵格地圖，結合二維直角坐標系確定柵格位置，并對每個柵格從下到上、從左到右依次標明序號，行和列的交叉位置代表地圖信息中的一個環境狀態。在柵格地圖中設置移動機器人的運行環境，包括障礙物、起點和目標點，如圖2所示。對于移動機器人來說，這些障礙物的位置信息未知，機器人在學習過程中根據執行動作后得到的獎懲值來確定障礙物的位置信息。

圖2 柵格地圖

2.2 狀態-動作的表示

設定移動機器人的起點和目標點后，將移動機器人看作一個質點，機器人在運行環境中的每個坐標表示一個狀態，記為st，坐標記為Φ(i,j)。根據柵格地圖的維數，共有Xlim×Ylim個狀態,其中lim∈[1,20]，lim為整數。所有狀態組成的狀態集S為

S={st|st=Φ(i,j),i∈Xlim,j∈Ylim}。

(2)

一般情況下，移動機器人的探索為上、下、左、右4個動作。為提高算法探索效率，增加對角線方向的探索行為，即以該質點為中心，定義移動機器人可以執行8個方向上的動作，記為ai(i=1～8)：上、下、左、右、右上、右下、左上和左下，機器人可以按照以上8個動作移動，平移一格的步長為1，對角線移動一格的步長約為1.4，如圖3所示。動作集合A記為

圖3 動作空間

A={ai,i=1～8}。

(3)

機器人選擇不同的動作執行后，狀態會發生不同的改變，分別執行8個動作時所對應的狀態變換見表1。

表1 狀態-動作關系表

2.3 Q表的設計

建立一個二維表，用來存儲Q值，其中行表示每種狀態s，列代表每種狀態的動作a，Q值是某一狀態下執行某種動作獲得的獎勵。根據移動機器人Xlim×Ylim個狀態、8個動作建立的Q表為

(4)

Q表建立后將其初始化，經過訓練不斷迭代更新，根據最終的Q表進行最優路徑的選擇。

2.4 獎懲函數的設計

獎懲函數R的設置對移動機器人的行動具有導向作用。為提高算法尋找最優路徑的效率，本文增加對角線移動的獎勵值，獎懲函數的設計為

(5)

2.5 動作策略的選擇

動作策略采取ε-greedy改進的貪心策略，在移動機器人做決策時，有ε的概率隨機選擇未知的一個動作，剩下的1-ε的概率選擇已有動作中價值最大的動作，公式為

π(a|s)=

(6)

式中：ε是小于1且很小的正數；a表示機器人的動作；s表示機器人的狀態；A(s)表示機器人處于某個狀態下可以選擇的動作集合。這種策略可以均衡利用與探索，采用回報值最大的動作值為利用，其他非最優的動作值有一定概率繼續探索。

2.6 IQ-learning算法的訓練過程

基于柵格地圖設計IQ-learning算法，完成移動機器人局部路徑規劃任務，算法學習步驟如下：

1) 清空二維環境地圖，給定移動機器人起點、目標點和障礙物信息。建立Pmat線性表，用來存儲從起點到目標點的歷史最佳狀態-動作對；Q表存儲當前學到的從起點到目標點的最佳狀態-動作對；len記錄當前最短路徑長度；min_total_steps記錄歷史最短路徑的長度。

初始化獎懲函數，學習次數i=0，最大學習次數Nmax=80。初始化Pmat線性表及歷史最短路徑長度min_total_steps=Nmax。

2)設置迭代計數器初始值count=0，len=Nmax，清空Q表。

3)根據式(6)動作選擇策略選擇一個動作a執行，執行完動作a后，機器人狀態轉為st +1，count++。若此時機器人已到達目標點，則轉到步驟6)；否則轉到步驟4)。

4)根據式(5)獎懲函數計算當前狀態的獎懲值。若機器人收到獎勵則轉到步驟5)；若機器人收到懲罰，則機器人退回上一個狀態s=st并轉到步驟3)繼續探索。

5)按照式(1)更新Q值，并轉到步驟3)繼續探索。

6)記錄迭代次數count值、當前最短路徑長度len，更新Q表，且i++。

7)更新Pmat表與min_total_steps的值。若學習次數i

3 仿真驗證

本文將分別在離散型障礙物、一字型障礙物、U型障礙物和混合型障礙物環境下，對所設計的IQ-learning算法的規劃路徑進行仿真，測試算法的可行性。在所設計的柵格地圖中設置移動機器人的起點和目標點，根據不同的環境設置不同的障礙物，在同一環境下對比Q-learning算法和IQ-learning算法訓練80次得到的最短路徑。

3.1 離散型障礙物環境下的路徑規劃仿真

IQ-learning算法在離散型障礙物環境下的訓練過程如圖4所示，圖中藍色圓點代表算法在探索路徑的過程中走過的柵格位置。由圖4可以看出，隨著算法訓練次數的增多，學習到的規劃路徑越來越好，路徑長度逐漸收斂到最短。

圖4 離散型障礙物環境下的訓練過程

Q-learning算法和IQ-learning算法訓練80次得到的最短路徑如圖5所示，由圖5可以看出,Q-learning算法訓練得到的路徑在坐標(7,8)處存在步數浪費的現象，此時路徑長度為20.8；而IQ-learning學習80次得到的機器人規劃路徑更短，此時路徑長度為19.4。

圖5 離散型障礙物環境下的路徑規劃

3.2 一字型障礙物環境下的路徑規劃仿真

移動機器人在一字形障礙物環境下規劃路徑時容易陷入對稱冗余狀態。IQ-learning算法在一字型障礙物環境下的訓練過程如圖6所示。從圖6可以看出，隨著算法訓練次數的增多，機器人逐漸走出對稱冗余狀態，并從中選擇了最短路徑。

圖6 一字型障礙物環境下的訓練過程

Q-learning算法和IQ-learning算法訓練80次得到的最短路徑如圖7所示，由圖7可以看出，Q-learning算法存在多處步數浪費現象，算法訓練得到的路徑長度為26.4；IQ-learning算法訓練得到的路徑更短，其路徑長度為22.8。

圖7 一字型障礙物環境下的路徑規劃

3.3 U型障礙物環境下的路徑規劃仿真

移動機器人在U型障礙物環境下規劃路徑時，因為傳感器信息感知的局限性，機器人容易陷入死鎖狀態，而找不到最優路徑。IQ-learning算法在U型障礙物環境下的訓練過程如圖8所示。從圖8可以看出，隨著算法訓練次數的增多，機器人不再進入U型區域，規劃的路徑長度也越來越短。

圖8 U型障礙物環境下的訓練過程

Q-learning算法和IQ-learning算法訓練80次得到的移動機器人最短路徑如圖9所示。由圖9可以看出，Q-learning算法學習80次得到的訓練路徑較長，在坐標(3,5)和(9,10)處有步數浪費現象，此時路徑長度為27；而IQ-learning算法學習80次后得到的路徑更優，此時路徑長度為24.8，路徑長度明顯減少。

圖9 U型障礙物環境下的路徑規劃

3.4 混合型障礙物環境下的路徑規劃仿真

混合障礙物環境包括離散障礙物、一字型障礙物和近似U型障礙物。IQ-learning算法在混合型障礙物環境下的訓練過程如圖10所示。從圖10可以看出，隨著算法訓練次數的增多，機器人能夠擺脫U型和一字型障礙物的阻礙，路徑逐漸收斂，最后學習到更短的路徑。

圖10 混合型障礙物環境下的訓練過程

Q-learning算法和IQ-learning算法訓練80次得到的移動機器人最短路徑如圖11所示。由圖11可以看出，Q-learning算法經過80次學習得到的最短可行路徑在坐標(14,13)處，有明顯的步數浪費，規劃的路徑較長，此時路徑長度為23.6；IQ-learning算法學習80次得到的路徑更短，此時訓練得到路徑長度為22.8。

圖11 混合型障礙物環境下的路徑規劃

經過以上仿真驗證，本文提出的IQ-learning算法能夠減少移動機器人在局部路徑規劃中的路徑長度，不進入死鎖或陷阱區域。在不同環境下兩種算法的路徑長度對比見表2。

表2 不同環境下的路徑長度

實驗中，Q-learning算法和IQ-learning算法都經過80次學習得到最短路徑。在混合型障礙物環境下，記錄了Q-leaning算法和IQ-learning算法的路徑長度變化趨勢，如圖12所示，由圖12可以看出Q-learning算法在訓練40次后路徑長度趨于收斂，而IQ-learning算法在訓練20次后，路徑長度明顯下降并趨于收斂。IQ-learning算法相較于Q-learning算法能在更少的訓練次數內找到較優的路徑，加快了收斂速度。

圖12 路徑長度變化趨勢對比

4 結束語

本文基于柵格地圖環境對Q-learning算法進行改進，加入對角線運動獎勵值，使得移動機器人在規劃路徑中能夠以更少的訓練次數得到更優的路徑。通過改進后的IQ-learning算法和Q-learning算法在同一障礙物環境和同樣訓練次數下的仿真實驗結果對比，IQ-learning算法訓練得到的路徑長度更短，其收斂速度也有所提高，驗證了IQ-learning算法的可行性。

然而隨著移動機器人所處環境狀態越來越復雜，使用Q值表存儲狀態-動作值函數的缺點越來越明顯，會引起維數災難。下一步的研究工作是利用函數近似逼近來替代Q值表，增強算法的可行性和通用性。