Thread-Ordered Parallel Greedy Best First Search

Abstract

While parallelizing Greedy Best-First Search (GBFS) can accelerate planning, existing approaches offer no runtime guarantees: they are not necessarily faster than sequential GBFS, and counterintuitively, adding more threads can possibly degrade runtime. To address this unpredictable scaling, we introduce Thread-Ordered Parallel-GBFS (TOP-GBFS). Inspired by MonoBeam — which guarantees monotonically improving solution costs as beam width increases — TOPGBFS is a novel parallelization designed to ensure that search time never increases as thread count grows. Under standard assumptions, we prove that TOP-GBFS bounds the total number of expansions to a constant factor of sequential GBFS and guarantees monotonically non-increasing runtimes. We empirically validate this monotonicity and demonstrate that TOP-GBFS remains competitive with existing parallel GBFS implementations on standard PDDL benchmarks.