動態(tài)不確定環(huán)境下一種移動 機器人路徑規(guī)劃方法

王 帥

（煤炭科學(xué)研究總院沈陽研究院，遼寧 撫順 113001）

1 引言

動態(tài)不確定環(huán)境下的路徑規(guī)劃是移動機器人研究的一個重要問題，一直是一個沒能妥善解決的難題。所謂動態(tài)不確定環(huán)境，是指移動機器人只能通過傳感器探測其周圍有限范圍內(nèi)的環(huán)境信息，或者雖然有前驗的全局環(huán)境信息，但環(huán)境中的障礙物是動態(tài)變化的。在這種不確定環(huán)境下，移動機器人的路徑規(guī)劃大都采用局部路徑規(guī)劃方法，又稱動態(tài)或在線路徑規(guī)劃。

局部路徑規(guī)劃方法主要有：人工勢場法[1]、遺傳算法[2]和模糊邏輯算法[3]等。人工勢場法結(jié)構(gòu)簡單，存在局部極小值問題和抖動問題。遺傳算法使用點群進行尋優(yōu)，在種群數(shù)目有限，計算量不大的情況下可以滿足實時性的要求。模糊邏輯算法的實時性很好，但是人的經(jīng)驗不一定完備，當(dāng)輸入量增多時，推理規(guī)則或模糊表會急劇膨脹。此外還有適用于環(huán)境信息完全未知時的滾動窗口法[4]，有效地解決了動態(tài)障礙物環(huán)境下的機器人運動過程中的避障問題，該方法對障礙物的大小和形狀有一定限制。

環(huán)境是動態(tài)變化的，路徑規(guī)劃方法一定要有學(xué)習(xí)的能力才能適應(yīng)環(huán)境變化，提高移動機器人的自適應(yīng)性和智能性。強化學(xué)習(xí)[5]是一種無監(jiān)督的在線學(xué)習(xí)方法，由于其不需要知道環(huán)境精確模型，具有實時性和自適應(yīng)性，因而適應(yīng)解決動態(tài)環(huán)境下的移動機器人路徑規(guī)劃問題。采用強化學(xué)習(xí)算法中的Sarsa學(xué)習(xí)算法來實現(xiàn)移動機器人在動態(tài)未知環(huán)境下的路徑規(guī)劃。Sarsa算法適應(yīng)動態(tài)環(huán)境下的學(xué)習(xí)，但其學(xué)習(xí)速度較慢，基于上述考慮，在Sarsa算法的基礎(chǔ)上，引入信度分配函數(shù)，提出了信度分配Sarsa算法（Credit Assignment Sarsa，CAS），提高算法的學(xué)習(xí)速度和自適應(yīng)能力，可以在動態(tài)不確定環(huán)境下快速有效地實現(xiàn)路徑規(guī)劃。

2 信度分配Sarsa(CAS)學(xué)習(xí)算法

2.1 Sarsa學(xué)習(xí)算法

Sarsa算法是Rummery和Niranjan在1994年提出的[6]，最初被稱為改進的Q-learning算法，它仍然采用Q值迭代，Sarsa算法通過反復(fù)的實驗去學(xué)習(xí)狀態(tài)動作對的值函數(shù)，一步Sarsa算法可用下式表示

Sarsa與Q-learning的最大差別在于Q-learning采用的是值函數(shù)的最大值進行迭代，而Sarsa采用的是實際的Q值進行迭代，此外，Sarsa學(xué)習(xí)在每個學(xué)習(xí)步，智能體依據(jù)當(dāng)前Q值確定下一狀態(tài)時的動作，而Q-learning依據(jù)修改后的Q值確定動作，因此Sarsa是一種在策略TD學(xué)習(xí)。

2.2 信度分配Sarsa(CAS)學(xué)習(xí)算法

為了提高智能體強化學(xué)習(xí)的效率和速度，在Sarsa算法中引入信度分配函數(shù)[7]，信度分配函用來在各行動規(guī)則之間分配報酬，在此算法中，在智能體每次學(xué)習(xí)中把強化信號分配到為達到某些狀態(tài)所采取的每一步行動上，根據(jù)到目標(biāo)的距離不同，而分配不同的報酬，信度分配函數(shù)的原理如圖1所示。

圖1 信度分配函數(shù)示意圖

引入信度分配函數(shù)后的Sarsa算法（CAS）的Q值更新規(guī)則如下：

當(dāng)智能體在某一時間段T內(nèi)經(jīng)歷多步動作后，智能體獲得強化信號為R，通過下式來重新修改Q值表：

可以保證此學(xué)習(xí)算法的收斂。

3 基于CAS學(xué)習(xí)算法的路徑規(guī)劃

