基于改進(jìn)Q-learning的移動(dòng)機(jī)器人路徑規(guī)劃應(yīng)用研究

文/彭玲玲 劉凱

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

引言

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

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

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

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

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

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

1.2 Q-learning算法

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

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

2.1 環(huán)境模型

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

圖2 對(duì)障礙物抽象化的柵格地圖

2.2 改進(jìn)Q-learning算法

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

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

2.3 動(dòng)作空間的表示

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

2.4 獎(jiǎng)懲函數(shù)

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

3.實(shí)驗(yàn)結(jié)果與分析

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

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

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

4.結(jié)束語(yǔ)

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