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     

Consistency in networks of relations

Artificial intelligence tasks which can be formulated as constraint satisfaction problems, with which this paper is for the most part concerned, are usually by solved backtracking the examining the thrashing behavior that nearly always accompanies backtracking, identifying three of its causes and proposing remedies for them we are led to a class of algorithms whoch can profitably be used to eliminate local (node, arc and path) inconsistencies before any attempt is made to construct a complete solution. A more general paradigm for attacking these tasks is the altenation of constraint manipulation and case analysis producing an OR problem graph which may be searched in any of the usual ways.Many authors, particularly Montanari and Waltz, have contributed to the development of these ideas; a secondary aim of this paper is to trace that history. The primary aim is to provide an accessible, unified framework, within which to present the algorithms including a new path consistency algorithm, to discuss their relationships and the may applications, both realized and potential of network consistency algorithms.     

Backjump-based backtracking for constraint satisfaction problems

The performance of backtracking algorithms for solving finite-domain constraint satisfaction problems can be improved substantially by look-back and look-ahead methods. Look-back techniques extract information by analyzing failing search paths that are terminated by dead-ends. Look-ahead techniques use constraint propagation algorithms to avoid such dead-ends altogether. This paper describes a number of look-back variants including backjumping and constraint recording which recognize and avoid some unnecessary explorations of the search space. The last portion of the paper gives an overview of look-ahead methods such as forward checking and dynamic variable ordering, and discusses their combination with backjumping.     

约束满足混合算法求解并行机Job-Shop调度问题

分析并行机Job-Shop调度问题的特点并建立其约束满足优化模型,结合约束满足与变邻域搜索技术设计了一个求解该问题的混合优化算法。该算法采用变量排序方法和值排序方法选择变量并赋值,利用回溯和约束传播消解资源冲突,生成初始可行调度,然后应用局部搜索技术增强收敛性,并通过结合问题特点设计的邻域结构的多样性提高求解质量。数据实验表明,提出的算法与其他两种算法相比,具有一定的可行性和有效性。     

Concurrent search for distributed CSPs

A distributed concurrent search algorithm for distributed constraint satisfaction problems (DisCSPs) is presented. Concurrent search algorithms are composed of multiple search processes (SPs) that operate concurrently and scan non-intersecting parts of the global search space. Each SP is represented by a unique data structure, containing a current partial assignment (CPA), that is circulated among the different agents. Search processes are generated dynamically, started by the initializing agent, and by any number of agents during search.In the proposed, ConcDB, algorithm, all search processes perform dynamic backtracking. As a consequence of backjumping, a search space can be found unsolvable by a different search process. This enhances the efficiency of the ConcDB algorithm. Concurrent Dynamic Backtracking is an asynchronous distributed algorithm and is shown to be faster than former algorithms for solving DisCSPs. Experimental evaluation of ConcDB, on randomly generated DisCSPs demonstrates that the network load of ConcDB is similar to the network load of synchronous backtracking and is much lower than that of asynchronous backtracking. The advantage of Concurrent Search is more pronounced in the presence of imperfect communication, when messages are randomly delayed.     

概率最大受限路径相容算法

研究了可用于求解约束满足问题的最大受限路径相容算法(maxRPC).maxRPC算法执行过程中有大量无效的寻找路径相容证明(PC-witness)的操作,有效地识别和避免这些无效的寻找PC-witness的操作,可以提高maxRPC算法的求解效率.首先,提出了在一条约束上任意两个相容的值在任意路径上存在PC-witness的概率;然后,基于这一概率提出了一种概率最大受限路径相容算法(PmaxRPC),并将新算法成功应用于求解约束满足问题的回溯搜索.实验结果显示:PmaxRPC可以避免一部分无效的寻找PC-witness的操作,在求解约束满足问题时,PmaxRPC效率高于maxRPC.在某些测试用例上,PmaxRPC比maxRPC和最流行的弧相容算法效率更高.     

