High-Performance A* Search Using Rapidly Growing Heuristics

IJCAI 1991

TL;DR

This paper challenges the conventional wisdom that accurate heuristics are paramount for efficient A* search. Instead, it proposes a new model suggesting that heuristics whose values are tightly clustered around a rapidly growing "central function" are key to achieving polynomial time complexity, even if they are not precisely accurate. This insight has significant implications for designing better search algorithms, particularly by demonstrating how "multiplying" heuristics can transform exponential complexity into polynomial.

What Problem Does This Paper Address?

The A search algorithm is a cornerstone of artificial intelligence for solving problems by exploring a state space. Its efficiency heavily relies on heuristic functions, which estimate the cost to reach a goal. Traditionally, research has focused on designing "accurate" heuristics (those close to the true cost) to achieve fast search times. However, this paper argues that the prevailing "IID model" of heuristics, which assumes errors are independent and identically distributed, leads to a misleading conclusion that accuracy is the primary driver of performance. The authors introduce a more realistic model that relaxes these assumptions and investigates what properties of heuristics truly lead to high-performance A search, specifically aiming for average polynomial time complexity. They also address the practical problem of how to improve heuristics that currently lead to exponential search times.

Methods

The paper introduces a new model for analyzing heuristic performance, termed the "NC model" (Non-Constrained), which contrasts with the "IID model." The NC model places no constraints on the errors of heuristic estimates or their distribution. Instead, it focuses on the clustering of heuristic values around a "central function."

The core of their theoretical contribution lies in defining and proving theorems about heuristic properties that lead to polynomial vs. exponential A* complexity.

  • Logarithmic Cluster Complexity Theorem (Theorem 1): This theorem states that if a heuristic is "rapidly growing with logarithmic cluster," A* search will have polynomial average time complexity. This means heuristic values are tightly grouped within a logarithmic range around a central function, which itself grows at least as fast as the true cost.
  • Slowly Growing Heuristic Complexity Theorem (Theorem 2): This theorem demonstrates that heuristics whose values grow slower than the true cost to the goal will lead to exponential A* complexity.

A key application of their NC model is the analysis of "multiplying" heuristics. By multiplying a heuristic function $h$ by a constant $z > 0$ to get $zh$, they show that this technique can transform exponential complexity into polynomial, a finding that contradicts conclusions from the IID model.

Datasets

The paper uses experimental data from the 8-Puzzle problem to illustrate its theoretical findings. Specifically, it references data from [Chen, 1989] for observed heuristic values and node expansion counts. No new datasets were introduced.

Key Insights and Ideas

  • Accuracy is Overrated; Clustering is Key: The most significant insight is that precise accuracy of a heuristic is less critical than its clustering around a rapidly growing central function. This challenges decades of AI research focused on heuristic accuracy.
  • The Power of "Rapidly Growing" Central Functions: The NC model highlights that the central function around which heuristics cluster must grow at least as fast as the true cost to the goal. If the heuristic values lag behind this growth, complexity suffers.
  • Multiplying Heuristics: A Powerful Transformation: The paper provides a theoretical and experimental basis for why multiplying a heuristic by a constant can dramatically improve A* performance, turning exponential complexity into polynomial. This offers a practical strategy for improving existing heuristics.
  • Beyond the IID Model: The NC model offers a more realistic framework for analyzing heuristics, as it doesn't impose restrictive assumptions about error distributions, making its conclusions more broadly applicable.

Key Results

  • Polynomial Complexity Achieved: Through experimental and theoretical examples, the paper demonstrates that heuristics exhibiting logarithmic clustering around a rapidly growing central function lead to polynomial A* complexity. For instance, using the 8-Puzzle with a multiplied Manhattan distance heuristic ($4h_2$) resulted in linear complexity.
  • Exponential Complexity Avoided/Transformed: The paper shows that slowly growing heuristics lead to exponential complexity (Theorem 2), but multiplying them can mitigate this, transforming exponential complexity to polynomial (Section 4).
  • Theoretical Guarantees: Theorems 1 and 2 provide formal conditions under which A* search exhibits polynomial or exponential time complexity, respectively, based on heuristic properties.

Limitations and Future Work

  • Sufficiency vs. Necessity: While logarithmic clustering is shown to be a sufficient condition for polynomial time complexity, the paper acknowledges that a necessary condition is still an open question.
  • Generalizing Beyond Trees: The current model assumes a uniform b-ary tree state space. While the 8-Puzzle example shows applicability to more complex graphs, further work could explore the implications for graphs with cycles and varying branching factors.
  • Admissibility and Consistency: The authors pose an interesting research question: can insights about heuristic clustering and growth rates be derived from domain constraints, similar to how admissibility and consistency are deduced?
  • Practical Heuristic Design: While the paper provides theoretical underpinnings, further research could focus on developing practical methods for automatically identifying or constructing heuristics that meet the NC model's criteria.

Summary updated

BibTeX
@inproceedings{1991high,
  title = {{High-Performance A* Search Using Rapidly Growing Heuristics}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1991},
}

Loading related content...

Figure