It is well-known that while strict admissibility of heuristics in problem solving guarantees the optimality of the A∗ algorithm, many problems cannot be effectively faced because of the combinatorial explosion. In order to address this problem the notion of ϵ-Admissible search has been introduced, which yields solutions with bounded costs [12]. In this paper, we introduce the related concept of likely-Admissible heuristics, where the admissibility requirement is relaxed in a probabilistic sense. Instead of providing an upper-bound to the cost we guarantee to end up with optimal solutions with a given probability. Interestingly, likely-Admissible heuristics can be obtained naturally by statistical learning techniques such as artificial neural networks, which can learn from examples the expected value of the cost to reach the target.We used multilayered neural networks with a proper 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 yield optimal solutions in 50% of the cases, taking only 1/500 time (1/13000 space) of classic Manhattan-based search.

Ernandes, M., Gori, M. (2004). Likely-admissible and sub-symbolic heuristics. In Proceedings of ECAI-2004 (pp.613-617). Amsterdam : IOS Press.

Likely-admissible and sub-symbolic heuristics

GORI, MARCO
2004-01-01

Abstract

It is well-known that while strict admissibility of heuristics in problem solving guarantees the optimality of the A∗ algorithm, many problems cannot be effectively faced because of the combinatorial explosion. In order to address this problem the notion of ϵ-Admissible search has been introduced, which yields solutions with bounded costs [12]. In this paper, we introduce the related concept of likely-Admissible heuristics, where the admissibility requirement is relaxed in a probabilistic sense. Instead of providing an upper-bound to the cost we guarantee to end up with optimal solutions with a given probability. Interestingly, likely-Admissible heuristics can be obtained naturally by statistical learning techniques such as artificial neural networks, which can learn from examples the expected value of the cost to reach the target.We used multilayered neural networks with a proper 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 yield optimal solutions in 50% of the cases, taking only 1/500 time (1/13000 space) of classic Manhattan-based search.
2004
978-158603452-8
1-58603-452-9
Ernandes, M., Gori, M. (2004). Likely-admissible and sub-symbolic heuristics. In Proceedings of ECAI-2004 (pp.613-617). Amsterdam : IOS Press.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11365/36008
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo