王淑玲 卓麗

摘 要：路徑規(guī)劃是移動(dòng)機(jī)器人研究領(lǐng)域的熱點(diǎn)問題。針對(duì)不同的規(guī)劃需求，已經(jīng)提出許多種路徑規(guī)劃的算法。本文考慮機(jī)場(chǎng)飛行場(chǎng)地環(huán)境，應(yīng)用Q學(xué)習(xí)算法規(guī)劃出點(diǎn)到點(diǎn)的靜態(tài)安全避障路徑。為進(jìn)一步優(yōu)化上述規(guī)劃結(jié)果，提出了一種改進(jìn)Q學(xué)習(xí)算法的方法，通過比較改進(jìn)前后的路徑規(guī)劃結(jié)果，驗(yàn)證了改進(jìn)方法的有效性。研究成果不僅給出該機(jī)場(chǎng)飛行場(chǎng)地環(huán)境中靜態(tài)路徑規(guī)劃的方法，也為相關(guān)移動(dòng)機(jī)器人的研發(fā)提供了理論依據(jù)。

關(guān)鍵詞：移動(dòng)機(jī)器人;Q學(xué)習(xí)算法;飛行場(chǎng)地;路徑規(guī)劃

1.引言

路徑規(guī)劃是移動(dòng)機(jī)器人研究領(lǐng)域的熱點(diǎn)問題，在很多方面都有應(yīng)用，如無人機(jī)的避障飛行，巡航導(dǎo)彈躲避雷達(dá)搜索，GPS導(dǎo)航等，是完成復(fù)雜導(dǎo)航及其他任務(wù)的前提。路徑規(guī)劃可以描述為：移動(dòng)機(jī)器人依據(jù)某些優(yōu)化原則在運(yùn)動(dòng)空間中找到一條從起始狀態(tài)到目標(biāo)狀態(tài)、可以避開障礙物的最優(yōu)或接近最優(yōu)的路徑。起初，移動(dòng)機(jī)器人路徑規(guī)劃技術(shù)主要集中在靜態(tài)全局路徑規(guī)劃的研究，提出的算法包括柵格法、Dijkstra算法、A*算法等。后來，研究人員將重心傾向于局部路徑規(guī)劃上，而局部路徑規(guī)劃主要解決動(dòng)態(tài)情況下完全未知或者局部未知工作環(huán)境的路徑規(guī)劃問題，這對(duì)路徑規(guī)劃算法的實(shí)時(shí)性有了更高的要求，已提出的算法包括人工勢(shì)場(chǎng)法、遺傳算法、蟻群算法等[1-7]。近年來，基于強(qiáng)化學(xué)習(xí)的路徑規(guī)劃在移動(dòng)機(jī)器人的導(dǎo)航研究中變得越來越重要，成為國(guó)內(nèi)外研究的熱點(diǎn)[8-11]。

2.Q學(xué)習(xí)算法的基本原理

在機(jī)器學(xué)習(xí)范疇內(nèi)，根據(jù)反饋的不同，機(jī)器學(xué)習(xí)可分為監(jiān)督學(xué)習(xí)（Supervised learning）、無監(jiān)督學(xué)習(xí)（Unsupervised learning）和強(qiáng)化學(xué)習(xí)（Reinforcement learning）三類[12]，其中強(qiáng)化學(xué)習(xí)以環(huán)境的反饋信號(hào)作為輸入，移動(dòng)機(jī)器人使用這種算法可以實(shí)現(xiàn)從環(huán)境信息到行為映射的學(xué)習(xí)。

強(qiáng)化學(xué)習(xí)是一種在線的學(xué)習(xí)方法，其整體框圖如圖1所示。移動(dòng)機(jī)器人將感知到的環(huán)境狀態(tài)傳遞給強(qiáng)化學(xué)習(xí)算法，強(qiáng)化學(xué)習(xí)算法會(huì)選擇一個(gè)動(dòng)作，在完成相應(yīng)的動(dòng)作后移動(dòng)機(jī)器人所處的環(huán)境會(huì)改變，此時(shí)根據(jù)改變后的環(huán)境狀態(tài)反饋一個(gè)獎(jiǎng)賞值給移動(dòng)機(jī)器人。強(qiáng)化學(xué)習(xí)的基本要素有：策略、值函數(shù)、獎(jiǎng)懲函數(shù)、環(huán)境模型。

