Analyzing and Avoiding Pathological Behavior in Parallel Best-First Search

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.