階層式解問題中的問題切割和狀態抽象化

Problem Decomposition and State Abstraction in Hierarchical Problem Solving

邱中鎮(Chung-Cheng Chiu)

指導教授 ： 蘇豐文

國立清華大學/電機資訊學院/資訊工程學系/碩士(2007年)

https://doi.org/10.6843/NTHU.2007.00563

摘要

這個研究的目的是要針對解問題的方法上，提出演算法將原有的問題做切割並做狀態抽象化以降低問題的複雜度。在維度降低的空間中，解問題的方法能夠花費更少的計算量來求出問題的解法。將問題做切割並降低維度，建出階層式架構以增進解問題的效率是一種常被採用的方法，而過去主要的研究多仰賴設計者手動執行這些分析。一些研究提出自動辨認的方法，但缺乏針對切割的問題做狀態抽象化的程序，原有複雜度並未被降低。這篇研究基於針對拉普拉斯圖的光譜分析提出新的問題切割演算法，並在切割過的子問題上分析參數相關度來施行狀態抽象化。每個子問題保留與解決該子目標相關的參數，再透過特徵比對方式將相同子問題合併。原有的完整問題被轉換成多個子問題的組合，在這維度降低的空間中求解將更有效率。其對解問題方法的幫助將在後面的實驗展示。

關鍵字

馬可夫決策過程 ； 增強式學習 ； 階層式增強式學習 ； 圖光譜分析

並列摘要

The purpose of this work is to propose an algorithm to decompose the problem and perform state abstraction to reduce the complexity of problem solving. In dimension-reduced state space, the computational cost for problem solving is lessened. Decomposing the problem and reducing its dimension to construct hierarchy structure is one of approach applied in problem solving, and it requires manual construction. Some previous works proposed for automatically subproblems identification, but with the lack of state abstraction, the complexity is not reduced. We propose an algorithm based on spectral analysis on graph Laplacian to decompose the problem and perform parameter relativity analysis to provide state abstraction. In each decomposed subproblem, only parameters in projected state space related to its subgoal are reserved, and identical subproblems are integrated into one through features comparison. The whole problem is transformed into a combination of projected subproblems, and problem solving in this space is more efficient. The paper demonstrates its improvement on problem solving experimentally.

並列關鍵字

Markov Decision Processes ； Reinforcement Learning ； Hierarchical Reinforcement Learning ； Spectral Graph Theory

參考文獻

Simulation of Adaptive Behavior. MIT Press.

Ahuja, R. K., Magnanti, T. L. and Orlin, J.B. (1993). Network Flows: Theory, Algorithms, and Applications. Prentice Hall.

Belkin, M. and Niyogi, P. (2004). Semi-supervised learning on Riemannian manifolds. Machine Learning, 56, 209-239.

Chung, F. (2005). Laplacians and the Cheeger inequality for directed graphs. Annals of Combinatorics, 9, 1-19.

Digney, B. (1998). Learning Hierarchical Control Structure for Multiple Tasks and Changing Environments. In Proceedings of the Fifth Conference on the