根據(jù)問題的不同，強(qiáng)化學(xué)習(xí)方法主要分為兩大類算法：一類是值函數(shù)估計(jì)法，如蒙特卡羅算法、Q-學(xué)習(xí)算法、瞬時(shí)差分法等;另一類是策略空間直接搜索法，如模擬退火法、遺傳程序設(shè)計(jì)、遺傳算法及一些改進(jìn)方法等。本文重點(diǎn)研究Q-學(xué)習(xí)算法及其在某軍用機(jī)場(chǎng)移動(dòng)機(jī)器人路徑規(guī)劃中的應(yīng)用。

Q-學(xué)習(xí)算法通過估計(jì)狀態(tài)—?jiǎng)幼鲗?duì)的值函數(shù)Q（s，a） 以尋求最優(yōu)策略π* ，Q值更新規(guī)則如下：

式中，Q（st，at） 為狀態(tài)st 后，所得到的累積加權(quán)獎(jiǎng)賞。根據(jù)策略π進(jìn)行狀態(tài)集合與動(dòng)作集合間的映射，即狀態(tài)—?jiǎng)幼鲗?duì)的值函數(shù)。在學(xué)習(xí)過程中通常將每個(gè)狀態(tài)與所有動(dòng)作的映射值建立一個(gè)查詢表。α 為學(xué)習(xí)率，γ 為折扣因子。

3.移動(dòng)機(jī)器人的路徑規(guī)劃

通過調(diào)研國(guó)內(nèi)外的研究現(xiàn)狀發(fā)現(xiàn)，在后勤裝備保障領(lǐng)域，移動(dòng)機(jī)器人有清掃機(jī)器人、搬運(yùn)機(jī)器人、巡查機(jī)器人、車輛搶救機(jī)器人、排彈搶修機(jī)器人、自動(dòng)加油機(jī)器人和醫(yī)療救助機(jī)器人等，主要遂行運(yùn)輸、裝卸、加油、搶修技術(shù)裝備、搶救病人等后勤保障任務(wù)。飛行場(chǎng)地是空軍后勤裝備保障領(lǐng)域機(jī)器人活動(dòng)的主要場(chǎng)所之一。

上圖是某機(jī)場(chǎng)的飛行場(chǎng)地，主要是供飛機(jī)起飛、著陸、滑行和停放的場(chǎng)地。由機(jī)場(chǎng)跑道、滑行道、聯(lián)絡(luò)道、拖機(jī)道、保險(xiǎn)道、土跑道、平地區(qū)、停機(jī)坪、加油坪、校靶坪、防吹坪、平行道路等組成。 各主要組成部分的尺寸及位置關(guān)系如下：

跑道：在飛行場(chǎng)地的中部，長(zhǎng)2000米，寬60米，用水泥混凝土筑成。

土跑道：在跑道旁邊有一片寬闊平整的場(chǎng)地，它和跑道一樣長(zhǎng)，但比跑道寬一些，80米左右。

端保險(xiǎn)道：在跑道的兩頭都有一片平整和密實(shí)的場(chǎng)地，它的長(zhǎng)度為200米至400米，寬度為100米左右。

停機(jī)坪：在跑道一側(cè)約100米遠(yuǎn)的地方，有一些用水泥混凝土澆筑成的地坪，供停放飛機(jī)用。

滑行道：在跑道一側(cè)100米的地方，與跑道平行的主滑行道，用水泥混凝土筑成，其寬度為40米。

聯(lián)絡(luò)道：主滑行道中部與跑道相聯(lián)接的部分，叫中間聯(lián)絡(luò)道。兩頭與跑道相聯(lián)接的部分，叫端聯(lián)絡(luò)道。聯(lián)絡(luò)道的寬度為100米。

平地區(qū)：主滑行道與跑道之間的一塊平整的地面。

