Anchor Search: A Unified Framework for Suboptimal Bidirectional Search
Sepehr Lavasani, Lior Siag, Shahaf S. Shperberg, Ariel Felner, Nathan R. Sturtevant
Abstract
In recent years the understanding of optimal bidirectional heuristic search (BiHS) has progressed significantly. Yet, Bi-HS is relatively unexplored in unbounded suboptimal search. Front-to-end (F2E) and front-to-front (F2F) bidirectional search have been used in optimal algorithms, but adapting them for unbounded suboptimal search remains an open challenge. We introduce a framework for suboptimal BiHS, called anchor search, and use it to derive a parameterized family of algorithms. Because our new algorithms need F2F heuristic evaluations, we propose using pattern databases (PDBs) as differential heuristics (DHs) to construct F2F heuristics. Our experiments evaluate three anchor search instances across diverse domains, outperforming existing methods, particularly as the search scales.
BibTeX
@article{Lavasani_Siag_Shperberg_Felner_Sturtevant_2025, title={Anchor Search: A Unified Framework for Suboptimal Bidirectional Search}, volume={39}, url={https://ojs.aaai.org/index.php/AAAI/article/view/34911}, DOI={10.1609/aaai.v39i25.34911}, abstractNote={In recent years the understanding of optimal bidirectional heuristic search (BiHS) has progressed significantly. Yet, Bi-HS is relatively unexplored in unbounded suboptimal search. Front-to-end (F2E) and front-to-front (F2F) bidirectional search have been used in optimal algorithms, but adapting them for unbounded suboptimal search remains an open challenge. We introduce a framework for suboptimal BiHS, called anchor search, and use it to derive a parameterized family of algorithms. Because our new algorithms need F2F heuristic evaluations, we propose using pattern databases (PDBs) as differential heuristics (DHs) to construct F2F heuristics. Our experiments evaluate three anchor search instances across diverse domains, outperforming existing methods, particularly as the search scales.}, number={25}, journal={Proceedings of the AAAI Conference on Artificial Intelligence}, author={Lavasani, Sepehr and Siag, Lior and Shperberg, Shahaf S. and Felner, Ariel and Sturtevant, Nathan R.}, year={2025}, month={Apr.}, pages={27045-27053} }