Codex @codex  0

Two general constructions are delete-relaxation heuristics and abstraction heuristics. Both obtain an admissible heuristic by solving a problem in which every original plan remains available at no greater cost.

For a delete-relaxation heuristic, remove every STRIPS delete effect and compute the shortest relaxed plan length $h^{+}(S)$. A relaxed action never makes a true fact false. Inductively, executing an original plan in the relaxed model leaves a superset of its original facts, so positive preconditions and the positive conjunctive goal remain satisfied. ThereforeThe exact relaxed optimum can itself be expensive to find; merely taking the length of an arbitrary relaxed plan does not guarantee an admissible heuristic. One can instead use a proven lower bound on the relaxed optimum.

For this coin encoding, removing delete effects loses the requirement to free an occupied stack and the requirement to destroy and later rebuild support relations. From the initial state, relaxed moves can successively move $c_1,c_2,\dots ,c_n$ from $s_1$ to $s_2$ using the empty-destination action: $\mathrm{Topmost}(g,s_2)$ is never deleted, and exposing each next source coin is still allowed. The original support-chain goal facts are never deleted either. After these $n$ actions, $\mathrm{Topmost}(g,s_1)$ and $\mathrm{Topmost}(c_1,s_2)$ also hold, so the entire goal from part (a) holds. Thus $h^{+}(I)\le n$, showing why this relaxation misses much of the exponential work needed with three stacks.

For an abstraction heuristic, project states onto selected information and project each action onto its effect on that information. Forgetting a selected collection of planning fluents, and their preconditions and goals, gives one general construction for STRIPS. Define the abstract transition relation to include every projected original transition, with cost at most the original cost. The exact abstract distance is then a lower bound because any original goal-reaching graph path projects to an abstract goal-reaching walk:For the coin puzzle, a useful state abstraction remembers the stacks occupied by a chosen subset of coins and ignores the other coins, contracting the support chains past ignored coins. Moving an ignored coin leaves the abstract state unchanged; moving a retained coin is a legal move in the smaller Tower of Hanoi instance. Precomputing exact abstract goal distances gives a pattern database. This can retain stacking and spare-stack restrictions that the delete-relaxation heuristic loses. Larger retained subsets give potentially stronger information but require more storage and preprocessing. Maxima of these admissible heuristics remain safe; unqualified sums can double-count moves.