Abstract

It has long been recognized that hierarchical problem solving can be used to reduce search. Yet, there has been little analysis of the problemsolving method and few experimental results. This paper provides the rst comprehensive analytical and empirical demonstrations of the e ectiveness 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 identi es a su cient 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 e ective in practice.

Date

July 14, 1991

Authors

Craig A Knoblock

Journal

AAAI

Volume

91

Pages

686-691