Is A* with an admissible but inconsistent heuristic optimal?

Question

I understand that, in tree search, an admissible heuristic implies that $A*$ is optimal. The intuitive way I think about this is as follows:
Let $P$ and $Q$ be two costs from any respective nodes $p$ and $q$ to the goal. Assume $P<Q$. Let $P'$ be an estimation of $P$. $P'le P Rightarrow P'<Q$. It follows from uniform-cost-search that the path through $p$ must be explored.
What I don't understand, is why the idea of an admissible heuristic does not apply as well to "graph-search". If a heuristic is admissible but inconsistent, would that imply that $A*$ is not optimal? Could you please provide an example of an admissible heuristic that results in a non-optimal solution?

Nathan S. · Answer

It depends on what you mean by optimal.

A* will always find the optimal solution (that is, the algorithm is admissible) as long as the heuristic is admissible. (Note that the definition of admissible is overloaded and means something slightly different for an algorithm and a heuristic.)

If you talk about the set of nodes expanded by A*, then it expands the minimal set of nodes up to tie-breaking even with an inconsistent heuristic.

If you talk about the number of expansions, then A* is not optimal. A* can perform up to $2^N$ expansions of $N$ states with an inconsistent heuristic. This result comes from Martelli, 1977.

Algorithm B has worst-case $N^2$ expansions and budgeted graph search (BGS) has worst-case $N log C$, where $C$ is the optimal solution cost.

You can see a demo that shows the worst-case performance of A* as well as the performance of BGS here:
https://www.movingai.com/SAS/INC/

Is A* with an admissible but inconsistent heuristic optimal?

One Answer

Add your own answers!

Ask a Question