下面，我們將應(yīng)用Q-學(xué)習(xí)算法對(duì)移動(dòng)機(jī)器人的路徑進(jìn)行規(guī)劃。

3.1 環(huán)境建模

首先構(gòu)建環(huán)境模型，在狀態(tài)s下執(zhí)行完動(dòng)作a后依據(jù)環(huán)境模型可以得出下一個(gè)狀態(tài)和獎(jiǎng)賞值R。本文采用柵格法在坐標(biāo)系中建立二維柵格地圖表示環(huán)境信息，柵格地圖將移動(dòng)機(jī)器人所處的場(chǎng)地環(huán)境（包括跑道、主滑行道、平地區(qū)及聯(lián)絡(luò)道）分解為小柵格，每個(gè)小柵格對(duì)應(yīng)于移動(dòng)機(jī)器人的一個(gè)狀態(tài)。每個(gè)狀態(tài)對(duì)應(yīng)于環(huán)境狀態(tài)集合S中的一個(gè)元素，每個(gè)柵格存在兩種狀態(tài)值0和1。其中，0表示此柵格為安全區(qū)域，在地圖中表示為白色方塊;1表示此柵格為危險(xiǎn)區(qū)域（主要指平地區(qū)），存在障礙物，在地圖中表示為黑色方塊。坐標(biāo)系中的線段（x，0） 、（0，y） 、（xmax，0） 、（0，ymax） 表示環(huán)境的邊界區(qū)域，即實(shí)際環(huán)境中的墻壁，藍(lán)色方塊區(qū)表示移動(dòng)機(jī)器人的起點(diǎn)位置，紅色方塊區(qū)域則表示目標(biāo)點(diǎn)位置。環(huán)境中的目標(biāo)位置和障礙物都處于靜止?fàn)顟B(tài)，且對(duì)于機(jī)器人而言環(huán)境中的障礙物及邊界位置是未知的。若柵格的寬度為1米，則整個(gè)環(huán)境為一個(gè)2000×200 的柵格世界，共形成了2000×200=400000 個(gè)環(huán)境狀態(tài)，不便于顯示工作環(huán)境模型及路徑規(guī)劃的結(jié)果，因此本文設(shè)置柵格長(zhǎng)度為100米，寬度為10米，則整個(gè)環(huán)境為一個(gè)20×20=400 的柵格世界。移動(dòng)機(jī)器人的工作環(huán)境建模如下圖所示：

3.2 動(dòng)作空間的表示

移動(dòng)機(jī)器人根據(jù)策略π來選擇動(dòng)作，π：S→A 表示狀態(tài)到動(dòng)作的映射。其中S 是狀態(tài)集、A 是動(dòng)作集，它們定義了移動(dòng)機(jī)器人在狀態(tài)s 下應(yīng)選擇哪個(gè)動(dòng)作來執(zhí)行。相對(duì)于機(jī)場(chǎng)的尺寸及面積，移動(dòng)機(jī)器人的尺寸較小，為簡(jiǎn)單起見，將移動(dòng)機(jī)器人視作一個(gè)質(zhì)點(diǎn)，不考慮機(jī)器人的尺寸大小，用一個(gè)藍(lán)色的圓圈表示。以移動(dòng)機(jī)器人為中心，定義機(jī)器人的真實(shí)動(dòng)作空間模型A為上、下、左、右四個(gè)離散動(dòng)作，即下式的矩陣：

。

3.3 動(dòng)作選擇策略

常用的動(dòng)作策略方法包括：ε- greedy策略、Boltzmann分布策略及模擬退火策略。本文選用基于近似動(dòng)作空間模型的模擬退火策略，通過觀測(cè)機(jī)器人周圍的環(huán)境信息，有針對(duì)性的對(duì)真實(shí)的動(dòng)作空間模型A進(jìn)行簡(jiǎn)化處理，得到與之相似的動(dòng)作模型 ? ? ? ，然后利用模擬退火策略選擇 ? ? ? 中的一個(gè)動(dòng)作并執(zhí)行。

3.4 獎(jiǎng)賞函數(shù)的設(shè)計(jì)

