Pattern Databases for Heuristic Search

22 concepts17 papers3 proposals

In combinatorial search, the primary challenge is the "state-space explosion." As problems grow—from simple puzzles to complex logistics or bioinformatics—the number of possible configurations grows exponentially. To find optimal solutions without visiting every state, algorithms like A rely on heuristics*: functions that estimate the remaining cost to reach a goal.

The most powerful modern heuristics are not calculated on the fly. Instead, they are retrieved from Pattern Databases (PDBs). This research direction focuses on a fundamental trade-off: using a one-time investment in memory to achieve massive, permanent speedups in search time.

The Core Intuition: Solving Subproblems Offline

The intuition behind a pattern database is to solve a simplified version of a problem completely and store the results in a lookup table.

Imagine solving a Rubik’s Cube. The total state space is roughly $4.3 \times 10^{19}$. However, if you ignore the edges and focus only on the eight corner pieces, the state space shrinks to about 88 million. As the authors demonstrated in 1997, we can precompute the exact number of moves required to solve every possible corner configuration and store these values in a table.

During a real search, when the algorithm encounters a scrambled cube, it looks up the cost to solve just the corners. Because the cost to solve a part of the problem is always less than or equal to the cost to solve the whole problem, this value is an admissible heuristic—a perfect lower bound that allows the search to safely prune paths that are guaranteed to be suboptimal.

From Macros to Cost-to-Goal Tables

The evolution of this idea began with identifying problem structures. Richard E. Korf initially proposed "operator decomposability," where complex problems are solved by pre-learning "macro-operators"—sequences of moves that solve specific subgoals without disturbing previous ones. While macros reduce search depth, they don't always guarantee optimality.

The shift toward PDBs transformed this from a sequence of moves into a numerical estimate. Viswanathan et al. showed that pre-calculating dynamic programming tables for sub-problems could turn expensive recursive calculations into constant-time lookups. This "search-to-lookup" transformation is the defining characteristic of the field:

  • Offline Phase: Exhaustively solve an abstract version of the problem.
  • Online Phase: Use the stored costs to guide the search through the full, complex state space.

Generalizing the Pattern Database

While early PDBs were fixed to a single goal, the research has expanded to handle more fluid search environments:

  • Multiple Goals: In problems where the target is a set of states rather than a single point, Korf et al. introduced multiple-goal PDBs. These seed the database with distances to an entire class of target configurations, which is particularly useful for bidirectional search.
  • Differential Heuristics: Standard PDBs estimate the distance to a fixed goal. Lavasani et al. describe how PDBs can be used as "differential heuristics." By storing distances from a set of "anchor" states and applying the triangle inequality, the system can estimate the distance between any two arbitrary states, enabling efficient bidirectional search.
  • Factored Projections: In high-dimensional tasks like natural language parsing, Manning et al. showed that complex models can be decomposed into simpler "projections." The optimal costs of these projections are pre-calculated and summed to create a powerful heuristic for the combined space.

Shifting the Computational Burden

The modern frontier of this research involves moving even more "online" work into the "offline" phase. Katz et al. argue for "implicit abstraction heuristics," where the most computationally intensive portions of a heuristic are partitioned into a heavy precomputation phase, leaving only a trivial minimization task for the search engine.

Similarly, in automated planning, Pommerening et al. demonstrated that by pre-calculating numerical "potentials" for individual facts, the cost of solving complex linear programs at every search node can be replaced by simple addition. Sreedharan et al. furthered this by using matrix pseudo-inverses calculated offline to reduce per-node costs to basic matrix-vector multiplication.

By treating memory as a cache for logic, pattern databases allow AI systems to "recognize" the difficulty of a situation based on past experience—much like how Campbell et al. described chess programs using "chunks" to evaluate positions—rather than re-calculating the laws of the domain from scratch at every step.

Key Foundational Work

An Exact Best-First Search Procedure for the Constrained Rectangular Guillotine Knapsack Problem (1988) — contributed 2 concept elements to this direction.
Operator Decomposability: A New Type of Problem Structure (1983) — contributed 1 concept elements to this direction.
A Chess Program That Chunks (1983) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_pattern_databases_33c68745,
  title = {pattern databases},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/pattern-databases/rdr_33c6874594ed4fb48119c1fe7fda4fc4},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_pattern_databases_33c68745_v1,
  title = {pattern databases},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/pattern-databases/rdr_33c6874594ed4fb48119c1fe7fda4fc4/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake