I'm having trouble figuring out how to create admissible heuristics from cost functions. For example, if I was trying to create an admissible heuristic from a cost function that takes in starting position and ending position and returns the cost based on differences in height, I don't understand how to create an admissible heuristic from such a basic function.
Any help would be greatly appreciated.
Most beginners in the field see heuristics construction more as an art than a science. While I am not claiming here that there is a truly scientific (or even computable) method to derive them, I am sure they are not an art and we know about specific procedures to derive them (some of which are truly computable). In any case, we do not consider the differences in cost between the goal and start states as you suggest in the question. In all cases, admissible heuristics are obtained after relaxing any component in the problem formulation.
Let me just introduce you to three different methods to compute admissible heuristics: constraint relaxation, pattern databases and max heuristics. First, I will just introduce the overall idea. Next, I will provide further details of every technique. I will try to mention also some of the most relevant works that went along any of these lines including merge-and-shrink and Linear Programming.
In all cases, I will refer to the definition of state spaces which consist of two main ingredients:
Also, I will be using the $N$-puzzle as a running example. The proper definition of a state space in the $N$-puzzle is as follows:
Please, be aware of the following: these techniques are not so simple that I could fully explain them in detail in a single response so that, unfortunately, my explanations will be rather incomplete
Constraint relaxation [Judea Pearl. Heuristics. Addison-Wesley, 1984] Judea Pearl proposed to pay attention to the constraints of the problem (and there should be some, otherwise we would not have an optimization problem), and then to relax a subset of them so that the resulting problem could be optimally solved. The optimal cost of the so-called relaxed problem can be easily proved to be an admissible estimate to reach the goal state. The constraints are usually found (but not only) in the pre-conditions implemented in the operators.
Take the $N$-puzzle. In this case, the constraints are found in the operator move. How would you program such a function? Well, most likely you would verify that $\pi[i]=0$ (i.e., $i$ is the blank location) and that $i$ and $j$ are either vertically or horizontally adjacent locations. Now, select either one of these constraints or both and relax them.
For example, relax both and consider now the resulting (relaxed) problem. For any state, how many moves does it take to get to the target node? If you are not constrained (and this is the point) to consider adjacent locations or the fact that you have to move the blank then you can swap any pair of locations. The optimal solution of the relaxed problems consists just of swapping the misplaced tiles.
Another example, relax only the first one. In this case, you are forced to swap adjacent locations but you are free to ignore the role of the blank tile. Clearly, the optimal solution consists of the sum of the minimum number of horizontal and vertical moves to place every misplaced tile in its goal location. This is known as the Manhattan distance.
In general, the heuristics that relax less constraints produce better estimations and are prefered.
Pattern databases [Culberson, J. C., Schaeffer, J. 1998. Pattern Databases. Computational Intelligence 14(3): 318-334] Constraint relaxation is just a general procedure that you, as an optimizer, have to follow in order to derive an admissible heuristic that you hard-code in your programs. Pattern databases are, instead, computable means to derive automatically the heuristic value of a lot of different configurations which are then stored in a large table.
I will not go here through more detailed explanations and I do suggest you instead to have a look at Need a practical solution for creating pattern database(5-5-5) for 15-Puzzle I am also providing a reply there but I do strongly suggest you to have a look at the response by Shashwat which is more detailed and uses the $N$-puzzle instead for explaining the main ideas. If you are interested in getting the source code for creating Pattern Databases, please e-mail me ([email protected]).
In case you are interested in the current state of the art of admissible heuristics in Automated Planning (introduced next) I do recommend you to have a look at merge-and-shrink (which do generalize Pattern Databases). A nice discussion is offered in: Malte Helmert, Patrik Haslum, Jörg Hoffmann and Raz Nissim. Merge-and-Shrink Abstraction: A Method for Generating Lower Bounds in Factored State Spaces. Journal of the ACM. 2013 (which was accepted at the time of writing but has not seen the light yet as far as I know).
Also, there has been some work on using Linear Programming Tasks to get the optimal cost of the relaxed problems:
(NOTE: all this people are really nice, so that if you contact them to get a copy of the paper to appear it is very likely that they will send it to you. The other option is to wait for ICAPS 2014 to take place and then to download the papers: they are absolutely free).
Note please that, in this context, Linear Programming Tasks are used just to derive optimal costs of the relaxed problems precisely in the same way noted by Raphael: you first relax some constraints (according to any procedure) and then you set up a LP task to derive the optimal cost. I do fully believe that this is a hot topic in the field that will get more and more attention.
Max heuristics [Blai Bonet and Héctor Geffner. Planning as Heuristic Search: New Results. Proc. 5th European Conf. on Planning (ECP). Durham, UK. 1999. Springer LNCS 1809. Pages 359-371] The two previous methods for deriving (either automatically or not) admissible heuristics were motivated by the need of creating domain-dependent solvers. However, what if you want to create a single solver that is expected to optimall solve any problem (with some constraints, of course, and not just saying that "The Answer to life, the universe and everything is 42" :) )? This field is known as Automated Planning In this case we relax the reachability analysis by ignoring the delete effects (i.e., the fact that when swapping two locations they are removed from their initial locations; indeed, they are preserved so that the same tile appears in various places at the same time in the relaxed problem).
We just assume that all actions can be executed in parallel and compute the minimum cost to reach every literal (i.e., any atomic observation of our state formulation such as tile 6 is in location 2) from any other literal. You can certainly assume that actions have to be executed in sequence. In this case, the resulting heuristic is known as h add but it is not admissible so I left out of the discussion.
I am just leaving a lot of details out of the discussion here and I do recommend you to have a look at the paper I am just referencing. This is a simple, very simple idea.
Hope all of this helps,
