• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>International Conference on Artificial Intelligence Planning and Scheduling; 2000414-17; Breckenridge,CO(US) >Admissible Heuristics for Optimal Planning
【24h】

Admissible Heuristics for Optimal Planning

机译：最优规划的可允许启发式

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

HSP and HSPr are two recent planners that search the state-space using an heuristic function extracted from Strips encodings. HSP does a forward search from the initial state recomputing the henristic in every state, while HSPr does a regression search from the goal computing a suitable representation of the heuristic only once. Both planners have shown good performance, often producing solutions that are competitive in time and number of actions with the solutions found by Graphplan and SAT planners. HSP and HSPr, however, are not optimal planners. This is because the heuristic function is not admissible and the search algorithms are not optimal. In this paper we address this problem. We formulate a new admissible heuristic for planning, use it to guide an IDA* search, and empirically evaluate the resulting optimal planner over a number of domains. The main contribution is the idea underlying the heuristic that yields not one but a whole family of polynomial and admissible heuristics that trade accuracy for efficiency. The formulation is general and sheds some light on the heuristics used in HSP and Graphplan, and their relation. It exploits the factored (Strips) representation of planning problems, mapping shortest-path problems in state-space into suitably defined shortest-path problems in atom-space. The formulation applies with little variation to sequential and parallel planning, and problems with different action costs.
机译：HSP和HSPr是最近的两个计划者，它们使用从Strips编码中提取的启发式函数来搜索状态空间。 HSP从初始状态进行正向搜索，以重新计算每种状态下的启发式，而HSPr从目标进行回归搜索，仅计算一次启发式的合适表示。两位计划者都表现出了良好的性能，他们经常使用Graphplan和SAT计划者找到的解决方案，在时间和动作数量上都具有竞争力。但是，HSP和HSPr并不是最佳计划者。这是因为启发式函数是不允许的，并且搜索算法不是最佳的。在本文中，我们解决了这个问题。我们制定了一种新的可允许的启发式计划，用于指导IDA *搜索，并根据经验评估了多个领域中的最佳计划者。主要的贡献是启发式思想的基础，该思想不仅产生一个多项式，而且产生一系列的多项式和可允许的启发式，它们以准确性为代价。该表述是一般性的，并阐明了HSP和Graphplan中使用的启发式方法及其关系。它利用规划问题的分解（带状）表示，将状态空间中的最短路径问题映射为原子空间中适当定义的最短路径问题。该表述适用于顺序计划和并行计划的几乎没有变化，并且存在具有不同操作成本的问题。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号