Understanding and Improving Local Exploration for GBFS
Understanding and Improving Local Exploration for GBFS
复制标题
理解和改进 GBFS 的本地探索
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
R. Holte
中科院分区：
文献类型：
--
作者：
Fan Xie;Martin Müller;R. Holte
贪婪的最佳优先搜索(GBFS)是许多最先进的满意计划者的核心算法。贪婪的局部搜索最佳优先搜索(GBFS-LS)算法将使用局部GBFS的探索添加到全局GBFS中。这大大提高了包含大的无信息启发式区域(UHR)的域的性能，例如高原或局部极小值。本文对GBFS-LS的性能进行了分析、量化和改进。结果表明，混合大小UHR的规划问题对于GBFS是困难的，而对于GBFS-LS是容易的。在详细分析的三个标准IPC规划实例中，添加使用当地GBF的勘探可使速度提高三个数量级以上。作为第二个贡献，详细的分析导致了改进的GBFS-LS算法，它用更多的较小的探索取代了较大规模的局部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.