Heuristic Functions

Oracle function

• e(n) = g(n) + h(n)
• n is a node in the search tree
• g(n) is the distance from the root to the node
• h(n) is the real distance from the node to a minimum-depth goal node

Heuristic function

• e(n) = g(n) + h’(n)
• h’(n) is an estimate of h(n)
• If h’(n) is zero, how does the search behave?

Heuristic Adequancy

• An evaluation function is heuristically adequate if it always finds a goal node at the minimum depth from the start node.
• What if h’(n) > h(n) for some n?
• What if h’(n) ≤ h(n) for all n? (An admissible heuristic)
• Best-first search plus an admissible heuristic is called A*

Monotonicity (or Local Admissibility)

• Let n1 and n2 be search nodes, such that n2 is a successor of n1 after applying an action a.
• Two properties establish monotonicity:
  • h(goal) = 0
  • h(n1) - h(n2) ≤ 1

Variable-Cost Actions

• The first definition of monotonicity assumes that all actions have a distance of 1.
• Let d(n1, a, n2) be the distance from n1 to n2 when action a is applied.
• Monotonicity is now defined as follows:
  • h(goal) = 0
  • h(n1) - h(n2) ≤ d(n1, a, n2)

Informedness

Given two heuristics h’(n) and h’‘(n), if:

1. For all n, h’(n) ≤ h’‘(n)
2. There exists n such that h’(n) < h’‘(n)
3. For all n, h’‘(n) ≤ h(n) (i.e., h’‘(n) is monotonic)

then we conclude that h’‘(n) is better informed than h’(n).