Simple Algorithm
Artificial Intelligence · Deep Layer · 26 min

Designing Heuristics

Relaxed problems, pattern databases and dominance.

The 15-puzzle has about 101310^{13} reachable states and Rubik's cube about 4.3×10194.3\times10^{19}, yet heuristic search solves individual instances of both optimally. The trick is not a faster search but a better hh: 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 hh.
  • 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

DerivationProof
  1. hα(s) ≤ ∑i<kc′(α(si),α(si+1)) ≤ ∑i<kc(si,si+1)=h∗(s)h^\alpha(s)\ \le\ \sum_{i<k}c'\big(\alpha(s_i),\alpha(s_{i+1})\big)\ \le\ \sum_{i<k}c(s_i,s_{i+1})=h^*(s)

    Admissible. A cheapest concrete solution s=s0,s1,…,sks=s_0,s_1,\dots,s_k maps to an abstract walk from α(s)\alpha(s) to an abstract goal that is, step by step, no more expensive (merged steps cost nothing):

  2. hα(s) ≤ c′(α(s),α(t))+hα(t) ≤ c(s,t)+hα(t)h^\alpha(s)\ \le\ c'\big(\alpha(s),\alpha(t)\big)+h^\alpha(t)\ \le\ c(s,t)+h^\alpha(t)

    Consistent. Abstract distances obey the triangle inequality, and one concrete edge (s,t)(s,t) maps to one abstract edge or a free loop:

  3. hβ(s)=hγ(α(s)) ≤ h′∗(α(s))=hα(s) ≤ h∗(s)h^\beta(s)=h^\gamma\big(\alpha(s)\big)\ \le\ h'^*\big(\alpha(s)\big)=h^\alpha(s)\ \le\ h^*(s)

    Coarser is weaker. Apply the first line to the abstraction γ\gamma of T′\mathcal T': its heuristic underestimates abstract costs, so

Three families cover most of practice:

  • Relaxations keep the states and add edges or lower costs (α=id\alpha=\mathrm{id}, E′⊇EE'\supseteq E, c′≤cc'\le c). Misplaced tiles and Manhattan distance are relaxations, and so is planning's delete relaxation, whose optimal cost h+h^+ is NP-hard to compute and is therefore approximated.
  • Projections forget variables, α(s)=s∣P\alpha(s)=s|_P for a pattern PP: in a sliding-tile puzzle, forget which tile is which outside PP. Tabulated, they are pattern databases.
  • Merge-and-shrink abstractions build α\alpha 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?

9⋅8=729\cdot8=72 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 hαh^\alpha for a projection onto a pattern PP 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 hh.

text
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.

