The distributed constraint satisfaction problem: formalization andalgorithms

We develop a formalism called a distributed constraint satisfaction problem (distributed CSP) and algorithms for solving distributed CSPs. A distributed CSP is a constraint satisfaction problem in which variables and constraints are distributed among multiple agents. Various application problems in distributed artificial intelligence can be formalized as distributed CSPs. We present our newly developed technique called asynchronous backtracking that allows agents to act asynchronously and concurrently without any global control, while guaranteeing the completeness of the algorithm. Furthermore, we describe how the asynchronous backtracking algorithm can be modified into a more efficient algorithm called an asynchronous weak-commitment search, which can revise a bad decision without exhaustive search by changing the priority order of agents dynamically. The experimental results on various example problems show that the asynchronous weak-commitment search algorithm is, by far more, efficient than the asynchronous backtracking algorithm and can solve fairly large-scale problems     

A graph-based immune-inspired constraint satisfaction search

We propose an artificial immune algorithm to solve constraint satisfaction problems (CSPs). Recently, bio-inspired algorithms have been proposed to solve CSPs. They have shown to be efficient in solving hard problem instances. Given that recent publications indicate that immune-inspired algorithms offer advantages to solve complex problems, our main goal is to propose an efficient immune algorithm which can solve CSPs. We have calibrated our algorithm using relevance estimation and value calibration (REVAC), which is a new technique recently introduced to find the parameter values for evolutionary algorithms. The tests were carried out using randomly generated binary constraint satisfaction problems and instances of the three-colouring problem with different constraint networks. The results suggest that the technique may be successfully applied to solve CSPs.     

Solving constraint satisfaction problems using hybrid evolutionarysearch

We combine the concept of evolutionary search with the systematic search concepts of arc revision and hill climbing to form a hybrid system that quickly finds solutions to static and dynamic constraint satisfaction problems (CSPs). Furthermore, we present the results of two experiments. In the first experiment, we show that our evolutionary hybrid outperforms a well-known hill climber, the iterative descent method (IDM), on a test suite of 750 randomly generated static CSPs. These results show the existence of a “mushy region” which contains a phase transition between CSPs that are based on constraint networks that have one or more solutions and those based on networks that have no solution. In the second experiment, we use a test suite of 250 additional randomly generated CSPs to compare two approaches for solving CSPs. In the first method, all the constraints of a CSP are known by the hybrid at run-time. We refer to this method as the static method for solving CSPs. In the second method, only half of the constraints of a CSPs are known at run-time. Each time that our hybrid system discovers a solution that satisfies all of the constraints of the current network, one additional constraint is added. This process of incrementally adding constraints is continued until all the constraints of a CSP are known by the algorithm or until the maximum number of individuals has been created. We refer to this second method as the dynamic method for solving CSPs. Our results show hybrid evolutionary search performs exceptionally well in the presence of dynamic (incremental) constraints, then also illuminate a potential hazard with solving dynamic CSPs     

Domain-dependent distributed models for railway scheduling

Many combinatorial problems can be modelled as Constraint Satisfaction Problems (CSPs). Solving a general CSP is known to be NP-complete, so closure and heuristic search are usually used. However, many problems are inherently distributed and the problem complexity can be reduced by dividing the problem into a set of subproblems. Nevertheless, general distributed techniques are not always appropriate to distribute real-life problems. In this work, we model the railway scheduling problem by means of domain-dependent distributed constraint models, and we show that these models maintained better behaviors than general distributed models based on graph partitioning. The evaluation is focused on the railway scheduling problem, where domain-dependent models carry out a problem distribution by means of trains and contiguous sets of stations.     

Algorithms for Distributed Constraint Satisfaction: A Review

When multiple agents are in a shared environment, there usually exist constraints among the possible actions of these agents. A distributed constraint satisfaction problem (distributed CSP) is a problem to find a consistent combination of actions that satisfies these inter-agent constraints. Various application problems in multi-agent systems can be formalized as distributed CSPs. This paper gives an overview of the existing research on distributed CSPs. First, we briefly describe the problem formalization and algorithms of normal, centralized CSPs. Then, we show the problem formalization and several MAS application problems of distributed CSPs. Furthermore, we describe a series of algorithms for solving distributed CSPs, i.e., the asynchronous backtracking, the asynchronous weak-commitment search, the distributed breakout, and distributed consistency algorithms. Finally, we show two extensions of the basic problem formalization of distributed CSPs, i.e., handling multiple local variables, and dealing with over-constrained problems.     

