董培方，張志安，梅新虎，朱 朔

DONG Peifang1,ZHANG Zhi’an1,MEI Xinhu2,ZHU Shuo1

1.南京理工大學(xué) 機(jī)械工程學(xué)院，南京 210094

2.南京理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，南京 210094

1.School of Mechanical Engineering,Nanjing University of Science and Technology,Nanjing 210094,China

2.School of Computer Science and Technology,Nanjing University of Science and Technology,Nanjing 210094,China

1 引言

隨著無(wú)人駕駛的興起，移動(dòng)機(jī)器人路徑規(guī)劃技術(shù)越來(lái)越受到人們的重視。作為移動(dòng)機(jī)器人自主移動(dòng)的核心技術(shù)，有大量的科研人員投入到相關(guān)的研究工作中。傳統(tǒng)的路徑規(guī)劃技術(shù)有人工勢(shì)場(chǎng)法、圖解法、動(dòng)態(tài)窗口法[1]等，基于人工智能的路徑規(guī)劃技術(shù)有遺傳算法[2]、神經(jīng)網(wǎng)絡(luò)[3]、蟻群算法[4]等，每種方法都存在一定的局限性。傳統(tǒng)方法在復(fù)雜的環(huán)境地圖中易陷入陷阱中無(wú)法逃逸，有較大的概率無(wú)法到達(dá)目標(biāo)位置；而智能算法計(jì)算量龐大，需要進(jìn)行較多的迭代次數(shù)之后才能規(guī)劃成功。強(qiáng)化學(xué)習(xí)算法是根據(jù)獎(jiǎng)勵(lì)和懲罰機(jī)制來(lái)提高對(duì)特定任務(wù)的完成能力，其探索和貪心思想適用于未知環(huán)境中的路徑規(guī)劃，隨機(jī)探索的概率越大則最終獲得的路徑越優(yōu)，理論上能滿足任意復(fù)雜環(huán)境的路徑規(guī)劃，具有較強(qiáng)的可開(kāi)發(fā)性。

Q學(xué)習(xí)（Q-learning）算法是強(qiáng)化學(xué)習(xí)中的一種高效離策學(xué)習(xí)算法，傳統(tǒng)的Q-learning算法基于馬爾可夫過(guò)程，采用隨機(jī)初始化，對(duì)環(huán)境的先驗(yàn)信息為0，初始路徑較為隨機(jī)，導(dǎo)致路徑規(guī)劃效率低下，訓(xùn)練所需的迭代次數(shù)過(guò)多?；诖?，研究人員提出了多種方法初始化Q值函數(shù)加快路徑規(guī)劃的迭代速度，有神經(jīng)網(wǎng)絡(luò)法、模糊規(guī)則法[5]、人工勢(shì)場(chǎng)法[6-8]等。人工勢(shì)場(chǎng)法規(guī)則簡(jiǎn)單，效率較高，但在復(fù)雜環(huán)境中基于障礙物的斥力勢(shì)場(chǎng)數(shù)量多，計(jì)算量大。針對(duì)Q-learning算法的迭代速度慢，本文提出了引力勢(shì)場(chǎng)和環(huán)境陷阱搜索聯(lián)合作為先驗(yàn)信息初始化Q值，避免了復(fù)雜環(huán)境中斥力勢(shì)場(chǎng)龐大的計(jì)算量，同時(shí)有效防止了移動(dòng)體陷入環(huán)境中的凹形陷阱，加快了算法的迭代速度。同時(shí)取消對(duì)障礙物的試錯(cuò)學(xué)習(xí)，縮小可行路徑的范圍，使訓(xùn)練能應(yīng)用于真實(shí)環(huán)境中。最后，通過(guò)python及pygame模塊在復(fù)雜環(huán)境中進(jìn)行仿真實(shí)驗(yàn)，驗(yàn)證了算法的可行性和高效性。

2 強(qiáng)化學(xué)習(xí)機(jī)制

