A*, admissible, consistent heuristics

Question 1

A* search

Answer 1

• basically it can be looked at in two ways:
  1) it can be viewed as greedy best-first search that takes the cost to reach each node into account AS WELL as the heuristic function to determine which node to expand

2) it can be viewed as uniform cost search where f = g + h instead of just using g.
3) Greedy best first search + uniform cost search = A* search

Question 2

Admissible heuristics

Answer 2

for every node n,
h(n) <= h(n), where h(n) equals the true cost to reach the goal state from n.

obvious things that follow from this:
1) an admissible heuristic never overestimates the cost to reach the goal, i.e. it is optimistic

Question 3

Admissible optimality claim

Answer 3

If h(n) is admissible, A* using TREE-SEARCH is optimal

Question 4

Admissible optimality proof

Answer 4

proof:
Suppose some suboptimal goal G2 has been generated and is in the fringe. Let n be an unexpanded node in the fringe such that n is on a shortest path to an optimal goal G. (I think h(n) is implied to just be 0 here)

• f(G2) = g(G2) since h(G2) = 0
• g(G2) > g(G) since h(G) = 0
• f(G) = g(G) since h(G) = 0
• f(G2) > f(G) inferred from the above two
• h(n) f(n), and A* will never select G2 over n for expansion

Question 5

consistent heuristics

Answer 5

for every node n, every successor n’ of n generated by any action a
h(n) is less then or equal to the cost to get to node n’ from n plus h(n’) admissibility

Question 6

h consistent optimality claim and proof outline

Answer 6

claim: if h(n) is consistent, A* using GRAPH-SEARCH is optimal

proof:
1) prove f(n) is non-decreasing along any path

2) prove when n is selected for expansion, an optimal path to n has been found

proof step 3 to bring it home

Question 7

h consistent optimality proof step 1

Answer 7

step 1: f(n) is non-decreasing along any path
A heuristic is consistent if for every node n, every successor n’ of n generated by any action a,
h(n) = g(n) + h(n)
= f(n)

-i.e., f(n) is non-decreasing along any path

Question 8

h consistent optimality proof step 2

Answer 8

step 2: when A* expands n an optimal path to n has been found

proof by contradiction:

• Assume A* expands n but it has NOT found an optimal path to n
• let n’ be on the frontier and on a minimal path to n
• by step 1 f(n’) <= f(n)
• CONTRADICTION

Question 9

h consistent optimality proof step 3

Answer 9

step 3: for any goal G, f(G)=g(G):

• G is the first goal to be selected for expansion if it has minimal f, and, thus also minimal g.
• G is optimal.

Question 10

Optimality of A*

Answer 10

if h(n) = 0, A* is just uniform cost search

the optimal cost to get to the goal is C*

A* will expand every node with cost less than C, and maybe some equal to C, but none with greater cost, because to get anywhere with greater cost, it has to expand C* first.

Question 11

Properties of A*

Answer 11

Completeness: Yes (unless there are infinitely many nodes with f <= f(G) )

Time: exponential

space: keeps all nodes in memory
optimality: yes