Best-First-Search: Why are nodes with higher path costs explored again?

Question

I am reading the book of Russell & Norvig: AIMA and wonder, why A* (Best-First-Search with f=g+h) does explore a node, even if it has already been explored with a lower PATH-COST.

Following the example from John Levin, Best-First-Search expands the following paths:

 ['S'],
 ['S', 'A'],
 ['S', 'A', 'B'],
 ['S', 'B'], <- unnecessary since the B before has lower path costs
 ['S', 'D'],
 ['S', 'D', 'C'],
 ['S', 'A', 'B', 'C'], <- unnecessary since the B before has lower path costs
 ['S', 'D', 'E'],
 ['S', 'D', 'C', 'G']

IMHO node <- POP(frontier) should happen until node.PATH-COST is lower than PATH-COST of all seen instances of that state. Am I wrong?

Answer 1

It depends on the heuristic.

If the heuristic is consistent (monotone), then the first time it's expanded we can guarantee that that's the shortest path to that node, and it never needs to be expanded again.

However, if the heuristic is admissible but not consistent, then we can't make that guarantee, and we might need to expand it multiple times.

So the algorithm shown does not assume consistency. If you can assume that, you can simplify the algorithm.