View Publication

Inconsistent Heuristics

Uzi Zahavi, Computer Science, Bar-Ilan University, Israel
Ariel Felner, Information Systems Engineering, Ben-Gurion University, Israel
Jonathan Schaeffer, Department of Computing Science, University of Alberta
Nathan R. Sturtevant

In the field of heuristic search it is well-known that improving the quality of an admissible heuristic can significantly decrease the search effort required to find an optimal solution. Existing literature often assumes that admissible heuristics are consistent, implying that consistency is a desirable attribute. To the contrary, this paper shows that an inconsistent heuristic can be preferable to a consistent heuristic. Theoretical and empirical results show that, in many cases, inconsistency can be used to achieve large performance improvements. The conventional wisdom about inconsistent heuristics is wrong.

Citation

U. Zahavi, A. Felner, J. Schaeffer, N. Sturtevant. "Inconsistent Heuristics". National Conference on Artificial Intelligence (AAAI), pp 1121-1216, April 2007.

Keywords:
Category:	In Conference

BibTeX

@incollection{Zahavi+al:AAAI07,
  author = {Uzi Zahavi and Ariel Felner and Jonathan Schaeffer and Nathan R.
    Sturtevant},
  title = {Inconsistent Heuristics},
  Pages = {1121-1216},
  booktitle = {National Conference on Artificial Intelligence (AAAI)},
  year = 2007,
}

Last Updated: July 03, 2020
Submitted by Sabina P

Not Logged In

PapersDB

Inconsistent Heuristics

Citation

BibTeX