獎(jiǎng)賞函數(shù)是執(zhí)行動(dòng)作a后對(duì)產(chǎn)生的結(jié)果進(jìn)行的一個(gè)評(píng)價(jià)性反饋。如果執(zhí)行完動(dòng)作a 后移動(dòng)機(jī)器人達(dá)到一個(gè)有益于最終目標(biāo)的狀態(tài)，則R值是正數(shù)。相反的，如果是一個(gè)不理想的狀態(tài)，則R值是負(fù)數(shù)。

獎(jiǎng)賞函數(shù)在機(jī)器人學(xué)習(xí)過程中起到了導(dǎo)向性的作用，強(qiáng)化學(xué)習(xí)的目標(biāo)就是使機(jī)器人最終獲得的總的獎(jiǎng)賞值達(dá)到最大，并找到最優(yōu)策略使得機(jī)器人從起點(diǎn)無碰撞的運(yùn)動(dòng)到目標(biāo)點(diǎn)。因此需要及時(shí)準(zhǔn)確的反映機(jī)器人在不同狀態(tài)下不同行為策略的好壞，設(shè)計(jì)良好的獎(jiǎng)賞函數(shù)足以滿足這一需求。本文采用如下分段函數(shù)表示立即獎(jiǎng)賞函數(shù)：

式中，s 表示機(jī)器人所處的狀態(tài)，1表示此柵格為危險(xiǎn)區(qū)域（主要指平地區(qū)），存在障礙物，在地圖中表示為黑色方塊。從上式可知，當(dāng)機(jī)器人到達(dá)目標(biāo)點(diǎn)時(shí)，獲得最大的立即獎(jiǎng)賞值100;當(dāng)機(jī)器人與障礙物發(fā)生沖突時(shí)，獲得的獎(jiǎng)賞值為-1;其他情形下的獎(jiǎng)賞值為0。

3.5 結(jié)果分析

若設(shè)定機(jī)器人起始位置為（1，1） ，目標(biāo)位置為（19，19） ，學(xué)習(xí)效率α=1 ，折扣因子γ=1 ，依據(jù)Q學(xué)習(xí)算法進(jìn)行路徑規(guī)劃，所得結(jié)果如下表所示：

從規(guī)劃出的路徑結(jié)果可以發(fā)現(xiàn)，機(jī)器人在行走的過程中會(huì)在某個(gè)柵格的附近反復(fù)，也就是探索。導(dǎo)致這一結(jié)果發(fā)生的主要原因是，Q學(xué)習(xí)算法是一種不需要先驗(yàn)知識(shí)的算法，而是需要機(jī)器人在學(xué)習(xí)中不斷地豐富策略知識(shí)。Q學(xué)習(xí)是從外部環(huán)境狀態(tài)到動(dòng)作的映射當(dāng)中，找到一個(gè)最優(yōu)策略，使得機(jī)器人獲得最大累積獎(jiǎng)懲值，這就需要機(jī)器人選擇傾向于能夠產(chǎn)生正的獎(jiǎng)懲值的動(dòng)作，即對(duì)動(dòng)作策略的利用，而為了發(fā)掘新的動(dòng)作策略，就需要機(jī)器人去嘗試那些沒有被選擇的動(dòng)作，即探索。探索是尋找最優(yōu)路徑的有效方法，但是過多的探索就會(huì)使得累計(jì)獎(jiǎng)懲值無法收斂，而如果探索進(jìn)行的不徹底，只利用僅有的一些動(dòng)作策略，就不能夠找到最優(yōu)策略。

為了優(yōu)化路徑規(guī)劃結(jié)果，找到更加短的路徑，只需將表1中重復(fù)的動(dòng)作刪除，得到的結(jié)果如下表2所示：

通過對(duì)比表1與表2的結(jié)果，可以發(fā)現(xiàn)優(yōu)化后的動(dòng)作個(gè)數(shù)只有38個(gè)，而優(yōu)化前的動(dòng)作個(gè)數(shù)有56個(gè)， 探索的過程減少了，移動(dòng)機(jī)器人行走的路徑和轉(zhuǎn)折角度也更小了。

4.結(jié)束語

