On the Pathological Search Behavior of Distributed Greedy Best-First Search

Authors

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

Abstract

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.

Downloads

Published

2019-07-06

How to Cite

Kuroiwa, R., & Fukunaga, A. (2019). On the Pathological Search Behavior of Distributed Greedy Best-First Search. Proceedings of the International Conference on Automated Planning and Scheduling, 29(1), 255-263. Retrieved from https://ojs.aaai.org/index.php/ICAPS/article/view/3485