DOWNWARD REFINEMENT AND THE EFFICIENCY OF HIERARCHICAL PROBLEM-SOLVING

Analysis and experiments have shown that hierarchical problem solving is most effective when the hierarchy satisfies the downward refinement property (DRP), whereby every abstract solution can be refined to a concrete-level solution without backtracking across abstraction levels. However, the DRP is a strong requirement that is not often met in practice. In this paper we examine the case when the DRP fails, and provide an analytical model of search complexity parameterized by the probability of an abstract solution being refinable. Our model provides a more accurate picture of the effectiveness of hierarchical problem solving. We then formalize the DRP in ABSTRIPs-style hierarchies, providing a syntactic test that can be applied to determine if a hierarchy satisfies the DRP. Finally, we describe an algorithm called HIGHPOINT that we have developed. This algorithm builds on the ALPINE algorithm of Knoblock in that it automatically generates abstraction hierarchies. However, it uses the theoretical tools we have developed to generate hierarchies superior to those generated by ALPINE. This superiority is demonstrated empirically.(2)