Thread-Ordered Parallel Greedy Best First Search
Proceedings of the International Symposium on Combinatorial Search · 14.08.2026 · 19 (1) · 157-165
DOI: 10.1609/socs.v19i1.43084 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the International Symposium on Combinatorial Search, online erschienen am 14.08.2026. Verfasst von Dawson Tomasz und 3 weiteren Autor:innen.
Abstract (Originalsprache)
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.
Zitieren
APA
Tomasz, D., Veerapaneni, R., Likhachev, M., & Valenzano, R. (2026). Thread-Ordered Parallel Greedy Best First Search. Proceedings of the International Symposium on Combinatorial Search, 19(1), 157-165. https://doi.org/10.1609/socs.v19i1.43084
Vancouver
Tomasz D, Veerapaneni R, Likhachev M, Valenzano R. Thread-Ordered Parallel Greedy Best First Search. Proceedings of the International Symposium on Combinatorial Search. 2026;19(1):157-165. doi:10.1609/socs.v19i1.43084
BibTeX
@article{Tomasz2026,
author = {Tomasz, Dawson and Veerapaneni, Rishi and Likhachev, Maxim and Valenzano, Richard},
title = {Thread-Ordered Parallel Greedy Best First Search},
journal = {Proceedings of the International Symposium on Combinatorial Search},
year = {2026},
volume = {19},
number = {1},
pages = {157--165},
doi = {10.1609/socs.v19i1.43084}
}
EUVIMED