DatabaseAbstract statesEntries
15-puzzle, 7 tiles, blank not tracked16!/9!16!/9!57,657,600
15-puzzle, 8 tiles, blank not tracked16!/8!16!/8!518,918,400
Rubik's cube, the 8 corner cubies8!⋅378!\cdot3^788,179,840
Rubik's cube, 6 of the 12 edge cubies12!6!⋅26\tfrac{12!}{6!}\cdot2^642,577,920
Positions times orientations (the last corner's twist is forced). Korf (1997) solved random cubes optimally with IDA* and the maximum of the corner table and two 6-edge tables; Korf and Felner (2002) split the 15-puzzle's tiles 7–8 into two additive tables.
DerivationProof, and the general principle
  1. h∗(s)=∑i=1kmi,mi=#{moves of tiles in Pi}h^*(s)=\sum_{i=1}^k m_i,\qquad m_i=\#\{\text{moves of tiles in }P_i\}

    Every move moves exactly one tile, so the moves of an optimal solution of ss split by pattern:

  2. ∑ihi(s) ≤ ∑imi=h∗(s)\sum_i h_i(s)\ \le\ \sum_i m_i=h^*(s)

    Projected onto PiP_i, the solution is an abstract solution that costs mim_i when only PiP_i's moves are charged, so hi(s)≤mih_i(s)\le m_i. Summing:

  3. ∑ihi(s) ≤ ∑ici(π)=c(π)⟹∑ihi ≤ h∗\sum_i h_i(s)\ \le\ \sum_i c_i(\pi)=c(\pi)\qquad\Longrightarrow\qquad\sum_i h_i\ \le\ h^*

    The principle is cost partitioning (Katz & Domshlak, 2008): split each action's cost as c=∑icic=\sum_ic_i with ci≥0c_i\ge0, and let each hih_i be admissible for the costs cic_i. For any solution path π\pi from ss,

  4. hall movesP1+hall movesP2 ≰ h∗in generalh^{P_1}_{\text{all moves}}+h^{P_2}_{\text{all moves}}\ \nleq\ h^*\quad\text{in general}

    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.

Check your understanding

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?

  1. The sum of all three tables
  2. max⁡(h1–7+h8–15, h1–5)\max\big(h_{1\text{–}7}+h_{8\text{–}15},\ h_{1\text{–}5}\big)
  3. The maximum of all three tables
  4. The third table alone, since it charges every move
Show the answer

B. max⁡(h1–7+h8–15, h1–5)\max\big(h_{1\text{–}7}+h_{8\text{–}15},\ h_{1\text{–}5}\big)

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 hh, A* must expand {s:g∗(s)+h(s)<C∗}\{s: g^*(s)+h(s)<C^*\}, so a pointwise larger heuristic never costs expansions (up to ties at f=C∗f=C^*). But expansions are not time. A PDB lookup is one memory access, a maximum over kk tables costs kk 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.

DerivationWhy heuristics shorten depth but keep the branching factor
  1. E(N,d,P) ≈ ∑i=0dNi P(d−i)E(N,d,P)\ \approx\ \sum_{i=0}^{d}N_i\,P(d-i)

    A node at depth ii survives the threshold-dd iteration iff i+h≤di+h\le d, that is h≤d−ih\le d-i, which holds for about a fraction P(d−i)P(d-i) of the NiN_i nodes:

  2. E ≈ ∑k=0db d−kP(k) = b d κd,κd=∑k=0db−kP(k)E\ \approx\ \sum_{k=0}^{d}b^{\,d-k}P(k)\ =\ b^{\,d}\,\kappa_d,\qquad \kappa_d=\sum_{k=0}^{d}b^{-k}P(k)

    In a brute-force tree with Ni≈biN_i\approx b^i, substitute k=d−ik=d-i:

  3. E(N,d+1,P)E(N,d,P) →  d→∞   b\frac{E(N,d+1,P)}{E(N,d,P)}\ \xrightarrow[\;d\to\infty\;]{}\ b

    Since P≤1P\le1, κd\kappa_d converges to a constant κ\kappa (for h=0h=0, κ=b/(b−1)\kappa=b/(b-1)). A heuristic therefore multiplies the work by a constant factor, like searching log⁡b ⁣(b(b−1)κ)\log_b\!\big(\tfrac{b}{(b-1)\kappa}\big) fewer levels, while successive iterations still grow by the brute-force factor:

Predict before you look

IDA* runs on a problem whose brute-force tree grows by b=6b=6 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

log⁡61000=ln⁡1000/ln⁡6≈6.91/1.79≈3.9\log_6 1000=\ln1000/\ln6\approx6.91/1.79\approx3.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 hFFh^{\mathrm{FF}} (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 hθ≈h∗h_\theta\approx h^* 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 hθh_\theta 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 16!/9!16!/9! 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 h∗−ch^*-c 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.

Question 1

You coarsen an abstraction by merging more concrete states into each abstract state. What happens to the heuristic?

  1. It can only stay the same or decrease, and it remains admissible and consistent
  2. It can only stay the same or increase
  3. It may become inadmissible, because merged states have different true costs
  4. 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 β=γ∘α\beta=\gamma\circ\alpha, then hβ=hγ∘α≤hαh^\beta=h^\gamma\circ\alpha\le h^\alpha: 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.

Question 2

When may the values of two pattern databases for the 15-puzzle be added without losing admissibility?

  1. Whenever both databases are admissible
  2. Never: only the maximum of two heuristics is admissible
  3. When the patterns are disjoint, whichever moves each database charges
  4. 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.

Question 3

A heuristic satisfies h=max⁡(h∗−1, 0)h=\max(h^*-1,\,0) everywhere. Which statement is true?

  1. A* expands only the states of one optimal path
  2. A* expands only linearly many states, since the error is constant
  3. A* must expand every state on every optimal path, which can be exponentially many
  4. 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 g∗+h<C∗g^*+h<C^*, 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).

Question 4

According to Korf, Reid and Edelkamp's analysis of IDA*, what does a better heuristic do asymptotically?

  1. It lowers the effective branching factor below the brute-force factor bb
  2. It divides the work by a constant factor, like searching a fixed number of levels less deep
  3. It makes the search polynomial whenever the heuristic is consistent
  4. 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

E≈bd∑kb−kP(k)E\approx b^d\sum_kb^{-k}P(k), and the sum tends to a constant, so successive iterations still grow by bb. 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).