Complexity Analysis of Admissible Heuristic Search

AAAI 1998

TL;DR

This paper presents a novel method for analyzing the performance of admissible heuristic search algorithms like A and IDA. Instead of relying on abstract models of heuristic accuracy, it characterizes heuristics by their distribution of values across the problem space, allowing for accurate predictions of performance on real-world problems like Rubik's Cube and sliding-tile puzzles. The key insight is that heuristics primarily reduce search depth, not branching factor, contrary to prior beliefs.

What Problem Does This Paper Address?

Heuristic search algorithms are fundamental to artificial intelligence for solving complex problems where exhaustive search is infeasible. Admissible heuristics, which never overestimate the cost to a goal, guarantee optimal solutions. However, accurately predicting the performance of these algorithms has been a long-standing challenge. Previous analyses relied on abstract models that characterized heuristics by their "accuracy" (how close they are to the true cost), which is difficult to measure in practice for real heuristics. This made it hard to predict how well algorithms like A or IDA would perform on problems like the sliding-tile puzzle or Rubik's Cube. The authors aim to bridge this gap by developing a more practical and accurate method for analyzing heuristic search complexity.

Methods

The paper introduces a new way to characterize admissible heuristics: by their distribution of values across the entire problem space. Instead of needing to know the true cost to a goal for each state (which is computationally expensive), the authors propose using the fraction of nodes that have a heuristic value less than or equal to a certain number, denoted as $P(x)$. This "overall distribution" can be estimated by random sampling or, for some heuristics like pattern databases, calculated exactly.

They then develop an analytical model for the number of node generations in search algorithms like A, IDA, and DFBnB. This model uses the branching factor ($b$), the solution depth ($d$), and the heuristic's equilibrium distribution ($P(x)$) – the distribution of heuristic values at a given depth in a brute-force search, in the limit of large depth. The core of their analysis shows that admissible heuristics, when consistent, prune nodes whose total estimated cost ($f(n) = g(n) + h(n)$) exceeds the optimal solution cost ($c$). This pruning effectively reduces the search depth rather than the branching factor.

Datasets

The paper evaluates its analytical model using data from:

  • Rubik's Cube: Specifically, a problem space allowing 180-degree twists, with a brute-force branching factor of ~13.35 and a median optimal solution depth of 18.
  • Eight Puzzle: Using the Manhattan distance heuristic, with a known total of 181,440 solvable states.
  • Fifteen Puzzle: Also using the Manhattan distance heuristic, a much larger problem space (over ten trillion states), for which the heuristic distribution was approximated by random sampling.

No new benchmarks were introduced; existing problem instances and heuristics were used for evaluation.

Key Insights and Ideas

  • Heuristics Reduce Depth, Not Branching Factor: This is the most significant finding. Contrary to previous theories that suggested heuristics reduce the branching factor ($b$) to some smaller value ($a < b$), this paper argues that the effective branching factor remains $b$. Instead, the heuristic's power lies in reducing the effective depth of the search from $d$ to $d-k$ for some constant $k$.
  • Distribution is Key, Not Accuracy: The paper shifts the focus from the abstract concept of heuristic "accuracy" to the more practical and measurable "distribution" of heuristic values. This makes the analysis applicable to real-world heuristics.
  • Equilibrium Distribution Matters: While the "overall distribution" is easier to obtain, the "equilibrium distribution" (heuristic values at a given depth in a deep search) is what truly governs performance. For some problem spaces (like bipartite graphs or those with specific state distributions), this can differ from the overall distribution.
  • Consistency is Crucial: The analysis relies on the heuristic being consistent (i.e., $h(n) \le k(n, n') + h(n')$). This property ensures that the pruning of nodes is well-behaved and doesn't complicate the distribution of fertile nodes at each level.

Key Results

The paper's analysis and experimental results show:

  • Accurate Predictions: The theoretical predictions for the number of nodes generated by IDA* closely match experimental data. For Rubik's Cube, predictions are within 1% of experimental results. For the Eight Puzzle, the agreement is exact. For the Fifteen Puzzle, predictions are within 2.5% for typical solution lengths.
  • Heuristic Branching Factor is $b$: The analysis confirms that the heuristic branching factor is indeed the same as the brute-force branching factor ($b$), meaning the number of nodes generated is approximately $b^d$ (adjusted by the heuristic's effect on depth).
  • Effective Depth Reduction: The primary benefit of admissible heuristics is shown to be the reduction of the effective search depth, leading to a complexity closer to $O(b^{d-k})$ rather than $O(a^d)$ where $a < b$.

Limitations and Future Work

  • Assumptions: The analysis assumes that nodes are counted separately even if they represent the same state (true for IDA and DFBnB, but not A with visited set). It also assumes unit edge costs and integer-valued heuristics (or rounded-up non-integer ones). Consistency of the heuristic is also assumed.
  • Fixed Heuristic, Growing Problem Size: The current analysis predicts performance for a fixed heuristic as the solution length grows large. A significant open problem is to predict the asymptotic performance of a fixed heuristic as the problem size increases (e.g., how Manhattan distance performs on larger sliding-tile puzzles).
  • Independence Assumption: For heuristics that are the maximum of multiple individual heuristics, the assumption of independence between these individual heuristics might not always hold, potentially introducing some error.

Summary updated

BibTeX
@inproceedings{1998complexity,
  title = {{Complexity Analysis of Admissible Heuristic Search}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1998},
}
Figure