張耀玉，李彩虹，張國(guó)勝，李永迪，梁振英

(山東理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院, 山東 淄博 255049)

隨著科學(xué)技術(shù)的快速發(fā)展，移動(dòng)機(jī)器人的應(yīng)用越來(lái)越廣泛。在移動(dòng)機(jī)器人的研究中，機(jī)器人避障并且規(guī)劃有效路徑是至關(guān)重要的問(wèn)題[1]。移動(dòng)機(jī)器人的路徑規(guī)劃分為全局路徑規(guī)劃[2]和局部路徑規(guī)劃[3]。全局路徑規(guī)劃是在靜態(tài)已知環(huán)境信息下，尋找一條從起點(diǎn)到目標(biāo)點(diǎn)的無(wú)碰撞最優(yōu)路徑。局部路徑規(guī)劃是在未知或部分已知環(huán)境信息下，在移動(dòng)過(guò)程中利用傳感器等檢測(cè)環(huán)境信息進(jìn)行實(shí)時(shí)路徑規(guī)劃。

當(dāng)前有效避障的路徑規(guī)劃方法有很多，傳統(tǒng)方法主要有A*算法[4]、Dijkstra算法[5]、模糊控制法[6]、遺傳算法[7]、人工勢(shì)場(chǎng)法[8]和神經(jīng)網(wǎng)絡(luò)[9]等。而智能算法的應(yīng)用在很大程度上解決了傳統(tǒng)算法效率低下、操作復(fù)雜等缺點(diǎn)。Q-learning算法是Watikins提出的一種強(qiáng)化學(xué)習(xí)算法[10]，在移動(dòng)機(jī)器人路徑規(guī)劃領(lǐng)域中應(yīng)用廣泛，具有不依賴(lài)環(huán)境先驗(yàn)?zāi)Ｐ偷奶攸c(diǎn)；缺點(diǎn)是算法收斂速度較慢，在訓(xùn)練次數(shù)不夠多時(shí)找不到最優(yōu)路徑。因此，高樂(lè)等[11]在Q-learning算法的基礎(chǔ)上增加了一層學(xué)習(xí)過(guò)程，對(duì)環(huán)境進(jìn)行了深度學(xué)習(xí)，提高了算法的收斂速度。毛國(guó)君等[12]引入了動(dòng)態(tài)搜索因子ε，根據(jù)環(huán)境的反饋來(lái)動(dòng)態(tài)調(diào)整貪婪因子ε，當(dāng)探索路徑失敗時(shí)，增大ε使下一次探索的隨機(jī)性增大；反之，則通過(guò)減少ε來(lái)增加目的性，該方法有效地減少了迭代搜索的代價(jià)，能夠找到更優(yōu)的路徑。Oh等[13]采用基于模糊規(guī)則的Q-learning算法指定Q值，然后與傳統(tǒng)的Q-learning算法相融合來(lái)加速算法的學(xué)習(xí)效率，以更少的迭代次數(shù)獲得良好的結(jié)果。Lillicrap等[14]以神經(jīng)網(wǎng)絡(luò)來(lái)擬合Q-learning中的Q(s,a)，然后采用經(jīng)驗(yàn)回放和目標(biāo)網(wǎng)絡(luò)的方法來(lái)改善Q-learning算法收斂穩(wěn)定性。

本文針對(duì)傳統(tǒng)的Q-learning算法存在的學(xué)習(xí)速度慢、效率低等問(wèn)題，提出一種改進(jìn)的IQ-learning算法，實(shí)現(xiàn)移動(dòng)機(jī)器人的局部路徑規(guī)劃。在傳統(tǒng)Q-learning算法的基礎(chǔ)上，增加對(duì)角線運(yùn)動(dòng)獎(jiǎng)勵(lì)值，減少算法在初始階段盲目搜索問(wèn)題，減少規(guī)劃路徑的長(zhǎng)度，提高路徑的規(guī)劃效率，使移動(dòng)機(jī)器人在更短時(shí)間內(nèi)找到一條從起點(diǎn)到目標(biāo)點(diǎn)的較優(yōu)路徑。

1 Q-learning算法

強(qiáng)化學(xué)習(xí)是從環(huán)境狀態(tài)到動(dòng)作映射的學(xué)習(xí)，使動(dòng)作從環(huán)境中獲得的獎(jiǎng)勵(lì)最大，其工作原理如圖1所示。強(qiáng)化學(xué)習(xí)基于馬爾可夫決策過(guò)程(Markov decisions process, MDP)[15]。馬爾可夫?qū)傩允侵赶到y(tǒng)的狀態(tài)只與當(dāng)前狀態(tài)有關(guān)，而與更早之前的狀態(tài)無(wú)關(guān)。

