Understanding and Improving Local Exploration for GBFS
- Fan Xie
- Martin Müller
- Robert Holte, Department of Computing Science, University of Alberta
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.
Citation
F. Xie, M. Müller, R. Holte. "Understanding and Improving Local Exploration for GBFS". ICAPS, (ed: Ronen I. Brafman, Carmel Domshlak, Patrik Haslum, Shlomo Zilberstein), pp 244-248, June 2015.| Keywords: | Artificial Intelligence, Planning, Heuristic Search, GBFS |
| Category: | In Conference |
| Web Links: | AAAI |
BibTeX
@incollection{Xie+al:ICAPS15,
author = {Fan Xie and Martin Müller and Robert Holte},
title = {Understanding and Improving Local Exploration for GBFS},
Editor = {Ronen I. Brafman, Carmel Domshlak, Patrik Haslum, Shlomo
Zilberstein},
Pages = {244-248},
booktitle = {},
year = 2015,
}Last Updated: June 30, 2020Submitted by Sabina P
