A Result on the Computational Complexity of Heuristic Estimates for the A* Algorithm

TL;DR

This paper analyzes a novel heuristic search algorithm that computes heuristic evaluation functions for A by solving less constrained "auxiliary problems." The authors demonstrate that this approach is computationally less efficient than Dijkstra's algorithm, proving that solving auxiliary problems with backtracking is not an effective way to generate A heuristics.

What Problem Does This Paper Address?

The A search algorithm is a cornerstone of artificial intelligence for finding optimal paths in graphs. Its efficiency hinges on a heuristic evaluation function, $h(n)$, which estimates the cost from a current node $n$ to the goal. While human experts often provide these heuristics, automatically generating them is a significant challenge. This paper investigates a method for automatically computing heuristics by leveraging a "semantic representation" of a problem, which captures more structure than a simple graph. The core question is whether this richer representation, used to solve auxiliary problems, can lead to more efficient heuristic computation for A compared to standard graph search methods.

Methods

The paper introduces a method for computing heuristic evaluation functions for A by solving "auxiliary problems." A semantic problem is defined by attributes, values, properties, and legal conditions, offering a structured representation. An auxiliary problem is a less constrained version of the original problem. The proposed algorithm, "Algorithm M," computes the heuristic $h(n)$ by solving an auxiliary problem related to the current state $n$ using Dijkstra's algorithm. This computed heuristic is then used by A to guide its search for the optimal solution to the original problem. The paper then rigorously compares the computational complexity (measured by node expansions) of Algorithm M against Dijkstra's algorithm.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Semantic Representation: Problems can be represented not just as graphs (syntactic) but with richer semantic structures, allowing for more information to be encoded.
  • Auxiliary Problems for Heuristics: The core idea is that solving a simpler, less constrained version of a problem can provide an admissible heuristic for the original, more complex problem.
  • The Cost of Computation: While solving auxiliary problems can generate heuristics, the paper highlights that the computational cost of generating these heuristics can outweigh the benefits gained by A*'s more focused search.
  • Dijkstra as a Baseline: The paper establishes Dijkstra's algorithm as a benchmark for efficiency in blind, unidirectional search, and then shows that the proposed heuristic computation method is less efficient.

Key Results

The main theoretical result is the Main Theorem: Algorithm M expands at least every node that Dijkstra's algorithm expands to solve the syntactic problem corresponding to the skeleton of the semantic problem. This implies that Algorithm M uses at least as many node expansions as Dijkstra's algorithm. The paper breaks down the complexity analysis into three cases, demonstrating that in each scenario, the cost of computing the heuristic (even with an efficient method like Dijkstra on the auxiliary problem) offsets or exceeds any potential savings in the A* search phase. Essentially, the paper proves that computing heuristics by solving auxiliary problems with backtracking is computationally inefficient.

Limitations and Future Work

The authors acknowledge that recognizing structure in auxiliary problems to simplify their solution is a difficult task, related to the "change of representation" problem, which is considered beyond the current state of the art. They note that even simple heuristics, like the one for the eight-tile puzzle, do not always exhibit obvious structural properties in their auxiliary problem skeletons. The paper implicitly suggests that future work might focus on finding more efficient ways to solve auxiliary problems or on alternative methods for heuristic generation that do not involve such a high computational overhead.

Summary updated

BibTeX
@inproceedings{1983result,
  title = {{A Result on the Computational Complexity of Heuristic Estimates for the A* Algorithm}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1983},
}
Figure