The Single Frontier Bi-Directional Search (SBS) framework was recently introduced. A node in SBS corresponds to a pair of states, one from each of the frontiers and it uses front-to- front heuristics. In this paper we present an enhanced version of SBS, called eSBS, where pruning and caching techniques are applied, which significantly reduce both time and memory needs of SBS. We then present a hybrid of eSBS and IDA∗ which potentially uses only the square root of the memory required by A∗ but enables to prune many nodes that IDA∗ would generate. Experimental results show the benefit of our new approaches on a number of domains.

Efficient Single Frontier Bidirectional Search / M. Lippi; M. Ernandes; A. Felner. - ELETTRONICO. - (2012), pp. 49-56. (Intervento presentato al convegno Proceedings of the Fifth Annual Symposium on Combinatorial Search tenutosi a Niagara Falls, Ontario, Canada nel July 2012).

Efficient Single Frontier Bidirectional Search

LIPPI, MARCO;
2012

Abstract

The Single Frontier Bi-Directional Search (SBS) framework was recently introduced. A node in SBS corresponds to a pair of states, one from each of the frontiers and it uses front-to- front heuristics. In this paper we present an enhanced version of SBS, called eSBS, where pruning and caching techniques are applied, which significantly reduce both time and memory needs of SBS. We then present a hybrid of eSBS and IDA∗ which potentially uses only the square root of the memory required by A∗ but enables to prune many nodes that IDA∗ would generate. Experimental results show the benefit of our new approaches on a number of domains.
2012
Proceedings of the Fifth Annual Symposium on Combinatorial Search
49
56
Efficient Single Frontier Bidirectional Search / M. Lippi; M. Ernandes; A. Felner. - ELETTRONICO. - (2012), pp. 49-56. (Intervento presentato al convegno Proceedings of the Fifth Annual Symposium on Combinatorial Search tenutosi a Niagara Falls, Ontario, Canada nel July 2012).
M. Lippi; M. Ernandes; A. Felner
File in questo prodotto:
Eventuali allegati, non sono esposti

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/11585/394762
 Attenzione

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

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 9
  • ???jsp.display-item.citation.isi??? ND
social impact