強(qiáng)化學(xué)習(xí)方法是指智能體（agent）通過(guò)在環(huán)境中按照一定的策略探索，根據(jù)環(huán)境的獎(jiǎng)勵(lì)和懲罰機(jī)制不斷調(diào)整行為策略，以獲得最大的回報(bào)值作為最終行為目的。在標(biāo)準(zhǔn)的強(qiáng)化學(xué)習(xí)框架中，包括智能體（agent）、環(huán)境及4個(gè)基本要素[9]。

（1）策略（policy）

策略π是智能體與環(huán)境交互時(shí)的行為選擇依據(jù)，S→A是狀態(tài)空間到動(dòng)作空間的映射，智能體在狀態(tài)St下根據(jù)π選擇動(dòng)作at+1∈A。

（2）獎(jiǎng)懲函數(shù)（reward）

獎(jiǎng)懲函數(shù)r反映當(dāng)前環(huán)境狀態(tài)St∈S（S為狀態(tài)空間集）下的動(dòng)作at∈A（A為動(dòng)作空間集）對(duì)達(dá)成目標(biāo)的貢獻(xiàn)度，r值越大代表當(dāng)前環(huán)境下的動(dòng)作越有利于達(dá)成目標(biāo)。

（3）值函數(shù)（value function）

值函數(shù)V是agent在環(huán)境下行動(dòng)的期望回報(bào)，強(qiáng)化學(xué)習(xí)通過(guò)不斷地試錯(cuò)來(lái)迭代值函數(shù)，以獲得較大期望回報(bào)，用于提高高回報(bào)值的狀態(tài)動(dòng)作選擇概率而降低低回報(bào)值的環(huán)境狀態(tài)選擇概率。

通過(guò)對(duì)值函數(shù)評(píng)估來(lái)不斷改變對(duì)應(yīng)狀態(tài)的行動(dòng)策略，以達(dá)到最大化回報(bào)：

（4）環(huán)境模型（model of environment）

環(huán)境模型強(qiáng)化學(xué)習(xí)的基本運(yùn)行環(huán)境，包括環(huán)境狀態(tài)及其對(duì)應(yīng)的動(dòng)作映射空間。

3 Q-learning算法模型

Q-learning算法是基于時(shí)序差分（Temporal-Difference，TD）誤差的離策強(qiáng)化學(xué)習(xí)算法，采用了動(dòng)態(tài)規(guī)劃的思想，根據(jù)下一步的最大動(dòng)作-狀態(tài)值函數(shù)作為動(dòng)作選擇的策略：

基于Q-learning的強(qiáng)化學(xué)習(xí)方法建立在馬爾可夫決策過(guò)程理論框架上，即智能體與環(huán)境的交互過(guò)程中，t時(shí)刻的狀態(tài)St只與上一個(gè)狀態(tài)S(t-1)下所采取的動(dòng)作a(t-1)有關(guān)，而與歷史狀態(tài)和動(dòng)作無(wú)關(guān)，即：

Q-learning更新函數(shù)：

其中，α為學(xué)習(xí)率，學(xué)習(xí)率越大，迭代速度越快，但易過(guò)擬合；γ為折扣率，即未來(lái)獎(jiǎng)勵(lì)對(duì)當(dāng)前動(dòng)作的影響程度[10]。

4 加入環(huán)境初始信息的快速Q(mào)-learning迭代算法

傳統(tǒng)的Q-learning算法無(wú)環(huán)境先驗(yàn)信息，初始狀態(tài)的所有狀態(tài)值函數(shù)V(s)均相等或完全隨機(jī)，每一步動(dòng)作a產(chǎn)生于隨機(jī)狀態(tài)，即此時(shí)的MDP環(huán)境狀態(tài)轉(zhuǎn)移概率是均等的。對(duì)于路徑規(guī)劃問(wèn)題而言，只有在達(dá)到目的地或者碰到障礙物才會(huì)更改回報(bào)值R，進(jìn)行一次有效的狀態(tài)-動(dòng)作值更新，回報(bào)函數(shù)的稀疏性致使初期的規(guī)劃效率低，迭代次數(shù)多，特別對(duì)于尺度較大的未知環(huán)境，易出現(xiàn)巨大的無(wú)效迭代搜索空間[11-12]。

結(jié)合人工勢(shì)場(chǎng)法和陷阱搜索的基本思想改進(jìn)基于Q-learning算法的路徑規(guī)劃：

