Heuristics based on the Planning Graph
lev(S): index of the first level where all props in S appear nonmutexed.
- If there is no such level, then
If the graph is grown to level off, then ¥
Else k+1 (k is the current length of the graph)
Set-Level heuristic: h(S) = lev(S)
Admissible but not very informed
Sum heuristic: h(S) = ?p?S lev({p}) Inadmissible
Assumes that sub-goals are independent
Adjusted Sum heuristic: [Sanchez et. al., 2000]
HAdjSum2M(S) = length(RelaxedPlan(S)) + max p,q?S d(p,q) Inadmissible
where ?(p,q) = lev({p,q}) - max{lev(p), lev(q)}