[SOLVED] Why does A* with admissible non consistent heuristic find non optimal solution?

Why does A* with admissible non consistent heuristic find non optimal solution?

I know that A* with admissible non consistent heuristic will not find optimal solution but I am struggling with finding example when will it happen.

I can not find example because of this thought - after inserting our goal node (with non optimal f(n)) to the priority queue, priority queue must also contains node e.g. node_1 which is on the optimal path. f(n) of node_1 in priority queue must be less than f(n) of our goal node, since we are using admissible heuristic. That is why node_1 will be dequeued earlier and after some iterations of A* (using the same idea) goal_node will get dequeued later after optimal path is found.

Where am I thinking wrong ? Can someone give me concise example of simple graph when A* with admissible non consistent heuristic will find non optimal path ?

Thank you.

Solution

Here's an example of a graph where we get the wrong answer with an inconsistent heuristic. Here, heuristics are shown with parentheses near each node and edge costs written next to the edges:

     (8)
      A
     / \
+1  /   \ +3
   /     \   
  B ----- C ----- D
(7)  +1  (0)  +6  (0)

Here, the optimal path from A to D is A - B - C - D for a total cost of 8. But let's see what A* would do:

Starting at A, the options are to go A - B for a cost plus heuristic of 8, or to go from A - C for a cost plus heuristic of 3. So we pick A - C.
Now, our options are to expand out A - B for a cost plus heuristic of 8, or expand C - D for a cost plus heuristic of 9. So we pick A - B.
We've already closed out C by the earlier path, so we don't consider the edge B - C. Instead, we pick C - D for a cost of 9.
Overall, we found the path A - C - D. Oops.

The next question is how on earth you'd find an example like this one, and for that, a perspective that I think is quite useful for thinking about how A* works is the following:

Running A* on a graph whose edges have costs c(u, v), using a heuristic function h(v), is equivalent to running Dijkstra's algorithm on a graph where the cost of an edge (u, v) is c(u, v) + h(v) - h(u).

In other words, you can think of what A* is doing as though you were running Dijkstra's algorithm, tweaking the cost of each edge by adding in the change in the heuristic value across each edge.

The reason this is useful is that Dijkstra's algorithm, famously, will give back the wrong answer in cases where there are negative edges in the graph. So we can ask - when we change the edge costs to be c(u, v) + h(v) - h(u), could we ever end up with a negative cost? In other words, what would have to happen to ensure that

c(u, v) + h(v) - h(u) ≥ 0?

With a quick rearrangement, you might notice that this happens precisely if

c(u, v) + h(v) ≥ h(u)

or, equivalently, uf

h(u) ≤ c(u, v) + h(v).

And hey! That's the definition of a consistent heuristic.

What this means is that things can go wrong using A* with an inconsistent heuristic in exactly the same way that things can go wrong with Dijkstra's algorithm using negative edge weights. You'd (mostly likely) run into an issue where you find a suboptimal path to some intermediary node on the path to the goal, and from there get the wrong answer.

I ended up making the above graph where A* fails by starting with this graph where Dijkstra's gets the wrong answer, then reverse-engineering a heuristic that made the edge costs all positive:

    A
+0 / \ -5
  /   \
 B --- C --- D
    -6    +6

Here, the path Dijkstra's would find from A to D is the path A - C - D for a cost of 1, rather than the path A - B - C - D for a cost of 0. That's the same wrong path as in the A* example up top.