Hosted Pages

Pathfinding Benchmarks

Grid-Based Path Planning Competition

AAAI 2017 Job Fair

AAAI 2017 Workshop on what's next for AI in games

Archived Pages

AAAI16 Student Activities

AAAI15 Student Activities

MAPF 2012 Workshop

AIIDE 2011

GIGA 2011

SoCS 2010

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.

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.


Download full movie (larger size).

© Nathan Sturtevant, All rights reserved.