Value ordering for quantified CSPs

We investigate the use of value ordering in backtracking search for Quantified Constraint Satisfaction problems (QCSPs). We consider two approaches for ordering heuristics. The first approach is solution-focused and is inspired by adversarial search: on existential variables we prefer values that maximise the chances of leading to a solution, while on universal variables we prefer values that minimise those chances. The second approach is verification-focused, where we prefer values that are easier to verify whether or not they lead to a solution. In particular, we give instantiations of this approach using QCSP-Solve’s pure-value rule Gent et al. (QCSP-solve: A solver for quantified constraint satisfaction problems. In Proceedings of IJCAI, pp. 138–143, 2005). We show that on dense 3-block problems, using QCSP-Solve, the solution-focused adversarial heuristics are up to 50% faster than lexicographic ordering, while on sparse loose interleaved problems, the verification-focused pure-value heuristics are up to 50% faster. Both types are up to 50% faster on dense interleaved problems, with one pure-value heuristic approaching an order of magnitude improvement. This work was supported in part by Microsoft Research through the European PhD Scholarship Programme, and by the Embark Initiative of the Irish Research Council for Science, Engineering and Technology (IRCSET).     

淀粉三(4-三氟甲氧基苯基氨基甲酸酯)手性固定相的制备及其手性识别能力

制备了基于淀粉三(4-三氟甲氧基苯基氨基甲酸酯)衍生物的涂敷型手性固定相(CSP1),并考察了其手性识别能力。研究表明:与商品化Chiralpak AD柱相比,CSP1显示出较低的手性识别能力;CSP1的手性识别能力随流动相中异丙醇含量的降低而升高;与以乙醇为流动相添加剂相比,使用异丙醇为添加剂更有利于对映体的分离。此研究拓展了多糖类衍生物手性固定相的种类。     

非二元约束满足问题求解

在约束满足问题(CSP)的研究中，大部分工作集中在二元约束，但处理实际问题时，常常会遇到非二元约束的情况．该文在概要地讨论了两类求解非二元约束问题方法的基础上，研究了一种将约束传播技术和一般弧相容回溯算法相结合的非二元约束求解方法，并在设计开发的约束求解工具“明月SOLVER1.0”中实现了该方法，以典型例子给出了实现系统的运行结果．     

A new approach to partial constraint satisfaction problems

A finite binary Constraint Satisfaction Problem (CSPs) is defined as consisting of a set of n problem variables, a domain of d potential values for each variable and a set of m binary constraints involving only two variables at a time. A solution to such a CSP is specified by assignment of a value to each variable that does not violate any of the constraints. The CSPs belong to the class of NP-Complete Problems. Backtracking and its variants have been generally used for solving CSPs. The class of Partial Constraint Satisfaction Problems (PCSPs) is a subclass of CSPs that are either too difficult to solve or are unsolvable. Near optimal solutions are always desired to these problems.

In this article, we have considered only finite binary CSPs or PCSPs and developed a method of time complexity O(n ² d ²) to obtain a near optimal solution for them. The performance of the method in terms of the average number of consistency checks and the average number of constraint violations is measured on various randomly generated binary CSPs and compared with the Branch and Bound (BB) method used to obtain the same solution. The BB method is a widely used optimization technique that may be viewed as a variation of backtracking. Thus, it was a natural choice in seeking an analog of backtracking to find optimal partial solutions for PCSPs. The proposed method moves much faster to the solution. The performance results indicate that in terms of the number of consistency checks, the proposed method has much less consistency checks than BB whereas in terms of average number of constraint violations both methods are same. An upper bound on the distance of the solution from the optimal solution is obtained analytically as ?n(n???2)(d???2)/(d???1)?.     

Production management as a constraint satisfaction problem

Production management problems can be quite straightforwardly presented as constraint satisfaction problems, where values for some variables are searched for under a set of constraints. A combination of an operation and a resource is usually interpreted as the variable, and a time window is usually interpreted as the value to be searched for. This convention is challenged. A case is considered where the most appropriate interpretation treats the combination of a resource and a time window as the variable, and an operation as the value. A third possible interpretation is also briefly covered, where the combination of an operation and a time window is the variable, and the resource is the value.     

一个基于最小冲突修补的动态约束满足求解算法

约束满足问题是人工智能中一个重要的研究方向,近年来,对动态变化的约束满足问题的研究逐渐成为该领域的热点.在目前该领域最流行的LC算法基础上,引入禁忌搜索策略,提出了一个基于最小冲突修补的算法Tabu_LC.算法在每次冲突调整时将所有冲突变量看成一个整体,并采用分支定界搜索策略求解冲突变量组成的子问题,极大地提高了求解效率.同时,在约束求解系统"明月1.0"架构下给出了算法的具体实现,并针对大量随机问题进行了对比实验.结果表明,Tabu_LC算法在求解效率和解的质量上都明显优于LC算法.     

基于结合空间拓扑和方向关系信息的空间推理

结合了定性空间推理中著名的区域连接演算（region connection calculus,RCC）和基于区域的方向关系演算（cardinal direction calculus,CDC）,并且给出两个演算在两个方向上的交互表,即RCC8-To-CDC和CDC-To-RCC8．给出了结合RCC8和CDC知识的约束满足问题的路径一致算法（path consistency algorithm）（该算法是对Allen著名的路径一致算法的修改）,并且采用两个队列实现了该算法,采用这种结构可以实现并行计算．在该算法中,基于以上两个交互表的交互操作被嵌入到算法里面来保证整个约束满足问题的一致性．算法的计算复杂性证明是多项式的,     

Current Approaches for Solving Over-Constrained Problems

We summarize existing approaches to model and solve overconstrained problems. These problems are usually formulated as combinatorial optimization problems, and different specific and generic formalisms are discussed, including the special case of multi-objective optimization. Regarding solving methods, both systematic and local search approaches are considered. Finally we review a number of case studies on overconstrained problems taken from the specialized literature.     

Cooperative Resolution of Over-Constrained Information Requests

In this paper, we present a constraint-based model of cooperative agents for information systems dialogues, with an emphasis on how the agents detect and resolve situations in which the user's information needs have been over-constrained. The constraint-based model of the information agents integrates and extends the AI techniques of constraint satisfaction, solution synthesis and constraint hierarchy, providing an incremental computational mechanism for constructing and maintaining partial parallel solutions. Such a mechanism supports immediate detection of over-constrained situations. In addition, we explore using the knowledge in the solution synthesis network to support different relaxation strategies to support cooperative dialogue behaviors.