AAAI Publications, Twenty-First International Joint Conference on Artificial Intelligence

Font Size: 
A* Search with Inconsistent Heuristics
Zhifu Zhang, Nathan R. Sturtevant, Robert Holte, Jonathan Schaeffer, Ariel Felner

Last modified: 2009-06-25

Abstract


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.

Full Text: PDF