A* optimality of the expanded node

Question

Suppose I have a admissible and consistent heuristic.

Is it true, that when I expand a node, I have guaranteed that the path I found to this node is optimal?

Look at this pseudocode from wikipedia:

function A*(start,goal)
 closedset := the empty set    // The set of nodes already evaluated.
 openset := {start}    // The set of tentative nodes to be evaluated, initially containing the start node
 came_from := the empty map    // The map of navigated nodes.

 g_score[start] := 0    // Cost from start along best known path.
 // Estimated total cost from start to goal through y.
 f_score[start] := g_score[start] + heuristic_cost_estimate(start, goal)

 while openset is not empty
     current := the node in openset having the lowest f_score[] value
     if current = goal
         return reconstruct_path(came_from, goal)

     remove current from openset
     add current to closedset
     for each neighbor in neighbor_nodes(current)
         tentative_g_score := g_score[current] + dist_between(current,neighbor)
         if neighbor in closedset
             if tentative_g_score >= g_score[neighbor]
                 continue

         if neighbor not in openset or tentative_g_score < g_score[neighbor] 
             came_from[neighbor] := current
             g_score[neighbor] := tentative_g_score
             f_score[neighbor] := g_score[neighbor] + heuristic_cost_estimate(neighbor, goal)
             if neighbor not in openset
                 add neighbor to openset

 return failure

I suppose it should be true. Because of this:

if current = goal
     return reconstruct_path(came_from, goal)

If it wasn't true then this test would not guarantee me that the solution is optimal right?

What I don't get and the reason I am asking this question is this:

if neighbor in closedset
         if tentative_g_score >= g_score[neighbor]
             continue

If the neighbor is in closed list, it means that it has already been expanded. Why are they testing the scores then? Why would not the next condition work?

if neighbor in closedset
         continue

Answer 1

Please, let me contribute to this question with some observations. Most of them refer to the reply by Shaull.

First, and foremost, I found that the answer provided to the question pointed to by Shaull is a little bit strange. The property of monotonicity is defined there in a strange way and indeed, I posted a question ---note I am not saying that's wrong but just strange to me and not very common and frankly speaking, I am a little bit suspicious that it might be wrong.

In the original question I see various questions so let's go by steps.

First, consistency is usually defined as follows [Pearl, 1984]: a heuristic $h(n)$ is consistent if and only if $h(n) \leq c(n,n') + h(n')$ for every pair of nodes $n$ and $n'$ in the state space, where $c(n,n')$ stands for the cost of the shortest path joining $n$ and $n'$. I think it is clear that admissibility (i.e., $h(n) < h^*(n)$ where $h^*(n)$ is the true optimal cost of node $n$) is immediately implied from consistency if $h(t)=0$ where $t$ is the goal node. For this and other definitions see "Common Misconceptions Concerning Heuristic Search".

So far, no need to say "Suppose I have a admissible and consistent heuristic". It just suffices saying "Suppose I have a consistent heuristic".

Now, regarding your first question. If you have a consistent heuristic, there is no need to reopen nodes or, equivalently, everytime a node $n$ is expanded by A$^*$, the path discovered to it is necessarily optimal.

Proof: Let us assume this is not true and after expanding node $n$ through a path $\pi\langle s, n_1, n_2, \ldots, n_k, n\rangle$ there was another path $\pi'\langle s, n'_1, n'_2, \ldots, n'_l, n\rangle$ such that $g_{\pi}(n) > g_{\pi'}(n)$. Note that $f(n)=g(n)+h(n)$ so that from our assumption $f_{\pi}(n) > f_{\pi'}(n)$ since $h(n)$ takes the same value in spite of the path followed to node $n$. But this is impossible, since $n$ was expanded as a successor or the path $\pi$ so that $f_{\pi}(n) \leq f_{\pi'}(n)$. Of course, you might say that the error was committed somewhere along the path $\pi'$ because a node $n'_i$ had such a large value of $h(n'_i)$ that it was delayed in the OPEN list, but this is impossible by definition of consistency.

From here it should be obvious that the condition:

if current = goal return reconstruct_path(came_from, goal)

works smoothly since once the goal is about to be expanded it is guaranteed that the path discovered to it is optimal.

Regarding your second question, the reason of your post, Shaull already answered in the footnotes of his reply: if the heuristic function is consistent then nodes are never reopened and your condition:

if neighbor in closedset continue

is enough. However, in practice, it is just simply substituted by a different condition: when expanding a node, their children are only added to OPEN if it was never expanded (not in closedset) and also, it is not already in OPEN (not in openset). With the appropriate structures for managing the open and closed list this can be done very fastly. This trick make it unnecessary to use that statement.

But again, bear in mind what Shaull says, the pseudocode you show in your post is intended to work also with inconsistent heuristic functions. What you are asking for are, indeed, simplifications that result from the assumption of consistency.

Hope this helps,

[Pearl, 1984] Judea Pearl. Heuristics. Addison-Wesley. 1984

Answer 2

The A* algorithm is a non exhaustive search algorithm, it does not check all the possibilities, but rests on the hypothesis that the heuristic will consistently provide accurate estimates of the cost of reaching the goal node from a given node in the graph. The algorithm will skip certain possibilities because of their costs, yet if the estimate is wrong, there might be a better path going through that list of skipped nodes. The garantee is therefore dependent of the heursitic garantee.

Regarding the algorithm presented, indeed the test is wrong. Any node in the closed list is there because it has been fully explored and cannot yeld any new path.

Answer 3

This would depend on the heuristic. Consider a graph where $start\to a\to d\to end$ and also $start\to b\to c\to d\to end$. Now assume you have a bad heuristic that prefers that gives $b,c,d$ much higher scores than $a$, then you would reach $end$ in a non-optimal path. In particular, when you open $d$, you are in a non-optimal path.