Search reduction in hierarchical problem solving

Craig A. Knoblock

1991 · 69 citations · 11 references

Concepts

TL;DR

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.

Abstract

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.

References

11