基于Q（λ）-learning的移動機器人路徑規劃改進探索方法

王 健，趙亞川，趙忠英 ，張平陸

（1.沈陽新松機器人自動化股份有限公司 特種機器人BG，沈陽 110169.2.沈陽科技學院 機械與交通工程系，沈陽 110167）

路徑規劃是移動機器人導航的重要組成部分，其目標是在復雜環境下能夠尋找一條從起點到終點的無碰撞路徑。路徑規劃的優劣直接影響移動機器人的運動效率、機器損耗和工作效率。基于強化學習的智能移動機器人的導航和避障正在成為一個重要的研究方向。與其它機器學習方法不同，增強學習方法無需監督信號，通過智能體與環境之間的信息交互進行“試錯”，以極大化評價反饋信號為目標，通過學習得到最優或次優的搜索策略。

目前強化學習已經引起國內外機器學習領域學者的廣泛關注。文獻[1]所提出的基于獎賞的強化學習方法具有較快的收斂速度；文獻[2]深入研究基于BP神經網絡的Q-learning，實現移動機器人環境下的自主導航；文獻[3]將強化學習方法用于機器人的任務規劃和調度；文獻[4]以神經網絡擬合Q-learning中的Q函數，再用經驗回放和目標網絡方法改善Q-learning收斂穩定性；文獻[5]基于模糊邏輯的路徑規劃方法，利用狀態空間與動作空間映射關系，解決了人工勢場法容易陷入局部極小問題。

強化學習在未知環境下求解具有較少先驗信息的問題具有巨大優勢，是目前機器學習中富有挑戰性和廣泛應用前景的研究領域之一[6-8]。

在移動機器人路徑規劃相關應用中，傳統的基于Q（λ）-learning探索方法存在由于探索不平衡致使無法找到最優解的問題。故在此通過改進探索方法，提出基于成功率動態調整探索因子的探索方法。

1 基于Q（λ）-learning的改進探索方法

Q-learning 是以狀態-動作對應的 Q（s，a）為估計函數，逐漸減小相鄰狀態間Q值估計的差異達到收斂條件。更新公式為

引入跡的思想，其更新公式為

誤差項為

更新動作公式為

解決探索利用平衡問題常用的方法是ε-貪心策略。這種方法探索環境時，隨著訓練時間的增加而減小探索因子。搜索函數為

式中：σ為0～1之間的隨機數；ε為探索因子，為0～1之間的數。傳統調整探索因子的方法過多利用環境快速收斂到對應解，但由于探索不夠充分，往往很難得到最優解。在此，采用基于成功率的方法動態調整探索因子ε，適時的鼓勵探索，使移動機器人對環境探索的更加完全，找到更多解，從而找到最優解。其算法流程如圖1所示。

隨著訓練次數的增加，移動機器人找到目標路徑成功率逐漸增加，此時判斷路徑解數量。當低于最少路徑解數量時，增大探索因子，以尋找更多解；當高于最多路徑解時，說明移動機器人對環境熟悉程度已經很高，此時逐漸降低探索因子，直至降為0。

圖1 動態調整探索因子算法流程Fig.1 Dynamic exploring factor algorithm flow chart

基于Q（λ）-learning的改進探索方法，具體實現步驟如下：

步驟1 初始化，并獲取當前狀態s；

步驟2 進行第i次迭代計算，最大迭代次數為n，根據圖1所示流程更新探索因子ε；

步驟3 生成隨機數σ，執行搜索策略π（s），如式（5）所示；

步驟4 執行動作a，得到獎勵r，轉移到新狀態 s′；

步驟5 根據s′是否為目標狀態更新成功率Suc，并根據路徑解是否為新解，更新路徑解數量Path；

步驟6 判斷s′是否為終止狀態，如果是則跳到步驟2進行下一次迭代（i=i+1），如果不是則跳到步驟7；

步驟7 根據式（3），計算誤差；

步驟8 根據式（2），更新動作狀態跡，并更新其他動作狀態跡；

步驟9 根據式（4），更新動作值函數；

步驟10 s←s′，跳到步驟3搜索下一個狀態。

2 仿真試驗與結果分析

通過仿真試驗來驗證改進探索方法的有效性。試驗環境采用10×10柵格地圖，如圖2所示。由圖可見，以圖左上角為移動機器人起點，右下角為目標，移動機器人無法穿越黑色柵格障礙物。

圖2 10×10柵格地圖Fig.2 10×10 grid map

移動機器人動作集A包括上移、下移、左移、右移4個動作。狀態集用1～100表示，障礙物和目標狀態為終止狀態。當移動機器人移動到終止狀態，本次訓練循環結束，重新進行下一次訓練。

將本文方法與典型的ε-decreasing探索方法進行仿真對比試驗，驗證該方法的有效性。ε-decreasing探索方法采用式（6）更新探索因子，即

式中：Vinit為探索因子初始值；i為迭代學習次數；S為步長。

Q（λ）-learning算法中幾個重要的參數會直接影響收斂速度。仿真試驗中，折扣因子γ初始化為0.8，學習速率α初始化為0.05。在此，探索因子ε初始化為0.5，ε-decreasing方法初始化為1，最大探索步數初始化為100。當搜索步數超過最大步數時，仍未到達終止狀態，則認為此次訓練失敗，重新進入下一次訓練。

獎勵函數設置：當移動機器人到達目標狀態時獎勵1，當碰到障礙物得到-1的懲罰，到達其余狀態時得到-0.05的懲罰，用于加快向目標狀態移動。

ε-decreasing方法收斂曲線如圖3所示，約在訓練13000次時收斂；基于成功率搜索方法收斂曲線如圖4所示，約在訓練32000次時收斂。兩者收斂時間差別較大，是因為當ε-decreasing搜索方法找到一條最優策略時，有很大的幾率不去試探新的最優策略，很快地達到收斂狀態，本文方法會根據最優解的搜索情況適當增大探索因子，犧牲收斂時間來尋找更多最優解。

圖3 ε-decreasing方法收斂曲線Fig.3 Convergence curve based onε-decreasing search method

圖4 基于成功率搜索方法收斂曲線Fig.4 Convergence curve based on success rate search method

2種搜索方法訓練完成的最優策略分別如圖5和圖6所示。由圖5可見，ε-decreasing搜索策略中，一些狀態并未得到最優解（陰影表示），以圖5中狀態83和87為例，最優解應分別為向右和向下，由于訓練過程中隨著探索因子不斷減小，不再進行新的探索，因此并未得到最優解。由圖6可見，基于成功率的搜索策略，完全接近于最優策略。

圖5 基于ε-decreasing方法收斂策略Fig.5 Search strategy based onε-decreasing method

圖6 基于成功率搜索方法收斂策略Fig.6 Search strategy based on success rate search method

統計移動機器人在地圖所有狀態下到達目標狀態的平均步數見表1。其中，2號～5號試驗為使用同樣的方法，另外生成的4個障礙物分布不同的柵格地圖，采用同樣的參數完成訓練。

表1 平均步數的對比Tab.1 Comparison of average step

移動機器人移動的平均步數越少，說明策略越優。由表1可知，本文搜索策略在4次試驗中，平均步數均明顯低于ε-decreasing策略。

3 結語

本文提出了一種基于成功率的探索方法，采用Q（λ）-learning算法對移動機器人進行路徑規劃，引入成功率的改進搜索方法，解決了強化學習中存在的探索利用平衡問題。最后通過仿真實驗將改進搜索方法與經典ε-decreasing搜索方法作對比，驗證了該方法的有效性。