王 慧 秦廣義 夏 鵬 楊春梅 王 剛

(東北林業(yè)大學(xué)機(jī)電工程學(xué)院 黑龍江 哈爾濱 150040)

0 引 言

隨著科學(xué)技術(shù)的不斷進(jìn)步，各式各樣的移動機(jī)器人逐漸進(jìn)入到人們的日常生活中，在軍事、工業(yè)、探險、醫(yī)療等領(lǐng)域發(fā)揮了重大作用[1]。移動機(jī)器人的路徑規(guī)劃問題一直是機(jī)器人研究的核心內(nèi)容，能夠直接影響到移動機(jī)器人的智能水平[2]。路徑規(guī)劃是指移動機(jī)器人在復(fù)雜的環(huán)境中，在滿足某些預(yù)先設(shè)定好的條件下，在初始點到達(dá)目標(biāo)點之間找出一條無碰撞的路徑[3-5]。目前常用的算法主要有柵格法、A*算法、粒子群算法、蟻群算法、強(qiáng)化學(xué)習(xí)方法[6-7]。Q-learning算法是由Watkins在1989年提出的強(qiáng)化學(xué)習(xí)方法中的一種離軌策略下的時序差分控制算法。標(biāo)準(zhǔn)Q-learning算法應(yīng)用在路徑規(guī)劃時，存在收斂速度慢、學(xué)習(xí)時間長等問題[8-9]。為此，國內(nèi)外一些學(xué)者提出了一些解決方法。宋清昆等[10]提出一種基于經(jīng)驗知識的Q-學(xué)習(xí)算法，該算法利用具有經(jīng)驗知識信息的函數(shù), 使智能體在進(jìn)行無模型學(xué)習(xí)的同時學(xué)習(xí)系統(tǒng)模型, 避免對環(huán)境模型的重復(fù)學(xué)習(xí), 從而加速智能體的學(xué)習(xí)速度，提高了算法的效率。Lillicrap等[11]使用人工神經(jīng)網(wǎng)絡(luò)來擬合Q-learning中的Q函數(shù)，然后使用經(jīng)驗回放方法來使得Q-learning保持收斂穩(wěn)定性從而加快了Q-learning算法的收斂速度，進(jìn)而提高了算法的效率。高樂等[12]在原有算法的基礎(chǔ)上增加了一層深度學(xué)習(xí)層，使得算法可以提前發(fā)現(xiàn)障礙物和目標(biāo)位置，從而加快了標(biāo)準(zhǔn)Q-learning算法的收斂速度。董瑤等[13]使用具有競爭網(wǎng)絡(luò)結(jié)構(gòu)的深度雙Q網(wǎng)絡(luò)的方法來改進(jìn)深度Q網(wǎng)絡(luò)模型以提高深度Q網(wǎng)絡(luò)的收斂速度，但是深度網(wǎng)絡(luò)的搭建具有很強(qiáng)的經(jīng)驗性，不同大小的柵格需要的網(wǎng)絡(luò)結(jié)構(gòu)和超參數(shù)不同，在維數(shù)較小的柵格中依然需要較多的先驗數(shù)據(jù)的采集與回放，具有較長的計算時間，計算效率較低。徐曉蘇等[14]通過引入人工勢場來初始化環(huán)境信息來使得Q表在初始化時具有先驗知識來加快Q-learning算法的收斂速度，但其未對原有Q-learning算法進(jìn)行改進(jìn)且算法收斂速度較慢。

本文在標(biāo)準(zhǔn)Q-learning算法基礎(chǔ)上，借鑒增加學(xué)習(xí)層和先驗知識啟發(fā)搜索的思想，提出一種基于具有先驗知識的改進(jìn)Q-learning移動機(jī)器人路徑規(guī)劃算法。該路徑規(guī)劃算法在原來標(biāo)準(zhǔn)Q-learning算法的基礎(chǔ)上增加了一層深度學(xué)習(xí)層、在算法初始化的過程中加入了關(guān)于環(huán)境的先驗知識作為啟發(fā)信息并且根據(jù)不同的狀態(tài)在構(gòu)建的標(biāo)量場中的位置獲得不同的獎賞值來使得獎賞值具有導(dǎo)向性。因此算法可以指引移動機(jī)器人快速向目標(biāo)位置移動，解決了算法學(xué)習(xí)初始階段的無目的性，使得算法在學(xué)習(xí)過程中具有導(dǎo)向性，提高了算法的學(xué)習(xí)效率以及算法的收斂速度。

