陽(yáng) 杰，張 凱

（西安工程大學(xué)電子信息學(xué)院，西安710600）

1 引 言

近年，國(guó)內(nèi)外學(xué)者對(duì)解決智能體路徑規(guī)劃方面進(jìn)行了廣泛的研究[1]。在早期研究中，常用的路徑規(guī)劃算法有柵格法、引力-排斥力勢(shì)場(chǎng)法、幾何構(gòu)造法、約束條件下的圖解法、基于時(shí)間窗動(dòng)態(tài)窗口法[2]等。隨著研究深入與人工智能的產(chǎn)生，產(chǎn)生了多種智能路徑規(guī)劃算法，如基于遺傳因子的遺傳算法[3]、基于粒子適應(yīng)度的粒子群算法[4]、基于信息素的蟻群算法[5]等，然而傳統(tǒng)的路徑規(guī)劃方法在解決規(guī)劃尋優(yōu)上都稍有不足。在解決復(fù)雜的環(huán)境路徑規(guī)劃時(shí)，基本智能路徑規(guī)劃算法易于陷入局部最優(yōu)解，無法避免規(guī)劃出現(xiàn)局部最優(yōu)解，得到結(jié)果只是次優(yōu)解；傳統(tǒng)的人工智能算法在解決復(fù)雜環(huán)境路徑規(guī)劃尋優(yōu)問題時(shí)，處理優(yōu)化的數(shù)據(jù)量龐大，需要通過反復(fù)迭代，不斷從初始位置進(jìn)行探索才能得到最佳的路徑。

強(qiáng)化學(xué)習(xí)算法是根據(jù)執(zhí)行動(dòng)作，將環(huán)境狀態(tài)改變反饋給智能體獎(jiǎng)勵(lì)值，來提高探索尋優(yōu)的路徑規(guī)劃能力。它通過對(duì)環(huán)境探索的不斷試錯(cuò)來尋找目標(biāo)點(diǎn)，通過對(duì)所有到達(dá)目標(biāo)點(diǎn)路徑優(yōu)化處理得到最優(yōu)路徑，對(duì)未知環(huán)境具有較好的效果，具有廣闊的應(yīng)用前景，但在針對(duì)復(fù)雜度較高的未知環(huán)境求解時(shí)，經(jīng)典Q 值的獲得仍然很困難。針對(duì)算法規(guī)劃尋優(yōu)問題，研究者提出了多種初始化Q 值函數(shù)以及增加環(huán)境先驗(yàn)知識(shí)的方法來加快路徑規(guī)劃收斂速度，例如神經(jīng)網(wǎng)絡(luò)初始化訓(xùn)練Q 值法、基于模糊規(guī)則初始Q 值計(jì)算法[6]、基于人工勢(shì)場(chǎng)法初始化狀態(tài)信息[7-9]等?；镜娜斯?shì)場(chǎng)法實(shí)施簡(jiǎn)單，能快速求解問題，但在大規(guī)模復(fù)雜未知障礙物環(huán)境中勢(shì)場(chǎng)力多，對(duì)之一一分析計(jì)算合力，會(huì)令工作量大增。

針對(duì)Q-learning 算法收斂慢、易陷入局部最優(yōu)、凹型障礙物探索能力差等問題，在此提出基于人工勢(shì)場(chǎng)與Metropolis 準(zhǔn)則的先驗(yàn)知識(shí)信息以及區(qū)域擴(kuò)展的Q 學(xué)習(xí)算法，旨在增強(qiáng)Q 學(xué)習(xí)算法對(duì)初始環(huán)境狀態(tài)探索感知能力，避免智能體在路徑探索中陷入凹形等障礙物環(huán)境而發(fā)生機(jī)器人鎖死等情況，并通過仿真實(shí)驗(yàn)，驗(yàn)證改進(jìn)算法在解的質(zhì)量和收斂速度上的表現(xiàn)情況。

2 柵格法建立倉(cāng)儲(chǔ)環(huán)境模型

在理想狀態(tài)下進(jìn)行路徑規(guī)劃不必考慮規(guī)劃路面是否是平坦，智能體也無需考慮具體行走姿態(tài)。為了能夠使用DL 算法，需要首先基于這個(gè)空間抽象定義出DL 算法中的環(huán)境，機(jī)器人在某一單元格需要?jiǎng)幼鳑Q策時(shí)，由強(qiáng)化學(xué)習(xí)算法提供狀態(tài)決策[10]。

