• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Proceedings of the Twentieth international conference on automated planning and scheduling >Constraint Propagation in Propositional Planning
【24h】

Constraint Propagation in Propositional Planning

机译：命题计划中的约束传播

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

摘要

Planning as Satisfiability is a most successful approach to optimal propositional planning. It draws its strength from the efficiency of state-of-the-art propositional satisfiability solvers, combined with the utilization of constraints that are inferred from the problem planning graph. One of the recent improvements of the framework is the addition of long-distance mutual exclusion (londex) constraints that relate facts and actions which refer to different time steps. In this paper we compare different encodings of planning as satisfiability wrt the constraint propagation they achieve in a modern SAT solver. This analysis explains some of the differences observed in the performance of different encodings, and leads to some interesting conclusions. For instance, the BLACKBOX encoding achieves more propagation than the one of SATPLAN0 6, and therefore is a stronger formulation of planning as satisfiability. Moreover, our investigation suggests a new more compact and stronger model for the problem. We prove that in this new formulation many of the londex constraints are redundant in the sense that they do not add anything to the constraint propagation achieved by the model. Experimental results suggest that the theoretical results obtained are practically relevant.
机译：作为可满足性进行计划是最佳命题计划的最成功方法。它从最先进的命题可满足性求解器的效率以及从问题计划图中推断出的约束的利用中汲取了力量。该框架的最新改进之一是增加了远距离互斥（londex）约束，这些约束将涉及不同时间步长的事实和动作联系起来。在本文中，我们比较了计划的不同编码，因为它们在现代SAT求解器中实现的约束传播具有可满足性。该分析解释了在不同编码性能方面观察到的一些差异，并得出了一些有趣的结论。例如，BLACKBOX编码比SATPLAN0 6中的编码实现了更多的传播，因此是将计划作为可满足性的更强有力的表述。此外，我们的调查提出了针对该问题的新的更紧凑，更强大的模型。我们证明，在这种新公式中，许多londex约束是多余的，因为它们不会对模型实现的约束传播添加任何内容。实验结果表明，所获得的理论结果具有实际意义。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号