Heuristic function

Denoted as h(n)

An estimator for the optimal cost from node n to goal state
- Exact cost cannot be determined unless a table of exact cost was precomputed
May not include history since its focus is on future cost of current node to goal

Properties

Admissibility
- Never overestimate the cost to reach a goal
- An optimistic heuristic
- Crucial as Dijkstra uses the foundation of shortest-path and an overestimation cannot guarantee that path is less than or equal to optimal path
- Suppose the optimal path is C* and the algorithm returns C with C>C*. Then some node on optimal path C* not expanded since the path was not discovered.
- Let g*(n) be the actual cost of optimal path from start to n, and h*(n) be the actual cost of n to goal
- f(n) > C* (since we assume that algorithm expanded a non-optimal node)
- f(n) = g(n) + h(n)
- f(n) = g*(n) + h(n) (n is on optimal path)
- f(n) \le g*(n) + h*(n) (h(n)\leh*(n) from admissibility where heuristic cannot overestimate)
- f(n) \le C*
- Proved by contradiction. A sub-optimal cannot be returned because node n must lie on the optimal path
Consistency
- For every node n, and successor n' generated by action a
- h(n) \le cost(n,a,n') + h(n')
  - h(n) estimation will not exceed true cost and the estimation of the successor
- Triangular inequality

Links: