情報保存的な問題領域におけるトレースからの問題分割戦略の獲得

概要

論文の詳細を見る
Search is one of the most important and basical technique underlying most computer problem solving methods. Exhaustive search method explore all possible paths to a goal state. However, this method requires exponentially large time and space for computation as state spaces become large. Problem decomposition is one of the effective methods to reduce search space. General Problem Solver implements means-ends analysis. The necessary condition for its applicability is the existence of a set of subgoals and an ordering among them, such that once satisfying a subgoal, it must not be violated in order to satisfy the remaining subgoals. But problems, like Rubik's Cube, whose subgoals have strong interaction among one another, do not satisfy this condition. Korf has developed Macro Problem Solver and used macro operators to overcome this difficulty. His system solves a problem based on a macro table without no search. A macro table is a table of macro operators whose column headings are state components (differences in GPS) and whose row headings are the values of state components. Korf proposes a method to learn macro tables. His idea is basically a backward search from a goal by applying the inverse of the primitive operators. But in this paper, we consider the problem of acquiring a macro table from traces. We first define the extended definition of Korf's Macro Table, called Problem Decomposition Strategy. Because the acquisition of it seems to be intractable in general, we limit the attention to the domains which are information preserving and whose goal state space is composed of only one state. After investigating the characteristics of such domains, we present the efficient method for acquiring Problem Decomposition Strategy from traces. Our method does not need the information of subgoal ordering, which is necessary in advance for applying Korf's method. This is one of the most important contributions of this research.
社団法人人工知能学会の論文
1992-11-01

情報保存的な問題領域におけるトレースからの問題分割戦略の獲得

スポンサーリンク

概要

著者

関連論文

スポンサーリンク