1 Q-learning算法原理

1.1 馬爾可夫決策過程

設(shè)環(huán)境建模為有限馬爾可夫決策過程，該馬爾可夫決策過程可由元組M=(S,A,T,R,γ)表示，其中：S為一組有限的狀態(tài)集合；A為全部狀態(tài)下的所有動作行為的集合；T(s,a,s′)=P{st=s′|st-1=s,at-1=a},s′,s∈S,a∈A，T表示在狀態(tài)s和動作a下，到達(dá)狀態(tài)s′的概率；R表示由狀態(tài)s在動作a作用下到達(dá)狀態(tài)s′的獎勵函數(shù)，如R(s,a)是在狀態(tài)s下執(zhí)行動作a時所獲得的立即獎賞值；γ∈(0,1)為折扣因子，后面時刻的獎勵按照γ值進(jìn)行衰減。

1.2 標(biāo)準(zhǔn)Q-learning原理

Q-learning算法是一種離軌策略下的時序差分學(xué)習(xí)方法[15]。關(guān)于Q-learning的一個關(guān)鍵假設(shè)是智能體和環(huán)境的交互看作為一個馬爾可夫決策過程。在Q-learning中每個狀態(tài)-工作對(s,a)的評價值為Q(s,a)。評價值的定義是如果執(zhí)行當(dāng)前相關(guān)的動作并且按照某一個策略執(zhí)行下去，將得到回報的折扣總和。最優(yōu)的評價值則可以定義為在當(dāng)前狀態(tài)s下執(zhí)行動作a，此后按照策略π執(zhí)行下去獲得的折扣回報的總和，即：

s,s′∈Sa,a′∈A

(1)

Q-learning的學(xué)習(xí)過程如下：首先初始化Q(s,a)，然后初始化狀態(tài)s，選擇某一策略對動作進(jìn)行選擇(通常為ε-greed策略)，執(zhí)行選擇的動作a,根據(jù)獲得直接回報R(s,a),以及新狀態(tài)s′，來對Q(s,a)進(jìn)行更新，更新公式為：

Q(s,a)←Q(s,a)+

(2)

式中：α∈(0,1)表示學(xué)習(xí)率；Q(s,a)表示在狀態(tài)s處執(zhí)行動作a迭代時的估計值函數(shù)。然后令s←s′，繼續(xù)循環(huán)下去，直到到達(dá)算法停止的要求或達(dá)到最大迭代次數(shù)，算法停止運行。

2 改進(jìn)Q-learning移動機(jī)器人路徑規(guī)劃

2.1 依據(jù)環(huán)境先驗知識初始化Q值

本文算法的基本思想是在將Q-learning算法增加深度學(xué)習(xí)層后，在Q-learning學(xué)習(xí)的初始階段引入對環(huán)境的先驗知識。令任意狀態(tài)柵格到目標(biāo)狀態(tài)柵格的歐氏距離為D(si,sg)，任意狀態(tài)柵格到初始狀態(tài)柵格的歐氏距離為D(si,ss)，取D(si)=(1-η)·D(si,sg)+η·D(si,ss)，使用D(si)的線性歸一化數(shù)值來初始化各個狀態(tài)的Q值(η∈(0,0.2)，η為權(quán)重系數(shù))，這就避免了Q-learning學(xué)習(xí)前期盲目地進(jìn)行探索，使得算法在前期就有目的地選擇下一個路徑點，大幅提高算法的收斂速度。