基于动态度的回溯算法求解大值域约束满足问题

针对一个具有精确可满足性相变现象的大值域随机约束满足问题,提出了两种启发式动态回溯算法,即基于动态度的ddeg-MAC（dynamic degree-maintaining arc consistency）回溯算法和基于值域与动态度比值的dom/ddeg-MAC（dom/dynamic degree-maintaining arc consistency）回溯算法。这两种算法分别基于ddeg和dom/ddeg挑选变量,利用维持弧相容（MAC）技术为挑选的变量进行赋值。当赋值无法进行时,再执行动态回溯修正变量的赋值。数值实验结果表明：在控制参数非常接近理论相变点时,算法仍然能够有效地找到问题的解。与经典回溯算法相比,这两种启发式动态回溯算法具有显著的优越性。     

Itemset mining: A constraint programming perspective

The field of data mining has become accustomed to specifying constraints on patterns of interest. A large number of systems and techniques has been developed for solving such constraint-based mining problems, especially for mining itemsets. The approach taken in the field of data mining contrasts with the constraint programming principles developed within the artificial intelligence community. While most data mining research focuses on algorithmic issues and aims at developing highly optimized and scalable implementations that are tailored towards specific tasks, constraint programming employs a more declarative approach. The emphasis lies on developing high-level modeling languages and general solvers that specify what the problem is, rather than outlining how a solution should be computed, yet are powerful enough to be used across a wide variety of applications and application domains.This paper contributes a declarative constraint programming approach to data mining. More specifically, we show that it is possible to employ off-the-shelf constraint programming techniques for modeling and solving a wide variety of constraint-based itemset mining tasks, such as frequent, closed, discriminative, and cost-based itemset mining. In particular, we develop a basic constraint programming model for specifying frequent itemsets and show that this model can easily be extended to realize the other settings. This contrasts with typical procedural data mining systems where the underlying procedures need to be modified in order to accommodate new types of constraint, or novel combinations thereof. Even though the performance of state-of-the-art data mining systems outperforms that of the constraint programming approach on some standard tasks, we also show that there exist problems where the constraint programming approach leads to significant performance improvements over state-of-the-art methods in data mining and as well as to new insights into the underlying data mining problems. Many such insights can be obtained by relating the underlying search algorithms of data mining and constraint programming systems to one another. We discuss a number of interesting new research questions and challenges raised by the declarative constraint programming approach to data mining.     

约束可满足性中求解RB模型实例的算法综述

约束满足问题是人工智能领域中最基本的NP完全问题之一。多年来,随着约束满足问题的深入研究,国内外学者提出多种实例模型。其中,RB模型是一种能生成具有精确相变的增长域约束满足问题实例,其求解难度极具挑战性。为了寻找其求解的新型高效算法,促进约束可满足问题的RB模型求解算法领域的研究,首先从约束满足问题的模型发展、求解技术进行分析;其次,对各类求解RB模型实例算法进行梳理,将求解的算法文献划分为回溯启发式类、信息传播类和元启发式类相关改进算法,从算法原理、改进策略、收敛性和精确度等方面进行对比综述;最后给出求解RB模型实例算法的研究趋势和发展方向。     

Intractable unifiability problems and backtracking

Restrictions of the problem of finding all maximal unifiable or minimal nonunifiable subsets to those of certain sizes are shown to be NP-hard, and consequently inappropriate in general for reducing thrashing by intelligent backtracking in resolution theorem provers and logic program executions. We also show that existing backtrack methods based on the computation of all maximal unifiable subsets of assignments as a means to avoid thrashing are intractable because the solution length of these subsets can increase exponentially with the input length, and we give a corresponding result for minimal nonunifiability. The results apply not only to standard unification, but to a characterized collection of unification algorithms which includes unification without the occurs check. This now justifies the necessity for approximate or heuristic approaches to reduce thrashing in resolution theorem provers and the execution of logic programs.A version of this paper appears in Proceedings of the Third International Logic Programming Conference, London, Lecture Notes in Computer Science, Springer 225, 107–121 (1986).     

