## 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)`

where `h*(n)`

is the true cost to reach a goal from `n`

- 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]`

dominates `h[1]`

if for all nodes `n`

we have `h[2](n) >= h[1](n)`