標(biāo)準(zhǔn)Q-learning算法僅使得移動機(jī)器人對下一步進(jìn)行搜索，使得搜索的范圍很有限，借鑒增加深度學(xué)習(xí)層搜索的思想，本文中Q值函數(shù)的更新公式為：

(3)

式中：ω∈(0.5,1)為深度學(xué)習(xí)因子；Q(s′,a′)為在s狀態(tài)執(zhí)行動作a后到達(dá)的狀態(tài)s′后，狀態(tài)-動作對(s′,a′)所對應(yīng)的Q值；Q(s″,a″)為在s′狀態(tài)執(zhí)行動作a′到達(dá)的狀態(tài)s″后，狀態(tài)-動作對(s″,a″)所對應(yīng)的Q值。

在學(xué)習(xí)的過程中，Q-learning的動作策略是沿著Q值上升的方向進(jìn)行移動，因此應(yīng)該在移動機(jī)器人的狀態(tài)空間內(nèi)形成一個以目標(biāo)點狀態(tài)為中心的標(biāo)量場，場的值從側(cè)面向中心依次上升，在中心處達(dá)到最高值。為達(dá)到這個目的，做了以下工作。

取歐氏距離來對任意柵格之間的距離進(jìn)行描述，假設(shè)垂直和水平方向上相鄰的柵格之間為距離為1。令起始狀態(tài)坐標(biāo)為ss，目標(biāo)狀態(tài)坐標(biāo)為sg，任意狀態(tài)坐標(biāo)為si，記任意點到目標(biāo)點的距離為D(si,sg),任意點到起始點的距離為D(si,ss)。D(si,sg)、D(si,ss)可以表示為：

(4)

(5)

令D(si)=(1-η)·D(si,sg)+η·D(si,ss)，其中η∈(0,0.2)，獲得的D(si)為si點到目標(biāo)點和起始點的加權(quán)后的距離值。使用歸一化函數(shù)對D(si)進(jìn)行歸一化。

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

步驟1初始化學(xué)習(xí)率α，選擇合適的折扣因子γ，選取合適的ε-greed選擇策略的ε值，深度學(xué)習(xí)因數(shù)學(xué)習(xí)率衰減步數(shù)STEP，學(xué)習(xí)率衰減率decay-rate，設(shè)置最大循環(huán)次數(shù)epoch_max，循環(huán)次數(shù)epoch=0，初始化最優(yōu)路徑記錄器Pathrecord_best=[]。

步驟2確定起始點的坐標(biāo)位置ss和目標(biāo)點坐標(biāo)sg,初始化以目標(biāo)點為中心的標(biāo)量場，保存標(biāo)量場中各個狀態(tài)對應(yīng)場的數(shù)值Dnorm(si)，路徑記錄器Pathrecord=[ss]。

步驟3對Q值進(jìn)行初始化，即令Q(s,a)=Dnorm(s′)。

步驟4將移動機(jī)器人置于起始狀態(tài)點。

步驟5移動機(jī)器人對動作進(jìn)行選擇，選擇策略使用ε-greed方法，系統(tǒng)在(0,1)中隨機(jī)取值E，若E>ε,則從狀態(tài)的動作空間選取動作a：

a={ai,|ai,=argmaxQ(s,ai),ai∈A}

(6)

否則在狀態(tài)的動作空間中隨機(jī)選擇一個動作a。

步驟6選擇動作a后，對到達(dá)的狀態(tài)s′進(jìn)行檢測，到達(dá)s′的直接獎勵值為:

(7)

步驟7若檢測狀態(tài)為障礙物，則停止進(jìn)一步探索，該Q(s,a)更新為：

Q(s,a)←Q(s,a)+α[R(s,a)-Q(s,a)]

(8)

狀態(tài)返回s，返回步驟5。

若檢測狀態(tài)為目標(biāo)點，則停止進(jìn)一步探索，該Q(s,a)更新為：

Q(s,a)←Q(s,a)+α[R(s,a)-Q(s,a)]

(9)

若檢測狀態(tài)為其他，則進(jìn)行下一步的探索，選擇動作a′為：

