李志龍，張建偉

（四川大學(xué)視覺合成圖形圖像技術(shù)國防重點(diǎn)學(xué)科實驗室，成都610065）

0 引言

現(xiàn)階段國內(nèi)民航事業(yè)邁入了飛速發(fā)展的階段，機(jī)場客流量數(shù)量也同時呈現(xiàn)飛速的增長。在機(jī)場旅客客流量不斷增多的同時，機(jī)場行李所需的運(yùn)輸量也隨之大幅的增長，故而機(jī)場需要雇傭更多的人工來進(jìn)行機(jī)場行李的搬運(yùn)裝卸等工作。但是伴隨著工作量的增大，行李的安全問題難以得到保障。而目前國外某機(jī)場所應(yīng)用的服務(wù)機(jī)器人很好的克服了這個問題，一方面削減了人工開支，另一方面繁重的工作量并不會對行李的搬運(yùn)產(chǎn)生影響，但是在機(jī)場中服務(wù)機(jī)器人的行駛軌跡會存在一個不確定性，且地勤人員、行李運(yùn)輸車等都可能會與服務(wù)機(jī)器人產(chǎn)生碰撞的問題，故而需要對服務(wù)機(jī)器人進(jìn)行合理的路徑規(guī)劃。

1 問題描述

研究服務(wù)機(jī)器人實時躲避障礙問題的難點(diǎn)分別為復(fù)雜性、隨機(jī)性、約束性和條件性等。現(xiàn)階段應(yīng)用較多的方法為基于隨機(jī)采樣的路徑規(guī)劃算法。例如YTing等人[1]提出了一種改進(jìn)的基于RRT 的平滑RRT 方法，此算法通過設(shè)立一個最大的曲率約束來防止遇到占該物體時可以獲得平滑的曲線，通過論文中的仿真實驗顯示，此算法比傳統(tǒng)的基于RRT 方法擁有更快的收斂速度。AlvesNetoA 等人[2]討論了基于PRM 方法的概率基礎(chǔ)，結(jié)論為其中部份的先驗知識能夠加快算法自身的收斂速度。但是此類中基于概率的路徑規(guī)劃方常常很難確保每次運(yùn)行期間都可以實現(xiàn)對期望軌跡的高精度跟蹤。由一種典型的避障算法稱作人工勢場法，障礙物在此類算法中被冠以為某類排斥性的表面的稱號，并且目標(biāo)防衛(wèi)則被刻畫成為一種具有吸引能力的端子，這樣使得機(jī)器人可以趨近最終目標(biāo)任務(wù)，從而避免與障礙物發(fā)生碰撞[3]。陳鋼等人[4]采用人工勢場法對障礙物進(jìn)行碰撞檢測獲取到了虛擬的排斥力，且引入臂平面和避障面設(shè)立了機(jī)械臂的動力學(xué)避障算法。申浩宇等人[5]定義了兩個轉(zhuǎn)換算子，且定義了一類基于主從任務(wù)轉(zhuǎn)換的動力學(xué)避障算法，使得冗余機(jī)器人可以實現(xiàn)輕松在多主從任務(wù)之間進(jìn)行平穩(wěn)切換。方承等人[6]設(shè)計了基于多個目標(biāo)函數(shù)的避障規(guī)劃算法，主要是為了解決單獨(dú)使用最短距離某些場景下會導(dǎo)致避障失敗的問題，該算法主要為當(dāng)障礙物位于機(jī)器人手臂構(gòu)型內(nèi)部時，以兩者之間的最短距離作為避障優(yōu)化指標(biāo)，而當(dāng)障礙物位于構(gòu)型外部時，以避障區(qū)域作為替代。Lacevic等人[7]提出了一種新的安全評價方法——危險場法。該算法結(jié)合了機(jī)器人手臂與障礙物之間的位置關(guān)系、機(jī)器人手臂的使用速度以及障礙物與障礙物手臂之間產(chǎn)生的夾角，導(dǎo)致了危險場中的不穩(wěn)定因素，并將其應(yīng)用于修改后的CLIK 算法[8]，順利解決了例如某些順利可變障礙物體的問題。其他方法還有如Hart、Nilsson和Raphael 提出的A*算法[9]，但是這些方法都存在一個明顯的問題，只是一味追求局部最優(yōu)解而忽略全局解。

針對以上所分析的情況，本文采用深度學(xué)習(xí)中的Q-Learning 算法對服務(wù)機(jī)器人的路徑選擇學(xué)習(xí)行為進(jìn)行建模，使得機(jī)器人可以在快速選擇合理的路徑，完善自身沖突探測和解脫知識庫的不足，進(jìn)一步提升自身的智能程度。

2 算法描述

2.1 強(qiáng)化學(xué)習(xí)相關(guān)理論