圖1 強(qiáng)化學(xué)習(xí)工作原理

Q-learning算法是強(qiáng)化學(xué)習(xí)算法之一，是基于Q值迭代的無(wú)模型算法。通過(guò)不斷迭代，對(duì)每個(gè)可能的狀態(tài)動(dòng)作進(jìn)行多次嘗試，最終學(xué)到最優(yōu)的控制策略[16]。迭代過(guò)程中不斷對(duì)Q值更新，Q值的更新公式為

newQ(s,a)=(1-α)Q(s,a)+α(R(s,a)+

γmaxQ'(s',a')),

(1)

式中：s和s'分別代表當(dāng)前狀態(tài)和下一個(gè)狀態(tài)；a代表s到s'的有效動(dòng)作；Q(s,a)代表當(dāng)前狀態(tài)s和動(dòng)作a的Q值；R(s,a)是指當(dāng)前狀態(tài)s和動(dòng)作a的獎(jiǎng)勵(lì)；maxQ'(s',a')代表下一個(gè)狀態(tài)下所有動(dòng)作中最大的Q值；α表示學(xué)習(xí)率，α越大，Q值收斂越快，但也越容易產(chǎn)生振蕩，本文α取0.6。根據(jù)式(1)，Q-learning算法在某個(gè)狀態(tài)下采取貪心策略對(duì)所有可能路徑進(jìn)行探索，每前進(jìn)一步都在尋找當(dāng)前狀態(tài)下的局部最優(yōu)解。

2 IQ-learning算法

本文所設(shè)計(jì)的IQ-learning算法在Q-learning算法基礎(chǔ)上，在獎(jiǎng)懲函數(shù)中添加對(duì)角線運(yùn)動(dòng)獎(jiǎng)勵(lì)值，使得移動(dòng)機(jī)器人在路徑規(guī)劃時(shí)減少盲目搜索，提高算法的學(xué)習(xí)效率。

2.1 柵格地圖設(shè)計(jì)

本文基于柵格地圖構(gòu)造機(jī)器人的運(yùn)行環(huán)境。運(yùn)行環(huán)境為20×20的八連通柵格地圖，結(jié)合二維直角坐標(biāo)系確定柵格位置，并對(duì)每個(gè)柵格從下到上、從左到右依次標(biāo)明序號(hào)，行和列的交叉位置代表地圖信息中的一個(gè)環(huán)境狀態(tài)。在柵格地圖中設(shè)置移動(dòng)機(jī)器人的運(yùn)行環(huán)境，包括障礙物、起點(diǎn)和目標(biāo)點(diǎn)，如圖2所示。對(duì)于移動(dòng)機(jī)器人來(lái)說(shuō)，這些障礙物的位置信息未知，機(jī)器人在學(xué)習(xí)過(guò)程中根據(jù)執(zhí)行動(dòng)作后得到的獎(jiǎng)懲值來(lái)確定障礙物的位置信息。

圖2 柵格地圖

2.2 狀態(tài)-動(dòng)作的表示

設(shè)定移動(dòng)機(jī)器人的起點(diǎn)和目標(biāo)點(diǎn)后，將移動(dòng)機(jī)器人看作一個(gè)質(zhì)點(diǎn)，機(jī)器人在運(yùn)行環(huán)境中的每個(gè)坐標(biāo)表示一個(gè)狀態(tài)，記為st，坐標(biāo)記為Φ(i,j)。根據(jù)柵格地圖的維數(shù)，共有Xlim×Ylim個(gè)狀態(tài),其中l(wèi)im∈[1,20]，lim為整數(shù)。所有狀態(tài)組成的狀態(tài)集S為

S={st|st=Φ(i,j),i∈Xlim,j∈Ylim}。

(2)

一般情況下，移動(dòng)機(jī)器人的探索為上、下、左、右4個(gè)動(dòng)作。為提高算法探索效率，增加對(duì)角線方向的探索行為，即以該質(zhì)點(diǎn)為中心，定義移動(dòng)機(jī)器人可以執(zhí)行8個(gè)方向上的動(dòng)作，記為ai(i=1～8)：上、下、左、右、右上、右下、左上和左下，機(jī)器人可以按照以上8個(gè)動(dòng)作移動(dòng)，平移一格的步長(zhǎng)為1，對(duì)角線移動(dòng)一格的步長(zhǎng)約為1.4，如圖3所示。動(dòng)作集合A記為

圖3 動(dòng)作空間

A={ai,i=1～8}。

(3)

機(jī)器人選擇不同的動(dòng)作執(zhí)行后，狀態(tài)會(huì)發(fā)生不同的改變，分別執(zhí)行8個(gè)動(dòng)作時(shí)所對(duì)應(yīng)的狀態(tài)變換見(jiàn)表1。

表1 狀態(tài)-動(dòng)作關(guān)系表

2.3 Q表的設(shè)計(jì)

建立一個(gè)二維表，用來(lái)存儲(chǔ)Q值，其中行表示每種狀態(tài)s，列代表每種狀態(tài)的動(dòng)作a，Q值是某一狀態(tài)下執(zhí)行某種動(dòng)作獲得的獎(jiǎng)勵(lì)。根據(jù)移動(dòng)機(jī)器人Xlim×Ylim個(gè)狀態(tài)、8個(gè)動(dòng)作建立的Q表為

(4)

Q表建立后將其初始化，經(jīng)過(guò)訓(xùn)練不斷迭代更新，根據(jù)最終的Q表進(jìn)行最優(yōu)路徑的選擇。

2.4 獎(jiǎng)懲函數(shù)的設(shè)計(jì)

獎(jiǎng)懲函數(shù)R的設(shè)置對(duì)移動(dòng)機(jī)器人的行動(dòng)具有導(dǎo)向作用。為提高算法尋找最優(yōu)路徑的效率，本文增加對(duì)角線移動(dòng)的獎(jiǎng)勵(lì)值，獎(jiǎng)懲函數(shù)的設(shè)計(jì)為

(5)

2.5 動(dòng)作策略的選擇

動(dòng)作策略采取ε-greedy改進(jìn)的貪心策略，在移動(dòng)機(jī)器人做決策時(shí)，有ε的概率隨機(jī)選擇未知的一個(gè)動(dòng)作，剩下的1-ε的概率選擇已有動(dòng)作中價(jià)值最大的動(dòng)作，公式為

π(a|s)=

(6)

式中：ε是小于1且很小的正數(shù)；a表示機(jī)器人的動(dòng)作；s表示機(jī)器人的狀態(tài)；A(s)表示機(jī)器人處于某個(gè)狀態(tài)下可以選擇的動(dòng)作集合。這種策略可以均衡利用與探索，采用回報(bào)值最大的動(dòng)作值為利用，其他非最優(yōu)的動(dòng)作值有一定概率繼續(xù)探索。

2.6 IQ-learning算法的訓(xùn)練過(guò)程

基于柵格地圖設(shè)計(jì)IQ-learning算法，完成移動(dòng)機(jī)器人局部路徑規(guī)劃任務(wù)，算法學(xué)習(xí)步驟如下：

1) 清空二維環(huán)境地圖，給定移動(dòng)機(jī)器人起點(diǎn)、目標(biāo)點(diǎn)和障礙物信息。建立Pmat線性表，用來(lái)存儲(chǔ)從起點(diǎn)到目標(biāo)點(diǎn)的歷史最佳狀態(tài)-動(dòng)作對(duì)；Q表存儲(chǔ)當(dāng)前學(xué)到的從起點(diǎn)到目標(biāo)點(diǎn)的最佳狀態(tài)-動(dòng)作對(duì)；len記錄當(dāng)前最短路徑長(zhǎng)度；min_total_steps記錄歷史最短路徑的長(zhǎng)度。