a={ai,|ai,=argmaxQ(s,ai),ai∈A}

(10)

沿著動作a′，對狀態(tài)s″進(jìn)行檢測，若s″為障礙物或目標(biāo)點，Q(s,a)更新為：

(1-ω)R(s′,a′))-Q(s,a)]

(11)

若s″為其他，則Q(s,a)更新為：

步驟8進(jìn)入狀態(tài)s′，將s′坐標(biāo)記入路徑記錄器Pathrecord。

步驟9判斷狀態(tài)s′是否為目標(biāo)點狀態(tài)，若目標(biāo)點狀態(tài)為True，結(jié)束該次嘗試學(xué)習(xí)；若目標(biāo)點狀態(tài)為False則s=s′，返回步驟5。

步驟10判斷是否epoch==1，為True則Pathrecord_best= Pathrecord。

步驟11判斷Pathrecord的長度是否小于Pathrecord_best,為True則Pathrecord_best=Pathrecord。運行柵格步數(shù)steps為Pathrecord長度。

步驟12判斷判讀循環(huán)次數(shù)是否達(dá)到最大循環(huán)次數(shù)，為True則算法停止，為Flase則循環(huán)次數(shù)epoch加1并返回步驟2進(jìn)行下一次嘗試學(xué)習(xí)。

3 實驗仿真

3.1 標(biāo)量場仿真實驗驗證

通過仿真實驗來驗證本文算法的有效性及其先進(jìn)性。仿真實驗的環(huán)境為MATLAB(2016b)以及Python3.5.3。由于柵格法建模的廣泛性和實用性[16]，本文實驗環(huán)境使用柵格法進(jìn)行建模。本文在柵格地圖上對提出的改進(jìn)方法和標(biāo)準(zhǔn)Q-learning算法及增加深度學(xué)習(xí)層的Q-learning算法進(jìn)行效果對比。

建立20×20的柵格，設(shè)起始點選擇為點(1,1)，目標(biāo)點選擇為點(10,10)，觀察形成的標(biāo)量場的形狀，如圖1所示。

圖1 20×20柵格標(biāo)量場

可以看出，標(biāo)量場場值的最大值在目標(biāo)點坐標(biāo)(10,10)處取到并且滿足各點場值的大小與D(si)成反比關(guān)系，即D(si)值越大，其場值越小。

3.2 算法仿真實驗驗證及分析

仿真實驗采用22×22的柵格來組成，以左下角點(1,1)為原點建立坐標(biāo)系，取水平方向為x軸，豎直方向為y軸。仿真實驗中學(xué)習(xí)率使用線性衰減的方法，即每循環(huán)STEP次，α=α·decay-rate，使得Q值趨于穩(wěn)定。

在圖2中，黑色的圓形表示移動機(jī)器人所處的起始點，黑色的星形表示移動機(jī)器人的目標(biāo)點，白色部分為移動機(jī)器人移動區(qū)域，黑色的方形部分為障礙物，移動機(jī)器人的動作A={向上移動，向下移動，向左移動，向右移動}。

圖2 柵格環(huán)境一

首先以圖2障礙物擺放較為簡單的柵格環(huán)境進(jìn)行仿真實驗分析。仿真實驗的各個參數(shù)如表1所示。

表1 仿真實驗參數(shù)

在圖2柵格環(huán)境中對標(biāo)準(zhǔn)Q-learning算法，增加深度層的Q-learning算法、本文算法、引入引力場的算法、深度雙Q網(wǎng)絡(luò)算法進(jìn)行仿真實驗。實驗結(jié)果如圖3-圖8所示。

圖3 環(huán)境一中前四種算法收斂過程

圖4 環(huán)境一中深度雙Q網(wǎng)絡(luò)算法收斂過程

圖5 標(biāo)準(zhǔn)Q-learning算法

圖6 增加學(xué)習(xí)層Q-learning算法

圖7 本文算法

圖8 引入引力場算法

