TL;DR
This paper investigates the relationship between the memory used by heuristic search algorithms and the time they take to find solutions. The authors experimentally test a conjecture that memory (m) and time (t) are inversely proportional (mt = constant), finding that while more memory generally leads to less search time, the relationship is not a strict inverse proportionality but rather a power law (t ∝ m⁻ᵃ, where α is between 0.57 and 0.95). This work is crucial for understanding how to effectively leverage memory in AI search problems.
What Problem Does This Paper Address?
In artificial intelligence, heuristic search algorithms are used to find solutions in complex problem spaces (like puzzles or games). These algorithms often rely on "heuristics" – educated guesses about how close a given state is to the goal. "Memory-based heuristics," particularly "pattern databases," store precomputed heuristic values in lookup tables. The core idea is that a larger lookup table (more memory, m) should allow for a more accurate heuristic, leading to faster search (less time, t).
Richard Korf conjectured that this relationship is a simple inverse proportionality: mt = constant. This would imply that doubling the memory would halve the search time, a very appealing trade-off. However, this conjecture was based on informal analysis and limited experimental evidence. This paper aims to rigorously test Korf's conjecture through a large-scale experiment using automatically generated heuristics across several problem domains.
Methods
The authors developed a novel method for automatically generating a wide variety of "state space abstractions." These abstractions are essentially simplified versions of the original problem's state space, created by mapping multiple original labels to a single abstract label. By controlling the degree of abstraction (how many original labels are mapped to fewer abstract ones), they can generate heuristics with varying memory requirements (m).
They then used these generated heuristics to guide an A search algorithm on various problem instances. For each heuristic (defined by its memory size m), they measured the average number of nodes expanded (t) to solve a set of problem instances. This allowed them to collect data points of (m, t*) pairs across different problem domains and difficulty levels.
Datasets
The experiments were conducted on three well-known state spaces:
- 8-Puzzle: A classic sliding tile puzzle.
- 8-Perm: A permutation puzzle.
- (8,4)-Top-Spin: A puzzle involving tokens arranged in a ring.
For each state space, they generated hundreds of heuristics with varying memory requirements. Problem instances were categorized as "easy," "typical," and "hard" based on their solution lengths, and 100 random instances of each type were used for evaluation. In total, 236,100 problem instances were solved across all experiments.
Key Insights and Ideas
- Korf's Conjecture is an Approximation: The strict inverse proportionality (mt = constant) does not hold. Instead, the relationship is closer to a power law: t ∝ m⁻ᵃ, where the exponent α is consistently less than 1 (between 0.57 and 0.95). This means doubling memory reduces search time, but by less than half.
- Log-Log Plots Reveal Trends: When plotting log(t) against log(m), the data forms nearly straight lines, supporting the power-law relationship.
- Heuristic Value vs. Distribution: While a higher average heuristic value (e) generally leads to less search time (t), the distribution of heuristic values is also critical. Some heuristics with lower average values can outperform others with higher average values due to a more favorable distribution of values.
- Automatic Heuristic Generation is Powerful: The ability to automatically generate a vast number of heuristics demonstrates that effective memory-based heuristics don't necessarily require manual design. This opens doors for more systematic exploration of the space-time trade-off.
- Extrapolation to Extremes: Extrapolating the observed trends to the extremes (e.g., m=1 for breadth-first search, or m=n for a perfect heuristic) shows that the linear approximations are less accurate at these boundaries, suggesting a subtle non-linearity in the relationship.
Key Results
- The experimental results showed a strong correlation (0.99 or higher) between log(t) and log(m) across all tested state spaces.
- The exponent α in the power-law relationship t ∝ m⁻ᵃ ranged from -0.57 to -0.95. This implies that doubling memory reduces search time by a factor between approximately 1.4 and 2.
- For the 8-Puzzle, randomly generated abstractions of relatively small size (less than 3% of the state space) performed as well as, or even better than, the well-known Manhattan distance heuristic.
- The paper demonstrated that even with a fixed memory size (m), different heuristic abstractions can lead to significantly different search times (t).
Limitations and Future Work
- Non-Linearity at Extremes: The authors acknowledge that the observed linear trends in log-log plots might be approximations, and subtle non-linearities appear, especially when extrapolating to the smallest (m=1) or largest (m=n) memory sizes.
- Single Heuristic Use: The experiments primarily used a single memory-based heuristic at a time. Future work could explore the space-time trade-off when multiple memory-based heuristics are used concurrently.
- Optimal Memory Allocation: The paper touches upon the idea that memory-based heuristics can be combined with other search techniques. Determining the optimal allocation of memory among these different techniques remains an open research question.
- Predicting Performance: While the paper shows a relationship between heuristic value and search time, more precise methods for predicting a heuristic's performance based on its properties are still desirable.
Summary updated