[defatigable]

If you use an inconsistent heuristic, it may be possible to revisit a node a second time via a cheaper path. And thus, as you say, if you generate a node a second time but with a cheaper path, you may not find the optimal solution if you discard the regenerated node.

So if you do A* with an inconsistent heuristic, you need to revisit nodes if you explore them a second time with a cheaper cost (i.e., you can re-expand nodes in your closed list). If you do this, you will find optimal solutions even with an inconsistent heuristic.

The only requirement on your heuristic if you A* to find optimal solutions is that it be admissible.

[sgeisenh]

I am talking about frontier A* where you discard all nodes that have already been visited. This requires the heuristic to be consistent. As opposed to the breadth-first heuristic search which revisits nodes.

[defatigable]

Ah. Yes, in frontier A* you definitely need a consistent heuristic, although I'd be surprised if frontier A* is the most popular form of the algorithm used, particularly for grid search. You really only want it in a very large implicit domain where the closed list would be too large to fit in memory. If the problem space is small enough then the traditional form of A* with an explicit closed list is much easier to think about.

A nitpick: "breadth-first heuristic search" is an algorithm developed by Zhou and Hansen and, while it's related to A* (in that it uses an admissible heuristic to prune the search space), it's not actually a variant of A*. (It's not a best-first search algorithm, since it doesn't expand nodes in increasing order of f cost.)