Abstraction heuristic ($h_{\mathrm{abs}}$)

Map original states to simpler abstract states, include every projected original transition at no greater cost, and map original goals to abstract goals. An original goal-reaching graph path then projects to an abstract goal-reaching walk, so the exact abstract distance is an admissible heuristic. A pattern database stores such distances for repeated lookup.

A table of precomputed exact abstract goal distances used as an abstraction heuristic. Retaining a subset of the disks of a Tower of Hanoi instance gives a smaller abstract puzzle: moving an ignored disk does not change the abstract state, and moving a retained disk projects to a legal abstract move. Taking maxima of pattern database estimates preserves admissibility; summing them requires an additional cost-partition argument.