（1）確定起始點(diǎn)坐標(biāo)a和目標(biāo)點(diǎn)坐標(biāo)b，在初始化狀態(tài)值函數(shù)中以目標(biāo)點(diǎn)為勢(shì)場(chǎng)中心建立引力勢(shì)場(chǎng)，根據(jù)目標(biāo)點(diǎn)的位置作為環(huán)境先驗(yàn)信息初始化V(S)表，設(shè)定初始化后的V(S)值均大于等于0。

（2）對(duì)環(huán)境地圖進(jìn)行4個(gè)方位的逐層搜索，若發(fā)現(xiàn)障礙物，則進(jìn)行V(S(t+1))=-A操作，若發(fā)現(xiàn)陷阱區(qū)域，則對(duì)該區(qū)域進(jìn)行逐層向外搜索，每層之間設(shè)置梯度值-B,并通過(guò)Lmax＜A/B，保證陷阱區(qū)的最外層狀態(tài)值為負(fù)數(shù)。

（3）利用環(huán)境狀態(tài)值函數(shù)更新?tīng)顟B(tài)-動(dòng)作值函數(shù)表：

（4）智能體從起始點(diǎn)開(kāi)始探索環(huán)境，只把V(S(t+1))≥0的狀態(tài)作為可探索狀態(tài)，采取可變貪心法則，每移動(dòng)一步更新一次狀態(tài)-動(dòng)作值。到達(dá)目標(biāo)點(diǎn)后結(jié)束此輪迭代，從起始點(diǎn)開(kāi)始進(jìn)入下一輪探索。

4.1 改進(jìn)人工勢(shì)場(chǎng)法

人工勢(shì)場(chǎng)法的基本原理是在目標(biāo)物周圍產(chǎn)生虛擬引力勢(shì)場(chǎng)，智能體在任何位置都受到來(lái)自目標(biāo)點(diǎn)的引力吸引，而障礙物對(duì)移動(dòng)物體產(chǎn)生排斥力，阻止物體靠近產(chǎn)生碰撞[13]。

引力勢(shì)場(chǎng)函數(shù)：

式中，kyin為引力常數(shù)；ρ(q)=||q-qg||是智能體與目標(biāo)位置的歐幾里德距離。

基于改進(jìn)引力勢(shì)場(chǎng)法初始化狀態(tài)值函數(shù)法則：Q-learning算法是基于馬爾科夫決策的無(wú)模型強(qiáng)化學(xué)習(xí)算法，采用可變?chǔ)?greedy法則[14]，其行為策略是往Q值增大的方向移動(dòng)，因此對(duì)于初始化狀態(tài)值函數(shù)表，應(yīng)滿足距離目標(biāo)點(diǎn)越近其引力勢(shì)場(chǎng)越大，與距離成反比（傳統(tǒng)的引力勢(shì)場(chǎng)與距離平方成正比），為了保證算法的實(shí)時(shí)性，不考慮障礙物的斥力勢(shì)場(chǎng)，同時(shí)減小公式計(jì)算復(fù)雜度，引入?yún)⒘縇用于調(diào)整初始狀態(tài)值的變化范圍：

D(Pinit,Pgoal)=為起始點(diǎn)和目標(biāo)點(diǎn)之間的距離。

對(duì)于復(fù)雜環(huán)境的Q-learning算法路徑規(guī)劃，動(dòng)作狀態(tài)空間龐大，迭代速度慢，引入目標(biāo)點(diǎn)改進(jìn)引力勢(shì)場(chǎng)來(lái)初始化狀態(tài)值函數(shù)，從而提供初始目標(biāo)位置，智能體具有目標(biāo)趨向性，能迅速朝目標(biāo)方向移動(dòng)，同時(shí)隨機(jī)策略保證其不陷入局部最優(yōu)解。

4.2 環(huán)境陷阱搜索算法

