3
$\begingroup$

In "AI: A Modern Approach", 4th edition, by Russell and Norvig, they give a purported proof that A* is cost-optimal for any admissible heuristic. The given proof seems most certainly wrong. They want to show that all nodes on the optimal path are expanded. Towards a contradiction, they consider a node n on the optimal path that is not expanded, and say that its evaluation f(n) must be strictly greater than the optimal cost C*, for "otherwise, n would have been expanded".

In other words, they claim that a node n with f(n) less or equal than C* will be expanded. That claim is obviously not true in general? Take the heuristic that is identically zero; it is trivially admissible. Now consider a model with initial state A, which can transition to states B, C and D with costs 1, 2 and 3, respectively. Then B, C and D all transition to the goal state E, all with cost 3. The A* algorithm will simply expand B, then E. So it certainly finds an optimal path. Note that states C and D have no chance to be expanded. Nevertheless, they have evaluations 2 and 3, which are both less than 4, the optimal cost. So the claim does not hold.

I would like confirmation of my analysis - is the proof given in the book incorrect?

Just to be clear, I am not saying that A* is not always cost-optimal for any admissible heuristic, although I would love to see a reference (I've found research papers but they are about other notions of optimality, such as number of nodes expanded.) I am just saying that the proof given in the book is wrong.

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ Could you be clearer about what your question is please. It appears you want a critique of whether your counter-example is valid, but you don't actually say. $\endgroup$
    – Neil Slater
    Commented Feb 4, 2022 at 21:57
  • 2
    $\begingroup$ Indeed I just want confirmation that the proof given in the book is incomplete. In the meantime I understood that the cost-optimality (confusingly also called admissibility) of A* under an admissible heuristic is quite easy to see, and outlined on this forum by John Doucette $\endgroup$
    – vdbuss
    Commented Feb 5, 2022 at 9:53
  • $\begingroup$ I have folded that into your question. You can treat it as a suggestion of how to phrase "It (doesn't) work this way - am I right?" questions on the site. Feel free to roll back if you think it changes the question too much. I am keen though that you use question phrasing and not a general "looking for comments" ending (whcih would be more appropriate on a forum) $\endgroup$
    – Neil Slater
    Commented Feb 5, 2022 at 12:32

1 Answer 1

Reset to default
2
$\begingroup$

You did not compute $g(n)$ correctly.

A* expands according to the evaluation function $f(n) = g(n) + h(n)$, where $g(n)$ is the cost of the path from the start node to $n$. Initially, you add $A$ to the frontier $F = \{A \}$. Then you pop from the frontier according to $f(n)$, so you pop $A$, and add its children to the frontier, which are $B$, $C$ and $D$, i.e. $F = \{B, C, D \}$. Now, you have

  1. $f(B) = g(B) + 0 = 1$
  2. $f(C) = g(C) + 0 = 2$
  3. $f(D) = g(D) + 0 = 3$

So, you pop $B$ from the frontier and explore it, i.e. add $E$ to the frontier, so $F = \{C, D, E \}$. Now, you have

  1. $f(C) = g(C) + 0 = 2$
  2. $f(D) = g(D) + 0 = 3$
  3. $f(E) = g(E) + 0 = 1 + 3 = 4$

So, you pop $C$. And so on.

(I didn't want to give more answers, but, hey, I like A*)

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .