文/彭玲玲 劉凱

關(guān)鍵字：移動機器人；路徑規(guī)劃；Q-learning算法；柵格法

引言

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

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

1.強化學(xué)習(xí)

1.1 強化學(xué)習(xí)原理

經(jīng)典的強化學(xué)習(xí)基于馬爾科夫決策過程（Markov decisions process，MDP），強化學(xué)習(xí)是指從環(huán)境狀態(tài)到動作映射的學(xué)習(xí)，使動作從環(huán)境中獲得的獎勵最大，從而使目標的值函數(shù)最大，其學(xué)習(xí)框架如圖1。

圖1 強化學(xué)習(xí)基本框架

1.2 Q-learning算法

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

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

2.1 環(huán)境模型

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

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

2.2 改進Q-learning算法

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

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

2.3 動作空間的表示

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

2.4 獎懲函數(shù)

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

3.實驗結(jié)果與分析

本文將對有障礙物的同一環(huán)境下的移動機器人進行最優(yōu)路=0.6，0.7，0.8，0.9。

表1 不同參數(shù)時的學(xué)習(xí)次數(shù)及效率對比

圖3 最終的學(xué)習(xí)結(jié)果

4.結(jié)束語

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