Parallel Greedy Best-First Search with a Bound on Expansions Relative to Sequential Search
Parallelization of non-admissible search algorithms such as GBFS poses a challenge because straightforward parallelization can result in search behavior which significantly deviates from sequential search. Previous work proposed PUHF, a parallel search algorithm which is constrained to only expand states that can be expanded by some tie-breaking strategy for GBFS. We show that despite this constraint, the number of states expanded by PUHF is not bounded by a constant multiple of the number of states expanded by sequential GBFS with the worst-case tie-breaking strategy. We propose and experimentally evaluate One Bench At a Time (OBAT), a parallel greedy search which guarantees that the number of states expanded is within a constant factor of the number of states expanded by sequential GBFS with some tie-breaking policy.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Decoupling Generation and Evaluation for Parallel Greedy Best-First Search(extended version)
In order to understand and control the search behavior of parallel search, recent work has proposed a class of constrained parallel greedy best-first search algorithms which only expands states that satisfy some constrai…
Parallel Predictive Entropy Search for Batch Global Optimization of Expensive Objective Functions
We develop parallel predictive entropy search (PPES), a novel algorithm for Bayesian optimization of expensive black-box objective functions. At each iteration, PPES aims to select a batch of points which will maximize t…
Bayesian Optimizationglobal-optimizationPSRR-MaxpoolNMS: Pyramid Shifted MaxpoolNMS with Relationship Recovery
Non-maximum Suppression (NMS) is an essential postprocessing step in modern convolutional neural networks for object detection. Unlike convolutions which are inherently parallel, the de-facto standard for NMS, namely Gre…
object-detectionObject DetectionAsynchronous Parallel Greedy Coordinate Descent
n this paper, we propose and study an Asynchronous parallel Greedy Coordinate Descent (Asy-GCD) algorithm for minimizing a smooth function with bounded constraints. At each iteration, workers asynchronously conduct greed…
Sample Complexity of Learning Heuristic Functions for Greedy-Best-First and A* Search
Greedy best-first search (GBFS) and A* search (A*) are popular algorithms for path-finding on large graphs. Both use so-called heuristic functions, which estimate how close a vertex is to the goal. While heuristic functi…