在復(fù)雜環(huán)境中，常常存在凹形障礙物，對(duì)于人工勢(shì)場(chǎng)法或蟻群算法等易陷入凹形區(qū)域，無(wú)法到達(dá)目標(biāo)點(diǎn)。基于強(qiáng)化學(xué)習(xí)算法的路徑規(guī)劃能夠通過(guò)隨機(jī)探索策略和策略改進(jìn)逃離此類障礙物，這種智能行為是高效導(dǎo)航基礎(chǔ)[15]，但規(guī)劃效率低，只引入引力勢(shì)場(chǎng)的強(qiáng)化學(xué)習(xí)算法由于目標(biāo)趨向性同樣容易陷入與目標(biāo)相對(duì)的凹形障礙物中，需要較多的訓(xùn)練次數(shù)才能逃逸，如果能直接將凹形障礙物從可行的規(guī)劃路徑中剔除，則能提高規(guī)劃的效率，減少迭代的次數(shù)。

針對(duì)此類障礙物，提出沿x、y方向的陷阱逐層搜索，并把搜索結(jié)果作為環(huán)境先驗(yàn)信息初始化狀態(tài)函數(shù)表V(S)。

陷阱搜索算法如下：

步驟1將探索環(huán)境柵格化，并對(duì)障礙物進(jìn)行膨脹處理，將移動(dòng)物體（agent）看作質(zhì)點(diǎn)。以地圖某一頂點(diǎn)作為坐標(biāo)原點(diǎn)建立直角坐標(biāo)系（如圖1所示，黑色為障礙區(qū)，白色為可行區(qū)域）。建立當(dāng)前層疑似陷阱長(zhǎng)度存儲(chǔ)數(shù)組Suspect-trap[]、層數(shù)存儲(chǔ)數(shù)組Trap-length[]以及當(dāng)前層陷阱個(gè)數(shù)存儲(chǔ)數(shù)組Trap-number[]。初始點(diǎn)坐標(biāo)為a(x,y)，目標(biāo)位置的坐標(biāo)為b(x,y)。對(duì)柵格地圖進(jìn)行4個(gè)方向的逐層搜索，如圖1為沿X正方向進(jìn)行層內(nèi)搜索，Y正方向進(jìn)行層級(jí)搜索，即沿柵格內(nèi)數(shù)字順序搜索。

圖1 柵格地圖

步驟2利用改進(jìn)人工勢(shì)場(chǎng)法初始化狀態(tài)函數(shù)表，距離目標(biāo)點(diǎn)越近，狀態(tài)值越大，非障礙物區(qū)域狀態(tài)值大于等于0，障礙物區(qū)域狀態(tài)值為-A(A＞0)，陷阱層數(shù)為N，陷阱狀態(tài)梯度值為G，已標(biāo)記陷阱區(qū)域狀態(tài)值為：

步驟3搜索陷阱起始頂點(diǎn)。從坐標(biāo)原點(diǎn)沿X正方向進(jìn)行層內(nèi)搜索，沿Y方向進(jìn)行層級(jí)搜索，每次移動(dòng)1個(gè)柵格，判斷當(dāng)前柵格狀態(tài)值V([x,y])，左側(cè)柵格狀態(tài)值V([x-1,y])，上側(cè)柵格狀態(tài)值V([x,y-1])，如果滿足：

即當(dāng)前柵格上側(cè)和左側(cè)均為障礙物，且當(dāng)前柵格為非障礙物，則認(rèn)為當(dāng)前柵格為陷阱區(qū)域的起始頂點(diǎn)，將疑似陷阱標(biāo)志位置1，將當(dāng)前層疑似陷阱序號(hào)加1，記錄當(dāng)前坐標(biāo)，轉(zhuǎn)步驟4；否則不做任何處理，繼續(xù)搜索起始頂點(diǎn)。

步驟4繼續(xù)沿X右側(cè)移動(dòng)，判斷V([x,y]),V([x,y-1]),V([x,y+d]),V([x+1,y]),若V([x,y-1])＞0,則此處非陷阱區(qū)域，置0疑似陷阱標(biāo)志位，返回步驟3；若V([x,y+d])=-A，為防止將可行路徑識(shí)別為陷阱區(qū)域而變成不可行域，則認(rèn)為[x,y+d]為當(dāng)前疑似陷阱非相鄰障礙物，取消當(dāng)前層的疑似陷阱標(biāo)志位，返回步驟3，其中d為可行路徑寬度調(diào)節(jié)參數(shù)。若同時(shí)滿足：

