[發明專利]一種基于模型學習的清潔機器人最優目標路徑規劃方法

有效

• 申請號: 201610171859.8
• 申請日: 2016-03-24
• 公開（公告）號: CN105740644B
• 公開（公告）日: 2018-04-13
• 發明（設計）人: 劉全;周誼成;朱斐
• 申請（專利權）人: 蘇州大學
• 主分類號: G06F19/00
• 分類號: G06F19/00
• 代理公司: 蘇州市新蘇專利事務所有限公司32221
• 代理人: 朱亦倩

技術領域

本發明涉及一種涉及機器學習中的強化學習方法，具體涉及一種基于模型學習的清潔機器人最優目標路徑規劃方法。

背景技術

強化學習(Reinforcement Learning,RL)是一種學習環境狀態到動作映射的機器學習方法。Agent選擇動作作用于環境，改變環境的狀態，遷移到新的環境狀態，并得到環境的反饋信號。這個反饋信號通常稱為獎賞或強化信號，Agent利用它通過一定的算法強化自己已經學習到的經驗，它的目標是最大化累計期望獎賞。

傳統的強化學習方法利用Agent與環境交互得到的信息進行學習，不斷更新值函數使之趨近最優解，例如動態規劃(Dynamic Programming,DP)，蒙特卡洛(Monte Carlo,MC)，和時間差分(Temporal Difference,TD)。這些方法是強化學習的基本方法，許多算法都由它們衍生而來。

模型學習方法的出現使強化學習的算法效率提高了一個臺階，它在近年來已成為強化學習中的一個研究熱點。

模型學習的最初思想(Dyna-Q算法)是將采集到的歷史樣本保存下來，在隨后的更新步驟中，除了更新當前時間步的樣本外，還從歷史樣本中抽取一些樣本進行更新。這樣，樣本的利用率得到增加，提高了值函數收斂的效率。在這樣的思想下之后進一步演化為對模型的構建，即利用當前得到的樣本構建一個環境的模型。在對真實環境的不斷探索中，構建的模型會越來越精確和完整，這個模型就可以代替真實環境被充分地利用，節省與真實環境交互的開銷。

那么，模型學習的效率就取決于模型構建的速度，模型構建得越快，算法從模型中得到的信息就越有價值。顯然，交互獲得的樣本廣度直接影響到模型構建的速度。Dyna-H使用了一種啟發式的規劃方法，通過預測做出動作后到達的下一個狀態與終點之間的歐式距離，來使Agent盡量遠離終點，這樣就可以使Agent在一個情節中盡可能多地探索環境，避免過早到達終點。

然而，Dyna-H算法是有局限性的。在有障礙物的情況下，兩點間的歐式距離并不能很好的反映它們之間的真實距離。可能由于一墻之隔，位于墻一側的Agent可能需要繞一個大彎才能到達墻另一側的終點，而歐式距離則顯示它們離得很近。另外，Dyna-H保留了Dyna-Q中取歷史樣本的方法，而沒有去為環境建立真正的模型。基于此，算法的性能還可以進一步提高。

在模型學習的方法中，R-MAX是一種高效探索的方法，它的核心思想是假設所有未知的狀態-動作所獲得的獎賞為最大獎賞R_max，并轉移到終止狀態。這樣，當選擇值最大的動作時，就會選擇這個未知動作，從而隱式地達到了探索的目的。當狀態-動作對被訪問到m次時，則標記該狀態-動作對為已知，將來不再探索。這樣，所有狀態-動作對都能被快速均勻地探索，從而學習到較為精確的模型。

針對Dyna-H中計算狀態間距離的局限性，本發明采用更為精確的自模擬度量的方法。首先介紹自模擬關系：若兩個狀態滿足自模擬關系，則它們擁有相同的最優值函數和最優動作。Ferns等人在在自模擬關系的基礎之上，利用Kantorovich距離衡量兩個概率分布之間的距離，提出了一種可用于衡量兩個狀態之間遠近關系的自模擬度量方法(Bisimulation Metric)。相比于歐式距離，自模擬度量引入了獎賞函數，狀態轉移函數等要素，能更精確地表示狀態之間的距離。

發明內容

本發明目的是：提供一種基于模型學習的清潔機器人最優目標路徑規劃方法，通過將自模擬度量和R-MAX相結合來改進搜索方式，提高模型學習的效率，從而最終提高值函數的搜索效率，效率的提高使得機器人能夠快速地建立環境模型，從而優先選擇垃圾最多的地點，并計算出達到該地點的最優路徑。

本發明的技術方案是：一種基于模型學習的清潔機器人最優目標路徑規劃方法，其特征在于，包括如下步驟：

步驟1)初始化模型，設置R(x,u)＝R_max，f(x,u,x′)＝1，其中R(x,u)為獎賞函數，f(x,u,x′)為狀態轉移函數，R_max為最大獎賞值，x、u為狀態動作對，x′為執行x、u后轉移到的下一個狀態；

步驟2)初始化環境，設置機器人的起始位置；

步驟3)判斷當前的探索完全度η，若達到閾值I，轉入步驟4)，否則轉入步驟(5)；

步驟4)使用自模擬度量方法，計算當前機器人可做的所有動作所到達的地點與最多垃圾堆的距離，選擇使距離最大的動作，轉入步驟(6)；