為便于研究，把復(fù)雜三維空間簡(jiǎn)單化降維并離散化成一個(gè)二維柵格地圖，再將智能體質(zhì)點(diǎn)化，以一個(gè)質(zhì)點(diǎn)代表機(jī)器人。在柵格地圖一般分為可行區(qū)域部分和障礙物部分，以0 和1 區(qū)分不同柵格。在柵格地圖中0 表示障礙物柵格，智能體不可行駛；1表示智能體可通行柵格。為了智能體路徑規(guī)劃研究的方便，將連續(xù)的狀態(tài)環(huán)境空間離散化處理，建立柵格化地圖模型。進(jìn)一步地，建立倉(cāng)儲(chǔ)柵格地圖環(huán)境模型，如圖1 所示。在此環(huán)境模型中仿真驗(yàn)證本文法，為算法在實(shí)際環(huán)境的應(yīng)用提供輔助參考。

圖1 倉(cāng)儲(chǔ)柵格地圖環(huán)境模型

在這一柵格環(huán)境中，機(jī)器人在某一個(gè)位置預(yù)測(cè)的下一步動(dòng)作柵格節(jié)點(diǎn)共8 個(gè)，以每個(gè)機(jī)器人所在的柵格坐標(biāo)點(diǎn)為準(zhǔn)，機(jī)器人行駛方向如圖2 所示。

圖2 機(jī)器人運(yùn)動(dòng)范圍

圖1 中，機(jī)器人坐標(biāo)（1，1）是第一個(gè)柵格，柵格序號(hào)為1。按照從左到右，從下到上排序，可得序號(hào)7的柵格坐標(biāo)是（7，1）；也可以由柵格坐標(biāo)為（7，1）得到柵格序號(hào)是7。

3 算法解析

3.1 Q-learning 算法

強(qiáng)化學(xué)習(xí)主要由智能體、環(huán)境、狀態(tài)、動(dòng)作、獎(jiǎng)勵(lì)值組成，其基本結(jié)構(gòu)模型如圖3 所示。Q-learning 是強(qiáng)化學(xué)習(xí)算法中基于價(jià)值的算法。Q 是智能體在狀態(tài)s(s∈S)下，通過動(dòng)作a(a∈A)獲得獎(jiǎng)勵(lì)值的收益期望函數(shù)，環(huán)境會(huì)對(duì)據(jù)Agent 的動(dòng)作反饋，給予相應(yīng)的回報(bào)r。算法的主要思想是基于環(huán)境狀態(tài)信息S與智能體動(dòng)作A 構(gòu)建一個(gè)表格來存儲(chǔ)Q 值，將其稱為Q 值表，智能體的動(dòng)作選擇根據(jù)Q 值表，使得優(yōu)化選擇出收益最大的動(dòng)作。

圖3 強(qiáng)化學(xué)習(xí)結(jié)構(gòu)模型

Q-learning 算法將值函數(shù)V(s)進(jìn)一步細(xì)分為了“狀態(tài)-動(dòng)作”對(duì)的值函數(shù)Q(s,a)，即原本狀態(tài)s 上的值函數(shù)V(s)被分為了s 狀態(tài)上各個(gè)動(dòng)作a 對(duì)應(yīng)的值函數(shù)Q(s,a)。Q 值更新公式如下式所示：

式中，r 為智能體從狀態(tài)s 下采取動(dòng)作a 使得環(huán)境狀態(tài)轉(zhuǎn)變到s'后獲得的獎(jiǎng)賞值；γ 為折扣因子；Q(s,a)為狀態(tài)s 下動(dòng)作a 對(duì)應(yīng)的Q 值；Q(s',a)為狀態(tài)s'下動(dòng)作a 對(duì)應(yīng)的Q 值；α 為學(xué)習(xí)效率。Q-learning 算法的優(yōu)勢(shì)在于將值函數(shù)進(jìn)行了細(xì)分，評(píng)價(jià)策略更加容易，更易學(xué)出最優(yōu)策略。缺點(diǎn)是Agent 的動(dòng)作空間必須離散且維數(shù)不能過高，否則容易陷入維數(shù)災(zāi)難,在解決倉(cāng)儲(chǔ)物流大規(guī)模路徑規(guī)劃問題時(shí)顯得乏力。

