Parallel Greedy Best-First Search with a Bound on Expansions Relative to Sequential Search

Takumi Shimoda, Alex FukunagaAAAI 2025 · DOI

Introduction

Parallelizing search algorithms is a common strategy to leverage multi-core architectures in AI planning. However, Greedy Best-First Search (GBFS) presents a unique challenge: parallel versions often suffer from "search explosion," where multiple threads expand orders of magnitude more states than a sequential search. This paper, presented at AAAI-25, introduces OBAT (One Bench At a Time), the first parallel GBFS algorithm that provides a mathematical guarantee on search effort, ensuring that parallelization does not lead to pathological work increases.

The Challenge: Pathological Search Behavior

GBFS is highly sensitive to tie-breaking. In a sequential search, the algorithm typically explores one "bench"—a set of states with identical heuristic values—until it finds a state that leads to a lower heuristic value (a progress state). In parallel environments, different threads may inadvertently start exploring multiple different benches simultaneously. This can lead to pathological behavior where a 16-thread search expands 100x more states than a single-threaded search, resulting in a net slowdown.

Example of pathological search behavior in PUHF where parallel threads explore multiple benches simultaneously, leading to excessive expansions.

Previous attempts to mitigate this, such as the PUHF algorithm, constrained the search to "legal" states but lacked a hard theoretical bound. This research proves that even state-of-the-art methods like PUHF can still exhibit pathological expansion rates in certain search spaces.

The OBAT Algorithm

The core philosophy of OBAT is to allow parallel work within a bench while strictly serializing the transitions between benches. This prevents threads from wandering into unrelated areas of the search space.

Key features of OBAT include:

  • State Classification: States are classified as a-states (no immediate progress) or b-states (potential progress states leading to lower heuristic values).
  • Expansion Constraints: The algorithm uses a Deferred queue for b-states and only allows one b-state to be "committed" and expanded at a time. This ensures the search stays focused on the current plateau.
  • OBAT$_S$ (OBAT with SGE): To address potential thread idling caused by the expansion constraint, the authors introduced Separate Generation and Evaluation (SGE). This variant allows idle threads to evaluate the heuristics of newly generated states even when they are not permitted to expand them, maximizing CPU utilization.

Theoretical Guarantees

OBAT is the first parallel GBFS algorithm to provide a proven bound on search effort. The number of states it expands is guaranteed to be at most the number of states expanded by a sequential GBFS (under worst-case tie-breaking) plus a small constant factor proportional to the number of threads and the solution path length ($k \times L$).

Experimental Evaluation

The researchers evaluated OBAT on the Autoscale-21.11 satisficing benchmark set, comprising 1,260 instances across 42 STRIPS domains.

Performance comparison of OBAT and OBAT_S against KPGBFS and PUHF3 baselines, showing improved efficiency and coverage.

Key results include:

  • Coverage: OBAT$_S$ solved 532 out of 1260 problems using 16 threads, matching the performance of the best unconstrained parallel baseline (KPGBFS$_S$) and significantly outperforming PUHF3 (494).
  • Efficiency: OBAT expanded significantly fewer states than standard parallel GBFS, confirming that its constraints effectively prevent search explosion.
  • Practicality: While basic OBAT faced lower evaluation rates due to thread idling, the OBAT$_S$ variant successfully utilized idle cycles to remain competitive in wall-clock time while maintaining its theoretical safety net.

Conclusion

OBAT successfully bridges the gap between parallel search performance and theoretical reliability. By treating the "bench" as the fundamental unit of progress, it provides a robust framework for parallel GBFS that avoids the pitfalls of pathological search behavior. Future work may focus on tightening the bounds relative to best-case sequential search and exploring scalability on systems with higher core counts.

Summary updated

BibTeX
@inproceedings{shimoda2025parallel,
  author = {Takumi Shimoda and Alex Fukunaga},
  title = {{Parallel Greedy Best-First Search with a Bound on Expansions Relative to Sequential Search}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.1609/aaai.v39i25.34869},
}
Figure