Abstract
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.