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

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

0 引 言

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

本文在標(biāo)準(zhǔn)Q-learning算法基礎(chǔ)上，借鑒增加學(xué)習(xí)層和先驗(yàn)知識(shí)啟發(fā)搜索的思想，提出一種基于具有先驗(yàn)知識(shí)的改進(jìn)Q-learning移動(dòng)機(jī)器人路徑規(guī)劃算法。該路徑規(guī)劃算法在原來標(biāo)準(zhǔn)Q-learning算法的基礎(chǔ)上增加了一層深度學(xué)習(xí)層、在算法初始化的過程中加入了關(guān)于環(huán)境的先驗(yàn)知識(shí)作為啟發(fā)信息并且根據(jù)不同的狀態(tài)在構(gòu)建的標(biāo)量場(chǎng)中的位置獲得不同的獎(jiǎng)賞值來使得獎(jiǎng)賞值具有導(dǎo)向性。因此算法可以指引移動(dòng)機(jī)器人快速向目標(biāo)位置移動(dòng)，解決了算法學(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)下的所有動(dòng)作行為的集合；T(s,a,s′)=P{st=s′|st-1=s,at-1=a},s′,s∈S,a∈A，T表示在狀態(tài)s和動(dòng)作a下，到達(dá)狀態(tài)s′的概率；R表示由狀態(tài)s在動(dòng)作a作用下到達(dá)狀態(tài)s′的獎(jiǎng)勵(lì)函數(shù)，如R(s,a)是在狀態(tài)s下執(zhí)行動(dòng)作a時(shí)所獲得的立即獎(jiǎng)賞值；γ∈(0,1)為折扣因子，后面時(shí)刻的獎(jiǎng)勵(lì)按照γ值進(jìn)行衰減。

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

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

s,s′∈Sa,a′∈A

(1)

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

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

(2)

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

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

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

本文算法的基本思想是在將Q-learning算法增加深度學(xué)習(xí)層后，在Q-learning學(xué)習(xí)的初始階段引入對(duì)環(huán)境的先驗(yàn)知識(shí)。令任意狀態(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ù)值來初始化各個(gè)狀態(tài)的Q值(η∈(0,0.2)，η為權(quán)重系數(shù))，這就避免了Q-learning學(xué)習(xí)前期盲目地進(jìn)行探索，使得算法在前期就有目的地選擇下一個(gè)路徑點(diǎn)，大幅提高算法的收斂速度。

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

(3)

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

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

取歐氏距離來對(duì)任意柵格之間的距離進(jìn)行描述，假設(shè)垂直和水平方向上相鄰的柵格之間為距離為1。令起始狀態(tài)坐標(biāo)為ss，目標(biāo)狀態(tài)坐標(biāo)為sg，任意狀態(tài)坐標(biāo)為si，記任意點(diǎn)到目標(biāo)點(diǎn)的距離為D(si,sg),任意點(diǎn)到起始點(diǎn)的距離為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點(diǎn)到目標(biāo)點(diǎn)和起始點(diǎn)的加權(quán)后的距離值。使用歸一化函數(shù)對(duì)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確定起始點(diǎn)的坐標(biāo)位置ss和目標(biāo)點(diǎn)坐標(biāo)sg,初始化以目標(biāo)點(diǎn)為中心的標(biāo)量場(chǎng)，保存標(biāo)量場(chǎng)中各個(gè)狀態(tài)對(duì)應(yīng)場(chǎng)的數(shù)值Dnorm(si)，路徑記錄器Pathrecord=[ss]。

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

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

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

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

(6)

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

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

(7)

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

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

(8)

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

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

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

(9)

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

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

(10)

沿著動(dòng)作a′，對(duì)狀態(tài)s″進(jìn)行檢測(cè)，若s″為障礙物或目標(biāo)點(diǎn)，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)點(diǎn)狀態(tài)，若目標(biāo)點(diǎn)狀態(tài)為True，結(jié)束該次嘗試學(xué)習(xí)；若目標(biāo)點(diǎn)狀態(tài)為False則s=s′，返回步驟5。

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

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

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

3 實(shí)驗(yàn)仿真

3.1 標(biāo)量場(chǎng)仿真實(shí)驗(yàn)驗(yàn)證

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

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

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

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

3.2 算法仿真實(shí)驗(yàn)驗(yàn)證及分析

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

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

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

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

表1 仿真實(shí)驗(yàn)參數(shù)

在圖2柵格環(huán)境中對(duì)標(biāo)準(zhǔn)Q-learning算法，增加深度層的Q-learning算法、本文算法、引入引力場(chǎng)的算法、深度雙Q網(wǎng)絡(luò)算法進(jìn)行仿真實(shí)驗(yàn)。實(shí)驗(yà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 引入引力場(chǎng)算法

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

由圖4可以看出深度雙Q網(wǎng)絡(luò)在訓(xùn)練時(shí)損失值隨迭代次數(shù)增加的變化情況，當(dāng)?shù)螖?shù)達(dá)到6 326時(shí)，損失值處于平穩(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可得引入引力場(chǎng)算法在82次嘗試后便進(jìn)入收斂狀態(tài)。

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

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

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

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

接下來在障礙物擺放較為復(fù)雜的環(huán)境中對(duì)三種算法進(jìn)行仿真實(shí)驗(yà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ù)少、計(jì)算效率高的優(yōu)點(diǎn)。在環(huán)境二中，移動(dòng)機(jī)器人的軌跡如圖13所示。

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

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

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

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

4 結(jié) 語

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

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