4
$\begingroup$

How does one prove that a suggested heuristic is admissible? Is this even possible?

For Example: Let's say I have the game Free Cell.
Rules: https://en.wikipedia.org/wiki/FreeCell

How can I prove that the number of cards not in the foundation plus every out of order card is an admissible heuristic?

$\endgroup$
1
$\begingroup$

Proving a heuristic is admissible usually means proving two things:

  1. it follows the triangular inequality principle

  2. given the same preconditions, the heuristic never overestimates the actual solution

$\endgroup$
1
$\begingroup$

In general, it is usually the other way round, i.e., one applies one technique which ensures that the resulting heuristic will be admissible instead of devising an idea and then proving it is admissible. Nonetheless, the question is pretty interesting, but let me please start by introducing the general idea.

There are several techniques to derive admissible heuristics. As mentioned by Emanuele Giona this implies that the heuristic function will never overestimate the cost of an optimal solution from the current node. Thus, all techniques rely in one way or another on the concept of relaxation. A problem is said to be relaxed if it makes it easier to compute an optimal solution even if the resulting problem is not like the original one. For example, in the sliding-tile puzzle you might relax the condition that the blank tile can only move to adjacent locations and thus, that it can be swapped with any tile on the board; in the Towers of Hanoi you could relax the only operator in the domain to say that it is possible for example to take any disc in any peg and not necessarily the one on the top. Other relaxations are possible. For example, in an instance of an arbitrary cost domain, you could relax the cost of the operators to say that all of them cost one unit (and thus, the cost of the relaxed optimal solution would be its length).

The first idea to derive heuristic functions was proposed by Judea Pearl at the end of the 80s and his technique is known as Constraint Relaxation as it relaxes the constraints of the operators. If you want, for example, to relax the cost of the operators, then some heuristics are obtained by solving Linear Programming Tasks. Other slightly more involved ideas are abstractions which map your problem into a relaxed instance where some constants of your problem have been ignored (for example, in the Rubik's Cube by saying that all corner qubies are indistinguishable among them). Examples of abstractions are Pattern Databases and Merge-and-Shrink heuristics ---the latter proven to be a super-class of the former.

So far, if you are facing a new problem, the natural approach consists of applying any or some of these techniques. They all guarantee by design that the resulting heuristic function is necessarily admissible. There are interesting theoretical properties that prove this, e.g., while applying an abstraction it just suffices to prove that the abstraction performed is a homomorphism.

Now, to go the other way round (i.e., from an intuition of a possibly admissible heuristic function to prove it is indeed admissible) my suggestion would be to prove that applying any of this techniques, the devised heuristic function results. In your specific case, the number of cards not in the foundation is clearly an admissible heuristic function that results from Constraint Relaxation as it is necessary to reveal those cards in order to finish the game. I do not know very well the game of FreeCell and so, I beg your pardon for not delving deeper into your possible heuristic but this is, in general, the way of thinking.

Finally, I'd like to highlight that there are even domain-independent admissible heuristics (obtained automatically with the usage of any of the previous techniques) for the specific case of the game of FreeCell as this is one of the standard domains in the International Planning Competitions.

Hope this helps,

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.