摘 要：機(jī)器人的路徑規(guī)劃一直是機(jī)器人研究領(lǐng)域的難點(diǎn)問題。針對(duì)煤礦井下環(huán)境的不確定性，環(huán)境的復(fù)雜使機(jī)器人很難得到好的規(guī)劃結(jié)果。采用強(qiáng)化學(xué)習(xí)算法中的Q-learning算法實(shí)現(xiàn)井下移動(dòng)機(jī)器人的局部路徑規(guī)劃，并對(duì)Q函數(shù)中的即時(shí)回報(bào)進(jìn)行加權(quán)修正，使算法更有效地利用環(huán)境特征信息，進(jìn)一步提高了避障能力。最后通過(guò)VC++進(jìn)行仿真和模擬。仿真實(shí)驗(yàn)說(shuō)明該方法的有效性和可行性。

關(guān)鍵詞：移動(dòng)機(jī)器人；不確定環(huán)境；強(qiáng)化學(xué)習(xí)；路徑規(guī)劃

中圖分類號(hào)：TP18文獻(xiàn)標(biāo)識(shí)碼：B

文章編號(hào)：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，F(xiàn)ushun，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 引 言

我國(guó)煤礦井下安全事故頻發(fā)，其中由于瓦斯爆炸而引起的煤礦災(zāi)害事故占一半以上，安全一直是制約煤炭開采的關(guān)鍵問題。為了在井下發(fā)生煤礦瓦斯等事故中及時(shí)開展救援工作，研究一種能進(jìn)入危險(xiǎn)礦井進(jìn)行現(xiàn)場(chǎng)環(huán)境檢測(cè)和人員搜救的井下移動(dòng)機(jī)器人是非常必要的。

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

災(zāi)害后的井下環(huán)境是不確定的，路徑規(guī)劃方法一定要有學(xué)習(xí)的能力才能適應(yīng)環(huán)境，提高井下移動(dòng)機(jī)器人的智能性。強(qiáng)化學(xué)習(xí)是一種無(wú)監(jiān)督的在線學(xué)習(xí)方法，由于其不需要知道環(huán)境精確模型，具有實(shí)時(shí)性和自適應(yīng)性，因而適應(yīng)解決井下不確定環(huán)境下的移動(dòng)機(jī)器人路徑規(guī)劃問題。采用強(qiáng)化學(xué)習(xí)算法中的Q-learning算法來(lái)實(shí)現(xiàn)移動(dòng)機(jī)器人在井下不確定環(huán)境下的路徑規(guī)劃，Q-learning算法適應(yīng)不確定性環(huán)境下的學(xué)習(xí)，可以在井下的復(fù)雜多變的環(huán)境下快速有效地實(shí)現(xiàn)路徑規(guī)劃。

2 強(qiáng)化學(xué)習(xí)中Q-learning的算法

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

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

3 基于Q-learning算法的路徑規(guī)劃

為了實(shí)時(shí)而準(zhǔn)確獲得機(jī)器人所處環(huán)境的信息，解決障礙物的避障問題，機(jī)器人必須通過(guò)一定數(shù)量的傳感器來(lái)感知局部環(huán)境。假定機(jī)器人配置有8個(gè)測(cè)距傳感器，傳感器分別探測(cè)8個(gè)不同的方向，這8個(gè)方向平分圓周。根據(jù)移動(dòng)機(jī)器人局部路徑規(guī)劃特點(diǎn)，假定機(jī)器人在任何時(shí)刻都能通過(guò)這些傳感器感知8個(gè)方向上一定距離之內(nèi)是否存在障礙物，可以通過(guò)傳感信息測(cè)定機(jī)器人與障礙物之間的距離，并假定機(jī)器人與障礙物之間的安全距離為D，當(dāng)距離小于D時(shí)，則會(huì)發(fā)生碰撞。

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

Step1：觀察當(dāng)前的環(huán)境狀態(tài)；

Step2：選擇并執(zhí)行一個(gè)動(dòng)作；

Step3：觀察下一個(gè)環(huán)境狀態(tài)；

Step4：收到一個(gè)立即強(qiáng)化信號(hào)；

Setp5：調(diào)整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。