3.2 Metropolis 準(zhǔn)則的區(qū)域擴(kuò)張策略

為了避免探索的盲目性以及找到最優(yōu)路徑后的重復(fù)學(xué)習(xí)，此處作如下改進(jìn):

1）在路徑規(guī)劃過程中，智能體碰到障礙物時(shí),不需要重新返回到起始點(diǎn)再進(jìn)行迭代搜索, 而是在碰到障礙物之前的地方進(jìn)行搜索，尋找其它方向的可行路徑。

2）依照ε-greedy 貪婪策略探索，找到目標(biāo)后，根據(jù)模擬Metropolis 準(zhǔn)則退出此次探索過程，將目標(biāo)位置作為探索初始位置，對(duì)目標(biāo)周圍區(qū)域探索。隨著探索的繼續(xù)，目標(biāo)區(qū)域先驗(yàn)知識(shí)增加，探索區(qū)域隨之增大。

3）探索結(jié)束的自主學(xué)習(xí)條件的依據(jù)，根據(jù)目標(biāo)周圍區(qū)域探索，判斷出周圍位置距目標(biāo)點(diǎn)的距離是否到達(dá)最優(yōu)值。當(dāng)前規(guī)劃步數(shù)與前一步中步數(shù)相等時(shí)結(jié)束此次探索學(xué)習(xí)。

利用反向探索，可擺脫陷入局部最優(yōu)解，將目標(biāo)點(diǎn)作為探索初始點(diǎn)可以增加周圍區(qū)域最小規(guī)劃，加快算法收斂，避免了盲目的重復(fù)探索，提高整體搜索到?jīng)Q策的效率。

在傳統(tǒng)的智能算法中，并不采取區(qū)域探索學(xué)習(xí)，而是人為加入結(jié)束條件，進(jìn)行反復(fù)迭代規(guī)劃出一條到多條初始點(diǎn)到目標(biāo)點(diǎn)的路徑，學(xué)習(xí)效率一般。改進(jìn)方法增加了智能體環(huán)境先驗(yàn)知識(shí)，使智能體能夠自主結(jié)束學(xué)習(xí)，避免重復(fù)探索學(xué)習(xí)，節(jié)省了學(xué)習(xí)時(shí)間。改進(jìn)后的算法描述如下:

Step1: 初始化;

Step2: 以初始位置為探索點(diǎn)，規(guī)劃探索目標(biāo)點(diǎn)位置所在；

Step3: 探索如果碰到障礙物，不返回初始位置值，而是探索初始點(diǎn)在碰到障礙物前的位點(diǎn)，直到尋到目標(biāo)點(diǎn)，結(jié)束此次探索轉(zhuǎn)入下次探索；

Step4: 以探索到目標(biāo)點(diǎn)為中心探索策略，設(shè)置探索半徑大小為ρ，根據(jù)ε-greedy 貪婪策略從A(S)選擇一個(gè)動(dòng)作a，如果a 的探索半徑大于ρ，則轉(zhuǎn)到step5，否則轉(zhuǎn)到step6；

Step5: 根據(jù)A(S)重新隨機(jī)選擇一個(gè)動(dòng)作a'；

Step6: 執(zhí)行動(dòng)作a, 得到下一個(gè)狀態(tài)s'；

Step7: 如果步數(shù)越界, 總步數(shù)加1, 回到初始目標(biāo)位置, 降溫，轉(zhuǎn)到step4;

Step8: 如果到達(dá)目標(biāo),總幕數(shù)加1，成功步數(shù)加1，總步數(shù)加1，δ 加1, r 賦最大值, 更新Q, 回到初始位置，降溫，轉(zhuǎn)到step4;

Step9: 根據(jù)狀態(tài)s'的最大Q 值更新狀態(tài)s 的Q 值, 返回step2;

Step10: 如滿足結(jié)束條件，結(jié)束，否則返回step2。

3.3 人工勢(shì)場(chǎng)強(qiáng)化學(xué)習(xí)

