Inference Based Algorithms For Solving Constraint Satisfaction Problems

Constraint Satisfaction Problem(CSP) , as an important research branch in artificial intelligence, is a hotspot recently. A Constraint Satisfaction Problem is defined by a finite set of variables, a set of finite domains, and a finite set of constraints. Each variable takes its values in a domain, and each constraint restricts the combinations of values that can be taken by the variables. A solution to a CSP is a set of values assign to all variables, which satisfies all the constraints. Solving the CSP is to find a solution or all solutions, and solving a constraint optimization problem is to find an optimization solution.Practically, in the real world there are all kinds of combinatorial optimization problems which are connected with the constraints, such as scheduling in industry, logistics, product configuration problem, network routing problem, diagnose, distributed constraint optimization, and workforce management.Searching for solutions (the optimization solutions) of those problems always needs enumerate assignments in exponentially sized solution space. In the past, there are two methods to solve this kind of problems: handwork and tradition methods in operational research. But it makes the process of modeling become very complex, and sometimes obtains an irrational solution. When solving some kind of constraint satisfaction problems, we can use the domain knowledge to design a specialized algorithm, which usually get a better efficiency. For example, after researchers studied the n-queen problems, they proposed a very efficient method. However, designing specialized algorithms needs enormous overhead, and the algorithms will not be available even problems have a slight change. As a result, designing a generalized system for solving CSPs is significant.According to the book"constraint processing"written by Rina Dechter, who is Professor of college of information and computer science, California university, USA, the technology of solving CSPs is divided into two kinds: search and inference. The main algorithm of search is backtracking, and inference contains variable elimination and consistency technology. Those two algorithms have their own advantages and disadvantages. Inference is fit for solving lower density constraint network, and when the density of constraint network grow higher the time and space needed maybe increase exponentially. The worse time complexity of search algorithms is exponential, but the space needed is polynomial. In order to optimize the performance of the entire solving system, inference must be combined with search framework. With the cooperation of inference and search, time of search and space taken by inference can decrease.The searching algorithms follow the idea of generate and test, which derived from method to solve combinatorial optimization problems. It systematically generates and tests each possible combination of variable assignment, and checks whether it satisfies all the constraints. Other search algorithms can be regarded as the expansion forms of this method. Search algorithms are required inference technology to solve practical problems effectively. Backtracking searching algorithms needs consistency check to reduce the search space; Local searching requires tabu list and the corresponding inference methods to avoid trapping in a local minima time after time; artificial immunity usually added to genetic algorithms; Branch-and-bound algorithms use variable and value heuristics as well as methods of evaluating bounds; So how to add suitable inference technologies to the specific search strategy is the key factor of designing a constraint satisfaction algorithm. At present, consistency check, tree decomposition, bucket elimination, and counting solutions for variable and value heuristics are the main inference technologies, which are widely used in constraint solving.Inference methods for solving CSPs are the main contributions in this paper, we study and improve kinds of inference methods in backtracking search as well as local search. What's more, those methods are applied to classical and extended CSP models. In addition, a DFA reduction algorithm is designed based on knowledge compilation, which is used as an inference method for solving CSPs, and this algorithm can reduce the size of DFA greatly. The main four contributions are listed as follows:(1)In order to make the constraint satisfaction solving algorithm more efficient, this paper analyses processing of constraint propagation, and represents parameterized description of the arc consistency propagation depth by using variable domain retraction proportion, then proposes an arc consistency algorithm whose propagation degree is controllable, the same time studies the constraint solving algorithm's efficiency under different parameters. The algorithm is implemented under the platform of"Mingyue 1.0", and the results show that, the key factor that impacts the efficiency of the algorithm is constraint propagation degree, so through adjusting the control parameter, the algorithm can be 3 to 4 times faster.(2)Recently, dynamic CSPs were proposed as a powerful tool for solving many real-world problems on dynamic environments. As a result, several algorithms to solve dynamic CSPs were presented. Among those algorithms, Local Change (LC) algorithm based on solution reuse strategy is a method for solving many kinds of dynamic CSPs and efficient for flexible planning. On the basis of LC algorithm which is widely used, this paper integrates the tabu search strategy, and proposes a mini-conflict repair based algorithm, which is called Tabu_LC. The improved algorithm considers all the conflict variables as a whole, and then solves the sub-problems with branch and bound algorithm to find the best neighbor assignment, which improves the efficiency markedly. Furthermore, the Tabu_LC algorithm is implemented in the framework of constraint solving system"Ming-yue 1.0", and compared with the LC algorithm using large amount of Random CSPs. The experiment indicates that the improved algorithm overwhelmed the LC algorithm both on the efficiency and quality of solutions.(3)As the network technology being more and more popular, distributed CSPs become a new hotspot in AI. It extends the application of CSPs to the complex distributed environment. This paper improves the variable order strategy in concurrent search for solving distributed CSPs, combines dynamic variable ordering with concurrent search. At the same time, a method to select variables fit for distributed environment is proposed. Experiments of several random CSPs have been done, and the results show that the improved method performs better on efficiency and communication overhead.(4)Deterministic finite automaton (DFA) is used to compile CSPs and its application in product configuration got great successful. This paper studies reduction technology in the process of compiling. Considering the variable order for constructing DFA impacts structure of the DFA dramatically and the heuristic methods for computing variable order are not efficiency enough, a novel reduction algorithm, which is based on equivalent transform under difference variable order, is proposed to reduce the space taken by the DFA. In addition, the definitions on DFA equivalence under difference variable order and soundness of equivalent transform are given. Experiments based on automobile show that the proposed reduction algorithm can reduce space of DFA greatly in the processing of off-line compiling.