Dynamic Improvements of Heuristic Evaluations during Search

AAAI 1996

TL;DR

This paper introduces a novel "difference approach" to dynamically improve heuristic evaluation functions during search. By leveraging the errors in static heuristics and known path costs, their methods (Add and Max) significantly speed up search algorithms like A and IDA in complex domains, outperforming previous state-of-the-art results.

What Problem Does This Paper Address?

Heuristic search algorithms are fundamental to solving many complex problems, from game playing to route planning. Their efficiency heavily relies on "heuristic evaluation functions" that estimate the cost to reach a goal. However, these static heuristics, while often efficient to compute, are imperfect and can lead to suboptimal or slow searches. The challenge is to improve the accuracy of these heuristics during the search process itself, without incurring prohibitive computational costs. Existing methods often require significant memory or are limited in applicability.

Methods

The core contribution is the difference approach, which uses the discrepancy between known path costs and static heuristic estimates to refine future heuristic evaluations. Two concrete methods are proposed:

  • Add Method: This method calculates the minimum error (difference between actual cost and static heuristic) across nodes on the search frontier. This minimum error is then added as a constant to the static heuristic for all nodes outside this frontier. This ensures the new heuristic remains admissible (never overestimates the true cost) and can improve search efficiency by providing tighter bounds.
  • Max Method: This approach uses the difference between a known path cost and a static heuristic to create an alternative heuristic estimate. It then takes the maximum of this new estimate and the original static heuristic. This method also aims to improve accuracy while maintaining admissibility.

These methods are designed to be integrated into existing search algorithms like A and IDA, often requiring minimal additional computational overhead per node.

Datasets

The paper evaluates its methods on two standard benchmarks:

  • 15-Puzzle: A classic sliding-tile puzzle used to test heuristic search algorithms. The authors used a set of 100 instances from Korf (1985).
  • Maze: A domain for finding shortest paths, inspired by the Xwindows demo package Xmaze. The authors generated instances by modeling navigation in the presence of obstacles, using Manhattan distance as the heuristic. They specifically focused on larger mazes (2000x2000) and more difficult instances where the initial heuristic estimate was high.

Key Insights and Ideas

  • Leveraging Heuristic Errors: The fundamental insight is that the errors made by static heuristics are valuable information. Instead of discarding them, the authors show how to systematically use these errors to improve future estimates.
  • Dynamic vs. Static: The paper clearly distinguishes between static heuristics (computed once) and dynamic heuristics (updated during search), highlighting the potential for significant gains by making search "aware" of its own progress.
  • Unifying View: The proposed difference approach provides a framework that can encompass and explain previously existing dynamic improvement techniques, offering a more cohesive understanding of the field.
  • Domain Adaptability: The methods are shown to be effective across different domains (puzzle and maze), suggesting their general applicability.

Key Results

The proposed "difference approach" methods (Add and Max) demonstrated significant improvements:

  • 15-Puzzle:
    • Max-BAI-Trans achieved the fastest search times, requiring only 15.4% of the time needed by IDA* (Korf's implementation).
  • Max-BAI generated 54.4% of the nodes compared to IDA, with a running time of 76.1%*, showing good performance for a linear-space algorithm.
  • These results were statistically significant improvements over competitors that did not use the difference approach.
  • Maze:
    • Add-A generated 70.7% of the nodes and used 71.7% of the time compared to pure A, representing significant improvements.
  • The perimeter search method (PS*), while effective in the 15-Puzzle, performed poorly in the maze domain, highlighting domain-specific limitations of some existing techniques.

Limitations and Future Work

  • Memory Requirements: While the Add method has negligible overhead, achieving significant improvements might require substantial memory to store enough frontier nodes to find a meaningful minimum difference. The Max method also benefits from stored information.
  • Perimeter Search Limitations: The paper notes that perimeter search (a Front-to-Front method) struggled in the maze domain due to high computational costs and memory requirements, suggesting it's not universally applicable.
  • Future Work: The authors suggest further investigation into the relationship between their methods and "learning" in machine research, particularly how results from one problem instance could inform future ones. They also point to the need for more in-depth analysis of the advantages and disadvantages of perimeter search.

Summary updated

BibTeX
@inproceedings{1996dynamic,
  title = {{Dynamic Improvements of Heuristic Evaluations during Search}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1996},
}
Figure