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.
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
Deferredqueue 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.
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