【24h】

A New Local-Search Algorithm for Forward-Chaining Planning

机译:前向规划中的一种新的局部搜索算法

获取原文
获取原文并翻译 | 示例

摘要

Forward-chaining heuristic search is a well-established and popular paradigm for domain-independent planning. Its effectiveness relies on the heuristic information provided by a state evaluator, and the search algorithm used with this in order to solve the problem. This paper presents a new stochastic local-search algorithm for forward-chaining planning. The algorithm is used as the basis of a planner in conjunction with FF's Relaxed Planning Graph heuristic. Our approach is unique in that localised restarts are used, returning to the start of plateaux and saddle points, as well as global restarts to the initial state. The majority of the search time when using FF's 'Enforced Hill Climbing' is spent using breadth-first search to escape local minima. Our localised restarts, in conjunction with stochastic search, serve to replace this expensive breadth-first search step. We also describe an extended search neighbourhood incorporating non-helpful actions and the 'lookahead' states used in YAHSP. Making use of non-helpful actions and stochastic search allows us to restart the local-search from the initial state when dead-ends are encountered; rather than resorting to best-first search. We present analyses to demonstrate the effectiveness of our restart strategies, along with results that show the new planning algorithm is effective across a range of domains.
机译:正向链启发式搜索是一种独立于域的规划的公认且流行的范例。它的有效性依赖于状态评估器提供的启发式信息,以及用于解决问题的搜索算法。本文提出了一种用于前向链计划的新的随机局部搜索算法。该算法与FF的放松规划图启发式算法一起用作规划器的基础。我们的方法的独特之处在于,使用了局部重启,返回到平稳点和鞍点的起点,以及全局重启到初始状态。使用FF的“强制爬山”时,大部分搜索时间是使用广度优先搜索来逃避局部最小值。我们的本地化重启与随机搜索相结合,可替代这种昂贵的广度优先搜索步骤。我们还将描述一个扩展的搜索邻域,其中包含无用的动作以及YAHSP中使用的“超前”状态。利用无用的操作和随机搜索,当遇到死胡同时,我们可以从初始状态重新开始本地搜索。而不是诉诸最佳优先搜索。我们提供分析以证明我们的重新启动策略的有效性,并显示新计划算法在多个领域都有效的结果。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号