约束满足问题的局部一致性维护理论与方法

人工智能与计算机科学中的许多问题都可视为约束满足问题,为了简化问题的求解,常采用局部一致性方法减小搜索空间。本文首先介绍与分析了着眼于全局一致性的局部处理的理论与方法,以及尽可能消除回溯因素的局部一致性方法,最后给出了一种在减少局部一致性维护代价上优于已有方法的新算法。     

Special issue on distributed computing and artificial intelligence

4:1! Google’s artificial intelligence (AI) program, AlphaGo, has won Go Master Lee Sedol in a best-of-five competition held in Korean March 9?15, 2016. Seen by many as a landmark moment for AI, the outcome did not come as a surprise, considering the excellent combination of 1920 CPUs with sophisticated AI algorithms, including neural networks and Monte Carlo tree search (Gibney, 2016; Silver et al., 2016). Indeed, research on distributed computing and artificial intelligence (DCAI) has matured during the last decade and many effective applications are now deployed, performing an increasingly important role in modern computer science, including the two most hyped technologies: Internet of Things and Big Data. Indeed, it is fair to say that the application of artificial intelligence in distributed environments is becoming an essential element of high added value and economic potential.     

等待时间受限Flowshop调度的HGA算法

针对等待时间受限的Flowshop调度问题,提出嵌入约束满足和变邻域搜索技术的混合遗传算法。该算法基于约束满足思想,通过递归回溯和约束传播修复工件的开工时间,以解消工件在相邻阶段的等待时间受限冲突,根据回溯工件的位置信息设计相应的交叉算子和变异算子,利用变邻域搜索技术增强算法的收敛性。仿真实验表明该混合遗传算法的有效性,并分析等待时间上限对目标值的影响。     

Knowledge-based tools for development of engineering theories

An approach to solving of the knowledge integration problem on the basis of engineering theories had been considered by Vittikh (Artif. Intell. Engng, 1997, 11). Current paper describes constraint-oriented tools for generation of engineering models which are organized around a constraint-oriented knowledge base. It also allows use of them for maintaining this approach. Many efforts in the field of artificial intelligence are concentrated on solving geometric constraint satisfaction problems in a specific domain. This paper describes the solving of a geometric constraint system called ANMEC that has been created with the use of these tools. The way the system is applied to tasks of mechanism's analysis and synthesis is considered.     

Experimental Analysis of Numeric and Symbolic Constraint Satisfaction Techniques for Temporal Reasoning

Many temporal applications like planning and scheduling can be viewed as special cases of the numeric and symbolic temporal constraint satisfaction problem. Thus we have developed a temporal model, TemPro, based on the interval Algebra, to express such applications in term of qualitative and quantitative temporal constraints. TemPro extends the interval algebra relations of Allen to handle numeric information. To solve a constraint satisfaction problem, different approaches have been developed. These approaches generally use constraint propagation to simplify the original problem and backtracking to directly search for possible solutions. The constraint propagation can also be used during the backtracking to improve the performance of the search. The objective of this paper is to assess different policies for finding if a TemPro network is consistent. The main question we want to answer here is how much constraint propagation is useful for finding a single solution for a TemPro constraint graph. For this purpose, we have experimented by randomly generating large consistent networks for which either arc and/or path consistency algorithms (AC-3, AC-7 and PC-2) were applied. The main result of this study is an optimal policy combining these algorithms either at the symbolic (Allen relation propagation) or at the numerical level.     

STR2: optimized simple tabular reduction for table constraints

