ECAI 2004 Conference Paper

A Study on the Accuracy of Heuristic Functions

Carlos Linares

From a practical point of view, most problems cannot be optimally solved applying brute-force single-agent search algorithms. Thus, a new class of single-agent search algorithms was devised to find the optimal solution faster and/or consuming less space, heuristic single-agent search algorithms. However, designing accurate heuristic functions is still a major challenge. In this paper, a mathematical model is introduced for characterizing the accuracy of any heuristic function. This is a step ahead in the analysis of heuristic functions since this method could be used to aid other procedures to improve the original heuristic estimations of h(.).

Keywords: Game Playing, Planning,, Search

Citation: Carlos Linares: A Study on the Accuracy of Heuristic Functions. In R.López de Mántaras and L.Saitta (eds.): ECAI2004, Proceedings of the 16th European Conference on Artificial Intelligence, IOS Press, Amsterdam, 2004, pp.201-205.

ECAI-2004 is organised by the European Coordinating Committee for Artificial Intelligence (ECCAI) and hosted by the Universitat Politècnica de València on behalf of Asociación Española de Inteligencia Artificial (AEPIA) and Associació Catalana d'Intel-ligència Artificial (ACIA).