Value Compression of Pattern Databases

Nathan R. Sturtevant, Ariel Felner, Malte Helmert

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 for optimal range partitioning.

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.

Comparison of Entry Compression (EC) and Value Compression (VC) performance on the TopSpin puzzle.

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

Abstract

One common pattern database compression technique is to merge adjacent database entries and store the minimum of merged entries to maintain heuristic admissibility. In this paper we propose a compression technique that preserves every entry, but reduces the number of bits used to store each entry, therefore limiting the values that can be represented. Even when this technique throws away low values in the heuristic, it can still have better performance than the traditional approach. We develop a theoretical basis for selecting which values to keep and show improved performance in both unidirectional and bidirectional search.
BibTeX
@inproceedings{sturtevant2017value,
  author = {Nathan R. Sturtevant and Ariel Felner and Malte Helmert},
  title = {{Value Compression of Pattern Databases}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.1609/aaai.v31i1.10665},
}
Figure