Distance Heuristics from Relaxed Problems
Problem: Estimating the distance of a (partial) state from the initial (or goal) state
Solution: --Relax the problem by assuming that all subgoals are
independent (ignore +ve / -ve interactions between actions)
--Solve the relaxed problem and use the length of the solution as
Properties: The heuristic is neither a lower bound (-ve interactions) nor an
upper-bound (+ve interactions).
--leads to inoptimal solutions (in terms of plan length)
>>Possible to reduce inoptimality by considering interactions
History: First used in IxTET [Ghallab et. al. 1995]
independently re-discovered in UNPOP [McDermott, 1996]
independently re-re-discovered in HSP [Bonet & Geffner, 1997]