Parallel Greedy Best-First Search with a Bound on Expansions Relative to Sequential Search
This work provides a solution for researchers and practitioners in AI planning and search algorithms who need efficient parallelization of non-admissible search methods, though it is incremental as it builds on prior work like PUHF.
The paper tackles the challenge of parallelizing greedy best-first search (GBFS) by proposing One Bench At a Time (OBAT), a parallel algorithm that guarantees the number of states expanded is within a constant factor of sequential GBFS with some tie-breaking policy, addressing deviations in search behavior from straightforward parallelization.
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.