ECAI-2000 Conference Paper

[full paper]

Towards Real-Time Search with Inadmissible Heuristics

Masashi Shimbo, Toru Ishida

We discuss the effect of heuristic functions that violate admissibility and consistency on real-time search algorithms. Although the flexibility and the leaning ability of LRTA*, the popular real-time search algorithm, makes it an attractive candidate for the generic model of intelligent autonomous agents, its behavior is far from rational, in that it is too optimistic in the face of uncertainty. Such behavior is known to be relaxed by incorporating pessimism into the algorithm, via the use of inadmissible (or overestimating) heuristic functions and it is also known that the use of such functions often improves the performance of real-time search. However, there is no theory that well describes when and why these algorithms benefit from such property of heuristic functions yet. In this paper, as a step towards fully understand and utilize the advantage of such nonstandard heuristic functions, we present several proofs of the properties of LRTA* and the Moving-Target Search algorithm, when the heuristic function violates admissibility or consistency.

Keywords: search, real-time systems

Citation: Masashi Shimbo, Toru Ishida: Towards Real-Time Search with Inadmissible Heuristics. In W.Horn (ed.): ECAI2000, Proceedings of the 14th European Conference on Artificial Intelligence, IOS Press, Amsterdam, 2000, pp.609-613.