由圖3可以看出，在障礙物擺放較為簡單的環(huán)境中，標(biāo)準(zhǔn)Q-learning算法、增加學(xué)習(xí)層的Q-learning算法、引入引力場的算法在算法初始學(xué)習(xí)階段迭代次數(shù)較多，浪費較多的規(guī)劃時間。本文算法由于在學(xué)習(xí)的初始階段具有較強(qiáng)的目的性，大幅減少了算法前期的迭代次數(shù)；因在探索過程中增加一層學(xué)習(xí)層并且獎賞值具有導(dǎo)向性，于是使用較少的嘗試次數(shù)便收斂。

由圖4可以看出深度雙Q網(wǎng)絡(luò)在訓(xùn)練時損失值隨迭代次數(shù)增加的變化情況，當(dāng)?shù)螖?shù)達(dá)到6 326時，損失值處于平穩(wěn)狀態(tài)，算法達(dá)到收斂。由圖5可得標(biāo)準(zhǔn)Q-learning算法在85次嘗試后達(dá)到收斂，由圖6可得增加學(xué)習(xí)層的Q-learning算法在60次嘗試后達(dá)到收斂，由圖7可得本文算法在42次嘗試后便進(jìn)入收斂狀態(tài)，由圖8可得引入引力場算法在82次嘗試后便進(jìn)入收斂狀態(tài)。

由表2可以得到在環(huán)境一的柵格中各種算法達(dá)到收斂時的總迭代次數(shù)。由此可以得到本文算法在環(huán)境一柵格中具有較快達(dá)到收斂的能力。

表2 環(huán)境一五種算法達(dá)到收斂的迭代次數(shù)

五種算法在圖3柵格環(huán)境中規(guī)劃出的路徑完全相同，路徑如圖9所示，其中，黑色的圓形和線條組成了由點(2,2)到達(dá)點(21,21)規(guī)劃出的路徑。

圖9 環(huán)境一路徑規(guī)劃圖

接下來在障礙物擺放較為復(fù)雜的環(huán)境中對三種算法進(jìn)行仿真實驗，環(huán)境柵格如圖10所示。

圖10 柵格環(huán)境二

在圖10障礙物擺放較為復(fù)雜的環(huán)境中，前四種算法收斂過程如圖11所示，深度雙Q網(wǎng)絡(luò)算法收斂過程如圖12所示。

圖11 環(huán)境二中四種算法收斂過程

圖12 環(huán)境二中深度雙Q網(wǎng)絡(luò)算法收斂過程

從圖11中可以看出，在障礙物擺放較為復(fù)雜的環(huán)境中，本文算法相較于其他算法在較少的嘗試次數(shù)下便可以達(dá)到收斂。由表3可以看出在局部較為復(fù)雜的環(huán)境下，本文算法相較于其他算法具有迭代次數(shù)少、計算效率高的優(yōu)點。在環(huán)境二中，移動機(jī)器人的軌跡如圖13所示。

表3 環(huán)境二五種算法達(dá)到收斂的迭代次數(shù)

圖13 環(huán)境二路徑規(guī)劃圖

為了進(jìn)一步驗證算法的環(huán)境適應(yīng)性，在障礙物更為復(fù)雜的40×40柵格中進(jìn)行仿真，結(jié)果如圖14所示。

圖14 40×40復(fù)雜柵格的路徑軌跡

4 結(jié) 語

本文提出一種具有先驗知識的增加深度學(xué)習(xí)層的改進(jìn)Q-learning算法，該算法在原有算法的基礎(chǔ)上通過構(gòu)建標(biāo)量場來對Q進(jìn)行初始化，根據(jù)不同狀態(tài)所在標(biāo)量場的位置返回不同的獎賞值并且在原有算法上增加了一層學(xué)習(xí)層來使得算法更快地尋找到目標(biāo)位置。

由仿真實驗可以看出，在低維度的環(huán)境下本文算法相較于標(biāo)準(zhǔn)Q-learning算法、引入引力場的算法、深度雙Q網(wǎng)絡(luò)算法具有更低的迭代次數(shù)，從而節(jié)省了計算時間，提高了計算效率。