The Research Of Constraint Satisfaction Problem And Its Application In Configuration

Constraint Satisfaction Problem(CSP) has played an important role in Artifical Intelligence. It can be applied into many real world problems. Such as Configuration, Map Coloring, Scheduling, Planning. A CSP is a triple P={X, D, C}where X is a finite set of variables X={x1,x2,…,xn},D is a corresponding finite set of domains D={D1, D2,…,Dn} such that Di is the domain of xi , C is a finite set of constraints C={c1,c2,…,ck}.A solution to the CSP P is an n-tuple S={v1,v2,…,vk}where vi∈Di and each cj is satisfied according to S. Solving a CSP is NP-complete. In many solving algorithms, Backtracking(BT) is currently the most important. BT algorithms can be divided into two classes which are look-back and look-forward. The look-forward algorithms are usually separated into two parts, search and constraint propagation. The most popular algorithms are BT with consistence technology, which use the arc consistence algorithm to delete the redundant values, if arc consistence check fails, it backtracks. The typical algorithm of look-forward is Maintaining Arc Consistecne(MAC) based on AC4, which was proposed by Sabin and Freuder in 1994. The main idea of look-back is recording the conflict location, if an assignment fails, it directly backtracks to the variable which lead to the conflict. It avoids the defect of backtracking by order. The typical algorithm of look-forward is Dynamic Backtracking(DBT), which was proposed by Ginsberg in 1993. Solving a CSP is NP-complete, therefore.There are two works about solving a CSP in this article.1. This work improves the classical look-back algorithm---Dynamic Backtracking. Giving three different strategies to implement DBT. The differences among the three strategies are the location of inserting the backtracked variable into uninstantiated queue. Implementing three different assignment strategied by insert the backtracked variable into different location of uninstantiated queue. After analyzing the experiment, this work proposed the Assignment Successful Principle(ASP). Additionally, it combines the ASP with the FFP ,and gives a more efficient strategy without increasing the Time complexity and the Space complexity.2. In most cases, people need only one solution to a CSP in practice. This work proposes an algorithm of solving CSPs based on cycle-cut. The main idea of the algorithm is transforming a CSP into an equivalent CSP without cycles, and the CSPs without cycles can be solved by the backtrack-free algorithms. After assigning a value to a variables i, it executes the Arc Consistecne algorithm. It takes the property of AC as its theoretic foundation, if the AC algorithm executes successfully, it means that every value in the domains of the variables that associated with i supports the assignment of i, then all the variables that associated with i and all the constraints that involves i can be temporarily removed from the constraint graph. If i is a part of a cycle, the cycle can be cut. According to the notion of cycle-cutset proposed by Detcher, we firstly assign values for the variables in cycle-cutset, if all the variables in cycle-cutset have been assigned successfully, then the constraint graph can be cut into a cycle-free graph and it can be solved by an efficient backtrack-free algorithm for tree-structure CSPs. Different from the previous methods based on cycle-cut, this algorithm can ensure that the cut problem is solvable. The experimental results show that while solving the random CSPs which thin density of constraints, CCS can reach a maximum of 2.3 times than MAC, and while solving the four groups of benchmark, CCS is more efficient than MAC ,and CCS can reach up to 4,000 times more efficient than MAC.With the rapid development of manufacturing and the increasing of users'requirement, the traditional uniform production mode can not meet the demands, configurator is proposed under such background. Configuration has has occupied an important position in the field of artificial intelligence. The famous conferences- International Joint Conference on Artificial Intelligence and European Conference on Artificial Intelligence- have the special topic on Configuration. There are several knowledge representations for Configuration, based on logic, based on structure and based on constraint. The Configuration based on constraint is the most common one. The Configuration based on constraint is to modeling the product model by CSPs. The configurable product parameters can be seen as the variables of CSPs, the configurable value of the product parameters can be seen as the domains of CSPs, and the production rules can be seen as the constraints of CSPs. The CSPs can represent Configuration perfectly, therefore, the classical algorithms for CSPs can be applied to Configuration. Distinguished from classical CSP, Configuration has some characteristics as follows.1 The product model will not change in short term once it has been built successfully.2 The configuration process is interactive.3 The configurator must show the explanations if there exists conflicts during the configuration process.4 The product models are always the CSPs with sparse constraints, and some variables in the model may has no constraint, either direct or indirect.According to the forth characteristic, this work proposes a decompose method based on Equivalence Class Partition for Configuration. We give the definition of Correlative Relation and Equivalence to describe the problem. This method decomposes the model conform to the Correlative Relation between the variables, it put the variables that will affect each other during the constraint propagation process into one Equivalence. This method can partition the product model into some sub-problems. We analyse the typical algorithms of look-forward and look-back with Equivalence Class Partition. We point out the improvements after the partition for backtracking algorithms with depth first strategy and backtrack in order. Furthermore, We show the advantages of Dynamic Backtracking with the partition. In the explanation aspect, we combine the partition method with QuickXplain. The experiments show that no matter in the aspect of solving or computing the explanation, the Equivalence Class Partition can improve the efficiency.