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

Download BibTeX Cite

Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence. Pages 634-638.

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

Zhifu Zhang, Nathan R. Sturtevant, Robert C. Holte, Jonathan Schaeffer, and Ariel Felner. 2009. A* Search with Inconsistent Heuristics. In Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence, IJCAI-09. IJCAI, 634–638. https://ijcai.org/proceedings/2009/111

@inproceedings{ijcai2009p111,
  title     = {A* Search with Inconsistent Heuristics},
  author    = {Zhang, Zhifu and Sturtevant, Nathan R. and Holte, Robert C. and Schaeffer, Jonathan and Felner, Ariel},
  booktitle = {Proceedings of the Twenty-First International Joint Conference on
               Artificial Intelligence, {IJCAI-09}},
  publisher = {International Joint Conferences on Artificial Intelligence},
  editor    = {Hiroaki Kitano},
  pages     = {634--638},
  year      = {2009},
  url       = {https://ijcai.org/proceedings/2009/111},
}

TY  - CPAPER
TI  - A* Search with Inconsistent Heuristics
AU  - Zhang, Zhifu
AU  - Sturtevant, Nathan R.
AU  - Holte, Robert C.
AU  - Schaeffer, Jonathan
AU  - Felner, Ariel
T2  - Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence, IJCAI-09
PB  - International Joint Conferences on Artificial Intelligence
PY  - 2009
SP  - 634
EP  - 638
UR  - https://ijcai.org/proceedings/2009/111
ER  -