Cs188AI Wiki

General Info[]

What[]

A heuristic is a function that estimates how close a state is to a goal state

Details[]

  • A heuristic is designed for a particular search problem

Admissability[]

What[]

A heuristic is admissible if its estimate from a state to a goal state is not more than the actual cost from a state to the nearest goal state.

Definition[]

A heuristic is defined to be admissible if

where is the true cost from the current state to a goal state

Implications[]

  • For A Star Search, having an admissable heuristic guarantees optimality

Proving[]

Proving admissability can be done in two ways:

  1. Explain the relaxed problem
  2. Prove that the heuristic describes a lower bound on the problem. In other words, prove that there is no way to solve the search problem with lower cost than your heuristic predicts

Consistency[]

What[]

Consistency is saying that each arc in the graph must also be admissable. Imagine there are two nodes A and C. There is some real cost in moving from A to C. The heuristic estimates that the cost will be . The heuristic is consistent only if the difference is less than or equal to the actual cost.

Definition[]

Implications[]

  • A Star Graph Search is always optimal
  • The f value along a path will never decrease

Dominance[]

We see that h_a dominates h_c

What[]

An admissable heuristic dominates another admissable heuristic if for all states, it gives a higher value

Definition[]

where and are admissable heuristics

Implications[]

  • If an admissible heuristic dominates another admissable heuristic , then it is a better heuristic for using in A Star Search


Semi-Lattice[]

Demonstrating semi-lattice

What[]

Two admissable heuristics can form another admissable heuristic called a semi-lattice. The semi-lattice returns the higher value between the two heuristics given any state.

Definition[]

where is a semi-lattice

Implications[]

  • The max of two admissable heuristics is also admissable
  • Given two admissable heuristics that don't dominate each other, we can always make a better heuristic by simply taking the max of the two heuristic values