基于強(qiáng)化學(xué)習(xí)的機(jī)場(chǎng)服務(wù)機(jī)器人動(dòng)態(tài)路徑規(guī)劃

李志龍，張建偉

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

0 引言

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

1 問(wèn)題描述

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

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

2 算法描述

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

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

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

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

2.2 Q-Learning

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

表1 Q 值表

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

圖2 算法基本流程圖

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

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

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

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

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

因?yàn)? ＜α＜1，所以當(dāng)n→∞時(shí)，Q(st,at)收斂。

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

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

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

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

3.1 環(huán)境建模

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

圖3 原始地圖

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

為了驗(yàn)證所設(shè)計(jì)的機(jī)場(chǎng)服務(wù)機(jī)器人自動(dòng)避障算法可行性，采用MATLAB 軟件對(duì)本算法進(jìn)行仿真實(shí)驗(yàn)。現(xiàn)在我們拿其中一次實(shí)驗(yàn)結(jié)果舉例，在本次仿真實(shí)驗(yàn)中，隨機(jī)生成障礙路徑，機(jī)器人初始時(shí)刻位于1 號(hào)節(jié)點(diǎn)，終點(diǎn)坐標(biāo)位于28 號(hào)節(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，試驗(yàn)結(jié)果如圖4 所示。

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

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

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

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

4 結(jié)語(yǔ)

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

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

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

圖6