
[full paper] 
Marco Ernandes, Marco Gori
It is wellknown 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 epsilonadmissible 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 likelyadmissible search, where the admissibility requirement is relaxed in a probabilistic sense and guarantees to end up with optimal solutions with a given probability. Interestingly, likelyadmissible 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 15puzzle and IDA* show that the adoption of likelyadmissible subsymbolic heuristics yields optimal solutions in 50\% of the cases, taking only 1/500 time (1/13000 space) of classic Manhattanbased 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 NPHardness of strict admissibility from time to space.
Keywords: Heuristics, Search, Problem Solving, Machine Learning, Neural Networks
Citation: Marco Ernandes, Marco Gori: Likelyadmissible and subsymbolic 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.613617.