Table constraints play an important role within constraint programming. Recently, many schemes or algorithms have been proposed to propagate table constraints and/or to compress their representation. In this paper, we describe an optimization of simple tabular reduction (STR), a technique proposed by J. Ullmann to dynamically maintain the tables of supports when generalized arc consistency (GAC) is enforced/maintained. STR2, the new refined GAC algorithm we propose, allows us to limit the number of operations related to validity checking and search of supports. Interestingly enough, this optimization makes simple tabular reduction potentially r times faster where r is the arity of the constraint(s). The results of an extensive experimentation that we have conducted with respect to random and structured instances indicate that STR2 is usually around twice as fast as the original STR, two or three times faster than the approach based on the hidden variable encoding, and can be up to one order of magnitude faster than previously state-of-the-art (generic) GAC algorithms on some series of instances. When comparing STR2 with the more recently developed algorithm based on multi-valued decision diagrams (MDDs), we show that both approaches are rather complementary.     

Boosting Search with Variable Elimination in Constraint Optimization and Constraint Satisfaction Problems

There are two main solving schemas for constraint satisfaction and optimization problems: i) search, whose basic step is branching over the values of a variables, and ii) dynamic programming, whose basic step is variable elimination. Variable elimination is time and space exponential in a graph parameter called induced width, which renders the approach infeasible for many problem classes. However, by restricting variable elimination so that only low arity constraints are processed and recorded, it can be effectively combined with search, because the elimination of variables may reduce drastically the search tree size.In this paper we introduce BE-BB(k), a hybrid general algorithm that combines search and variable elimination. The parameter k controls the tradeoff between the two strategies. The algorithm is space exponential in k. Regarding time, we show that its complexity is bounded by k and a structural parameter from the constraint graph. We provide experimental evidence that the hybrid algorithm can outperform state-of-the-art algorithms in constraint satisfaction, Max-CSP and Weighted CSP. Especially in optimization tasks, the advantage of our approach over plain search can be overwhelming.     

HYBRID ALGORITHMS FOR THE CONSTRAINT SATISFACTION PROBLEM

It might be said that there are five basic tree search algorithms for the constraint satisfaction problem (csp), namely, naive backtracking (BT), backjumping (BJ), conflict-directed backjumping (CBJ), backmarking (BM), and forward checking (FC). In broad terms, BT, BJ, and CBJ describe different styles of backward move (backtracking), whereas BT, BM, and FC describe different styles of forward move (labeling of variables). This paper presents an approach that allows base algorithms to be combined, giving us new hybrids. The base algorithms are described explicitly, in terms of a forward move and a backward move. It is then shown that the forward move of one algorithm may be combined with the backward move of another, giving a new hybrid. In total, four hybrids are presented: backmarking with backjumping (BMJ), backmarking with conflict-directed backjumping (BM-CBJ), forward checking with backjumping (FC-BJ), and forward checking with conflict-directed backjumping (FC-CBJ). The performances of the nine algorithms (BT, BJ, CBJ, BM, BMJ, BM-CBJ, FC, FC-BJ, FC-CBJ) are compared empirically, using 450 instances of the ZEBRA problem, and it is shown that FC-CBJ is by far the best of the algorithms examined.     

A Foundation of Solution Methods for Constraint Hierarchies

Constraint hierarchies provide a framework for soft constraints, and have been applied to areas such as artificial intelligence, logic programming, and user interfaces. In this framework, constraints are associated with hierarchical preferences or priorities called strengths, and may be relaxed if they conflict with stronger constraints. To utilize constraint hierarchies, researchers have designed and implemented various practical constraint satisfaction algorithms. Although existing algorithms can be categorized into several approaches, what kinds of algorithms are possible has been unclear from a more general viewpoint. In this paper, we propose a novel theory called generalized local propagation as a foundation of algorithms for solving constraint hierarchies. This theory formalizes a way to express algorithms as constraint scheduling, and presents theorems that support possible approaches. A benefit of this theory is that it covers algorithms using constraint hierarchy solution criteria known as global comparators, for which only a small number of algorithms have been implemented. With this theory, we provide a new classification of solution criteria based on their difficulties in constraint satisfaction. We also discuss how existing algorithms are related to our theory, which will be helpful in designing new algorithms.