Forward planning heuristics - hmax, hadd, hff

Question

I'm studying the forward planning heuristics hmax, hadd, and hff and I've found some resources online, but I really can't understand how they actually work.

Here the resources I've found so far:

http://icaps09.uom.gr/tutorials/tut1.pdf
(An ICAPS (International Conference on Planning and Scheduling) tutorial 2009 by Emil Keyder & Blai Bonet about "Heuristics For Planning", which explains hmax, hadd, hff, and h+.)

http://gki.informatik.uni-freiburg.de/papers/betz-helmert-icaps2009ws.pdf
(A scientific paper by Betz and Helmert, published at the German Converence on AI 2009 with the title "Planning with h+ in Theory and Practice", which is closely related to the other three.)

https://cw.felk.cvut.cz/wiki/_media/courses/a4m36pah/07_relaxation.pdf
(Another tutorial (of unknown source), which is also about the heuristics hmax, hadd, hff.)

Can you explain in a simpler way how they work? Thank you

Answer 1

I'm assuming that you already understand the basic ideas of planning. The hMax, hAdd and hFF algorithms are used to calculate a heuristic value for a given state on the planning graph, relative to the currently occupied state.

All three algorithms work by considering a relaxed version of the problem; specifically, a version that has been relaxed by removing the delete list for each applicable action. The effect of this can be summed up as once an atom is achieved (made true), it stays achieved.

---

hMax and hAdd work in very similar ways. The two algorithms work by considering a state in the planning graph, and using all applicable actions to make every atom in that state true. The cost of the actions required to make all atoms true is the basis of the heuristic value they produce.

For hAdd, the heuristic for a given state is the combined cost of achieving every atom in that state.

For hMax, the heuristic for a given state is the cost of the most expensive atom in that state.

Note that neither algorithm actually solves the relaxed problem, they just compute an estimate of how difficult a given state would be to achieve, relative to the current state.

hMax is admissible, whereas hAdd is not.

---

hFF is different, as it actually solves the relaxed problem. It does not attempt to find an optimal solution (see † below), but rather a solution that is reasonable.

To determine the heuristic of a given state (let's call it s), hFF finds a solution from the current state to the given state in the relaxed plan, which is often referred to as π(s). Once that solution has been found, the heuristic value given to the state s is the number of actions in the relaxed solution. This can be written as:

h(s) = |π(s)|

hFF is sometimes called the relaxed plan h. It is not admissible, but it is informative.

The method used to find a solution in the relaxed plan varies depending on the implementation of the hFF algorithm.

† hFF doesn't try to find an optimal solution because, whilst easier than planning for the original problem, computing an optimal solution is still far too difficult to use as a heuristic because it has to be computed for each state. Instead, it tries to find a reasonable plan, which is computationally much less expensive.

---

I really hope this has helped, and that I haven't confused you further.

I also really hope I'm right - I'm relativelty confident that I am, but I am fully open to being corrected. Having had this checked by an AI lecturer, I'm now confident that this is correct.