Designing Heuristics
Relaxed problems, pattern databases and dominance.
The 15-puzzle has about reachable states and Rubik's cube about , yet heuristic search solves individual instances of both optimally. The trick is not a faster search but a better : tables of exact costs for well-chosen subproblems, computed once and combined without ever overestimating.
What you’ll learn
- Define abstraction heuristics and prove that they are admissible and consistent, with relaxed problems as a special case.
- Build a pattern database by backward search, count its entries, and prove when the values of several databases may be added.
- Combine heuristics by maximization and cost partitioning, and weigh accuracy against the cost of evaluating .
- Relate heuristic quality to search effort: Korf, Reid and Edelkamp's prediction for IDA*, and why even "almost perfect" heuristics can leave A* exponential.
Abstractions, precisely
Admissible. A cheapest concrete solution maps to an abstract walk from to an abstract goal that is, step by step, no more expensive (merged steps cost nothing):
Consistent. Abstract distances obey the triangle inequality, and one concrete edge maps to one abstract edge or a free loop:
Coarser is weaker. Apply the first line to the abstraction of : its heuristic underestimates abstract costs, so
Three families cover most of practice:
- Relaxations keep the states and add edges or lower costs (, , ). Misplaced tiles and Manhattan distance are relaxations, and so is planning's delete relaxation, whose optimal cost is NP-hard to compute and is therefore approximated.
- Projections forget variables, for a pattern : in a sliding-tile puzzle, forget which tile is which outside . Tabulated, they are pattern databases.
- Merge-and-shrink abstractions build incrementally, merging variables and shrinking the product to a memory budget (Helmert, Haslum & Hoffmann, 2007).
Think first Project the 8-puzzle onto "where are tile 1 and the blank", with all other tiles alike. How many abstract states are there, and how does the heuristic compare with tile 1's Manhattan distance?
abstract states. Tile 1 moves only when the blank is beside it, so the abstract cost counts tile 1's Manhattan distance plus the blank moves needed to bring the blank alongside. It dominates tile 1's Manhattan distance, which comes from the coarser abstraction that forgets the blank as well.
Pattern databases and additivity
A pattern database (PDB; Culberson & Schaeffer, 1998) stores for a projection onto a pattern as a lookup table. The abstract space is small enough to enumerate, so one backward search from the abstract goals computes every entry, and the main search then pays one memory access per evaluation of .
function BUILD-PDB(abstract states S', abstract goals G', abstract costs c'):
table ← array indexed by S', every entry ∞
queue ← priority queue on table values (a FIFO queue suffices for unit costs)
for each g in G': table[g] ← 0; insert g into queue
while queue is not empty:
u ← pop the entry with the smallest table value
for each abstract edge (v → u): # search backward
if table[u] + c'(v, u) < table[v]:
table[v] ← table[u] + c'(v, u)
insert v into queue
return table # during search: h(s) = table[α(s)]Backward uniform-cost search over the whole abstract space, a retrograde analysis. The table is built once per pattern and goal, then reused for every instance.
| Database | Abstract states | Entries |
|---|---|---|
| 15-puzzle, 7 tiles, blank not tracked | 57,657,600 | |
| 15-puzzle, 8 tiles, blank not tracked | 518,918,400 | |
| Rubik's cube, the 8 corner cubies | 88,179,840 | |
| Rubik's cube, 6 of the 12 edge cubies | 42,577,920 |
Every move moves exactly one tile, so the moves of an optimal solution of split by pattern:
Projected onto , the solution is an abstract solution that costs when only 's moves are charged, so . Summing:
The principle is cost partitioning (Katz & Domshlak, 2008): split each action's cost as with , and let each be admissible for the costs . For any solution path from ,
Manhattan distance is the extreme case of one-tile patterns. The argument fails if each database charges all moves: then two tables both count the same moves, and only their maximum is safe.
You hold two 15-puzzle databases, for tiles 1–7 and for tiles 8–15, each charging only moves of its own pattern's tiles. A third database, for tiles 1–5, charges every move. Which combination is admissible and strongest?
- The sum of all three tables
- The maximum of all three tables
- The third table alone, since it charges every move
Show the answer
B.
The two disjoint tables charge disjoint sets of moves, so their sum is admissible. The third charges moves that the first also charges, so it cannot be added; but a maximum of admissible heuristics is always admissible, and this one dominates every other option offered.
What accuracy buys
With a consistent , A* must expand , so a pointwise larger heuristic never costs expansions (up to ties at ). But expansions are not time. A PDB lookup is one memory access, a maximum over tables costs of them, and heuristics that run a search of their own, like LM-cut in planning, can dominate the running time. The real objective is expansions times time per expansion, and how fast expansions fall as accuracy rises is a quantitative question.
A node at depth survives the threshold- iteration iff , that is , which holds for about a fraction of the nodes:
In a brute-force tree with , substitute :
Since , converges to a constant (for , ). A heuristic therefore multiplies the work by a constant factor, like searching fewer levels, while successive iterations still grow by the brute-force factor:
IDA* runs on a problem whose brute-force tree grows by per level. A better heuristic divides the work of every large iteration by 1,000. How many extra levels of depth does that buy in the same time?
Show the answer
3.9
. A thousandfold saving is worth about four levels, because heuristics act as a constant factor, not as a smaller branching factor. This is why each new heuristic idea extends the reach of optimal search by a few moves rather than transforming it.
Planning heuristics, learned heuristics
Domain-independent planners derive heuristics automatically from a PDDL description. Satisficing planners use inadmissible approximations of the delete relaxation such as (Hoffmann & Nebel, 2001); optimal planners use admissible ones such as LM-cut (Helmert & Domshlak, 2009), pattern databases over automatically chosen patterns, merge-and-shrink, and cost partitionings computed by linear programming (see Classical Planning & Its Complexity).
Learned heuristics fit from solved instances or by approximate value iteration. DeepCubeA (Agostinelli et al., 2019) trained a deep network as a cost-to-go estimate for Rubik's cube and searched with it by a batched weighted A*, finding shortest solutions for most test scrambles. A learned is generally inadmissible, so its guarantee is empirical, "usually optimal", where a pattern database gives "always optimal".
Key takeaways
- An abstraction heuristic is the exact cost to go in an abstract space where every concrete path survives: always admissible and consistent, and weaker for coarser abstractions.
- Pattern databases tabulate projection heuristics with one backward search; their size is the number of abstract states, such as for seven tiles of the 15-puzzle.
- Heuristics combine safely by maximization, and by summation when action costs are partitioned among them, as in disjoint pattern databases.
- Heuristic quality buys IDA* a constant factor (a few levels of depth), and even leaves A* exponential when optimal paths are numerous.
Check yourself
In the interactive lesson these are scored with your confidence, and what you miss comes back for review.
You coarsen an abstraction by merging more concrete states into each abstract state. What happens to the heuristic?
- It can only stay the same or decrease, and it remains admissible and consistent
- It can only stay the same or increase
- It may become inadmissible, because merged states have different true costs
- It stays admissible but may become inconsistent
Show the answer
A. It can only stay the same or decrease, and it remains admissible and consistent
If , then : merging states creates abstract shortcuts and never lengthens abstract distances. Every abstraction heuristic is admissible and consistent, so coarsening trades accuracy for a smaller table.
When may the values of two pattern databases for the 15-puzzle be added without losing admissibility?
- Whenever both databases are admissible
- Never: only the maximum of two heuristics is admissible
- When the patterns are disjoint, whichever moves each database charges
- When the patterns are disjoint and each database charges only moves of its own pattern's tiles
Show the answer
D. When the patterns are disjoint and each database charges only moves of its own pattern's tiles
Then each move of a solution is charged to at most one database, so the sum is at most the solution's length. It is the special case of cost partitioning in which each move's cost goes entirely to the database of the tile it moves.
A heuristic satisfies everywhere. Which statement is true?
- A* expands only the states of one optimal path
- A* expands only linearly many states, since the error is constant
- A* must expand every state on every optimal path, which can be exponentially many
- A* may return a suboptimal solution
Show the answer
C. A* must expand every state on every optimal path, which can be exponentially many
Every nongoal state on an optimal path has , so it is in the must-expand set. When optimal plans can order many interchangeable objects freely, as in Gripper, their states are exponentially many (Helmert & Röger, 2008).
According to Korf, Reid and Edelkamp's analysis of IDA*, what does a better heuristic do asymptotically?
- It lowers the effective branching factor below the brute-force factor
- It divides the work by a constant factor, like searching a fixed number of levels less deep
- It makes the search polynomial whenever the heuristic is consistent
- Nothing: heuristics matter only at small depths
Show the answer
B. It divides the work by a constant factor, like searching a fixed number of levels less deep
, and the sum tends to a constant, so successive iterations still grow by . A heuristic buys a constant factor, which is a fixed number of extra levels of depth, not a smaller base of the exponential.
Further reading
- J. C. Culberson & J. Schaeffer, "Pattern databases," Computational Intelligence 14(3) (1998), 318–334.
- R. E. Korf & A. Felner, "Disjoint pattern database heuristics," Artificial Intelligence 134 (2002), 9–22.
- R. E. Korf, M. Reid & S. Edelkamp, "Time complexity of iterative-deepening-A*," Artificial Intelligence 129 (2001), 199–218.
- M. Helmert & G. Röger, "How good is almost perfect?," Proceedings of AAAI (2008).
- S. Edelkamp & S. Schrödl, Heuristic Search: Theory and Applications (Morgan Kaufmann, 2012).