Understanding and improving local exploration for GBFS

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