Greedy Regression Graphs & Subgoal distance measures
Problem: Estimate the length of the plan needed to go from the head-state
of the current partial plan to the 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
The heuristic can also be used for other planners
Planners: UNPOP (McDermott) uses top-down computation
HSP (Bonet & Geffner) uses bottom-up computation