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

張婷宇　鄭寶娟

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

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

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

0引言

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

1基于滾動的 Q 學習算法

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

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

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

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

Step 3：產生gsub，機器人以PR為出發點，gsub為終點，用滾動Q學習算法規劃出一條局部優化路徑，并記錄下該路徑長度local_pathlen;

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

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

2仿真實驗

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

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

3結論

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

參考文獻

[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] 宋清昆，胡子嬰.基于經驗知識的 Q-學習算法[J].自動化技術與應用，2006，25（11）：10-12.