Abstract
Pattern Databases (PDBs) are a cornerstone of modern heuristic search, providing exact distances for simplified problem abstractions. However, their substantial memory requirements often limit their applicability to large-scale problems. This paper presents Value Compression (VC), a novel approach that reduces the memory footprint of PDBs by decreasing the number of bits allocated per entry through optimal range partitioning. Experimental results on combinatorial puzzles demonstrate that VC significantly outperforms traditional Entry Compression (EC), particularly in bidirectional search contexts, by maintaining higher heuristic accuracy for a given memory budget.
Introduction
In automated planning and pathfinding, heuristics ($h$) guide search algorithms like A* toward a goal. Pattern Databases (PDBs) serve as lookup tables for these heuristics. As problem complexity grows, PDB sizes can easily exceed available RAM. Traditionally, researchers have employed Entry Compression (EC), which merges multiple states into a single bucket and stores the minimum heuristic value to maintain admissibility. However, EC often loses significant information because it groups states based on memory indices rather than their heuristic utility.
Value Compression (VC) addresses this by maintaining one entry per state but reducing the precision of the stored values. By partitioning the range of heuristic values into a small number of discrete subranges, VC preserves the "signal" necessary for efficient search while drastically reducing storage requirements.
Methodology: Optimal Range Partitioning
The effectiveness of VC hinges on how heuristic values are mapped to a limited number of bits. The authors propose a Dynamic Programming algorithm, OptPart, to find the optimal partitioning of values into $M$ disjoint subranges.
The OptPart algorithm (Figure 1) takes a distribution of heuristic values and identifies the partition that maximizes the average heuristic value returned by the compressed PDB. This ensures that the information loss is mathematically minimized. Furthermore, the authors extend this to "Delta Heuristics," where VC is applied to the difference between a simple heuristic (e.g., Manhattan Distance) and the true PDB value, further enhancing compression efficiency.
Experimental Setup
The proposed methods were evaluated using standard combinatorial search benchmarks:
- TopSpin Puzzle: Specifically the (18,k) variants, which allow for tunable state space sizes and heuristic difficulties.
- 16-disk 4-peg Towers of Hanoi (TOH4): A challenging problem characterized by long solution paths and a massive state space.
Key Results
The primary finding is that VC consistently yields better search performance than EC for the same memory footprint. As shown in the experimental data, reducing a PDB to 2 or 4 bits per entry often results in negligible increases in search time compared to the uncompressed 8-bit version.
In the (18,4)-TopSpin puzzle (Figure 6), a 2-bit VC PDB expanded 10.39M nodes, whereas an EC-compressed PDB of the same size required 13.75M nodes. This performance gap widens in bidirectional search scenarios, such as the Meet-in-the-Middle (MM) algorithm. Because MM primarily relies on high heuristic values for pruning, VC can be configured to provide high precision for large values while "squashing" less relevant low values, leading to search speeds up to twice as fast as EC-based compression.
Discussion and Future Work
A critical insight from this research is the distinction between "Static Distribution" (frequency of values in the PDB) and "Dynamic Distribution" (frequency of values encountered during search). VC is most effective when these distributions are aligned.
While VC demonstrates clear advantages, its performance can degrade if there is a significant distribution mismatch. Future research could explore adaptive partitioning techniques that "train" the compression on sample problem instances to better align with the dynamic search distribution. Additionally, the orthogonality of VC and EC suggests that hybrid compression schemes could provide even greater memory savings for extremely large-scale planning tasks.
This summary is based on the paper "Value Compression of Pattern Databases" by Sturtevant, Felner, and Helmert, published in AAAI-17.
Summary updated