基于改進Q-learning的移動機器人路徑規劃應用研究

文/彭玲玲 劉凱

關鍵字：移動機器人；路徑規劃；Q-learning算法；柵格法

引言

機器學習是研究如何使用機器來模擬人類學習活動的一門學科，包括監督學習、非監督學習和強化學習三類，近幾年隨著機器學習的發展，各類型移動機器人的應用也進入了高速發展期，它們可以完成一些人類無法完成或完成效率低耗時長的任務。在移動機器人的研究領域中，有效避障并路徑規劃[1]是一個很關鍵的問題，國內外在這個問題上有很多方法可以借鑒，主要包括：人工勢場法、基于路徑編碼的遺傳算法[2]、基于學習訓練的神經網絡和強化學習方法[3～4]、A*[6]等等。Watikins提出的Q-learning算法進行移動機器人的路徑規劃應用研究較為廣泛，其特點是無需環境的先驗知識，移動機器人與復雜的動態環境建立起一種交互關系，環境返給機器人一個當前的回報，機器人則根據回報評估所采取的動作，其收斂的條件是對每個可能的狀態和動作都進行多次的嘗試，并最終學到最優策略，即根據準則在未知環境中找到一條從起始點到目標點的最優或次優路徑。

本文的研究內容是針對Q-learning的一些缺點進行改進，并將改進的算法運用于移動機器人的路徑規劃，相關研究大多停留在理論的層面，缺少對實際問題與背景的解決方法。首先，本文介紹強化學習的原理與Q-learning算法基本原理，然后對移動機器人路徑規劃問題進行抽象建模，并對該問題應用改進的算法，使其在短時間內以最優路徑進行規劃，驗證算法的高效性，對結果進行相關分析。

1.強化學習

1.1 強化學習原理

經典的強化學習基于馬爾科夫決策過程（Markov decisions process，MDP），強化學習是指從環境狀態到動作映射的學習，使動作從環境中獲得的獎勵最大，從而使目標的值函數最大，其學習框架如圖1。

圖1 強化學習基本框架

1.2 Q-learning算法

移動機器人在路徑規劃的t時刻，可在有限的動作集合中，選取某個動作at，并將這個動作作用于環境中，環境接受該動作并進行狀態st到st+1的轉移，同時得到獎勵值R。Q學習就是采用狀態-動作對即Q(s,a)迭代方式來獲得最優策略，所以其值函數Q更新的公式為：

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

2.1 環境模型

本文將采用基于python的柵格地圖進行環境空間的構建，定義一個20×20的柵格環境，在編寫過程中，10表示可通行點，0表示障礙物，7表示起點，5表示終點，所以白色部分為機器人可行駛點，黑色部分為障礙物，黃色是起點，紅色是終點如圖2。

圖2 對障礙物抽象化的柵格地圖

2.2 改進Q-learning算法

由于Q-learning算法僅使移動機器人進行了一步的探索，其搜索范圍有限，根據已獲取的環境信息，移動機器人可以進行更深度的搜索。因此，本文將對原始Q-learning算法值函數的更新函數進行改進，加入深度學習因子為下兩步的Q值，促使移動機器人更早的預見障礙或者終點，盡早的更新值函數Q。改進后的值函數更新規則為：

此處引入ω的作用是保證Q值的收斂，更新的學習規則利用深度學習因子ω對第一步獲得的回報和第二步獲得的回報進行權衡，規定ω＞0.5是由于移動機器人的動作是周圍環境決定的，從而可以保證第一步的回報權重較大，不會出現因第二步無障礙而忽略第一步障礙的情況。而當ω=1則為值函數的取值規則僅由第一步決定，即為原始的Q-learning算法更新。

2.3 動作空間的表示

本文的仿真實驗將會把移動機器人抽象為一個質點，以移動機器人為中心，定義移動機器人可執行的四個動作空間為：A={上，下，左，右}。行動策略選擇 ε-greedy策略，其含義是選擇動作值最大的動作即貪婪動作的概率為而其他非貪婪動作的概率為等概率這種策略可以均衡利用與探索，采用最大的動作值為利用，其他非最優的動作值有平等概率繼續探索。

2.4 獎懲函數

對移動機器人進行最優路徑規劃具有導向性的獎懲函數，是環境給移動機器人的立即反饋，也是對移動機器人上一步執行動作的好壞評價。機器人每移動一個柵格，將會得到-1的懲罰值，直到到達終點，機器人將得到最大的獎勵值200，如果碰到障礙物，就會得到最大懲罰值-50，整個過程中，機器人也會選擇獎勵值高的動作，這樣可以促使機器人更快到達終點，使最終得到的總獎勵值最大。

3.實驗結果與分析

本文將對有障礙物的同一環境下的移動機器人進行最優路=0.6，0.7，0.8，0.9。

表1 不同參數時的學習次數及效率對比

圖3 最終的學習結果

4.結束語

本文提出了一種基于柵格法建立的地圖環境模型，對Q-learning算法進行改進，加入深度學習因子，使機器人在有不規則復雜障礙物的環境里能夠更快更早地發現終點，及時更新Q值。通過原始Q-learning算法與改進后的算法對靜態障礙物環境下的移動機器人進行最優路徑規劃的結果對比，可以證明改進后的算法收斂速度會加快。但本文只針對靜態障礙物的環境進行復雜路徑規劃，對于更復雜的動態障礙物環境的移動機器人路徑規劃，還需要進一步的研究。