Understanding and Improving Local Exploration for GBFS

Abstract

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.