Early research in heuristic search discovered that using inconsistent heuristics with A* could result in an exponential increase in the number of node expansions. As a result, the use of inconsistent heuristics has largely disappeared from practice. Recently, inconsistent heuristics have been shown to be effective in IDA*, especially when applying the bidirectional pathmax (BPMX) enhancement. This paper presents new worst-case complexity analysis of A*’s behavior with inconsistent heuristics, discusses how BPMX can be used with A*, and gives experimental results justifying the use of inconsistent heuristics in A* searches.

Authors

• Zhifu Zhang
• Nathan R. Sturtevant University of Alberta Alberta Machine Intelligence Institute (Amii)
• Robert Holte
• Jonathan Schaeffer University of Alberta
• Ariel Felner Ben-Gurion University of the Negev

Keywords

No keywords are indexed for this paper.