Structural decompositions for problems with global constraints

A wide range of problems can be modelled as constraint satisfaction problems (CSPs), that is, a set of constraints that must be satisfied simultaneously. Constraints can either be represented extensionally, by explicitly listing allowed combinations of values, or implicitly, by special-purpose algorithms provided by a solver. Such implicitly represented constraints, known as global constraints, are widely used; indeed, they are one of the key reasons for the success of constraint programming in solving real-world problems. In recent years, a variety of restrictions on the structure of CSP instances have been shown to yield tractable classes of CSPs. However, most such restrictions fail to guarantee tractability for CSPs with global constraints. We therefore study the applicability of structural restrictions to instances with such constraints. We show that when the number of solutions to a CSP instance is bounded in key parts of the problem, structural restrictions can be used to derive new tractable classes. Furthermore, we show that this result extends to combinations of instances drawn from known tractable classes, as well as to CSP instances where constraints assign costs to satisfying assignments.     

Ants can solve constraint satisfaction problems

We describe a novel incomplete approach for solving constraint satisfaction problems (CSPs) based on the ant colony optimization (ACO) metaheuristic. The idea is to use artificial ants to keep track of promising areas of the search space by laying trails of pheromone. This pheromone information is used to guide the search, as a heuristic for choosing values to be assigned to variables. We first describe the basic ACO algorithm for solving CSPs and we show how it can be improved by combining it with local search techniques. Then, we introduce a preprocessing step, the goal of which is to favor a larger exploration of the search space at a lower cost, and we show that it allows ants to find better solutions faster. Finally, we evaluate our approach on random binary problems     

On memoryless provers and insincere verifiers

In this article, we introduce a Prover–Verifier model for analysing the computational complexity of a class of constraint satisfaction problems (CSPs) termed boolean binary constraint satisfaction problems (BBCSPs). BBCSPs represent an extremely general class of CSPs and find applications in a wide variety of domains including constraint programming, puzzle solving and program testing. The constraints in a BBCSP permit the combination of multiple theories as opposed to traditional constraint systems in which all constraints belong to the same theory. We establish that each instance of a BBCSP admits a coin-flipping Turing machine that halts in time polynomial in the size of the input. Furthermore, the algorithm is oblivious in that it never sees more than one constraint at a time. The prover, P, in the Prover–Verifier model is endowed with very limited powers. In particular, it has no memory and it can only pose restricted queries to the verifier. The verifier, on the other hand, is both omniscient in that it is cognisant of all the problem details and insincere in that it does not have to decide a priori on the intended proof. However, the verifier must stay consistent in its responses, i.e. it cannot rule out a certain possibility in one response to a query from the prover and then rule in the same possibility in response to a subsequent query. We note that the combination of the resources required by the prover and the type of certificate demanded of the verifier, determine the resources required by an algorithm. Inasmuch as our provers will be memoryless and our verifiers will be asked for extremely simple certificates, our work establishes the existence of a simple, randomised algorithm for BBCSPs. Our model itself serves as a basis for the design of zero-knowledge machine learning algorithms in that the prover ends up learning the proof desired by the verifier. Likewise, our work finds applications in the domain of certifying algorithm design, wherein the goal is to provide a proof of correctness of the algorithm on the input instance by providing an easily checkable certificate.     

一种新的基于完全独立相容性的预处理技术

研究了求解约束满足问题(Constraint satisfaction problem, CSP)中的预处理技术. 首先提出了子论域上的完全独立相容性(Entirety singleton consistency, ESC)概念和相应算法, 分析并证明了算法的复杂性和正确性, 而后对其两条重要性质进行了详细证明. 基于此概念和性质, 提出了一种基于完全独立相容性的预处理算法: SAC-ESC算法, 并给出了正确性证明. 最后, 本文采用分治思想, 根据不同问题的论域自适应地合理划分其子论域. 实验结果表明, 对于随机问题、鸽巢问题、N皇后问题和基准用例, 算法SAC-ESC的执行效率大约是目前流行算法SAC-SDS和SAC-3的3~20倍.     

