Improved Exploration of the Bench Transition System in Parallel Greedy Best First Search


  • Takumi Shimoda The University of Tokyo
  • Alex Fukunaga The University of Tokyo



External-memory And Parallel Search, Analysis Of Search Algorithms, Problem Solving Using Search, Bounding And Pruning Techniques


While parallelization of A* is fairly well-understood, parallelization of GBFS has been much less understood. Recent work has proposed PUHF, a parallel GBFS which restricts search to exploration of the Bench Transition System (BTS), which is the set of states that can be expanded by GBFS under some tie-breaking policy. However, PUHF causes threads to spend much of the time waiting so that only states which are guaranteed to be in the BTS are expanded. We propose improvements to PUHF which significantly reduce idle time and allow more rapid exploration of the BTS, resulting in better search performance.