引入勢場及陷阱搜索的強化學(xué)習(xí)路徑規(guī)劃算法

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

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

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

2.南京理工大學(xué) 計算機科學(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 引言

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

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

2 強化學(xué)習(xí)機制

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

（1）策略（policy）

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

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

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

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

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

通過對值函數(shù)評估來不斷改變對應(yīng)狀態(tài)的行動策略，以達到最大化回報：

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

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

3 Q-learning算法模型

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

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

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

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

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

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

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

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

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

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

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

4.1 改進人工勢場法

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

引力勢場函數(shù)：

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

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

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

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

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

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

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

陷阱搜索算法如下：

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

圖1 柵格地圖

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

步驟3搜索陷阱起始頂點。從坐標(biāo)原點沿X正方向進行層內(nèi)搜索，沿Y方向進行層級搜索，每次移動1個柵格，判斷當(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ū)域的起始頂點，將疑似陷阱標(biāo)志位置1，將當(dāng)前層疑似陷阱序號加1，記錄當(dāng)前坐標(biāo)，轉(zhuǎn)步驟4；否則不做任何處理，繼續(xù)搜索起始頂點。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 仿真實驗

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

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

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

圖5 陷阱區(qū)域

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

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

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

圖6 基于引力勢場的強化學(xué)習(xí)路徑規(guī)劃

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

6 結(jié)論

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

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

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