初始化獎(jiǎng)懲函數(shù)，學(xué)習(xí)次數(shù)i=0，最大學(xué)習(xí)次數(shù)Nmax=80。初始化Pmat線性表及歷史最短路徑長(zhǎng)度min_total_steps=Nmax。

2)設(shè)置迭代計(jì)數(shù)器初始值count=0，len=Nmax，清空Q表。

3)根據(jù)式(6)動(dòng)作選擇策略選擇一個(gè)動(dòng)作a執(zhí)行，執(zhí)行完動(dòng)作a后，機(jī)器人狀態(tài)轉(zhuǎn)為st +1，count++。若此時(shí)機(jī)器人已到達(dá)目標(biāo)點(diǎn)，則轉(zhuǎn)到步驟6)；否則轉(zhuǎn)到步驟4)。

4)根據(jù)式(5)獎(jiǎng)懲函數(shù)計(jì)算當(dāng)前狀態(tài)的獎(jiǎng)懲值。若機(jī)器人收到獎(jiǎng)勵(lì)則轉(zhuǎn)到步驟5)；若機(jī)器人收到懲罰，則機(jī)器人退回上一個(gè)狀態(tài)s=st并轉(zhuǎn)到步驟3)繼續(xù)探索。

5)按照式(1)更新Q值，并轉(zhuǎn)到步驟3)繼續(xù)探索。