即當(dāng)前柵格處于疑似陷阱，累積當(dāng)前疑似陷阱中的柵格長(zhǎng)度，根據(jù)上一層V([x,y-1])的值來(lái)判斷當(dāng)前柵格處于陷阱中的位置，然后轉(zhuǎn)步驟5：

圖2 柵格地圖陷阱搜索流程圖

若未能滿足上述不等式，則將當(dāng)前疑似陷阱排除，清除陷阱柵格長(zhǎng)度和所處層級(jí)位置，清除疑似陷阱標(biāo)志位，返回步驟3。

步驟5當(dāng)沿著當(dāng)前層疑似陷阱搜索至另一端頂點(diǎn)時(shí)，即：

判斷目標(biāo)位置是否處于當(dāng)前層陷阱中，如果否，則記錄陷阱序號(hào)、起始頂點(diǎn)坐標(biāo)及陷阱長(zhǎng)度。如果目標(biāo)位置處于陷阱當(dāng)中，則將當(dāng)前疑似陷阱排除，清除陷阱柵格長(zhǎng)度和所處層級(jí)位置，清除疑似陷阱標(biāo)志位，返回步驟3。

步驟6當(dāng)一層搜索結(jié)束時(shí)，根據(jù)當(dāng)前層記錄的陷阱個(gè)數(shù)、陷阱序號(hào)及每個(gè)陷阱的長(zhǎng)度來(lái)更新相應(yīng)位置的值函數(shù)V，并從y+1層再次進(jìn)行步驟3，直至遍歷整個(gè)柵格地圖。

步驟7完成一次遍歷之后，再分別沿X正方向進(jìn)行層內(nèi)搜索，Y負(fù)方向進(jìn)行層級(jí)搜索；沿Y正方向進(jìn)行層內(nèi)搜索，X正方向進(jìn)行層級(jí)搜索；沿Y正方向進(jìn)行層內(nèi)搜索，X負(fù)方向進(jìn)行層級(jí)搜索；經(jīng)過(guò)4次柵格遍歷，能發(fā)現(xiàn)不同朝向的凹形陷阱。

步驟8更新完所有陷阱區(qū)域的狀態(tài)值函數(shù)后，根據(jù)當(dāng)前狀態(tài)-動(dòng)作對(duì)(S,a)來(lái)更新Q值，即采取動(dòng)作a后所獲得的瞬時(shí)回報(bào)值加上當(dāng)前狀態(tài)的最大折扣累積回報(bào)V(S)：

如圖2所示為示例柵格地圖的陷阱搜索過(guò)程，其中綠色柵格代表疑似陷阱起始頂點(diǎn)，黃色柵格代表疑似陷阱柵格，藍(lán)色代表疑似陷阱結(jié)束頂點(diǎn)，紅色代表疑似陷阱取消柵格，灰色代表已確認(rèn)陷阱柵格(d=1)。如圖3為陷阱搜索結(jié)束后各柵格的狀態(tài)值，陷阱區(qū)域狀態(tài)值呈現(xiàn)梯度變化。

圖3 柵格地圖陷阱搜索完成后狀態(tài)值

初始化完成之后，環(huán)境地圖狀態(tài)-動(dòng)作值函數(shù)有充分的環(huán)境先驗(yàn)信息，采取無(wú)障礙物試錯(cuò)的貪心策略。

回報(bào)函數(shù)是智能體移動(dòng)行為的判斷準(zhǔn)則，獲得回報(bào)越大，則相應(yīng)的行為策略概率得到提高，回報(bào)值越小，則對(duì)應(yīng)的行為策略概率減小?；赒-learning的常規(guī)路徑規(guī)劃把到達(dá)目標(biāo)點(diǎn)的回報(bào)值設(shè)為正數(shù)，激勵(lì)朝目標(biāo)方向移動(dòng)的行為策略，把碰到障礙物的回報(bào)值設(shè)為負(fù)數(shù)以懲罰相應(yīng)的行為。因此，基于此類的路徑規(guī)劃方法是從無(wú)任何環(huán)境認(rèn)知的狀態(tài)進(jìn)行不斷的試錯(cuò)，最終收斂Q值查詢表，使智能體以最優(yōu)的路徑達(dá)到目標(biāo)點(diǎn)[15]。