強(qiáng)化學(xué)習(xí)自身作為一種無監(jiān)督學(xué)習(xí)方法，機(jī)器人Agent 可以借助與動態(tài)環(huán)境的反復(fù)交互，學(xué)會選擇最優(yōu)或近最優(yōu)的行為以實現(xiàn)其長期目標(biāo)[10]。Sutton 和Barton 定義了強(qiáng)化學(xué)習(xí)方法的四個關(guān)鍵要素：策略、獎賞函數(shù)、價值函數(shù)、環(huán)境模型[11]。如1 圖表示為強(qiáng)化學(xué)習(xí)的主要基本模型。

圖1 強(qiáng)化學(xué)習(xí)基本模型

在圖1 中，Agent 會依照目前環(huán)境的狀態(tài)進(jìn)行下一步的動作與環(huán)境產(chǎn)生交互，而因此會從環(huán)境中得到此不行動所產(chǎn)生的獎勵，并更新為新的狀態(tài)，進(jìn)行更新策略的學(xué)習(xí)，接著再次執(zhí)行下一步動作作用于環(huán)境中，反復(fù)重復(fù)此過程，直到優(yōu)化策略完成任務(wù)。

2.2 Q-Learning

Q-Learning 作為一種典型的與模型無關(guān)的算法。該算法由Watkins[13]在1989 年提出，算法通過每一步進(jìn)行的價值來進(jìn)行下一步的動作。Q-Learning 算法首先會建立一張Q 值表，機(jī)器人自身每前進(jìn)一步都和環(huán)境會產(chǎn)生交互，并根據(jù)每次交互的結(jié)果，機(jī)器人會得到一定的獎賞，如上述強(qiáng)化學(xué)習(xí)的基本過程，其中Q 表如表1 所示。

表1 Q 值表

其中算法整體的基本流程如圖2 所示。

圖2 算法基本流程圖

Q-Learning 采用狀態(tài)-動作對Q(s,a)迭代方式來獲取到最優(yōu)的路徑策略。Q-Learning 在每次迭代的時候都會考慮每一個狀態(tài)-動作組合對Q(s,a)產(chǎn)生的結(jié)果值。其中算法的基本形式主要為：

其中：st,為t 時刻目標(biāo)機(jī)器人的移動狀態(tài)，在該st,狀態(tài)下執(zhí)行動作at,目標(biāo)機(jī)器人當(dāng)前狀態(tài)轉(zhuǎn)化為st,+1，同時獲取到此狀態(tài)的獎勵rt；rt主要的作用是對下一狀態(tài)st,+1進(jìn)行的評估，代表目標(biāo)物體從前一個狀態(tài)進(jìn)行到下一個狀態(tài)所能夠得到的獎勵值。動作a∈A，A 含義是作為動作空間；狀態(tài)st,,st,+1∈S，S 為狀態(tài)空間；α為學(xué)習(xí)率，Q 值會隨著學(xué)習(xí)率的增大而收斂速度加快，但是也存在更加容易產(chǎn)生振蕩的缺陷；maxaQ(st+1,a)代表從A 中選取某一個動作促使Q(st+1,a) 的當(dāng)前獲取值變?yōu)樽畲?；γ代表了折扣因子，表示未來獎勵對?dāng)前動作的影響程度[12]。

其中可以將式（1）變形為：

通過式（2）可得到，st所對應(yīng)的Q 值穩(wěn)定的必要條件需為st,+1對應(yīng)的maxaQ(st+1,a) 為固定值，若maxaQ(st+1,a)為非固定值則前一狀態(tài)Q 值將會隨下一狀態(tài)Q 值更新而發(fā)生變化，導(dǎo)致前序動作的狀態(tài)變得不穩(wěn)定。

通過對式（2）進(jìn)行n 此不斷迭代可以得到：

因為0 ＜α＜1，所以當(dāng)n→∞時，Q(st,at)收斂。

Q-Learning 會借助式（2）進(jìn)行更新，使得完整的Q表趨向一個極限的ΔQ(st,at)=rt+γmaxaQ( )st+1,a，隨著狀態(tài)得不斷更迭，Q 值會進(jìn)行更新操作，當(dāng)n→∞時，最終結(jié)果將趨向于最優(yōu)值。

避免產(chǎn)生局部最優(yōu)：Q-Learning 本質(zhì)上是貪心算法。如果每次都取預(yù)期獎勵最高的行為去做，那么在訓(xùn)練過程中可能無法探索其他可能的行為，甚至?xí)M(jìn)入“局部最優(yōu)”，無法完成游戲。所以，設(shè)置系數(shù)，使得智能體有一定的概率采取最優(yōu)行為，也有一定概率隨即采取所有可采取的行動。將走過的路徑納入記憶庫，避免小范圍內(nèi)的循環(huán)。

3 實驗仿真

