• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>AI communications >Solving disjunctive temporal problems with preferences using maximum satisfiability
【24h】

Solving disjunctive temporal problems with preferences using maximum satisfiability

机译：使用最大可满足性来解决带有偏好的析取性时间问题

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

摘要

The Disjunctive Temporal Problem (DTP) involves conjunction of DTP constraints, each DTP constraint being a disjunction of difference constraints of the form x - y ≤ c, where x and y range over a domain of interpretation, and c is a numeric constant. The DTP is recognized to be an expressive framework for constraints modeling and processing. The addition of preferences, in the form of weights associated to difference constraints for their satisfaction, needs methods for aggregating preferences among and within DTP constraints to compute meaningful and high quality solutions, while further enhancing DTP expressivity and applicability. In this paper we consider an utilitarian aggregation of DTP constraints weights, and a prominent semantic for aggregating such weights from its difference constraints weights that considers the maximum among the weights associated to satisfied difference constraints in it. We present a novel approach that reduces the problem to Maximum Satisfiability of DTPs (Max-DTPs). In this way, we can employ off-the-shelf Max-DTP solvers with different solution methods, ranging from Satisfiability Modulo Theories (SMT), to interval-based and Boolean optimization-based solvers. We then compare the performance of our approach with different back-end solvers on both randomly generated and real-world benchmarks, in comparison with MAX1L1TIS, the best solver that can deal with DTPs with preferences using the aggregation methods considered. Results show that the YlCES SMT solver is the best, and that YlCES and the TS AT# solver based on Boolean optimization can be orders of magnitude faster than maxilitis.
机译：析取时间问题（DTP）涉及DTP约束的结合，每个DTP约束都是形式为x-y≤c的差异约束的析取，其中x和y在解释范围内，并且c是数字常数。 DTP被认为是用于约束建模和处理的表达框架。以与差异约束相关的权重的形式满足他们的满意度，偏好的添加需要在DTP约束之中和之内聚合偏好的方法，以计算有意义的高质量解决方案，同时进一步增强DTP的表达性和适用性。在本文中，我们考虑了DTP约束权重的功利性聚合，以及从其差分约束权重聚合此类权重的突出语义，该语义考虑了与其中满足的差分约束相关的权重中的最大值。我们提出了一种新颖的方法，可以将问题减少到DTP的最大满意度（Max-DTP）。通过这种方式，我们可以采用具有不同求解方法的现成的Max-DTP求解器，范围从满意度模理论（SMT）到基于区间和基于布尔优化的求解器。然后，我们将我们的方法与随机后端基准和实际基准上的不同后端求解器的性能进行比较，并与MAX1L1TIS进行比较，MAX1L1TIS是可以使用所考虑的聚合方法处理具有优先权的DTP的最佳求解器。结果表明，YlCES SMT求解器是最好的，基于布尔优化的YlCES和TS AT＃求解器比上颌炎的速度快几个数量级。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号