這樣的試錯(cuò)策略難以應(yīng)用到真實(shí)的環(huán)境中去，對(duì)于真實(shí)的移動(dòng)機(jī)器人，如果采用無(wú)環(huán)境先驗(yàn)信息的試錯(cuò)學(xué)習(xí)，會(huì)不可避免地撞上障礙物，直接損壞本體，無(wú)法進(jìn)行后續(xù)實(shí)驗(yàn)。因此對(duì)狀態(tài)-動(dòng)作值函數(shù)表的更新進(jìn)行如下假設(shè)：當(dāng)智能體在隨機(jī)探索下預(yù)測(cè)動(dòng)作a的下一個(gè)環(huán)境狀態(tài)為障礙物，直接取對(duì)應(yīng)，并按照策略進(jìn)行下一步動(dòng)作選擇，由于規(guī)定了可探索環(huán)境模型的Q(S,a)≥0，每次檢測(cè)到障礙物后，將其從可探索環(huán)境模型中剔除，在避免了障礙物碰撞的同時(shí)，減少了可迭代Q值查詢表，能有效加快收斂速度，并能應(yīng)用于真實(shí)未知環(huán)境中的路徑規(guī)劃，無(wú)需對(duì)障礙物設(shè)定回報(bào)函數(shù)值。

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

采用python編程環(huán)境，pygame模塊作為地圖繪制工具進(jìn)行未知環(huán)境下的復(fù)雜地圖路徑規(guī)劃算法驗(yàn)證。建立地圖模型尺寸為800×500，最小移動(dòng)單位為5，智能體動(dòng)作空間集合A(s)包含前進(jìn)、后退、左移、右移、左前移、右前移、左后移、右后移8個(gè)動(dòng)作，動(dòng)作空間集A(s)越大，對(duì)應(yīng)的路徑軌跡越平滑。將地圖劃分為160×100個(gè)網(wǎng)格作為環(huán)境狀態(tài)空間S。以環(huán)境地圖的左上角為坐標(biāo)原點(diǎn)，水平方向?yàn)閄軸，豎直方向?yàn)閅軸建立坐標(biāo)系，設(shè)定起始點(diǎn)和目標(biāo)點(diǎn)位置如圖4所示：綠點(diǎn)代表初始點(diǎn)，初始坐標(biāo)為（760，200），藍(lán)點(diǎn)代表目標(biāo)位置，目標(biāo)坐標(biāo)為（100，60）。

圖4 環(huán)境地圖、起始點(diǎn)與目標(biāo)點(diǎn)坐標(biāo)位置示意

在確定起始點(diǎn)和目標(biāo)點(diǎn)坐標(biāo)之后，進(jìn)行引力勢(shì)場(chǎng)和陷阱搜索初始化Q值函數(shù)，將環(huán)境的已知信息更新于Q值表之中。圖5所示為進(jìn)行陷阱搜索之后的環(huán)境狀態(tài)，其中綠色線條所在區(qū)域?yàn)橄葳鍏^(qū)域，黑色區(qū)域?yàn)橛行剿骺臻g，相比于初始化之前減小了有效狀態(tài)空間。其中2號(hào)、5號(hào)陷阱至外部障礙物之間的距離d由參數(shù)調(diào)節(jié)。

圖5 陷阱區(qū)域

為了驗(yàn)證本文提出方案的有效性，在同一環(huán)境地圖下進(jìn)行3組對(duì)比實(shí)驗(yàn)，分別采用常規(guī)的不帶有環(huán)境先驗(yàn)信息的Q-learning算法、只應(yīng)用引力勢(shì)場(chǎng)作為環(huán)境先驗(yàn)信息的Q-learning算法和同時(shí)應(yīng)用引力勢(shì)場(chǎng)和陷阱搜索作為環(huán)境先驗(yàn)信息的改進(jìn)Q-learning算法進(jìn)行路徑規(guī)劃，采用相同的折扣率、學(xué)習(xí)率和ε-greedy法則，每種方法進(jìn)行2000次迭代，得到最終路徑和起始位置到目標(biāo)點(diǎn)所需的步數(shù)。

