A* Search with Inconsistent Heuristics

Zhang, Zhifu; Sturtevant, Nathan R.; Holte, Robert C.; Schaeffer, Jonathan; Felner, Ariel

A* Search with Inconsistent Heuristics

Zhifu Zhang, Nathan R. Sturtevant, Robert C. Holte, Jonathan Schaeffer, Ariel Felner

IJCAI 2009 pp. 634-639

/ijcai/2009/zhang2009ijcai-search/

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. Zhifu Zhang, Nathan R. Sturtevant, Robert Holte, Jonathan Schaeffer, Ariel Felner

PDF Semantic Scholar

Cite

Text

Zhang et al. "A* Search with Inconsistent Heuristics." International Joint Conference on Artificial Intelligence, 2009.

Markdown

[Zhang et al. "A* Search with Inconsistent Heuristics." International Joint Conference on Artificial Intelligence, 2009.](https://mlanthology.org/ijcai/2009/zhang2009ijcai-search/)

BibTeX

@inproceedings{zhang2009ijcai-search,
  title     = {{A* Search with Inconsistent Heuristics}},
  author    = {Zhang, Zhifu and Sturtevant, Nathan R. and Holte, Robert C. and Schaeffer, Jonathan and Felner, Ariel},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year      = {2009},
  pages     = {634-639},
  url       = {https://mlanthology.org/ijcai/2009/zhang2009ijcai-search/}
}