本研究使用MATLAB 軟件進(jìn)行仿真驗證，設(shè)計基于Q-Learning 的最短路徑規(guī)劃算法，并考慮障礙物體的實時且隨機(jī)的變化情況，更加符合實際情況。同時使用網(wǎng)絡(luò)對Q 值更新進(jìn)行一定的優(yōu)化，使得Q 值表能夠更加符合實際應(yīng)用。

3.1 環(huán)境建模

本文在仿真實驗中主要使用地圖建模的方式建立一個有33 個節(jié)點(diǎn)的無向圖，其中每兩個個節(jié)點(diǎn)間的路徑都含有一個權(quán)值，代表兩點(diǎn)之間位移的代價，從開始點(diǎn)至結(jié)束點(diǎn)代價最小的路徑則為最優(yōu)路徑。同時，兩個節(jié)點(diǎn)間相連則表示兩點(diǎn)可以互相連接，若兩節(jié)點(diǎn)之間無路徑連接或有障礙物則表明該路徑不可前進(jìn)，其中障礙物在本次實驗中設(shè)定為隨機(jī)生成，在圖中第一次生成的障礙路徑以紅色叉號顯示，之后在原本尋路路徑基礎(chǔ)上增添的新的障礙路徑則設(shè)定為黑色叉號顯示。

圖3 原始地圖

3.2 實驗仿真

為了驗證所設(shè)計的機(jī)場服務(wù)機(jī)器人自動避障算法可行性，采用MATLAB 軟件對本算法進(jìn)行仿真實驗。現(xiàn)在我們拿其中一次實驗結(jié)果舉例，在本次仿真實驗中，隨機(jī)生成障礙路徑，機(jī)器人初始時刻位于1 號節(jié)點(diǎn)，終點(diǎn)坐標(biāo)位于28 號節(jié)點(diǎn)，障礙路徑分別為9、11、19、29、34、35、41。其中總結(jié)點(diǎn)數(shù)量為33，單位路徑數(shù)量為44，迭代次數(shù)為50，學(xué)習(xí)率α=0.9 ，折扣因子γ=0.8，試驗結(jié)果如圖4 所示。

圖4 第一次出現(xiàn)障礙圖

其中在實驗中增加了障礙物動態(tài)變化的可能性，新增障礙路徑為7、14、16、26。在變化的仿真環(huán)境中機(jī)器人路徑也同時產(chǎn)生了優(yōu)化，每次和環(huán)境產(chǎn)生交互都會更新其獎勵值，再根據(jù)獎勵值更新Q 表，最終通過環(huán)境-動作交互求得最終的Q 表，顯示出其實時動態(tài)性。如圖5 所示，其中黑色叉號為新增障礙路徑。

圖5 第二次出現(xiàn)障礙圖

其中由于Q-Learning 特性需要重復(fù)學(xué)習(xí)并記錄相關(guān)知識庫，故而在多次實驗后建立了尋找最優(yōu)路徑時間和運(yùn)行次數(shù)統(tǒng)計圖。圖6 列出了Q-Learning 和傳統(tǒng)算法的時間和運(yùn)行次數(shù)比較圖，圖6（a）表示傳統(tǒng)A*算法，圖6（b）為深度學(xué)習(xí)Q-Learning 算法?？梢詮膬蓮垐D中看到隨著Q-Learning 實驗運(yùn)行次數(shù)的增加，使用傳統(tǒng)A*算法隨著運(yùn)行次數(shù)的增加，運(yùn)行時間并不會減少，而在使用Q-Learning 算法中隨著實驗次數(shù)的增加，路徑的動態(tài)變化，服務(wù)機(jī)器人順利找到起始點(diǎn)到終點(diǎn)的最優(yōu)路徑所需的時間消耗呈現(xiàn)大幅的下降，體現(xiàn)了Q-Learning 算法在動態(tài)路徑識別中所代表出的優(yōu)勢。

4 結(jié)語

（1）本文針對機(jī)場服務(wù)機(jī)器人的移動路徑中可能會發(fā)生的碰撞問題及碰撞物體的動態(tài)移動問題提出了以深度學(xué)習(xí)Q-Learning 算法為基礎(chǔ)的解決方法。

（2）此方法經(jīng)過實驗論證相較于傳統(tǒng)算法也是有了較大的提升。通過對路徑進(jìn)行數(shù)學(xué)建模的方式進(jìn)行拓?fù)浣；?，在拓?fù)浠?，將所有的障礙物所遮擋的路徑加入相應(yīng)的知識庫，該方法減少了多次運(yùn)行試驗后機(jī)器人尋路的時間消耗量，提高了服務(wù)機(jī)器人的運(yùn)算速度，并且在運(yùn)行過程中實時對障礙物所處路徑進(jìn)行實時更新，以模擬現(xiàn)場環(huán)境中人員及其他障礙物體的不確定性。

（3）在經(jīng)過多次Q-Learning 實驗之后，服務(wù)機(jī)器人以較短時間順利避開行李車或機(jī)場地勤人員等障礙物，滿足設(shè)計的要求。

圖6