Relaxation heuristic

A heuristic function obtained by solving an easier problem that permits every original transition and possibly additional ones, with original transitions costing no more in the easier problem. Every original solution remains available, so the easier optimum is an admissible heuristic.

If $h$ is the exact distance to the relaxed goal set, each original transition also gives $h(s)\le c(s,a,s^{\prime })+h(s^{\prime })$ by taking that transition and then a relaxed optimal continuation. Thus this construction gives a consistent heuristic when original goals have relaxed distance zero. For a four-direction grid walk, deleting obstacles gives Manhattan distance; deleting a pursuer's capture constraint supplies another relaxation. The resulting estimate can remain finite when the original goal is unreachable.

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.

For positive-precondition STRIPS with a positive conjunctive goal, remove every delete effect and use the exact shortest relaxed plan cost. Every original plan still succeeds in the relaxed model because facts can only accumulate, so its relaxed optimum is an admissible heuristic. The cost of an arbitrary relaxed plan is an upper bound on the relaxed optimum and need not be an admissible heuristic for the original problem.