Analyzing and Avoiding Pathological Behavior in Parallel Best-First Search

Authors

  • Ryo Kuroiwa The University of Tokyo
  • Alex Fukunaga The University of Tokyo

DOI:

https://doi.org/10.1609/icaps.v30i1.6659

Abstract

Recent work 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 both suboptimal (GBFS, Weighted A*) and optimal (A*) best-first search methods. We analyze the extent to which the search behavior of existing parallel best-first search methods differ from sequential best-first search, and show that existing methods are vulnerable to pathological behavior, and that they can expand nodes which would not be expanded by sequential search under any tie-breaking policy. We also propose PUHF, a parallel best-first search which is guaranteed to expand a node only if there is some tie-breaking strategy for sequential search which expands the node.

Downloads

Published

2020-06-01

How to Cite

Kuroiwa, R., & Fukunaga, A. (2020). Analyzing and Avoiding Pathological Behavior in Parallel Best-First Search. Proceedings of the International Conference on Automated Planning and Scheduling, 30(1), 175-183. https://doi.org/10.1609/icaps.v30i1.6659