Understanding and Improving Local Exploration for GBFS


  • Fan Xie University of Alberta
  • Martin Müller University of Alberta
  • Robert Holte University of Alberta




Artificial Intelligence, Planning, Heuristic Search, GBFS


Greedy Best First Search (GBFS) is a powerful algorithm at the heart of many state-of-the-art satisficing planners. The Greedy Best First Search with Local Search (GBFS-LS) algorithm adds exploration using a local GBFS to a global GBFS. This substantially improves performancefor domains that contain large uninformative heuristic regions (UHR), such as plateaus or local minima. This paper analyzes, quantifies and improves the performance of GBFS-LS.Planning problems with a mix of small and large UHRs are shown to be hard for GBFS but easy for GBFS-LS. In three standard IPC planning instances analyzed in detail, adding exploration using local GBFS gives more than three orders of magnitude speedup. As a second contribution, the detailed analysis leads to an improvedGBFS-LS algorithm, which replaces larger-scale local GBFS explorations with a greater number of smaller explorations.




How to Cite

Xie, F., Müller, M., & Holte, R. (2015). Understanding and Improving Local Exploration for GBFS. Proceedings of the International Conference on Automated Planning and Scheduling, 25(1), 244-248. https://doi.org/10.1609/icaps.v25i1.13704