Is Wikipedia's Astar reference implementation incomplete? It seems to omit properly updating cheaper paths

Question

I want to implement A* and I looked to Wikipedia for a reference.

It looks like it can fail in the following case. Consider three nodes, A, B, and C.

START -> A -> C -> GOAL
     |   ^
     \-> B

The path costs are:

START -> A : 10
START -> B : 1
B -> A     : 1
A -> C     : 100
C -> GOAL  : 100

Clearly the solution is START -> B -> A -> C -> GOAL but what happens if the heuristic lets us expand A before expanding B?

Our heuristic costs are as follows (note these are all underestimates)

A -> GOAL : 10
B -> GOAL : 50

When A is expanded, the true cost to C will turn out out to be higher than B's heuristic cost, and so B will be expanded before C.

Fine, right?

The problem I see is that when we expand B and replace the datum "A comes from START with cost 10" to "A comes from B with cost 2" we aren't also updating "C comes from A with cost 110" to "C comes from A with cost 102". There is nothing in Wikipedia's pseudocode that looks like it will forward-propagate the cheaper path. Now imagine another node D which can reach C with cost 105, it will erroneously override "C comes from A with cost 110".

Am I reading this wrong or does Wikipedia need to be fixed?

Answer 1

If you are using graph search, i.e. you remember which nodes you visit and you don't allow revisiting the nodes, then your heuristic is not consistent. It says in the article, that for a heuristic to be consistent, following needs to hold:

h(x) <= d(x, y) + h(y) for all adjacent nodes x, y

In your case the assumption h(B) = 50 is inconsistent as d(B -> A) + h(A) = 1 + 10 = 11. Hence your heuristic is inconsistent and A* wouldn't work in this case, as you rightly noticed and as is also mentioned in the wikipedia article: http://en.wikipedia.org/wiki/A%2a_search_algorithm#Properties.

If you are using tree search, i.e. you allow the algorithm to revisit the nodes, the following will happen:

Add A and B to the queue, score(A) = 10 + 10 = 20, score(B) = 1 + 50 = 51.

Pick A from queue as it has smallest score. Add C to the queue with score(C) = 10 + 100 + h(C).

Pick B from the queue as it is now the smallest. Add A to the queue with score(A) = 2 + 10 = 12.

Pick A from the queue as it is now again smallest. Notice that we are using tree search algorithm, so we can revisit nodes. Add C to the queue with score(C) = 1 + 1 + 100 + h(C).

Now we have 2 elements in the queue, C via A with score 110 + h(C) and C via B and A with score 102 + h(C), so we pick the correct path to C via B and A.

The wikipedia pseudocode is the first case, i.e. graph search. And they indeed state right under the pseudocode that:

Remark: the above pseudocode assumes that the heuristic function is monotonic (or consistent, see below), which is a frequent case in many practical problems, such as the Shortest Distance Path in road networks. However, if the assumption is not true, nodes in the closed set may be rediscovered and their cost improved. In other words, the closed set can be omitted (yielding a tree search algorithm) if a solution is guaranteed to exist, or if the algorithm is adapted so that new nodes are added to the open set only if they have a lower f value than at any previous iteration.