Local Search for Maximizing Satisfiability in Qualitative Spatial and Temporal Constraint Networks
Local Search for Maximizing Satisfiability in Qualitative Spatial and Temporal Constraint Networks
复制标题
定性空间和时间约束网络中最大化可满足性的局部搜索
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Lamjed Ben Saïd
中科院分区：
文献类型：
--
作者：
Jean;Ali Mensi;I. Nouaouri;Michael Sioutis;Lamjed Ben Saïd
在本文中，我们关注最近在空间和时间定性推理的背景下引入的一个问题，称为Max-QCN问题。这个问题涉及到在定性约束网络(QCN)中获得最大化满足约束的数量的空间或时间配置。为了有效地解决Max-QCN问题，我们引入并研究了部分最大可满足性问题(Pmax-SAT)的两类编码。这些编码中的每一种都是基于我们所说的关于所考虑的定性演算的合成表的禁止覆盖。直观地说，禁止覆盖允许我们以或多或少紧凑的方式来表达三个空间或时间实体的不可行的配置。我们用区间代数中的定性约束网络进行的实验表明了我们方法的兴趣。
In this paper, we focus on a recently introduced problem in the context of spatial and temporal qualitative reasoning, called the MAX-QCN problem. This problem involves obtaining a spatial or temporal configuration that maximizes the number of satisfied constraints in a qualitative constraint network (QCN). To efficiently solve the MAX-QCN problem, we introduce and study two families of encodings of the partial maximum satisfiability problem (PMAX-SAT). Each of these encodings is based on, what we call, a forbidden covering with regard to the composition table of the considered qualitative calculus. Intuitively, a forbidden covering allows us to express, in a more or less compact manner, the non-feasible configurations for three spatial or temporal entities. The experimentation that we have conducted with qualitative constraint networks from the Interval Algebra shows the interest of our approach.