The Expected Value of Hierarchical Problem-Solving

Fahiem Bacchus, Qiang YangAAAI 1992 · OpenReview

Abstract

In 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 necessarily improved. The phenomenon of a phase boundary where search is hardest agrees with recent empirical studies of Cheeseman et al. [CKT91].

Introduction

Hierarchical problem-solving is often touted as an exponential speed-up for AI search, but this paper reveals a hidden catch. By modeling search as a branching process, the authors identify a "phase boundary" where abstraction actually makes problems harder to solve if the probability of refining an abstract plan is neither very high nor very low.

In AI planning, hierarchical problem-solving involves creating a simplified (abstract) version of a problem, solving it, and then filling in the details to reach a concrete solution. Historically, researchers assumed the Downward Refinement Property (DRP): the idea that any abstract solution can always be successfully refined into a concrete one. However, in the real world, DRP often fails. A solver might find a promising abstract plan only to realize later that a tiny detail at the concrete level makes it impossible to execute, forcing costly backtracking across abstraction levels. This paper provides a formal analytical model of search complexity that doesn't rely on the "perfect world" assumption of DRP.

Methods

The authors use the theory of branching processes to create a mathematical model of the search space. They represent the search as a tree where:

  • Levels ($n$): The number of abstraction layers.
  • Branching Factor ($B$): The number of possible refinements for any given abstract plan.
  • Refinement Probability ($p$): The likelihood that a specific abstract plan can be successfully refined to the next level down.
  • Work ($k$): The number of new operators needed to solve a "gap" sub-problem during refinement.

By setting up recurrence relations for the expected amount of work to search "good" subtrees (those containing a solution) versus "bad" subtrees (dead ends), they derive closed-form expressions for search complexity across different regions of $p$.

Key Results

The authors categorize search complexity into distinct regions based on the refinement probability $p$ and the branching factor $B$. The most striking result is that in the middle region, the complexity increases by a factor of $(pB)^n$. If the abstraction tree is "bushy" (high $B$), the search becomes significantly more expensive than non-hierarchical search.

Table 1: Expected search complexity across different refinement probability regions.

The formal complexity bounds derived in the paper (shown in Table 1) highlight the phase boundary. When $p$ is very low ($p < 1/B$) or very high ($p = 1$), abstraction is highly effective. However, in the intermediate region ($1/B < p < 1$), complexity can explode exponentially with the number of abstraction levels.

Discussion and Key Insights

  • The Phase Boundary: Search complexity isn't a linear relationship with the probability of success. In the "middle region," abstract solutions are "refineable enough" to lure the search deep into the tree, but "unrefineable enough" that many paths eventually fail, leading to massive backtracking.
  • The "Cheap" Extremes: When $p$ is very high, DRP almost holds. When $p$ is very low, bad paths fail almost immediately, making them "cheap" to prune.
  • Independence Matters: The model assumes that "gap" sub-problems can be solved independently. If sub-problems interact, the benefits of abstraction vanish entirely.
  • Future Directions: Since $p$ is the critical factor, future AI planners might use machine learning to estimate $p$ for different abstraction hierarchies, allowing for adaptive planning decisions.

As a theoretical paper, this work provides a mathematical framework to explain empirical results previously observed in systems like ABSTRIPS and ABTWEAK, as well as the "hardest-problem" phase transitions noted by Cheeseman et al. (1991).

Summary updated

Abstract

In 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 necessarily improved. The phenomenon of a phase boundary where search is hardest agrees with recent empirical studies of Cheeseman et al. [CKT91].
BibTeX
@inproceedings{bacchus1992expected,
  author = {Fahiem Bacchus and Qiang Yang},
  title = {{The Expected Value of Hierarchical Problem-Solving}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1992},
  url = {https://openreview.net/forum?id=rJWEKyW_Wr},
}
Figure