本文詳細(xì)介紹了Q學(xué)習(xí)算法在機(jī)場(chǎng)環(huán)境中的路徑規(guī)劃，采用Q學(xué)習(xí)算法進(jìn)行移動(dòng)機(jī)器人路徑規(guī)劃雖然能獲得一條完全無碰的路徑，但探索過多，導(dǎo)致路徑的總長(zhǎng)度和總轉(zhuǎn)折角度較大。這在移動(dòng)機(jī)器人實(shí)際應(yīng)用中將消耗更多的能量和花費(fèi)更多的時(shí)間。論文結(jié)尾提出了優(yōu)化規(guī)劃結(jié)果的方法。理論研究為后勤裝備保障領(lǐng)域機(jī)器人的研發(fā)設(shè)計(jì)提供了基礎(chǔ)。當(dāng)然，實(shí)際應(yīng)用中還需考慮機(jī)器人的尺寸及轉(zhuǎn)彎半徑。圍繞該特定環(huán)境，還需在動(dòng)態(tài)避障、全覆蓋路徑規(guī)劃方面有更深入的研究。感謝空裝重點(diǎn)項(xiàng)目（KJ20182A050259）及院青年科研基金（KY2018D011B）對(duì)該研究的支持。

參考文獻(xiàn)：

[1]Fujimura K，Samet H. A hierarchical strategy for path planning among moving obstacles [mobile robot][J].IEEE Transactions on Robotics & Automation，1989，5（1）：61-69.

[2]Kyriakopoulos K J，Saridis G N. Optional motion planning for collision avoidance of mobile robots in non-stationary enviroments[J]. Journal of Intelligent & Robotic Systems，1992，11（3）：223-267.

[3]周婷. 基于改進(jìn)蟻群算法的移動(dòng)機(jī)器人路徑規(guī)劃及實(shí)現(xiàn)[D].中南大學(xué)，2010.

[4]朱大奇，顏明重. 移動(dòng)機(jī)器人路徑規(guī)劃技術(shù)綜述[J]. 控制與決策，2010，25（7）：961-967.

[5]吳乙萬，黃智. 基于動(dòng)態(tài)虛擬障礙物的智能車輛局部路徑規(guī)劃方法[J]. 湖南大學(xué)學(xué)報(bào)：自然科學(xué)版，2013，40（1）：33-37.

[6]柴寅，唐秋華，鄧明星，胡進(jìn). 機(jī)器人路徑規(guī)劃的柵格模型構(gòu)建與蟻群算法求解[J]. 機(jī)械設(shè)計(jì)與制造，2016，4：178-181.

[7]孫煒，呂云峰，唐宏偉，薛敏. 基于一種改進(jìn)A*算法的移動(dòng)機(jī)器人路徑規(guī)劃[J]. 湖南大學(xué)學(xué)報(bào)， 2017，44（4）：94-101.

[8]高慧. 基于強(qiáng)化學(xué)習(xí)的移動(dòng)機(jī)器人路徑規(guī)劃研究[D]. 西南交通大學(xué)， 2016.

[9]劉仕超. 基于強(qiáng)化學(xué)習(xí)的移動(dòng)機(jī)器人路徑規(guī)劃研究[D]. 山東科技大學(xué)， 2017.

[10]馮超. 強(qiáng)化學(xué)習(xí)精要核心算法與TensorFlow實(shí)現(xiàn)[M]. 北京：電子工業(yè)出版社， 2018.

[11]郭憲，方勇純. 深入淺出強(qiáng)化學(xué)習(xí)原理入門[M]. 北京電子工業(yè)出版社，2018.

[12]周志華. 機(jī)器學(xué)習(xí)[M]. 北京：清華大學(xué)出版社， 2016.

作者簡(jiǎn)介：

第一作者：王淑玲（1984-），女，漢族，安徽宿州，碩研，南京理工大，副教授，主要研究方向：機(jī)器學(xué)習(xí)算法，統(tǒng)計(jì)診斷

第二作者：卓麗（1980-），女，漢族，江蘇徐州，碩研，中國(guó)礦業(yè)大學(xué)，講師，主要研究方向：電工電子