Parallel Greedy Best-First Search with a Bound on Expansions Relative to Sequential Search
Abstract
Parallelization of non-admissible search algorithms such as GBFS poses a challenge because straightforward parallelization can result in search behavior which significantly deviates from sequential search. Previous work proposed PUHF, a parallel search algorithm which is constrained to only expand states that can be expanded by some tie-breaking strategy for GBFS. We show that despite this constraint, the number of states expanded by PUHF is not bounded by a constant multiple of the number of states expanded by sequential GBFS with the worst-case tie-breaking strategy. We propose and experimentally evaluate One Bench At a Time (OBAT), a parallel greedy search which guarantees that the number of states expanded is within a constant factor of the number of states expanded by sequential GBFS with some tie-breaking policy.
BibTeX
@article{Shimoda_Fukunaga_2025, title={Parallel Greedy Best-First Search with a Bound on Expansions Relative to Sequential Search}, volume={39}, url={https://ojs.aaai.org/index.php/AAAI/article/view/34869}, DOI={10.1609/aaai.v39i25.34869}, abstractNote={Parallelization of non-admissible search algorithms such as GBFS poses a challenge because straightforward parallelization can result in search behavior which significantly deviates from sequential search. Previous work proposed PUHF, a parallel search algorithm which is constrained to only expand states that can be expanded by some tie-breaking strategy for GBFS. We show that despite this constraint, the number of states expanded by PUHF is not bounded by a constant multiple of the number of states expanded by sequential GBFS with the worst-case tie-breaking strategy. We propose and experimentally evaluate One Bench At a Time (OBAT), a parallel greedy search which guarantees that the number of states expanded is within a constant factor of the number of states expanded by sequential GBFS with some tie-breaking policy.}, number={25}, journal={Proceedings of the AAAI Conference on Artificial Intelligence}, author={Shimoda, Takumi and Fukunaga, Alex}, year={2025}, month={Apr.}, pages={26668-26677} }