傳統(tǒng)的Q-learning 算法在環(huán)境初始化時(shí)，智能體就算法而言對(duì)環(huán)境狀態(tài)信息完全不熟知。在算法初始的所有狀態(tài)下，動(dòng)作值函數(shù)V(s)構(gòu)成的Q 值表基本是一致的，故就智能體而言，動(dòng)作a 的選擇產(chǎn)生都是隨機(jī)的，狀態(tài)的概率也是均勻分布的，且概率值相同。傳統(tǒng)Q 學(xué)習(xí)在解決智能體路徑規(guī)劃探索時(shí)，設(shè)定的總是智能體在搜索到目標(biāo)點(diǎn)或機(jī)器人碰撞到障礙物時(shí)，算法才會(huì)給予一個(gè)回報(bào)獎(jiǎng)勵(lì)值r，從而更新狀態(tài)動(dòng)作Q 值表，而對(duì)于有凹形陷阱障礙物的環(huán)境，智能體容易被凹形區(qū)域干擾，傳統(tǒng)的獎(jiǎng)勵(lì)值獲得方式算法效率低下，需反復(fù)不斷迭代，尤其對(duì)復(fù)雜度較大的未知環(huán)境會(huì)出現(xiàn)大量無效迭代，搜索空間重復(fù)而無用，不僅浪費(fèi)資源，也降低算法效率[11-12]。

構(gòu)建勢(shì)場(chǎng)路徑規(guī)劃模型時(shí)，要知道智能體起始位置，設(shè)置起始坐標(biāo)s=(x,y)，同時(shí)也要知道目標(biāo)位置，設(shè)置目標(biāo)點(diǎn)坐標(biāo)g=(a,b)。之后再初始化獎(jiǎng)勵(lì)值函數(shù)以及Q 值表，以目標(biāo)點(diǎn)為中心構(gòu)建引力勢(shì)場(chǎng)，以障礙物為中心構(gòu)建排斥力勢(shì)場(chǎng)，設(shè)定初始化后的V(s)值。

智能體在某一位置時(shí)需要對(duì)柵格環(huán)境行駛的8個(gè)柵格逐一探索，若發(fā)現(xiàn)障礙物，則進(jìn)行V(S(t+1))=-A 操作，對(duì)該障礙物進(jìn)行區(qū)域外側(cè)探索，確定障礙物環(huán)境區(qū)域，并針對(duì)該區(qū)域擴(kuò)展探索。該區(qū)域值函數(shù)狀態(tài)值為負(fù)數(shù)。

根據(jù)智能體動(dòng)作更新環(huán)境狀態(tài)值函數(shù)，并通過值函數(shù)按下式更新動(dòng)作Q 值表：

在初始時(shí)刻，智能體從起始位置出發(fā)，通過創(chuàng)建的引力勢(shì)場(chǎng)、排斥力勢(shì)場(chǎng)，構(gòu)建初始環(huán)境狀態(tài)信息，狀態(tài)V(S(t+1))≥0 是可移動(dòng)探索區(qū)域。智能體每一個(gè)動(dòng)作對(duì)應(yīng)Q 值表更新一對(duì)狀態(tài)-動(dòng)作值。探索到目標(biāo)位置或者碰到障礙物后，此探索結(jié)束，從障礙物前一步或者目標(biāo)點(diǎn)進(jìn)行區(qū)域擴(kuò)張?zhí)剿鳌?/p>

3.4 回報(bào)函數(shù)設(shè)計(jì)

綜合考慮機(jī)器人行駛每一步?jīng)Q策動(dòng)作而不是尋找到目標(biāo)點(diǎn)才得到獎(jiǎng)勵(lì)值，在對(duì)獎(jiǎng)勵(lì)值設(shè)計(jì)時(shí)，設(shè)定為每一步動(dòng)作都會(huì)獲得對(duì)應(yīng)獎(jiǎng)勵(lì)值，根據(jù)每一步的動(dòng)作情況不同設(shè)計(jì)不同的回報(bào)函數(shù)值。表1 是根據(jù)探索動(dòng)作出現(xiàn)的情況設(shè)計(jì)的回報(bào)函數(shù)?？拷繕?biāo)點(diǎn)獲得正獎(jiǎng)勵(lì)值、遠(yuǎn)離目標(biāo)獲得負(fù)獎(jiǎng)勵(lì)值、如果與障礙物發(fā)生碰撞獲得較大的負(fù)獎(jiǎng)勵(lì)值。為了避免機(jī)器人與障礙物或其他機(jī)器人相撞、對(duì)機(jī)器人每一個(gè)單元格的移動(dòng)設(shè)計(jì)最小安全距離。只要機(jī)器人與障礙物或其他機(jī)器人距離大于最小安全距離dq，則認(rèn)為兩車不會(huì)相撞。

