Automatic Generation of Memory Based Search Heuristics

AAAI 2000

TL;DR

This paper introduces a method for automatically generating admissible and monotonic heuristics for state-space search by creating abstract versions of the problem's state space. These "pattern databases" store pre-computed distances from abstract goal states, enabling faster search in complex problems by trading memory for speed.

What Problem Does This Paper Address?

State-space search, a fundamental problem in Artificial Intelligence, often involves exploring vast numbers of possible states to find a solution. The efficiency of this search heavily relies on the quality of heuristic functions, which estimate the cost to reach the goal from a given state. Designing good heuristics manually is challenging and time-consuming, especially for complex problems. This paper addresses the need for automated heuristic generation that produces effective heuristics, specifically those that are admissible (never overestimate the true cost) and monotonic (never decrease as the search progresses), which are crucial for many search algorithms like IDA*.

Methods

The core of the paper's contribution lies in domain abstraction. The authors propose creating abstract state spaces by applying simple syntactic transformations to the original problem's description. These transformations result in a simplified representation of the problem. The distances from abstract goal states to all abstract states are then pre-computed and stored in a look-up table, forming a "pattern database." These stored distances serve as the heuristic values for the original problem. The paper highlights that the size of the abstract space (and thus the memory required for the pattern database) can be varied by choosing different transformations, allowing for a trade-off between memory usage and search speed. They also discuss the concept of "non-surjective" abstractions, where some abstract states might not have a corresponding state in the original space, which can paradoxically shorten the optimal path in the abstract space.

Datasets

Not discussed in the paper. The paper focuses on the general methodology and its application to problem domains like the 15-Puzzle and Rubik's Cube, but does not specify particular datasets used for evaluation.

Key Insights and Ideas

  • Automated Heuristic Generation: The primary insight is that heuristics can be automatically generated by abstracting the problem space, eliminating the need for manual design.
  • Memory-Speed Trade-off: The size of the pattern database (memory) can be directly traded for search speed, allowing users to tune performance based on available resources.
  • Non-Surjective Abstractions: The paper identifies that abstractions where not all abstract states map back to the original space can be beneficial, leading to smaller heuristic values and potentially faster searches.
  • Potential for Macro Operators: The technique shows promise for finding "macro operators" (sequences of actions that reach a subgoal) more efficiently, which can further speed up search.

Key Results

The paper verifies a conjecture that the size of the pattern database and the speed of search can be linearly traded for each other. They also report on experiments that used these ideas to select the best heuristics from a large pool of candidates with equal memory requirements. While specific quantitative results are not detailed in this excerpt, the authors indicate that their technique has been effectively applied to problems like the 15-Puzzle and Rubik's Cube.

Limitations and Future Work

The authors acknowledge that while they have identified structural properties that could help avoid non-surjective abstractions, they currently lack an automatic method for doing so. They are investigating efficient methods to determine if an abstract state has a pre-image in the original space. Future work includes exploring other abstraction techniques that reduce state representation dimensionality, encoding more complex spaces, and developing methods to select the optimal combination of multiple smaller abstractions to achieve the best performance.

Summary updated

BibTeX
@inproceedings{2000automatic,
  title = {{Automatic Generation of Memory Based Search Heuristics}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2000},
}
Figure