煤礦井下基于Ｑ－ｌｅａｒｎｉｎｇ算法的移動機器人路徑規劃

摘 要：機器人的路徑規劃一直是機器人研究領域的難點問題。針對煤礦井下環境的不確定性，環境的復雜使機器人很難得到好的規劃結果。采用強化學習算法中的Q-learning算法實現井下移動機器人的局部路徑規劃，并對Q函數中的即時回報進行加權修正，使算法更有效地利用環境特征信息，進一步提高了避障能力。最后通過VC++進行仿真和模擬。仿真實驗說明該方法的有效性和可行性。

關鍵詞：移動機器人；不確定環境；強化學習；路徑規劃

中圖分類號：TP18文獻標識碼：B

文章編號：1004-373X(2008)24-106-03

Path Planning of Mobile Robot Based on Q-learning Algorithm under Coal Mine

WANG Shuai

(Fushun Branch，China Coal Research Institute，Fushun，113001，China)

Abstract：Path planning of robot is still a difficult question in the robot research domain.Q-learning algorithm is used to realize local path planning of mobile robot under coal mine for environment uncertainty of coal mine，because it is difficult to obtain a good path in such a complex enivronment.Instant rewards in the function are modified by using weight，then the information of environment characteristics is used effectively to avoid the obstacles.At last the algorithm is simulated by using VC++.Simulation shows that this algorithm is efficient and feasible.

Keywords：mobile robot;uncertain environment;reinforcement learning;path planning

1 引 言

我國煤礦井下安全事故頻發，其中由于瓦斯爆炸而引起的煤礦災害事故占一半以上，安全一直是制約煤炭開采的關鍵問題。為了在井下發生煤礦瓦斯等事故中及時開展救援工作，研究一種能進入危險礦井進行現場環境檢測和人員搜救的井下移動機器人是非常必要的。

煤礦井下地形復雜，環境惡劣，災害發生后的井下環境變得更加不確定，復雜的路況要求井下移動機器人要有較強的路徑規劃能力。不確定環境下的路徑規劃是移動機器人研究的一個重要問題，一直是一個沒能妥善解決的難題。所謂不確定環境，是指移動機器人只能通過傳感器探測其周圍有限范圍內的環境信息。在這種不確定環境下，移動機器人的路徑規劃大都采用局部路徑規劃方法，又稱動態或在線路徑規劃。

災害后的井下環境是不確定的，路徑規劃方法一定要有學習的能力才能適應環境，提高井下移動機器人的智能性。強化學習是一種無監督的在線學習方法，由于其不需要知道環境精確模型，具有實時性和自適應性，因而適應解決井下不確定環境下的移動機器人路徑規劃問題。采用強化學習算法中的Q-learning算法來實現移動機器人在井下不確定環境下的路徑規劃，Q-learning算法適應不確定性環境下的學習，可以在井下的復雜多變的環境下快速有效地實現路徑規劃。

2 強化學習中Q-learning的算法

強化學習又被稱為增強學習或再勵學習，它的本質是從環境狀態到動作映射的學習，以使動作從環境中獲得的累積回報值最大。強化學習是一種重要的機器學習方法，在智能控制、機器人及分析預測等領域有許多應用。它要解決的是這樣的問題，一個能夠感知環境的自治機器人，怎樣通過學習選擇能達到目標的最優動作，即從環境到行為映射的學習，以使獎勵信號(強化信號)最大。Q-learning算法是一種最重要的強化學習方法。Q-learning是無需環境模型的強化學習的一種形式，它可以被認為是異步動態規劃的一種方法。Q-learning面臨的任務是在初始條件未知的情況下來決定策略。Watikins把Q-learning看成一個增量式的動態規劃。用一步方式來決定策略，并希望找到一個策略π(動作序列)使評價總和得到最大。如果環境模型(即狀態轉移概率及評價模型)已知或由觀測估計出來，則上述問題可用動態規劃(DP)解決。Q-learning的思想是不去估計壞境模型，而是直接優化一個可迭代計算的Q函數，此Q函數為在狀態st時執行動作at，且此后按最優動作序列執行時的折扣累計強化值，即：

