Heuristics based on the Planning Graph
lev(p) : index of the first level at which p comes into 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)

SetLevel heuristic: h(S) = lev(S)
 Admissible but not very informed
Sum heuristic: h(S) = ?p?S lev({p}) Inadmissible
 Assumes that subgoals are independent
 Ineffective when there are strong negative subgoal interactions
 Poor solution quality with strong positive subgoal interactions

We experimented with a variety of more effective heuristics that consider both positive and negative interactions among subgoals