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-tofront 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. Copyright © 2012, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

Efficient single frontier bidirectional search / Lippi, Marco; Ernandes, Marco; Felner, Ariel. - (2012), pp. 49-56. (Intervento presentato al convegno 5th International Symposium on Combinatorial Search, SoCS 2012 tenutosi a Niagara Falls, ON, can nel 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-tofront 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. Copyright © 2012, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.
2012
5th International Symposium on Combinatorial Search, SoCS 2012
Niagara Falls, ON, can
2012
49
56
Lippi, Marco; Ernandes, Marco; Felner, Ariel
Efficient single frontier bidirectional search / Lippi, Marco; Ernandes, Marco; Felner, Ariel. - (2012), pp. 49-56. (Intervento presentato al convegno 5th International Symposium on Combinatorial Search, SoCS 2012 tenutosi a Niagara Falls, ON, can nel 2012).
File in questo prodotto:
File Dimensione Formato  
sfbdsh.pdf

Accesso riservato

Tipologia: Versione dell'autore revisionata e accettata per la pubblicazione
Dimensione 251.78 kB
Formato Adobe PDF
251.78 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

Licenza Creative Commons
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11380/1122674
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 9
  • ???jsp.display-item.citation.isi??? ND
social impact