基于Q學習算法的機場道面移動機器人路徑規劃研究

王淑玲 卓麗

摘 要：路徑規劃是移動機器人研究領域的熱點問題。針對不同的規劃需求，已經提出許多種路徑規劃的算法。本文考慮機場飛行場地環境，應用Q學習算法規劃出點到點的靜態安全避障路徑。為進一步優化上述規劃結果，提出了一種改進Q學習算法的方法，通過比較改進前后的路徑規劃結果，驗證了改進方法的有效性。研究成果不僅給出該機場飛行場地環境中靜態路徑規劃的方法，也為相關移動機器人的研發提供了理論依據。

關鍵詞：移動機器人;Q學習算法;飛行場地;路徑規劃

1.引言

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

2.Q學習算法的基本原理

在機器學習范疇內，根據反饋的不同，機器學習可分為監督學習（Supervised learning）、無監督學習（Unsupervised learning）和強化學習（Reinforcement learning）三類[12]，其中強化學習以環境的反饋信號作為輸入，移動機器人使用這種算法可以實現從環境信息到行為映射的學習。

強化學習是一種在線的學習方法，其整體框圖如圖1所示。移動機器人將感知到的環境狀態傳遞給強化學習算法，強化學習算法會選擇一個動作，在完成相應的動作后移動機器人所處的環境會改變，此時根據改變后的環境狀態反饋一個獎賞值給移動機器人。強化學習的基本要素有：策略、值函數、獎懲函數、環境模型。

根據問題的不同，強化學習方法主要分為兩大類算法：一類是值函數估計法，如蒙特卡羅算法、Q-學習算法、瞬時差分法等;另一類是策略空間直接搜索法，如模擬退火法、遺傳程序設計、遺傳算法及一些改進方法等。本文重點研究Q-學習算法及其在某軍用機場移動機器人路徑規劃中的應用。

Q-學習算法通過估計狀態—動作對的值函數Q（s，a） 以尋求最優策略π* ，Q值更新規則如下：

式中，Q（st，at） 為狀態st 后，所得到的累積加權獎賞。根據策略π進行狀態集合與動作集合間的映射，即狀態—動作對的值函數。在學習過程中通常將每個狀態與所有動作的映射值建立一個查詢表。α 為學習率，γ 為折扣因子。

3.移動機器人的路徑規劃

通過調研國內外的研究現狀發現，在后勤裝備保障領域，移動機器人有清掃機器人、搬運機器人、巡查機器人、車輛搶救機器人、排彈搶修機器人、自動加油機器人和醫療救助機器人等，主要遂行運輸、裝卸、加油、搶修技術裝備、搶救病人等后勤保障任務。飛行場地是空軍后勤裝備保障領域機器人活動的主要場所之一。

上圖是某機場的飛行場地，主要是供飛機起飛、著陸、滑行和停放的場地。由機場跑道、滑行道、聯絡道、拖機道、保險道、土跑道、平地區、停機坪、加油坪、校靶坪、防吹坪、平行道路等組成。 各主要組成部分的尺寸及位置關系如下：

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

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

端保險道：在跑道的兩頭都有一片平整和密實的場地，它的長度為200米至400米，寬度為100米左右。

停機坪：在跑道一側約100米遠的地方，有一些用水泥混凝土澆筑成的地坪，供停放飛機用。

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

聯絡道：主滑行道中部與跑道相聯接的部分，叫中間聯絡道。兩頭與跑道相聯接的部分，叫端聯絡道。聯絡道的寬度為100米。

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

下面，我們將應用Q-學習算法對移動機器人的路徑進行規劃。

3.1 環境建模

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

3.2 動作空間的表示

移動機器人根據策略π來選擇動作，π：S→A 表示狀態到動作的映射。其中S 是狀態集、A 是動作集，它們定義了移動機器人在狀態s 下應選擇哪個動作來執行。相對于機場的尺寸及面積，移動機器人的尺寸較小，為簡單起見，將移動機器人視作一個質點，不考慮機器人的尺寸大小，用一個藍色的圓圈表示。以移動機器人為中心，定義機器人的真實動作空間模型A為上、下、左、右四個離散動作，即下式的矩陣：

。

3.3 動作選擇策略

常用的動作策略方法包括：ε- greedy策略、Boltzmann分布策略及模擬退火策略。本文選用基于近似動作空間模型的模擬退火策略，通過觀測機器人周圍的環境信息，有針對性的對真實的動作空間模型A進行簡化處理，得到與之相似的動作模型 ? ? ? ，然后利用模擬退火策略選擇 ? ? ? 中的一個動作并執行。

