Early work on A* and inconsistent heuristics showed that A* could perform an exponential number of
node re-expansions when using an inconsistent heuristic. This discouraged work on inconsistent
heuristics. Recent work has revived the study of inconsistent heuristics and shown that these worst-case
scenarios do not happen in practice.
But, depending on the problem, inconsistency can still cause problems. Below we show a video that
demonstrate this, and also demonstrates the fix.
On the left is A* with a compressed differential heuristic (see Goldenberg et al, 2010). Green nodes are
on the open list. Red nodes are on the closed list. Blue nodes have been re-opened (after being closed)
and placed on the open list a second time. Purple nodes have been re-opened and then closed again.
On the right is A* with the same heuristic, but the bi-directional pathmax (BPMX) technique. BPMX tries
to propagate heuristics between neighboring states. As can be seen, this eliminates almost all of the
node re-expansions and greatly reduces the total work.
Permission is granted to download and use these videos for non-commercial use. If you are using them,
please let me know: sturtevant at cs . du . edu.
DownloadsDownload full movie (larger size).