采用CAS算法實現(xiàn)在動態(tài)環(huán)境下的移動機器人路徑規(guī)劃。強化信號是對學(xué)習(xí)系統(tǒng)性能的一種評價，用于改善系統(tǒng)的性能。在動態(tài)環(huán)境下的路徑規(guī)劃的學(xué)習(xí)中，其目的就是使移動機器人避開動靜態(tài)障礙物，并以盡可能少的步數(shù)到達目標(biāo)點。CAS算法的核心就是利用Sarsa算法適應(yīng)動態(tài)環(huán)境下學(xué)習(xí)的特性，并引入信度分配函數(shù)把強化信號分配給機器人為達到某些狀態(tài)所采取的每一步行動上，根據(jù)到目標(biāo)的距離不同分配不同的強化信號，來修改Q值，進而修改動作選擇策略，實現(xiàn)路徑規(guī)劃。將移動機器人的行為分為4種：到達目標(biāo)點，漫游尋找目標(biāo)點，動態(tài)障礙物避障，靜態(tài)障礙物避障。在學(xué)習(xí)過程中，考慮動作對這4種行為的影響，使這4種行為互相協(xié)調(diào)融合。

3.1 學(xué)習(xí)系統(tǒng)對環(huán)境的感知

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

3.2 學(xué)習(xí)系統(tǒng)的狀態(tài)空間和動作空間

環(huán)境狀態(tài)用動態(tài)環(huán)境中各物體的位置坐標(biāo)、速度大小和運動方向等參數(shù)來描述。這里機器人所處環(huán)境的狀態(tài)空間可以表示為S={sid ，ad，av，aθ}。

機器人的動作空間為在傳感器所指的8個方向上{N，S，W，E，NE，SE，NW，SW}前進一定的距離。

3.3 基于CAS學(xué)習(xí)算法的路徑規(guī)劃算法流程

step1：任意初始化 (,)Qsa；

step2：初始化環(huán)境狀態(tài)s；

step3：獲得此時環(huán)境狀態(tài) ts；

step4：根據(jù)Q值表和貪婪策略，獲得機器人在ts時的動作 ta；

step5：執(zhí)行動作 ta，獲得下一個狀態(tài) 1ts+；

step6：根據(jù)Q值表和貪婪策略，選擇動作 1ta+；

step8：收到強化信號R，按時間信度分配策略分配強化信號 (,)fRt，重新更新Q值表：

①如果步數(shù)過界，總步數(shù)加1，回到初始位置，轉(zhuǎn)step9；②如果到達目標(biāo)點，回到初始位置，成功幕數(shù)加1，總步數(shù)加1，轉(zhuǎn)step9，否則轉(zhuǎn)step2。

step9：如果學(xué)習(xí)滿足預(yù)定的結(jié)束條件，學(xué)習(xí)結(jié)束，否則轉(zhuǎn)step2。

機器人在動態(tài)未知環(huán)境中通過傳感器感知局部環(huán)境信息，做出判斷并執(zhí)行動作，環(huán)境給出即時強化信號，機器人根據(jù)強化信號來調(diào)整動作。在每個時間段，信度分配函數(shù)重新分配獎懲的強化信號給這一時間段內(nèi)所采取的每一步行動上，因為這每一步動作都對最終結(jié)果的產(chǎn)生負有責(zé)任。當(dāng)機器人碰撞到障礙物后不返回初始點，在原地尋找其他可行路徑，保證能夠?qū)ふ业侥繕?biāo)點。一個學(xué)習(xí)周期是由若干個學(xué)習(xí)步驟組成的序列，當(dāng)滿足：①到達目標(biāo)②達到預(yù)定最大步數(shù)兩個條件中的任何一個時，結(jié)束一個周期的學(xué)習(xí)，如此反復(fù)直到規(guī)劃出最優(yōu)路徑。

4 仿真實驗及結(jié)果分析

在仿真試驗中，移動機器人工作空間為離散化的柵格，每個柵格代表機器人的一種狀態(tài)。在其中設(shè)置靜態(tài)和動態(tài)的障礙物。系統(tǒng)的任務(wù)是從任何一個初始位置開始以盡可能少的步數(shù)到達目標(biāo)位置，并且不能和動靜態(tài)的障礙物發(fā)生碰撞，做如下假設(shè)：

（1）移動機器人在二維空間內(nèi)運動。

（2）機器人可以通過傳感器系統(tǒng)探測周圍一定范圍內(nèi)的環(huán)境。

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

（4）機器人事先不知道動態(tài)障礙物的運動特性。

仿真場景如圖2所示，環(huán)境為20×20的柵格。仿真場景中的黑色區(qū)域為靜態(tài)障礙物，其中十字型黑色區(qū)域為動態(tài)隨機運動的障礙物，其在一定區(qū)域內(nèi)在前后左右4個方向上隨機運動，速度恒定且小于機器人運動速度，即環(huán)境是動態(tài)的。S點為初始點，G為目標(biāo)點，其每次走過的軌跡被顯示出來，每個柵格對應(yīng)于機器人走過的每一步。環(huán)境中的目標(biāo)是靜態(tài)的，對于移動機器人而言，環(huán)境（即障礙物、邊界以及目標(biāo)的位置）是未知的。以機器人為中心的二維空間內(nèi)平均分布8個運動方向，代表它的8個可選動作。

圖2 仿真場景

