TY - JOUR AU - Kuroiwa, Ryo AU - Fukunaga, Alex PY - 2021/05/25 Y2 - 2024/03/28 TI - On the Pathological Search Behavior of Distributed Greedy Best-First Search JF - Proceedings of the International Conference on Automated Planning and Scheduling JA - ICAPS VL - 29 IS - 1 SE - Main Track DO - 10.1609/icaps.v29i1.3485 UR - https://ojs.aaai.org/index.php/ICAPS/article/view/3485 SP - 255-263 AB - <p>Although A* search can be efficiently parallelized using methods such as Hash-Distributed A* (HDA*), distributed parallelization of Greedy Best First Search (GBFS), a suboptimal search which often finds solutions much faster than A*, has received little attention. We show that surprisingly, HDGBFS, an adaptation of HDA* to GBFS, often performs significantly worse than sequential GBFS. We analyze and explain this performance degradation, and propose a novel method for distributed parallelization of GBFS, which significantly outperforms HDGBFS.</p> ER -