6.034 Artificial Intelligence - Recitations, fall 2004 online slides on search

Next: Effect on Search Cost Previous: Reasons

Informedness (and 'dominance')

If h1 and h2 never overestimate distance to the closest goal,

and

For all x, h1(x) $>$ h2(x), then h1 ``dominates'' h2
h1 is ``more informed'' than h2

For example, two heuristics for robot motion planning are:

h1(x): \(\mid x_{goal} \;-\; x \mid\)

h2(x): Euclidean distance \(\sqrt{(x_{goal} \;-\; x)^2 \;+\; (y_{goal} \;-\; y)^2}\)

Thus h2 dominates h1