[發明專利]基于Q-學習算法的路徑規劃方法

有效

• 申請號: 201810180843.2
• 申請日: 2018-03-06
• 公開（公告）號: CN108594803B
• 公開（公告）日: 2020-06-12
• 發明（設計）人: 千承輝;馬天錄;劉凱;張宇軒
• 申請（專利權）人: 吉林大學
• 主分類號: G05D1/02
• 分類號: G05D1/02
• 代理公司: 長春市恒譽專利代理事務所(普通合伙) 22212
• 代理人: 鞠傳龍

本發明公開了一種基于Q?學習算法的路徑規劃方法，其方法為：第一步：獲得基本信息；第二步：確定圖中的障礙物坐標；第三步：對圖形進行分割處理；第四步：利用改進Q?學習算法規劃路徑；第五步：得出最優路徑，根據學習結果用MATLAB繪制出最優的路徑；第六步：控制機器人行走驗證，根據學習的結果，電腦控制機器人行走對路徑進行驗證。有益效果：在柵格環境下進行仿真實驗，并成功地應用在多障礙物環境下移動機器人路徑規劃，結果證明了算法的可行性。改進Q?learning算法可以以更快的速度收斂、學習次數明顯減少、效率最大可提高20％。同時該算法框架對解決同類問題具有較強的通用性。

技術領域

本發明涉及一種路徑規劃方法，特別涉及一種基于Q-學習算法的路徑規劃方法。

背景技術

目前，強化學習中的一個重要里程碑就是Q-學習算法，Q-學習是由Watkins[1]在1989年提出的類似于動態規劃算法的一種最具有代表性的強化學習方法，它提供智能系統在馬爾可夫環境中利用經歷的動作序列選擇最優動作的一種學習能力，并且不需要建立環境模型。Q-學習算法實際上是馬爾可夫決策過程的一種變化形式，是目前最易理解和廣為使用的強化學習方法，采用增量的方式進行學習。自Watkins提出Q-學習算法并證明其收斂性，該算法在人工智能體及機器學習領域受到了普遍關注。

學習Q函數對應于學習最優策略。Q函數怎樣才能被學習到呢？

關鍵在于要找到一個可靠的方法，只在時間軸上展開的立即回報序列的基礎上估計訓練值。這可通過迭代逼近的方法完成。

Q(s，a)＝r(s，a)+γmaxQ(δ(s，a)，a′) (1)

這個Q函數的遞歸定義提供了迭代逼近Q算法的基礎。其中，r(s，a)為狀態-動作對s,a的獎勵值，γ∈(0，1)稱為折算因子，max為求最大值函數，δ(s，a)函數可以由前狀態-動作對s,a求得下一狀態s′，a′為下一動作。為描述此算法，將使用符號來指代學習器對實際Q函數的估計，或者說假設。在此算法中學習器通過一個大表表示其假設其中對每個狀態－動作對有一表項。狀態－動作對s,a的表項中存儲了的值，即學習器對實際的但未知的Q(s，a)值的當前假設。此表可被初始為隨機值。智能體重復地觀察其當前的狀態s，選擇某動作a，執行此動作，然后觀察結果回報r(s,a)以及新狀態s′＝δ(s，a)。然后智能體遵循每個這樣的轉換更新的表項，按照公式2的規則：

其中，r(s，a)為狀態-動作對s,a的獎勵值，γ∈(0，1)稱為折算因子，max為求最大值函數，s′為下一狀態，a′為下一動作。此訓練法使用智能體對新狀態s′的當前值來精化其對前一狀態s的估計。上述是對于確定性馬爾可夫決策過程的Q-學習算法的描述。使用此算法，智能體估計的在極限時收斂到實際Q函數，只要系統可被建模為一個確定性馬爾可夫決策過程，回報函數r有界，并且動作的選擇可使每個狀態－動作對被無限頻繁的訪問。

強化學習算法中的Q-學習算法是環境未知條件下的有效強化學習算法，由于易于理解而被廣泛使用。由于Q-學習的迭代就是一個試錯和探索(trial-and-error)的過程，其收斂的一個條件就是要求智能體對每個可能的狀態動作對都多次(無窮次)嘗試，只有這樣該智能體才能最終學到最優的控制策略，通過公式2我們知道，Q函數在更新的過程中，使用智能體對新狀態s′的當前值來精化其對前一狀態s的估計，當Q函數元素較多時，學習次數會大幅度增加。如何結合其它方法提高Q-學習算法在智能體系統中的學習速度是本課題研究的一個最重要的問題。

同時，查閱大量的論文我們發現，有關Q-學習算法的探索大多停留在仿真上，缺少與實際問題結合。

發明內容

本發明的目的是為了解決在多障礙物環境下機器人的尋路問題而提供的一種基于Q-學習算法的路徑規劃方法。

本發明提供的基于Q-學習算法的路徑規劃方法，其方法如下所述：