A* with Inconsistent Heuristics and BPMX
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.
Downloads Download full movie