[發明專利]基于因果圖的分層強化學習任務圖進化方法

無效

• 申請號: 201110369847.3
• 申請日: 2011-11-18
• 公開（公告）號: CN102521203A
• 公開（公告）日: 2012-06-27
• 發明（設計）人: 王紅兵;周建才
• 申請（專利權）人: 東南大學
• 主分類號: G06F15/18
• 分類號: G06F15/18;G06N3/12
• 代理公司: 南京天翼專利代理有限責任公司 32112
• 代理人: 朱戈勝

技術領域

本發明涉及利用計算機對分層強化學習的任務圖進行優化的方法。

技術背景

分層強化學習是解決強化學習維數災難問題的一種重要方法。目前分層強化學習中三種典型的方法分別是Sutton提出的Option、Parr提出的HAM和Dietterich提出的MAXQ。分層強化學習的一個重要問題是分層任務圖需要由設計者根據專家知識事先給定。由于手工構造分層強化學習的層次結構需要具備相關的專家知識，不能滿足動態未知環境的需要，于是如何自動發現并構造任務的層次結構成為分層強化學習的一個重大問題。而目前很多HRL自動分層方法都針對Option方法的，但是Option在利用先驗知識劃分子任務時任務的劃分結果表達不夠清晰且子任務內部策略難以確定。早期的關于HRL的自動分層研究主要針對Option方法，主要從發現路標狀態、共用子空間、狀態的特征向量和使子空間具有良好的Markov性質出發。這些自動分層方法總體上存在著對狀態空間的特性依賴過強的問題。由于MAXQ方法能很好的利用先驗知識并具有很強的在線學習能力，故而基于MAXQ分層強化學習方法的自動分層方法研究具有重要的意義。

目前，關于MAXQ自動分層方法主要有HI-MAT方法，但是HI-MAT得到的任務圖依賴于觀察到的一條成功路徑，從而得到任務圖結構空間中和這條軌跡一致的任務圖，這樣容易陷入局部最優。

發明內容

本發明提供了一種對HI-MAT分層強化學習任務圖自動構造方法構造出的任務圖的進行改進的方法。該方法得到的任務圖的學習速度可以和依靠專家知識構造出的任務圖一樣快，并在系統復雜時可以超過手工構造的任務圖。而且本方面所設計的改進算法可以適應環境動態變化的情況。

為實現上述目的，本發明提供一種基于因果圖的分層強化學習任務圖進化方法。在對本方法具體步驟進行描述之前，首先給出相關定義：

(a)因果圖：頂點集合為狀態變量集合和獎賞結點，邊集合為動作的作用下狀態變量之間的依賴關系，兩個狀態變量i、j之間有有向邊當且僅當存在一個動作a且它的DBN中i、j存在之間存在有向邊。

(b)強連通組件：由一個或者多個通過有向路徑可互達的狀態變量組成的集合V_c。引入強連通組件可對因果圖進行去環。

(c)組件圖：由強連通組件作為節點組成的有向圖，節點之間有邊當且僅當因果途中存在第一個節點組件中的某個狀態變量到第二個節點組件中的某個狀態變量在因果圖中有邊。組件圖是去環后的因果圖。

(d)狀態變量V的依賴狀態變量集由其所在強連通組件中的其它狀態變量和組件圖中有到此強連通組件的邊的組件所含狀態變量組成。

(e)任務(task)T_i＝(X_i，G_i，C_i)，其中X_i為T_i值函數的相關變量，G_i為目標或終止謂詞，C_i為子任務集合。

(f)任務結點之間保持因果依賴性是指父任務結點T_i的X_i中存在狀態變量其依賴狀態變量集V_di中含有子任務結點T_j的X_j中的狀態變量。即對父任務結點T_i和其任意子任務結點T_j，∃(Vi≡Xi)Λ(Vj∈Xj)Λ(Vj∈Vdi).]]>