Week 3 - A* Algorithm
Aims
- A* search algorithm
- How to invent admissible heuristics
A* Search
- UCS minimizes the cost so far
g(n) - GS minimizes the estimated cost to the goal
h(n) - A* combining UCS and GS
- Evaluation function:
f(n)=g(n)+h(n)-g(n) = cost so far to reach n-h(n) = est. cost from n to goal-f(n) = est. total cost of path through n to the goal
The idea is that we take into account both the cost and estimated cost and combine them to decide which nodes to add to the fringe queue!
BFS and UCS Special Case
- BFS is a special case of A* when f(n)=depth(n)
- BFS is also a special case of UCS when g(n)=depth(n)
- UCS is a special case of A* when h(n)=0
Admissible Heauristic
- Heuristic
h(n)is admissible if for every node n: -h(n) <= h*(n)whereh*(n)is the true cost to reach a goal fromn- The estimate to reach the goal is smaller or equal to the true cost to reach the goal - Admissible heuristics are
optimistic- they think that the cost of solving the problem is less than it actually is. - heuristic never overestimates actual cost -> it is admissible
Theorem
If h is an admissible heuristic than A* is complete and optimal.
How to check?
See if the estimated cost for a node is <= the actual cost from that node to the goal node.
Optimality of A* - Proof
Compare f(G2) and f(G)
- f(G2)=g(G2)+h(G2) (by definition) = g(G2) as h(G2)=0, G2 is a goal
- f(G)=g(G)+h(G) (by definition) = g(G) as h(G)=0, G is a goal
- g(G2)>g(G) as G2 is suboptimal
- => f(G2)>f(G) by substituting 1) and 2) into 3)
- f(n)=g(n)+h(n) (by definition)
- h(n) <= h(n) where h(n) is the true cost from n to G (as h is admissible)
- => f(n)<=g(n) + h*(n) (5 & 6)
- = g(G) path cost from S to G via n
- g(G) = f(G) as f(G)=g(G)+h(G)=g(G)+0 as h(G)=0, G is a goal
- => f(n)<=f(G) (7,8,9)
- Thus f(G)<f(G2) (4) & f(n)<=f(G) (10)
- f(n)<=f(G)<f(G2) (10, 4)
- f(n)<f(G2) => n will be expanded not G2; A* will not select G2 for expansion
Dominance
Two admissibleheuristics h(1) and h(2)
h[2]dominatesh[1]if for all nodesnwe haveh[2](n) >= h[1](n)