3.4 獎賞函數的設計

獎賞函數是執行動作a后對產生的結果進行的一個評價性反饋。如果執行完動作a 后移動機器人達到一個有益于最終目標的狀態，則R值是正數。相反的，如果是一個不理想的狀態，則R值是負數。

獎賞函數在機器人學習過程中起到了導向性的作用，強化學習的目標就是使機器人最終獲得的總的獎賞值達到最大，并找到最優策略使得機器人從起點無碰撞的運動到目標點。因此需要及時準確的反映機器人在不同狀態下不同行為策略的好壞，設計良好的獎賞函數足以滿足這一需求。本文采用如下分段函數表示立即獎賞函數：

式中，s 表示機器人所處的狀態，1表示此柵格為危險區域（主要指平地區），存在障礙物，在地圖中表示為黑色方塊。從上式可知，當機器人到達目標點時，獲得最大的立即獎賞值100;當機器人與障礙物發生沖突時，獲得的獎賞值為-1;其他情形下的獎賞值為0。

3.5 結果分析

若設定機器人起始位置為（1，1） ，目標位置為（19，19） ，學習效率α=1 ，折扣因子γ=1 ，依據Q學習算法進行路徑規劃，所得結果如下表所示：

從規劃出的路徑結果可以發現，機器人在行走的過程中會在某個柵格的附近反復，也就是探索。導致這一結果發生的主要原因是，Q學習算法是一種不需要先驗知識的算法，而是需要機器人在學習中不斷地豐富策略知識。Q學習是從外部環境狀態到動作的映射當中，找到一個最優策略，使得機器人獲得最大累積獎懲值，這就需要機器人選擇傾向于能夠產生正的獎懲值的動作，即對動作策略的利用，而為了發掘新的動作策略，就需要機器人去嘗試那些沒有被選擇的動作，即探索。探索是尋找最優路徑的有效方法，但是過多的探索就會使得累計獎懲值無法收斂，而如果探索進行的不徹底，只利用僅有的一些動作策略，就不能夠找到最優策略。

為了優化路徑規劃結果，找到更加短的路徑，只需將表1中重復的動作刪除，得到的結果如下表2所示：

通過對比表1與表2的結果，可以發現優化后的動作個數只有38個，而優化前的動作個數有56個， 探索的過程減少了，移動機器人行走的路徑和轉折角度也更小了。

4.結束語

本文詳細介紹了Q學習算法在機場環境中的路徑規劃，采用Q學習算法進行移動機器人路徑規劃雖然能獲得一條完全無碰的路徑，但探索過多，導致路徑的總長度和總轉折角度較大。這在移動機器人實際應用中將消耗更多的能量和花費更多的時間。論文結尾提出了優化規劃結果的方法。理論研究為后勤裝備保障領域機器人的研發設計提供了基礎。當然，實際應用中還需考慮機器人的尺寸及轉彎半徑。圍繞該特定環境，還需在動態避障、全覆蓋路徑規劃方面有更深入的研究。感謝空裝重點項目（KJ20182A050259）及院青年科研基金（KY2018D011B）對該研究的支持。

參考文獻：

[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]周婷. 基于改進蟻群算法的移動機器人路徑規劃及實現[D].中南大學，2010.

[4]朱大奇，顏明重. 移動機器人路徑規劃技術綜述[J]. 控制與決策，2010，25（7）：961-967.

[5]吳乙萬，黃智. 基于動態虛擬障礙物的智能車輛局部路徑規劃方法[J]. 湖南大學學報：自然科學版，2013，40（1）：33-37.

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

[7]孫煒，呂云峰，唐宏偉，薛敏. 基于一種改進A*算法的移動機器人路徑規劃[J]. 湖南大學學報， 2017，44（4）：94-101.

[8]高慧. 基于強化學習的移動機器人路徑規劃研究[D]. 西南交通大學， 2016.

[9]劉仕超. 基于強化學習的移動機器人路徑規劃研究[D]. 山東科技大學， 2017.

[10]馮超. 強化學習精要核心算法與TensorFlow實現[M]. 北京：電子工業出版社， 2018.

[11]郭憲，方勇純. 深入淺出強化學習原理入門[M]. 北京電子工業出版社，2018.

[12]周志華. 機器學習[M]. 北京：清華大學出版社， 2016.

作者簡介：

第一作者：王淑玲（1984-），女，漢族，安徽宿州，碩研，南京理工大，副教授，主要研究方向：機器學習算法，統計診斷

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