The Expected Value of Hierarchical Problem-Solving

Natural Language

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 10

Planning

n the best case using an abstraction hierarchy in problem-solving can yield an exponential speed-up in search efficiency. Such a speed-up is predicted by various analytical models developed in the literature, and efficiency gains of this order have been confirmed empirically. However, these models assume that the Downward Refinement Property (DRP) holds. When this property holds, backtracking never need occur across abstraction levels. When it fails, search may have to consider many different abstract solutions before finding one that can be refined to a concrete solution. In this paper we provide an analysis of the expected search complexity without assuming the DRP. We find that our model predicts a phase boundary where abstraction provides no benefit: if the probability that an abstract solution can be refined is very low or very high, search with abstraction yields significant speed up. However, in the phase boundary area where the probability takes on an intermediate value search efficiency is not nec- essarily improved. The phenomenon of a phase boundary-where search is hardest agrees with recent empirical studies of Cheeseman et al. [CKT91].