A heuristic is a function that estimates how close a state is to a goal state
- A heuristic is designed for a particular search problem
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.
A heuristic is defined to be admissible if
where is the true cost from the current state to a goal state
- For A Star Search, having an admissable heuristic guarantees optimality
Proving admissability can be done in two ways:
- Explain the relaxed problem
- 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 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.
- A Star Graph Search is always optimal
- The f value along a path will never decrease
An admissable heuristic dominates another admissable heuristic if for all states, it gives a higher value
where and are admissable heuristics
- If an admissible heuristic dominates another admissable heuristic , then it is a better heuristic for using in A Star Search
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.
where is a semi-lattice
- 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