6)記錄迭代次數(shù)count值、當(dāng)前最短路徑長(zhǎng)度len，更新Q表，且i++。

7)更新Pmat表與min_total_steps的值。若學(xué)習(xí)次數(shù)i

3 仿真驗(yàn)證

本文將分別在離散型障礙物、一字型障礙物、U型障礙物和混合型障礙物環(huán)境下，對(duì)所設(shè)計(jì)的IQ-learning算法的規(guī)劃路徑進(jìn)行仿真，測(cè)試算法的可行性。在所設(shè)計(jì)的柵格地圖中設(shè)置移動(dòng)機(jī)器人的起點(diǎn)和目標(biāo)點(diǎn)，根據(jù)不同的環(huán)境設(shè)置不同的障礙物，在同一環(huán)境下對(duì)比Q-learning算法和IQ-learning算法訓(xùn)練80次得到的最短路徑。

3.1 離散型障礙物環(huán)境下的路徑規(guī)劃仿真

IQ-learning算法在離散型障礙物環(huán)境下的訓(xùn)練過(guò)程如圖4所示，圖中藍(lán)色圓點(diǎn)代表算法在探索路徑的過(guò)程中走過(guò)的柵格位置。由圖4可以看出，隨著算法訓(xùn)練次數(shù)的增多，學(xué)習(xí)到的規(guī)劃路徑越來(lái)越好，路徑長(zhǎng)度逐漸收斂到最短。

圖4 離散型障礙物環(huán)境下的訓(xùn)練過(guò)程

Q-learning算法和IQ-learning算法訓(xùn)練80次得到的最短路徑如圖5所示，由圖5可以看出,Q-learning算法訓(xùn)練得到的路徑在坐標(biāo)(7,8)處存在步數(shù)浪費(fèi)的現(xiàn)象，此時(shí)路徑長(zhǎng)度為20.8；而IQ-learning學(xué)習(xí)80次得到的機(jī)器人規(guī)劃路徑更短，此時(shí)路徑長(zhǎng)度為19.4。

圖5 離散型障礙物環(huán)境下的路徑規(guī)劃

3.2 一字型障礙物環(huán)境下的路徑規(guī)劃仿真

移動(dòng)機(jī)器人在一字形障礙物環(huán)境下規(guī)劃路徑時(shí)容易陷入對(duì)稱(chēng)冗余狀態(tài)。IQ-learning算法在一字型障礙物環(huán)境下的訓(xùn)練過(guò)程如圖6所示。從圖6可以看出，隨著算法訓(xùn)練次數(shù)的增多，機(jī)器人逐漸走出對(duì)稱(chēng)冗余狀態(tài)，并從中選擇了最短路徑。

圖6 一字型障礙物環(huán)境下的訓(xùn)練過(guò)程

Q-learning算法和IQ-learning算法訓(xùn)練80次得到的最短路徑如圖7所示，由圖7可以看出，Q-learning算法存在多處步數(shù)浪費(fèi)現(xiàn)象，算法訓(xùn)練得到的路徑長(zhǎng)度為26.4；IQ-learning算法訓(xùn)練得到的路徑更短，其路徑長(zhǎng)度為22.8。

圖7 一字型障礙物環(huán)境下的路徑規(guī)劃

3.3 U型障礙物環(huán)境下的路徑規(guī)劃仿真

移動(dòng)機(jī)器人在U型障礙物環(huán)境下規(guī)劃路徑時(shí)，因?yàn)閭鞲衅餍畔⒏兄木窒扌裕瑱C(jī)器人容易陷入死鎖狀態(tài)，而找不到最優(yōu)路徑。IQ-learning算法在U型障礙物環(huán)境下的訓(xùn)練過(guò)程如圖8所示。從圖8可以看出，隨著算法訓(xùn)練次數(shù)的增多，機(jī)器人不再進(jìn)入U(xiǎn)型區(qū)域，規(guī)劃的路徑長(zhǎng)度也越來(lái)越短。

圖8 U型障礙物環(huán)境下的訓(xùn)練過(guò)程

