ECAI 2004 Conference Paper

[full paper]

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.