對于機器人的學(xué)習(xí)系統(tǒng)來說，學(xué)習(xí)的目標(biāo)有3個：成功避開靜態(tài)障礙物，成功避開動態(tài)障礙物，以最少步數(shù)到達目標(biāo)點。因此機器人強化信號包括三個方面：sR={-10,20,-100,0}，對應(yīng)條件為{接近靜態(tài)障礙物，遠離靜態(tài)障礙物，與靜態(tài)障礙物碰撞，其他}；gR={100,0}，對應(yīng)條件為{到達目標(biāo)點，漫游尋找目標(biāo)點}；aR={-10,20,-100,0}，對應(yīng)條件為{接近動態(tài)障礙物，遠離動態(tài)障礙物，與動態(tài)障礙物碰撞，其他}。

在仿真中取α=0.01，γ=0.95，β=0.4，K=2。仿真結(jié)果如圖3和4示，可以看出Sarsa算法和CAS算法在動態(tài)環(huán)境下都能學(xué)習(xí)到無避碰的成功步數(shù)最少的路徑，Sarsa算法的學(xué)習(xí)速度較慢，而CAS算法學(xué)習(xí)速度明顯優(yōu)于Sarsa算法的學(xué)習(xí)速度。成功步數(shù)最后在23步和24步兩個值之間交替變化，這體現(xiàn)出動態(tài)障礙物對學(xué)習(xí)算法的影響。如果環(huán)境是靜態(tài)的，最優(yōu)步數(shù)應(yīng)是23步，由于動態(tài)障礙物的隨機運動，其在某一時刻會阻擋機器人沿著23步最短路徑移動，此時機器人就會尋找到其他的無碰撞的最短路徑，這就是步數(shù)為24步的路徑，這條路徑也是當(dāng)前環(huán)境狀態(tài)下最優(yōu)的，隨著環(huán)境的不同可選擇的其他路徑數(shù)目也會不同。

圖3 Sarsa算法成功步數(shù)曲線

圖4 CAS算法成功步數(shù)曲線

成功幕數(shù)(episode)是指移動機器人從初始位置開始，通過學(xué)習(xí)成功到達目標(biāo)點的一個學(xué)習(xí)周期，成功步數(shù)是指每一幕中機器人成功學(xué)習(xí)的步數(shù)，成功步數(shù)越少，說明機器人的行動策略越來越優(yōu)，路徑規(guī)劃的效率也越來越高。隨著學(xué)習(xí)的不斷進行，機器人對動態(tài)環(huán)境逐漸適應(yīng)，機器人的行動越來越有效率，避障能力越來越高，成功幕數(shù)快速增加，每次成功學(xué)習(xí)步數(shù)呈減小趨勢，最終學(xué)習(xí)到最優(yōu)路徑，這個路徑能保證機器人從初始點任一時刻出發(fā)都能避開動靜態(tài)的障礙物，并在當(dāng)前環(huán)境下以最少的步數(shù)到達目標(biāo)點。大量仿真實驗都表明，當(dāng)環(huán)境變得較為復(fù)雜時，CAS算法的規(guī)劃效果也很好，這說明算法的自適應(yīng)性較強。

5 結(jié)論

本文提出了一種基于信度分配的Sarsa學(xué)習(xí)算法。通過信度分配函數(shù)的引入來有效分配強化信號，進而修正動作選擇策略，有效地提高了Sarsa算法的學(xué)習(xí)效率和速度，節(jié)省了學(xué)習(xí)時間，實現(xiàn)了在動態(tài)不確定環(huán)境下的移動機器人路徑規(guī)劃，仿真試驗說明該方法的有效性和可行性。接下來的主要工作是如何在環(huán)境特別復(fù)雜、路徑規(guī)劃的學(xué)習(xí)空間很大情況下，有效提高算法的學(xué)習(xí)效率和收斂速度。

[1] Khatib O.Real-time obstacle avoidance for manipulators and mobile robot [J].The International Journal of Robotic Research,1986,5(1)：90-98.

[2] M Gemeinder,M Gerke.GA-based Path Planning for Robot System Employing an Active Search Algorithm [J].Applied Soft Computing,2003(3)：149-158.

[3] 莊曉東,孟慶春,殷波等.動態(tài)環(huán)境中基于模糊概念的機器人路徑搜索方法[J].機器人,2001,23(5)：397-399.

[4] 張純剛,席裕庚.動態(tài)未知環(huán)境中移動機器人的滾動路徑規(guī)劃及安全性分析[J].控制理論與應(yīng)用,2003,20 (1)：37-44.

[5] Sutton R S,Barto A G.Reinforcement Learning：An Introduction [M].Cambridge,MA：MIT Press,1998.

[6] Rummery G,Niranjan M.On-line Q-learning using connectionist system.Technical Report CUED/FINFENG/ T-R166,Cambridge University EngineerIng Department,1994.

[7] 吳繼偉,蕭蘊詩,許維勝.基于信度分配的Agent強化學(xué)習(xí)算法[J].同濟大學(xué)學(xué)報,2003,31(8)：947-950.

[8] Miyazaki K,Yamamura M,Kobayashi S.On the rationality of profit sharing in reinforcement learning [A].Proc of the 3rd International Conference on Fuzzy Logic Neural Net and Soft computing,1994：285-288.