[Solved]: A* optimality of the expanded node

Problem Detail: 

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 

Asked By : Honza Brabec

Answered By : Carlos Linares López

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/10152

 Ask a Question

 Download Related Notes/Documents