機(jī)器人在井下復(fù)雜環(huán)境中通過(guò)傳感器感知局部環(huán)境信息，做出判斷并執(zhí)行動(dòng)作，環(huán)境給出即時(shí)強(qiáng)化信號(hào)，機(jī)器人根據(jù)強(qiáng)化信號(hào)來(lái)調(diào)整動(dòng)作。當(dāng)機(jī)器人碰撞到障礙物后不返回初始點(diǎn)，在原地尋找其他可行路徑，保證能夠?qū)ふ业侥繕?biāo)點(diǎn)。當(dāng)滿足：到達(dá)目標(biāo)和達(dá)到預(yù)定最大步數(shù)2個(gè)條件中的任何一個(gè)時(shí)，結(jié)束1個(gè)周期的學(xué)習(xí)，如此反復(fù)直到規(guī)劃出最優(yōu)路徑。

4 仿真實(shí)驗(yàn)及結(jié)果分析

在仿真試驗(yàn)中，井下環(huán)境為離散化的柵格，每個(gè)柵格代表機(jī)器人的1種狀態(tài)。黑色區(qū)域?yàn)檎系K物，空白處為巷道。井下移動(dòng)機(jī)器人的任務(wù)是從任何一個(gè)初始位置開始以盡可能少的步數(shù)到達(dá)事故發(fā)生位置，并且不能和障礙物發(fā)生碰撞，做如下假設(shè)：

(1) 移動(dòng)機(jī)器人在二維空間內(nèi)運(yùn)動(dòng);

(2) 機(jī)器人可以通過(guò)傳感器系統(tǒng)探測(cè)周圍一定范圍內(nèi)的井下環(huán)境;

(3) 機(jī)器人把除了目標(biāo)點(diǎn)外所有被觀測(cè)到的對(duì)象當(dāng)作障礙物。

仿真場(chǎng)景如圖1所示，環(huán)境為10×10的柵格，仿真場(chǎng)景中的黑色區(qū)域?yàn)檎系K物，綠色方格為初始點(diǎn)，紅色方格為目標(biāo)點(diǎn)，其每次走過(guò)的軌跡被顯示出來(lái)，每個(gè)柵格對(duì)應(yīng)于機(jī)器人走過(guò)的每一步。環(huán)境中的目標(biāo)是靜態(tài)的，對(duì)于移動(dòng)機(jī)器人而言，環(huán)境(即障礙物、邊界以及目標(biāo)的位置)是不確定的。以機(jī)器人為中心的二維空間內(nèi)平均分布8個(gè)運(yùn)動(dòng)方向，代表它的8個(gè)可選動(dòng)作。

圖1 井下環(huán)境仿真場(chǎng)景圖

對(duì)于機(jī)器人的學(xué)習(xí)系統(tǒng)來(lái)說(shuō)，學(xué)習(xí)的目標(biāo)有2個(gè)：成功避開障礙物，以最少步數(shù)到達(dá)目標(biāo)點(diǎn)。因此機(jī)器人強(qiáng)化信號(hào)包括2個(gè)方面：Rs={-10，10，-100，0}，對(duì)應(yīng)條件為{接近障礙物，遠(yuǎn)離障礙物，與靜態(tài)障礙物碰撞，其他}；Rg={100，0}，對(duì)應(yīng)條件為{到達(dá)目標(biāo)點(diǎn)，漫游尋找目標(biāo)點(diǎn)}。

移動(dòng)機(jī)器人從環(huán)境中獲得的總的強(qiáng)化信號(hào)：R=ωsRs+ωgRg，其中ωs和ωg是機(jī)器人相對(duì)于障礙物和目標(biāo)點(diǎn)回報(bào)的加權(quán)值，0＜ωs＜1，0＜ωg＜1，權(quán)值ωg和ωg的和為1。以上各強(qiáng)化信號(hào)的加權(quán)值的選定，可以根據(jù)環(huán)境中障礙物的相關(guān)性，對(duì)傳感器可感知區(qū)域內(nèi)是否感知到障礙物存在，是否趨向于目標(biāo)點(diǎn)來(lái)賦予不同的權(quán)值，權(quán)值的大小反映移動(dòng)機(jī)器人對(duì)環(huán)境特征的綜合重視程度。

仿真結(jié)果及分析如圖2和圖3所示，可以看出Q-learning算法在不確定環(huán)境下通過(guò)學(xué)習(xí)規(guī)劃出在當(dāng)前無(wú)避碰的最優(yōu)路徑。

