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 non-mutexed.

  • 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
  • Ineffective when there are strong negative sub-goal interactions
  • Poor solution quality with strong positive sub-goal interactions

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

Previous slide

Next slide

Back to first slide

View graphic version