一种基于变量熵求解约束满足问题的置信传播算法

在置信传播(belief propagation,BP)算法中,提出一种基于变量熵来挑选变量从而固定变量赋值的策略,用于求解一类具有增长定义域的随机约束满足问题.RB模型是一个具有增长定义域的随机约束满足问题的典型代表,已经严格证明它不仅存在精确的可满足性相变现象,而且可以生成难解实例.在RB模型上选取两组不同的参数进行数值实验.结果表明:在接近可满足性相变点时,BP引导的消去算法仍然可以非常有效地找到随机实例的解;不断增加问题的规模,算法的运行时间呈指数级增长;并且当控制参数(约束紧度)增加时,变量的平均自由度逐渐降低.     

On the phase transitions of random k-constraint satisfaction problems

Constraint satisfaction has received increasing attention over the years. Intense research has focused on solving all kinds of constraint satisfaction problems (CSPs). In this paper, first we propose a random CSP model, named k-CSP, that guarantees the existence of phase transitions under certain circumstances. The exact location of the phase transition is quantified and experimental results are provided to illustrate the performance of the proposed model. Second, we revise the model k-CSP to a random linear CSP by incorporating certain linear structure to constraint relations. We also prove the existence of the phase transition and exhibit its exact location for this random linear CSP model.     

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

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

一个基于模拟退火的多主体模型及其应用

近些年,多主体系统的理论及应用得到了人们的广泛关注,并得以迅速发展.研究者提出了很多基于多主体系统理论的模型,用于求解各种问题.AER(Agent-environment-rules)模型正是一个用于求解约束满足问题较为成功的例子.但是,主体的静态策略选择在一定程度上限制了模型的求解性能.将模拟退火算法与多主体系统思想相结合,并赋予主体更为高效的动态策略选择的能力,提出了SAAER模型(simulated annealing based AER model).基于约束满足问题经典实例--N-Queen问题和染色问题的实验表明,改进后的模型较之原模型获得了更高的效率和稳定性.对于N=10000的大规模N-Queen问题,能在200s左右的时间求得精确解.     

Efficient handling of universally quantified inequalities

This paper introduces a new framework for solving quantified constraint satisfaction problems (QCSP) defined by universally quantified inequalities on continuous domains. This class of QCSPs has numerous applications in engineering and technology. We introduce a generic branch and prune algorithm to tackle these continuous CSPs with parametric constraints, where the pruning and the solution identification processes are dedicated to universally quantified inequalities. Special rules are proposed to handle the parameter domains of the constraints. The originality of our framework lies in the fact that it solves the QCSP as a non-quantified CSP where the quantifiers are handled locally, at the level of each constraint. Experiments show that our algorithm outperforms the state of the art methods based on constraint techniques. This paper is an extended version of a paper published at the SAC 2008 conference [15].     

Dynamic Flexible Constraint Satisfaction

Existing techniques for solving constraint satisfaction problems (CSPs) are largely concerned with a static set of imperative, inflexible constraints. Recently, work has addressed these shortcomings of classical constraint satisfaction in the form of two separate extensions known as flexible and dynamic CSP. Little, however, has been done to combine these two approaches in order to bring to bear the benefits of both in solving more complex problems. This paper presents a new integrated algorithm, Flexible Local Changes, for dynamic flexible problems. It is further shown how the use of flexible consistency-enforcing techniques can improve solution re-use and hence the efficiency of the core algorithm. Empirical evidence is provided to support the success of the present approach.     

Constraint reasoning with learning automata

This article presents a decision-maker model, called learning automaton, exhibiting adaptive behavior in highly uncertain stochastic environments. This learning model is used in solving constraint satisfaction problems (CSPs) by a procedure that can be viewed as hill climbing in probability space. the use of a fast learning algorithm that relaxes previous common assumptions is investigated. It is proven that the algorithm converges with probability 1 to a solution of the CSP and a set of test problems show that good performance can be achieved. In particular, it is shown that this method achieves a higher level of performance than that presented in a previous similar approach. Finally, it is estimated the speedup of a parallel implementation and the proposed algorithm is compared with a backtracking algorithm enhanced with standard CSP techniques. © 1994 John Wiley & Sons, Inc.     

