The discussion of heuristics includes only information about admissibility and not consistency. An admissible but inconsistent heuristic can also cause A* to miss the correct solution.
This isn't true. An admissible heuristic guarantees the optimal solution. With an inconsistent heuristic, A* can re-expand states multiple times, but will still end with an optimal path.
In other words, if the heuristic is consistent, then it implies that A* will expand the optimal number of states.
If we operate under the assumption that each intermediate path found is shortest for its respective endpoint (which is the fundamental insight for Dijkstra's), we could potentially throw away the solution because it travels through the "visited set."
Edit: The paper you cited uses a traversal slightly different from traditional A*.
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.
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.
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.)
There's not even much about admissibility (which is not always used in game settings). I don't have a good sense for consistency/monotonicity. Do you have an example of an inconsistent admissible heuristic?
I'll do my best to provide an example. It is hard to come up with a general idea, but I can demonstrate using a graph:
http://i.imgur.com/AwpTeRt.png
The numbers in the nodes represent heuristic values at each node and the numbers on edges represent edge weights; we're looking to get from S to T.
Our heuristic is admissible because it never overestimates the distance to the target.
Consistency dictates that the heuristic value at any node may at most be the weight of any out-edge added to the heuristic value of the node that the edge connects to. So in our example, the heuristic at A is 3, but at B it is 0, but 3 > 1 + 0, so our heuristic is inconsistent.
The reason this causes issues is because our algorithm assumes that any visited path is the shortest path to the end vertex of that path. So when we traverse this graph, we will visit B first, because the sum of its heuristic value and the respective edge weight is less than that of A.
