Adjusted Sum Heuristic
Adjust the Sum heuristic to take positive and negative interactions
HAdjSum2M(S) = length(RelaxedPlan(S)) + max p,q?S d(p,q)
Relaxed Plan computed by ignoring all the mutex relations
Second component is an approximation of a penalty induced by ignoring the negative interactions
Degree of interaction
- ?(p,q) = lev({p,q}) - max{lev(p), lev(q)}
- ?(p,q) = ¥ if p and q are static mutex
- 0 < ?(p,q) < ¥ if p and q are level specific mutex
- ?(p,q) = 0 otherwise (p and q are non-interacting)
[Nguyen & Kambhampati, AAAI 2000]
Shown to be quite effective