表1 函數(shù)獎(jiǎng)勵(lì)值設(shè)置

4 實(shí)驗(yàn)結(jié)果及分析

針對(duì)強(qiáng)化學(xué)習(xí)算法特點(diǎn)，在Windows 系統(tǒng)中的MATLAB 1019a 上進(jìn)行仿真實(shí)驗(yàn)。利用路徑規(guī)劃建模常用的柵格法構(gòu)建環(huán)境模型，在E 形、凹形環(huán)境下進(jìn)行仿真，驗(yàn)證本算法有效性并與Q 學(xué)習(xí)算法進(jìn)行對(duì)比。實(shí)驗(yàn)在E 型障礙物、凹型障礙物兩種環(huán)境下進(jìn)行，深色星線代表本算法，淺色實(shí)線代表Q 學(xué)習(xí)算法。對(duì)E 型柵格環(huán)境，設(shè)置起點(diǎn)坐標(biāo)s=(15,6)，終點(diǎn)坐標(biāo)g=(20,20)。仿真實(shí)驗(yàn)結(jié)果如圖4 所示；

圖4 E 型障礙物環(huán)境仿真結(jié)果

對(duì)凹型柵格環(huán)境，設(shè)置起點(diǎn)坐標(biāo)s=(1,20)，終點(diǎn)坐標(biāo)g=(20,1)。仿真實(shí)驗(yàn)結(jié)果如圖5 所示。

圖5 凹型障礙物環(huán)境仿真結(jié)果

為確保驗(yàn)證結(jié)果更加準(zhǔn)確，在這四種障礙物環(huán)境中各運(yùn)行仿真10 次。對(duì)兩種算法的對(duì)比實(shí)驗(yàn)數(shù)據(jù)進(jìn)行統(tǒng)計(jì)，得到的結(jié)果如表2 所示。

表2 兩種方法對(duì)比實(shí)驗(yàn)統(tǒng)計(jì)結(jié)果

從圖4、圖5 可以看出，本改進(jìn)算法的收斂效果明顯要優(yōu)于Q 學(xué)習(xí)算法，不論是E 型障礙物環(huán)境或者凹型障礙物環(huán)境都具有較好的收斂效果。在表2中用最優(yōu)值、平均長(zhǎng)度、標(biāo)準(zhǔn)差及最優(yōu)值次數(shù)四個(gè)指標(biāo)來評(píng)估兩種算法性能的優(yōu)劣。用路徑最優(yōu)值、平均長(zhǎng)度表征本算法在全局搜索最優(yōu)路徑中的能力；用標(biāo)準(zhǔn)差來表征算法多樣性：標(biāo)準(zhǔn)差越小，多樣性越高。用在十次實(shí)驗(yàn)中達(dá)到全局最優(yōu)值次數(shù)的概率表征算法的魯棒性。

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

傳統(tǒng)Q 學(xué)習(xí)算法在智能體路徑規(guī)劃中全局搜索能力差，易陷入局部最優(yōu)，收斂速度慢，改進(jìn)算法采用勢(shì)場(chǎng)強(qiáng)化，以引力與排斥力勢(shì)場(chǎng)結(jié)合對(duì)初始環(huán)境狀態(tài)初始化，并引入了更新區(qū)域擴(kuò)張的搜索策略。仿真實(shí)驗(yàn)證明，新算法不僅在各種障礙物環(huán)境中保證解的質(zhì)量與收斂速度，在復(fù)雜環(huán)境中也同樣具有良好的準(zhǔn)確性與魯棒性。在此僅針對(duì)靜態(tài)障礙物驗(yàn)證了算法的有效性，在動(dòng)態(tài)環(huán)境下的路徑規(guī)劃還有待進(jìn)一步研究與摸索。