1991 · 69 citations · 11 references
ComputingComputer ScienceAlgorithmsArtificial IntelligenceTheory Of ComputationProblem SolvingProblem-solving StrategiesHierarchical SystemsReductionsSearch ProblemsSearch Space Reduction
Hierarchical problem solving has been recognized as a means to reduce search, yet analysis and experimental evidence have been scarce. This paper offers the first comprehensive analytical and empirical demonstration of hierarchical problem solving’s effectiveness. The authors analytically show that, under a sufficient set of assumptions, hierarchical problem solving can shrink the search space from exponential to linear in solution length, and they empirically validate this in both assumption‑satisfying and violating domains while examining practical effectiveness conditions.
It has long been recognized that hierarchical problem solving can be used to reduce search. Yet, there has been little analysis of the problem-solving method and few experimental results. This paper provides the first comprehensive analytical and empirical demonstrations of the effectiveness of hierarchical problem solving. First, the paper shows analytically that hierarchical problem solving can reduce the size of the search space from exponential to linear in the solution length and identifies a sufficient set of assumptions for such reductions in search. Second, it presents empirical results both in a domain that meets all of these assumptions as well as in domains in which these assumptions do not strictly hold. Third, the paper explores the conditions under which hierarchical problem solving will be effective in practice.
11
Depth-first iterative-deepening
Richard E. Korf · Artificial Intelligence · 1985 · 1.6K citations
Planning in a hierarchy of abstraction spaces
Earl D. Sacerdoti · Artificial Intelligence · 1974 · 1.2K citations
Engineering, Systems Engineering, Knowledge Representation +10
Planning with constraints (MOLGEN: Part 1)
Mark Stefik · Artificial Intelligence · 1981 · 817 citations
The theory of learning by doing.
Yuichiro Anzai, Herbert A. Simon · PubMed · 1979 · 609 citations