ECAI 2004 Conference Paper

[PDF] [full paper] [prev] [tofc] [next]

Likely-admissible and sub-symbolic heuristics

Marco Ernandes, Marco Gori

It is well-known in Problem Solving that while strict admissibility guarantees the optimality of A* algorithms many problems cannot be effectively faced in this way because of the combinatorial explosion. To avoid intractability it has been introduced the notion of epsilon-admissible search, which yields solutions with bounded costs, but it does not investigate the probability of discovering optimal solutions. In this paper, we introduce the related concept of likely-admissible search, where the admissibility requirement is relaxed in a probabilistic sense and guarantees to end up with optimal solutions with a given probability. Interestingly, likely-admissible heuristics can be obtained naturally by statistical learning techniques such as ANNs, which can learn from examples the expected distance to the target. We designed a novel cost function in order to bias the learning towards admissibility. Our experiments with the 15-puzzle and IDA* show that the adoption of likely-admissible sub-symbolic heuristics yields optimal solutions in 50\% of the cases, taking only 1/500 time (1/13000 space) of classic Manhattan-based search. This promising result seems to candidate our algorithm as an alternative to disjoint pattern databases[Korf2002], which makes a much more significant use of memory resources shifting NP-Hardness of strict admissibility from time to space.

Keywords: Heuristics, Search, Problem Solving, Machine Learning, Neural Networks

Citation: Marco Ernandes, Marco Gori: Likely-admissible and sub-symbolic heuristics . 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.613-617.

[prev] [tofc] [next]

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).