• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Proceedings of the Twentieth international conference on automated planning and scheduling >Classical Planning in MDP Heuristics: With a Little Help from Generalization
【24h】

Classical Planning in MDP Heuristics: With a Little Help from Generalization

机译：MDP启发式中的经典计划：在归纳法的帮助下

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

摘要

Heuristic functions make MDP solvers practical by reducing their time and memory requirements. Some of the most effective heuristics (e.g., the FF heuristic function) first deter-minize the MDP and then solve a relaxation of the resulting classical planning problem (e.g., by ignoring delete effects). While these heuristic functions are fast to compute, they frequently yield overly optimistic value estimates. It is natural to wonder, then, whether the improved estimates of using a full classical planner on the (non-relaxed) determinized domain will provide enough gains to compensate for the vastly increased cost of computation.rnThis paper shows that the answer is "No and Yes". If one uses a full classical planner in the obvious way, the cost of the heuristic function's computation outweighs the benefits. However, we show that one can make the idea practical by generalizing the results of classical planning successes and failures. Specifically, we introduce a novel heuristic function called GOTH that amortizes the cost of classical planning by 1) extracting basis functions from the plans discovered during heuristic computation, 2) using these basis functions to generalize the heuristic value of one state to cover many others, and 3) thus invoking the classical planner many fewer times than there are states. Experiments show that GOTH can provide vast time and memory savings compared to the FF heuristic function - especially on large problems.
机译：启发式功能通过减少MDP求解器的时间和内存需求使其实用。一些最有效的启发式方法（例如FF启发式功能）首先确定MDP，然后解决所产生的经典计划问题的松弛（例如，通过忽略删除效果）。尽管这些启发式函数可以快速计算，但它们经常会产生过于乐观的价值估算。那么，很自然地想知道，在（非松弛）确定域上使用完整经典规划器的改进估计值是否可以提供足够的收益来补偿大幅增加的计算成本。rn本文表明答案是“是的”。如果人们以明显的方式使用完整的经典计划器，则启发式函数的计算成本将超过收益。但是，我们表明，通过概括经典计划的成功和失败的结果，可以使该想法可行。具体来说，我们引入一种称为GOTH的新颖启发式函数，该函数通过以下方式摊销经典计划的成本：1）从启发式计算过程中发现的计划中提取基础函数，2）使用这些基础函数概括一个状态的启发式值以涵盖许多其他状态， （3）因此，调用经典计划程序的次数比状态调用次数少。实验表明，与FF启发式功能相比，GOTH可以节省大量时间和内存-特别是在大问题上。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号