文/彭玲玲 劉凱
關(guān)鍵字:移動(dòng)機(jī)器人;路徑規(guī)劃;Q-learning算法;柵格法
機(jī)器學(xué)習(xí)是研究如何使用機(jī)器來模擬人類學(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ā)展期,它們可以完成一些人類無法完成或完成效率低耗時(shí)長的任務(wù)。在移動(dòng)機(jī)器人的研究領(lǐng)域中,有效避障并路徑規(guī)劃[1]是一個(gè)很關(guān)鍵的問題,國內(nèi)外在這個(gè)問題上有很多方法可以借鑒,主要包括:人工勢(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)是無需環(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)路徑。
本文的研究內(nèi)容是針對(duì)Q-learning的一些缺點(diǎn)進(jìn)行改進(jìn),并將改進(jìn)的算法運(yùn)用于移動(dòng)機(jī)器人的路徑規(guī)劃,相關(guān)研究大多停留在理論的層面,缺少對(duì)實(shí)際問題與背景的解決方法。首先,本文介紹強(qiáng)化學(xué)習(xí)的原理與Q-learning算法基本原理,然后對(duì)移動(dòng)機(jī)器人路徑規(guī)劃問題進(jìn)行抽象建模,并對(duì)該問題應(yīng)用改進(jìn)的算法,使其在短時(shí)間內(nèi)以最優(yōu)路徑進(jìn)行規(guī)劃,驗(yàn)證算法的高效性,對(duì)結(jié)果進(jìn)行相關(guān)分析。
經(jīng)典的強(qiáng)化學(xué)習(xí)基于馬爾科夫決策過程(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í)基本框架
移動(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)迭代方式來獲得最優(yōu)策略,所以其值函數(shù)Q更新的公式為:

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

圖2 對(duì)障礙物抽象化的柵格地圖
由于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ù)見障礙或者終點(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)因第二步無障礙而忽略第一步障礙的情況。而當(dāng)ω=1則為值函數(shù)的取值規(guī)則僅由第一步?jīng)Q定,即為原始的Q-learning算法更新。
本文的仿真實(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ù)探索。
對(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è)過程中,機(jī)器人也會(huì)選擇獎(jiǎng)勵(lì)值高的動(dòng)作,這樣可以促使機(jī)器人更快到達(dá)終點(diǎn),使最終得到的總獎(jiǎng)勵(lì)值最大。
本文將對(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é)果
本文提出了一種基于柵格法建立的地圖環(huán)境模型,對(duì)Q-learning算法進(jìn)行改進(jìn),加入深度學(xué)習(xí)因子,使機(jī)器人在有不規(guī)則復(fù)雜障礙物的環(huán)境里能夠更快更早地發(fā)現(xiàn)終點(diǎn),及時(shí)更新Q值。通過原始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)一步的研究。