Qt+1(st，at)=rt+γmaxat∈A Q(st+1，at)

3 基于Q-learning算法的路徑規劃

為了實時而準確獲得機器人所處環境的信息，解決障礙物的避障問題，機器人必須通過一定數量的傳感器來感知局部環境。假定機器人配置有8個測距傳感器，傳感器分別探測8個不同的方向，這8個方向平分圓周。根據移動機器人局部路徑規劃特點，假定機器人在任何時刻都能通過這些傳感器感知8個方向上一定距離之內是否存在障礙物，可以通過傳感信息測定機器人與障礙物之間的距離，并假定機器人與障礙物之間的安全距離為D，當距離小于D時，則會發生碰撞。

在Q-learning算法中，井下機器人的路徑規劃過程包括一系列不同的階段習步驟如下：

Step1：觀察當前的環境狀態；

Step2：選擇并執行一個動作；

Step3：觀察下一個環境狀態；

Step4：收到一個立即強化信號；

Setp5：調整Q值：

Qt(st，at)=(1-at)Qt-1(st，at)+at，

s=st;a=at

Qt-1(st，at)，其他

其中V(st+1)=max∑a∈A。

機器人在井下復雜環境中通過傳感器感知局部環境信息，做出判斷并執行動作，環境給出即時強化信號，機器人根據強化信號來調整動作。當機器人碰撞到障礙物后不返回初始點，在原地尋找其他可行路徑，保證能夠尋找到目標點。當滿足：到達目標和達到預定最大步數2個條件中的任何一個時，結束1個周期的學習，如此反復直到規劃出最優路徑。

4 仿真實驗及結果分析

在仿真試驗中，井下環境為離散化的柵格，每個柵格代表機器人的1種狀態。黑色區域為障礙物，空白處為巷道。井下移動機器人的任務是從任何一個初始位置開始以盡可能少的步數到達事故發生位置，并且不能和障礙物發生碰撞，做如下假設：

(1) 移動機器人在二維空間內運動;

(2) 機器人可以通過傳感器系統探測周圍一定范圍內的井下環境;

(3) 機器人把除了目標點外所有被觀測到的對象當作障礙物。

仿真場景如圖1所示，環境為10×10的柵格，仿真場景中的黑色區域為障礙物，綠色方格為初始點，紅色方格為目標點，其每次走過的軌跡被顯示出來，每個柵格對應于機器人走過的每一步。環境中的目標是靜態的，對于移動機器人而言，環境(即障礙物、邊界以及目標的位置)是不確定的。以機器人為中心的二維空間內平均分布8個運動方向，代表它的8個可選動作。

圖1 井下環境仿真場景圖

對于機器人的學習系統來說，學習的目標有2個：成功避開障礙物，以最少步數到達目標點。因此機器人強化信號包括2個方面：Rs={-10，10，-100，0}，對應條件為{接近障礙物，遠離障礙物，與靜態障礙物碰撞，其他}；Rg={100，0}，對應條件為{到達目標點，漫游尋找目標點}。

移動機器人從環境中獲得的總的強化信號：R=ωsRs+ωgRg，其中ωs和ωg是機器人相對于障礙物和目標點回報的加權值，0＜ωs＜1，0＜ωg＜1，權值ωg和ωg的和為1。以上各強化信號的加權值的選定，可以根據環境中障礙物的相關性，對傳感器可感知區域內是否感知到障礙物存在，是否趨向于目標點來賦予不同的權值，權值的大小反映移動機器人對環境特征的綜合重視程度。

仿真結果及分析如圖2和圖3所示，可以看出Q-learning算法在不確定環境下通過學習規劃出在當前無避碰的最優路徑。

圖2 井下路徑規劃效果仿真圖

