Exploration among and within Plateaus in Greedy Best-First Search
Exploration among and within Plateaus in Greedy Best-First Search
复制标题
贪婪最佳优先搜索中高原之间和高原内的探索
DOI：
10.1609/icaps.v27i1.13800
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
A. Fukunaga
中科院分区：
文献类型：
--
作者：
Masataro Asai;A. Fukunaga
最近对贪婪最佳优先搜索（GBFS）的增强，如DBFS，-GBFS，Type-GBFS，通过偶尔引入探索行为来提高性能，偶尔扩展非贪婪节点。然而，这些探索机制中的大多数不解决共享相同的启发式估计（高原）的空间内的探索。在本文中，我们表明这两种模式的探索，跨（间）和（内）高原，是互补的，可以结合起来，以产生上级性能。然后，我们引入了一个新的分形启发计划称为入侵渗滤多样化，解决“广度”的偏见，而不是“深度”的偏见解决现有的多样化方法。我们评估了IP多样化的高原内和高原间的探索，并表明它显着提高了性能在几个领域。最后，我们表明，多样化的方法相结合的结果在一个计划，这是有竞争力的国家的最先进的满意的规划。
Recent enhancements to greedy best-first search (GBFS) such as DBFS, -GBFS, Type-GBFS improve performance by occasionally introducing exploratory behavior which occasionally expands non-greedy nodes. However, most of these exploratory mechanisms do not address exploration within the space sharing the same heuristic estimate (plateau). In this paper, we show these two modes of exploration, which work across (inter-) and within (intra-) plateau, are complementary, and can be combined to yield superior performance. We then introduces a new fractal-inspired scheme called Invasion-Percolation diversification, which addresses “breadth”-bias instead of the “depth”-bias addressed by the existing diversification methods. We evaluate IP-diversification for both intra- and inter-plateau exploration, and show that it significantly improves performance in several domains. Finally, we show that combining diversification methods results in a planner which is competitive to the state-of-the-art for satisficing planning.
影响因子：
--
作者：
PRIM, RC
通讯作者：
PRIM, RC