Introduction to planning, scheduling and constraint satisfaction

Planning, scheduling and constraint satisfaction are important areas in artificial intelligence (AI). Many real-world problems are known as AI planning and scheduling problems, where resources must be allocated so as to optimize overall performance objectives. Therefore, solving these problems requires an adequate mixture of planning, scheduling and resource allocation to competing goal activities over time in the presence of complex state-dependent constraints. Constraint satisfaction plays also an important role to solve real-life problems, so that integrated techniques that manage planning and scheduling with constraint satisfaction remains necessary. This special issue on Planning, Scheduling and Constraint Satisfaction compiles a selection of papers of CAEPIA’2007 workshop on Planning, Scheduling and Constraint Satisfaction and COPLAS’2007: CP/ICAPS 2007 Joint Workshop on Constraint Satisfaction Techniques for Planning and Scheduling Problems. This issue presents novel advances on planning, scheduling, constraint programming/constraint satisfaction problems (CSPs) and many other common areas that exist among them. On the whole, this issue mainly focus on managing complex problems where planning, scheduling, constraint satisfaction and search must be combined and/or interrelated, which entails an enormous potential for practical applications and future research. Furthermore, this issue also includes a complete survey about constraint satisfaction, planning, scheduling and integration among these areas.     

High-Order Consistency in Valued Constraint Satisfaction

k-consistency operations in constraint satisfaction problems (CSPs) render constraints more explicit by solving size-k subproblems and projecting the information thus obtained down to low-order constraints. We generalise this notion of k-consistency to valued constraint satisfaction problems (VCSPs) and show that it can be established in polynomial time when penalties lie in a discrete valuation structure.A generic definition of consistency is given which can be tailored to particular applications. As an example, a version of high-order consistency (face consistency) is presented which can be established in low-order polynomial time given certain restrictions on the valuation structure and the form of the constraint graph.     

一种基于时间戳的简单表缩减算法

表约束是一种外延的知识表示方法,每个约束在对应的变量集上列举出所有支持或禁止的元组.广义弧相容（generalized arc consistency,简称GAC）是求解约束满足问题应用最广泛的相容性.Simple Tabular Reduction（STR）是一类高效的维持GAC的算法.在回溯搜索中,STR动态地删除无效元组,降低了查找支持的开销,并拥有单位时间的回溯代价,在高元表约束上获得了广泛运用,并有大量基于STR的改进算法被提出,其中,元组集的压缩表示是目前研究较多的方法.同样基于动态维持元组集有效部分的思想,为STR提出一种检测并删除无效元组和为变量更新支持的算法,作用于原始表约束并拥有单位时间的回溯代价.实验结果表明,该算法在表约束上维持GAC的效率普遍高于现有的非基于压缩表示的STR算法,并且在一些实例上的效率高于最新的基于元组集压缩表示的STR算法.     

Issues in the performance measurement of constraint-satisfaction techniques

The richness of the constraint satisfaction problem (or CSP) in representing combinatorial search maladies has resulted in a torrent of techniques for efficiently solving them. These techniques have focused on discovering better backtrack points, learning from dead-ends and avoiding repetitious interference, problem reduction method and the use of network heuristics. Much of this research has derived innovative methods for solving the CSP, however, the evaluations of the techniques have remained diverse and in many cases, statistically inaccurate.Another issue with regard to the performance measurement of constraint satisfaction techniques is the inability to model computational constraint processing cost. It is not uncommon to find evaluations that are based on CSPs that differ only on the percentage of constraints and the tightness of each constraint. This may be justifiable if it can be established that they are the only contributing factors of the performance variable. The three aspects mentioned above comprise this paper's main focus points. They come under the general headings of Modelling CSP Difficulty, Modelling Constraint Cost and Elucidating Major Performance Factors respectively. This paper seeks to provide a set of proposals with respect to the above three well-known areas so as collectively to enhance the robustness of evaluations conducted in the field of constraint satisfaction.