Q-learning算法和IQ-learning算法訓(xùn)練80次得到的移動(dòng)機(jī)器人最短路徑如圖9所示。由圖9可以看出，Q-learning算法學(xué)習(xí)80次得到的訓(xùn)練路徑較長(zhǎng)，在坐標(biāo)(3,5)和(9,10)處有步數(shù)浪費(fèi)現(xiàn)象，此時(shí)路徑長(zhǎng)度為27；而IQ-learning算法學(xué)習(xí)80次后得到的路徑更優(yōu)，此時(shí)路徑長(zhǎng)度為24.8，路徑長(zhǎng)度明顯減少。

圖9 U型障礙物環(huán)境下的路徑規(guī)劃

3.4 混合型障礙物環(huán)境下的路徑規(guī)劃仿真

混合障礙物環(huán)境包括離散障礙物、一字型障礙物和近似U型障礙物。IQ-learning算法在混合型障礙物環(huán)境下的訓(xùn)練過(guò)程如圖10所示。從圖10可以看出，隨著算法訓(xùn)練次數(shù)的增多，機(jī)器人能夠擺脫U型和一字型障礙物的阻礙，路徑逐漸收斂，最后學(xué)習(xí)到更短的路徑。

圖10 混合型障礙物環(huán)境下的訓(xùn)練過(guò)程

Q-learning算法和IQ-learning算法訓(xùn)練80次得到的移動(dòng)機(jī)器人最短路徑如圖11所示。由圖11可以看出，Q-learning算法經(jīng)過(guò)80次學(xué)習(xí)得到的最短可行路徑在坐標(biāo)(14,13)處，有明顯的步數(shù)浪費(fèi)，規(guī)劃的路徑較長(zhǎng)，此時(shí)路徑長(zhǎng)度為23.6；IQ-learning算法學(xué)習(xí)80次得到的路徑更短，此時(shí)訓(xùn)練得到路徑長(zhǎng)度為22.8。

圖11 混合型障礙物環(huán)境下的路徑規(guī)劃

經(jīng)過(guò)以上仿真驗(yàn)證，本文提出的IQ-learning算法能夠減少移動(dòng)機(jī)器人在局部路徑規(guī)劃中的路徑長(zhǎng)度，不進(jìn)入死鎖或陷阱區(qū)域。在不同環(huán)境下兩種算法的路徑長(zhǎng)度對(duì)比見(jiàn)表2。

表2 不同環(huán)境下的路徑長(zhǎng)度

實(shí)驗(yàn)中，Q-learning算法和IQ-learning算法都經(jīng)過(guò)80次學(xué)習(xí)得到最短路徑。在混合型障礙物環(huán)境下，記錄了Q-leaning算法和IQ-learning算法的路徑長(zhǎng)度變化趨勢(shì)，如圖12所示，由圖12可以看出Q-learning算法在訓(xùn)練40次后路徑長(zhǎng)度趨于收斂，而IQ-learning算法在訓(xùn)練20次后，路徑長(zhǎng)度明顯下降并趨于收斂。IQ-learning算法相較于Q-learning算法能在更少的訓(xùn)練次數(shù)內(nèi)找到較優(yōu)的路徑，加快了收斂速度。

圖12 路徑長(zhǎng)度變化趨勢(shì)對(duì)比

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

本文基于柵格地圖環(huán)境對(duì)Q-learning算法進(jìn)行改進(jìn)，加入對(duì)角線運(yùn)動(dòng)獎(jiǎng)勵(lì)值，使得移動(dòng)機(jī)器人在規(guī)劃路徑中能夠以更少的訓(xùn)練次數(shù)得到更優(yōu)的路徑。通過(guò)改進(jìn)后的IQ-learning算法和Q-learning算法在同一障礙物環(huán)境和同樣訓(xùn)練次數(shù)下的仿真實(shí)驗(yàn)結(jié)果對(duì)比，IQ-learning算法訓(xùn)練得到的路徑長(zhǎng)度更短，其收斂速度也有所提高，驗(yàn)證了IQ-learning算法的可行性。

然而隨著移動(dòng)機(jī)器人所處環(huán)境狀態(tài)越來(lái)越復(fù)雜，使用Q值表存儲(chǔ)狀態(tài)-動(dòng)作值函數(shù)的缺點(diǎn)越來(lái)越明顯，會(huì)引起維數(shù)災(zāi)難。下一步的研究工作是利用函數(shù)近似逼近來(lái)替代Q值表，增強(qiáng)算法的可行性和通用性。