Anchor Search: A Unified Framework for Suboptimal Bidirectional Search
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.
Cite
Text
Lavasani et al. "Anchor Search: A Unified Framework for Suboptimal Bidirectional Search." AAAI Conference on Artificial Intelligence, 2025. doi:10.1609/AAAI.V39I25.34911Markdown
[Lavasani et al. "Anchor Search: A Unified Framework for Suboptimal Bidirectional Search." AAAI Conference on Artificial Intelligence, 2025.](https://mlanthology.org/aaai/2025/lavasani2025aaai-anchor/) doi:10.1609/AAAI.V39I25.34911BibTeX
@inproceedings{lavasani2025aaai-anchor,
title = {{Anchor Search: A Unified Framework for Suboptimal Bidirectional Search}},
author = {Lavasani, Sepehr and Siag, Lior and Shperberg, Shahaf S. and Felner, Ariel and Sturtevant, Nathan R.},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2025},
pages = {27045-27053},
doi = {10.1609/AAAI.V39I25.34911},
url = {https://mlanthology.org/aaai/2025/lavasani2025aaai-anchor/}
}