EUVIMEDEUVIMED entdecken
Crossref

Thread-Ordered Parallel Greedy Best First Search

Dawson Tomasz, Rishi Veerapaneni, Maxim Likhachev, Richard Valenzano

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →