Analyzing and Avoiding Pathological Behavior in Parallel Best-First Search

Ryo Kuroiwa, Alex Fukunaga

PosterID: 50 PDF Slides Poster BibTeX

Recent research has experimentally shown that parallelization of Greedy Best-First Search (GBFS), a satisficing best-first search method, can behave very differently from sequential GBFS. In this paper, we propose a theoretical framework to compare parallel best-first search with sequential best-first search, including not only GBFS but also A* and Weighted A*, optimal and suboptimal best-first search methods. We show to which extent exiting parallel best-first search methods are different from sequential best-first search. We show that this framework can be used to design a parallel best-first search method which is guaranteed to behave somewhat similarly to sequential best-first search.

Session Aus2: Search
Canb 10/28/2020, 20:00 – 21:00
10/30/2020, 13:00 – 14:00
Paris 10/28/2020, 10:00 – 11:00
10/30/2020, 03:00 – 04:00
NYC 10/28/2020, 05:00 – 06:00
10/29/2020, 22:00 – 23:00
LA 10/28/2020, 02:00 – 03:00
10/29/2020, 19:00 – 20:00