通過(guò)仿真實(shí)驗(yàn)發(fā)現(xiàn)，沒(méi)有任何環(huán)境先驗(yàn)信息的強(qiáng)化學(xué)習(xí)路徑規(guī)劃在設(shè)定的復(fù)雜環(huán)境地圖中無(wú)法順利到達(dá)終點(diǎn)，第一次迭代經(jīng)過(guò)100000步的移動(dòng)仍然未能到達(dá)目標(biāo)點(diǎn)，即認(rèn)為在無(wú)環(huán)境先驗(yàn)信息且移動(dòng)路徑不能穿越障礙物的情況下，基于Q-learning的強(qiáng)化學(xué)習(xí)算法的路徑規(guī)劃難以達(dá)到目標(biāo)點(diǎn)，無(wú)法完成規(guī)劃。

其余兩組方法均能從起始位置到達(dá)目標(biāo)位置，但加入陷阱搜索去掉了較大范圍的路徑搜索，迭代速度明顯快于未加入陷阱搜索的算法，且在初始的若干次迭代過(guò)程中，從起始位置到達(dá)目標(biāo)位置所需的步數(shù)更少，用時(shí)更快。其部分訓(xùn)練代數(shù)路徑規(guī)劃效果如圖6和圖7所示，相同的訓(xùn)練次數(shù)圖7的移動(dòng)路徑優(yōu)于圖6所示路徑，基于陷阱搜索的環(huán)境先驗(yàn)信息使得智能體在整個(gè)訓(xùn)練過(guò)程中不會(huì)移動(dòng)至陷阱區(qū)域，提高了算法的效率。

圖6 基于引力勢(shì)場(chǎng)的強(qiáng)化學(xué)習(xí)路徑規(guī)劃

將這兩種方法的訓(xùn)練次數(shù)作為橫坐標(biāo)，每次迭代從起始點(diǎn)到終點(diǎn)所需移動(dòng)的步數(shù)作為縱坐標(biāo)做圖可得這兩種方法的訓(xùn)練速度和訓(xùn)練效果，迭代收斂趨勢(shì)如圖8所示。由圖8可知，進(jìn)行陷阱搜索作為環(huán)境先驗(yàn)信息的路徑規(guī)劃訓(xùn)練效果明顯優(yōu)于未進(jìn)行陷阱搜索的路徑規(guī)劃，前者收斂速度更快，且在相同的訓(xùn)練次數(shù)下得到的移動(dòng)路徑短于后者，整個(gè)訓(xùn)練周期時(shí)間更短。

6 結(jié)論

圖7 基于引力勢(shì)場(chǎng)和陷阱搜索的強(qiáng)化學(xué)習(xí)路徑規(guī)劃

圖8 有無(wú)陷阱搜索對(duì)路徑規(guī)劃迭代影響趨勢(shì)圖

傳統(tǒng)強(qiáng)化學(xué)習(xí)由于訓(xùn)練速度慢，迭代效率低而難以直接應(yīng)用。將引力勢(shì)場(chǎng)和陷阱搜索聯(lián)合作為環(huán)境先驗(yàn)信息初始化Q值函數(shù)的強(qiáng)化學(xué)習(xí)路徑規(guī)劃可以得到更快的收斂速度和更優(yōu)的移動(dòng)路徑，同時(shí)利用初始化避免對(duì)障礙物的試錯(cuò)探索減少了移動(dòng)體有效狀態(tài)空間，在明顯少于傳統(tǒng)強(qiáng)化學(xué)習(xí)的訓(xùn)練次數(shù)情況下達(dá)到更好的路徑搜索效果。對(duì)于較為復(fù)雜，凹形障礙物較多的環(huán)境，傳統(tǒng)的路徑規(guī)劃算法不僅計(jì)算量龐大，而且易陷入局部陷阱中無(wú)法逃逸，本文提出的算法針對(duì)此類環(huán)境有較高的規(guī)劃效率，能找到較優(yōu)的路徑。