成功幕數(Episode)是指移動機器人從初始位置開始，通過學習成功到達目標點的1個學習周期，成功步數是指每一幕中機器人成功學習的步數，成功步數越少，說明機器人的行動策略越來越優，路徑規劃的效率也越來越高。隨著學習的不斷進行，機器人對環境逐漸適應，機器人的行動越來越有效率，避障能力越來越高，成功幕數快速增加，每次成功學習步數呈減小趨勢，最終收斂到一個固定值，這說明此算法學習到最優路徑，這個路徑能保證機器人從初始點任一時刻出發都能避開障礙物，并在當前環境下以最少的步數到達目標點，如圖4所示，當井下環境較復雜時，規劃效果也很好。

圖3 成功步數收斂曲線圖

圖4 較復雜環境下路徑規劃效果圖

5 結 語

研究了利用強化學習算法解決井下移動機器人局部路徑規劃問題，采用強化學習中Q-learning算法實現井下移動機器人的局部路徑規劃。利用Q-learning算法的實時性和自適應性適合局部路徑規劃的特點，在不確定環境下的實現快速有效規劃，而且當井下環境變得復雜時，該算法的路徑規劃效果也很好，仿真試驗說明該方法的有效性和可行性。下一步的主要工作是如何結合實際進一步提高學習的效率和收斂速度，并運用到實際機器人系統中。

參考文獻

［1］戴博，肖曉明，蔡自興.移動機器人路徑規劃技術的研究現狀與展望.控制工程，2005，2(3):198-202.

［2］Khatib O.Real-time Obstacle Avoidance for Manipulators and Mobile Robot .The International Journal of Robotic Research，1986，5(1):90-98.

［3］Gemeinder M，Gerke M.GA-based Path Planning for Robot System Employing an Active Search Algorithm .Applied Soft Computing，2003(3):149-158.

［4］蔡自興，賀漢根，陳虹.未知環境中移動機器人導航控制研究若干問題.控制與決策，2002，17(4):386-390.

［5］石鴻雁，孫茂相，孫昌志.未知環境下移動機器人路徑規劃方法.沈陽工業大學學報，2005，27(1):63-69.

［6］Sutton R S，Barto A G.Reinforcement Learning:An Introduction .Cambridge，MA:MIT Press，1998.

［7］樸松昊，洪炳熔.一種動態環境下移動機器人的路徑規劃方法.機器人，2003，25(1):18-21.

［8］Miyazaki K，Yamamura M，Kobayashi S.On the Rationality of Profit Sharing in Reinforcement Learning .Proc.of the 3rd International Conference on Fuzzy Logic Neural Net and Soft Computing，1994:285-288.

［9］ Labb A M，Kavraki L E.Measure Theoretic Analysis of Probabilistic Path Planning.Robotics and Automation，IEEE Transactions on，2004，20(2):229-242.

［10］Smith，Andrew James.Applications of the Self-organizing Map to Reinforcement Learning.Neural Networks，2002(15):1 107-1 124.

作者簡介

王 帥 男，1979年出生，遼寧西豐人，工學碩士。研究方向為智能控制與機器學習。

(上接第101頁)

［6］朱正明，姜明，馬小明.基于特征點匹配的圖像拼接系［J］.林業科學，2004，40(4):117-123.

［7］李寒，牛紀楨，郭禾.基于特征點的全自動無縫圖像拼接方法［J］.計算機工程與設計，2007，28(9):2 083-2 085.

［8］譚磊，張樺，薛彥斌.一種基于特征點的圖像匹配算法［J］.天津理工大學學報，2006，22(6):66-69.

［9］楊華中，汪蕙.數值計算方法與C語言工程函數庫.北京:科學出版社，1996.

［10］Madsen K，Nielsen H B，Tingleff O.Methods for Nonlinear Least Squares Problems［EB/OL］.http://www2.imm.dtu.dk/pubdb/views/edoc-download.php/3215/pdf/imm3215.pdf，2008.

［11］Lowe D G.Object Recognition from Local Scale-invariant features［A］.International Conference on Computer Vision［C］.Corfu.，Greece，1999:1 150-1 157.

［12］馮海波.虛擬全景空間生成技術研究與實現［D］.成都:電子科技大學，2007.

作者簡介

曹紅杏 女，1976年出生，甘肅臨洮人，在讀研究生。研究方向為圖像拼接。

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文