首页> 外文会议>International Conference on Automated Planning and Scheduling(ICAPS 2007); 2007; >From Conformant into Classical Planning: Efficient Translations That May be Complete Too
【24h】

From Conformant into Classical Planning: Efficient Translations That May be Complete Too

机译:从合规到古典规划:可能太完整的高效翻译

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

摘要

Focusing on the computation of conformant plans whose verification can be done efficiently, we have recently proposed a polynomial scheme for mapping conformant problems P with deterministic actions into classical problems K(P). The scheme is sound as the classical plans are all conformant, but is incomplete as the converse relation does not always hold. In this paper, we extend this work and consider an alternative, more powerful translation based on the introduction of epistemic tagged literals KL/t where L is a literal in P and t is a set of literals in P unknown in the initial situation. The translation ensures that a plan makes KL/t true only when the plan makes L certain in P given the assumption that t is initially true. We show that under general conditions the new translation scheme is complete and that its complexity can be characterized in terms of a parameter of the problem that we call conformant width. We show that the complexity of the translation is exponential in the problem width only, find that the width of almost all benchmarks is 1, and show that a conformant planner based on this translation solves some interesting domains that cannot be solved by other planners. This translation is the basis for To, the best performing planner in the Conformant Track of the 2006 International Planning Competition.
机译:着重于可以有效完成验证的一致性计划的计算,我们最近提出了一种多项式方案,用于将具有确定性动作的一致性问题P映射到经典问题K(P)中。由于经典计划都是一致的,因此该方案是合理的,但是由于逆向关系并不总是成立,因此该方案是不完整的。在本文中,我们将扩展这项工作,并在引入认知标记文字KL / t的基础上,考虑一种替代的,功能更强大的翻译,其中L是初始情况下P中的文字,而t是P中未知的一组文字。该转换确保仅在假设t最初为真的情况下,当计划在P中使L确定时,才能使计划KL / t为真。我们表明,在一般条件下,新的翻译方案是完整的,并且其复杂性可以通过我们称为一致宽度的问题参数来表征。我们证明翻译的复杂度仅在问题宽度上是指数的,发现几乎所有基准的宽度都是1,并且表明基于此翻译的一致计划者可以解决一些其他计划者无法解决的有趣领域。此翻译是To(2006年国际规划大赛合格路线)中表现最好的规划师的基础。

著录项

相似文献

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

客服邮箱:kefu@zhangqiaokeyan.com

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

  • 服务号