基于滾動 Q 學習的機器人路徑規(guī)劃算法

張婷宇　鄭寶娟

摘 要 采用滾動Q學習的方法解決大規(guī)模環(huán)境下機器人視野域范圍有限，同時有效改善因 Q 學習的狀態(tài)空間增大而產(chǎn)生的維數(shù)災難等問題。仿真實驗結果表明，應用該算法機器人可在復雜的未知環(huán)境中快速地規(guī)劃出一條從起點到終點的優(yōu)化避障路徑， 效果令人滿意。

關鍵詞 路徑規(guī)劃 滾動學習 Q學習 智能算法

中圖分類號：TP242文獻標識碼：A

0引言

目前，大多數(shù)自主移動機器人均是在高度結構化的環(huán)境中執(zhí)行預先規(guī)定的動作序列，但在新的環(huán)境下或遇到意外情況時，卻不能很好地完成指定任務，其主要原因是當機器人面對非結構化且存在不確定性的實際環(huán)境時沒有主動學習和自適應的能力。自適應路徑規(guī)劃可以部分解決這一問題，即機器人在與環(huán)境的不斷交互過程中，規(guī)劃出一條從指定的起始點到目標點，并且滿足一定優(yōu)化標準的、安全避障的路徑。該算法是機器人應用研究的一個重要方面，屬于NP-hard問題。針對上述研究現(xiàn)狀及不足，本文提出了滾動Q學習機器人路徑規(guī)劃算法，以滾動學習算法來解決Q學習可能發(fā)生的維數(shù)災難問題。

1基于滾動的 Q 學習算法

算法的基本思想是充分利用機器人實時探測到的局部環(huán)境信息，以滾動方式分別在各個規(guī)模較小的視野域內進行 Q 學習，并得到一條該視野域內的局部最優(yōu)路徑。機器人沿該路徑前進一段距離后 （該距離長度記為 ），在新的視野域內重新獲取動作-狀態(tài)對進行 Q 學習， 并規(guī)劃當前路徑。這樣，在一條條局部最優(yōu)路徑的導航下，機器人最終沿著一條全局優(yōu)化的避碰路徑到達終點。

在視野域內障礙物較少時，機器人走1/3長的局部路徑后才在新的視野域內繼續(xù)規(guī)劃新路徑;在障礙較多時，每走2步再重新規(guī)劃新路徑;只有在障礙物很多時，機器人走1步后即重新規(guī)劃。 的取值很難有一個嚴格的最優(yōu)界定，它只能是根據(jù)實驗結果抽象出比較保守的值，其取值原則是必須能保證各個局部路徑疊加后仍能使全局路徑最優(yōu)或近似最優(yōu)。此外，算法得到的路徑是否近似最優(yōu)，會受到視野域尺寸大小的影響。若將視野域半徑設置過小，則機器人獲得的環(huán)境信息將過于局部化，規(guī)劃過程容易陷入局部最小;若將視野域半徑設置過大，則又使狀態(tài)-動作對大增，降低算法的收斂速度。因此本實驗中對于算法中的視野域半徑參數(shù)是根據(jù)大量實驗的經(jīng)驗來設定的。大量的實驗結果表明，一般視野域半徑范圍取整個工作環(huán)境半徑的 1/10 左右為適。

Step 1：設置起點gstart和終點gend，并初始化工作環(huán)境WS，機器人的視野半徑r，以及保守閾值n1和n2;

Step 2：若機器人在當前視野域內探測到gend，則用新算法規(guī)劃出一條從機器人當前位置到gend的優(yōu)化路徑，規(guī)劃算法終止;

Step 3：產(chǎn)生gsub，機器人以PR為出發(fā)點，gsub為終點，用滾動Q學習算法規(guī)劃出一條局部優(yōu)化路徑，并記錄下該路徑長度local_pathlen;

Step 4：計算Pobstacle、 ，機器人沿局部規(guī)劃路徑行進;

Step 5：根據(jù)機器人當前位置PR和視野半徑r更新視野域，并對視野域內環(huán)境作柵格化處理，轉至Step 2。

2仿真實驗

通過仿真實驗來驗證本文提出算法的有效性和先進性。實驗環(huán)境為 Windows XP， Intel（R） Core（TM）2Duo CPU T6400 2.00 GHz， 2G 內存，編譯工具為VC++6.0。

為了驗證在較大規(guī)模環(huán)境下全局滾動 Q 學習算法的效果，在 50 ？50 的未知環(huán)境下做了大量的實驗，效果令人滿意。以半徑為r = 5的機器人為例，即 實時地進行動態(tài)調整。根據(jù)大量實驗總結的經(jīng)驗，設置 n1= 0.3，n2= 0.7。在第1個視野域內，機器人用滾動算法規(guī)劃出一條局部路徑記為 l1，并計算出 Pobstacle= 0.25 < n1，所以機器人將 設為l1長度的1 /3 （即 = 3）;然后沿l1前進3步后，再根據(jù)新的 視野域重新映射子目標并規(guī)劃路徑，重新計算 ;重復上述過程;直到探測到 gend并規(guī)劃完最后一段路徑為止。

3結論

在未知環(huán)境下采用標準的Q學習算法進行機器人路徑規(guī)劃時，由于缺乏對環(huán)境的先驗知識，使得算法速度緩慢，特別是隨著環(huán)境規(guī)模增大，學習狀態(tài)空間增大，甚至會發(fā)生維數(shù)災難。為此，本文提出了滾動Q學習算法，該算法在未知較大規(guī)模環(huán)境下進行滾動學習，采取這些措施后，大幅提高了算法的收斂速度和環(huán)境適應能力。仿真實驗結果表明該算法的效果令人滿意，具有算法簡單、速度快、環(huán)境適應性強等特點。特別是當機器人對復雜環(huán)境中障礙物信息一無所知以及環(huán)境規(guī)模較大時，更能體現(xiàn)該算法的優(yōu)越性。該算法具有自學習和自適應能力，是一種很有發(fā)展前景的算法。

參考文獻

[1] Ahuh，D，J&J.H.Park.Path planning and navigationfor autonomous mobile robot[C].IEEE 28th the AnnualConf of the Industrial Electronics Society. Seville： IEEEPress，2002：1538-1542.

[2] Vladimiro Miranda， Nuno Fonseca. EPSO-evolutionaryparticle swarm optimization， a new algorithm withapplication in power systems[C]. Transmission andDistributionConf and Exhibition.Yokohama，2002：745-750.

[3] 宋清昆，胡子嬰.基于經(jīng)驗知識的 Q-學習算法[J].自動化技術與應用，2006，25（11）：10-12.