EUVIMEDEUVIMED entdecken
Crossref

Runahead A*: Speculative Parallelism for A* with Slow Expansions

Mohammad Bakhshalipour, Mohamad Qadri, Dominic Guri, Seyed Borna Ehsani, Maxim Likhachev, Phillip B. Gibbons

Proceedings of the International Conference on Automated Planning and Scheduling · 01.07.2023 · 33 (1) · 31-41

DOI: 10.1609/icaps.v33i1.27176 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the International Conference on Automated Planning and Scheduling, online erschienen am 01.07.2023. Verfasst von Mohammad Bakhshalipour und 5 weiteren Autor:innen. Die Arbeit wurde bisher 2-mal zitiert (Crossref).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

A* suffers from limited parallelism. The maximum level of traditional parallelism in A* is the same as the degree of the search graph nodes, which is too small in many applications. As such, A* cannot fully leverage the multithreading capabilities of modern processors. In this paper, we go beyond traditional parallelism and introduce speculative parallelism for A*. We observe that A*'s node expansions exhibit predictable patterns in applications like path planning. Based on this observation, we propose Runahead A* (RA*). When a node is being expanded, RA* predicts future likely-to-be-expanded nodes, performs their corresponding computation on separate threads, and memoizes the computation results. Later when a predicted node is selected for expansion, rather than performing its computation, the memoized results are used, saving significant time in slow-expansion applications. We study five applications of A*. We show that when its prediction accuracy is high, RA* offers significant speedup over vanilla A* for slow-expansion applications. With 16 threads, RA*'s speedup for such applications ranges from 3.1x to 14.1x. We also study and provide insight into when, why, and to what extent node expansions are predictable. We provide an implementation of RA* at: https://github.com/cmu-roboarch/runahead-astar/

Zitieren

APA

Bakhshalipour, M., Qadri, M., Guri, D., Ehsani, S. B., Likhachev, M., & Gibbons, P. B. (2023). Runahead A*: Speculative Parallelism for A* with Slow Expansions. Proceedings of the International Conference on Automated Planning and Scheduling, 33(1), 31-41. https://doi.org/10.1609/icaps.v33i1.27176

Vancouver

Bakhshalipour M, Qadri M, Guri D, Ehsani SB, Likhachev M, Gibbons PB. Runahead A*: Speculative Parallelism for A* with Slow Expansions. Proceedings of the International Conference on Automated Planning and Scheduling. 2023;33(1):31-41. doi:10.1609/icaps.v33i1.27176

BibTeX
@article{Bakhshalipour2023,
  author = {Bakhshalipour, Mohammad and Qadri, Mohamad and Guri, Dominic and Ehsani, Seyed Borna and Likhachev, Maxim and Gibbons, Phillip B.},
  title = {Runahead A*: Speculative Parallelism for A* with Slow Expansions},
  journal = {Proceedings of the International Conference on Automated Planning and Scheduling},
  year = {2023},
  volume = {33},
  number = {1},
  pages = {31--41},
  doi = {10.1609/icaps.v33i1.27176}
}
Kostenlos starten →