圖2 井下路徑規(guī)劃效果仿真圖

成功幕數(shù)(Episode)是指移動(dòng)機(jī)器人從初始位置開始，通過(guò)學(xué)習(xí)成功到達(dá)目標(biāo)點(diǎn)的1個(gè)學(xué)習(xí)周期，成功步數(shù)是指每一幕中機(jī)器人成功學(xué)習(xí)的步數(shù)，成功步數(shù)越少，說(shuō)明機(jī)器人的行動(dòng)策略越來(lái)越優(yōu)，路徑規(guī)劃的效率也越來(lái)越高。隨著學(xué)習(xí)的不斷進(jìn)行，機(jī)器人對(duì)環(huán)境逐漸適應(yīng)，機(jī)器人的行動(dòng)越來(lái)越有效率，避障能力越來(lái)越高，成功幕數(shù)快速增加，每次成功學(xué)習(xí)步數(shù)呈減小趨勢(shì)，最終收斂到一個(gè)固定值，這說(shuō)明此算法學(xué)習(xí)到最優(yōu)路徑，這個(gè)路徑能保證機(jī)器人從初始點(diǎn)任一時(shí)刻出發(fā)都能避開障礙物，并在當(dāng)前環(huán)境下以最少的步數(shù)到達(dá)目標(biāo)點(diǎn)，如圖4所示，當(dāng)井下環(huán)境較復(fù)雜時(shí)，規(guī)劃效果也很好。

圖3 成功步數(shù)收斂曲線圖

圖4 較復(fù)雜環(huán)境下路徑規(guī)劃效果圖

5 結(jié) 語(yǔ)

研究了利用強(qiáng)化學(xué)習(xí)算法解決井下移動(dòng)機(jī)器人局部路徑規(guī)劃問題，采用強(qiáng)化學(xué)習(xí)中Q-learning算法實(shí)現(xiàn)井下移動(dòng)機(jī)器人的局部路徑規(guī)劃。利用Q-learning算法的實(shí)時(shí)性和自適應(yīng)性適合局部路徑規(guī)劃的特點(diǎn)，在不確定環(huán)境下的實(shí)現(xiàn)快速有效規(guī)劃，而且當(dāng)井下環(huán)境變得復(fù)雜時(shí)，該算法的路徑規(guī)劃效果也很好，仿真試驗(yàn)說(shuō)明該方法的有效性和可行性。下一步的主要工作是如何結(jié)合實(shí)際進(jìn)一步提高學(xué)習(xí)的效率和收斂速度，并運(yùn)用到實(shí)際機(jī)器人系統(tǒng)中。

參考文獻(xiàn)

［1］戴博，肖曉明，蔡自興.移動(dòng)機(jī)器人路徑規(guī)劃技術(shù)的研究現(xiàn)狀與展望.控制工程，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］蔡自興，賀漢根，陳虹.未知環(huán)境中移動(dòng)機(jī)器人導(dǎo)航控制研究若干問題.控制與決策，2002，17(4):386-390.

［5］石鴻雁，孫茂相，孫昌志.未知環(huán)境下移動(dòng)機(jī)器人路徑規(guī)劃方法.沈陽(yáng)工業(yè)大學(xué)學(xué)報(bào)，2005，27(1):63-69.

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

［7］樸松昊，洪炳熔.一種動(dòng)態(tài)環(huán)境下移動(dòng)機(jī)器人的路徑規(guī)劃方法.機(jī)器人，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.

作者簡(jiǎn)介

王 帥 男，1979年出生，遼寧西豐人，工學(xué)碩士。研究方向?yàn)橹悄芸刂婆c機(jī)器學(xué)習(xí)。

(上接第101頁(yè))

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

［7］李寒，牛紀(jì)楨，郭禾.基于特征點(diǎn)的全自動(dòng)無(wú)縫圖像拼接方法［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2007，28(9):2 083-2 085.

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

［9］楊華中，汪蕙.數(shù)值計(jì)算方法與C語(yǔ)言工程函數(shù)庫(kù).北京:科學(xué)出版社，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］馮海波.虛擬全景空間生成技術(shù)研究與實(shí)現(xiàn)［D］.成都:電子科技大學(xué)，2007.

作者簡(jiǎn)介

曹紅杏 女，1976年出生，甘肅臨洮人，在讀研究生。研究方向?yàn)閳D像拼接。

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文