Researches On The Propagation Algorithms For Constraint Satisfaction Problem

Artificial Intelligence(AI)is a strategic technology for the future.Constraint satisfaction problems are an intrinsic part of knowledge representation and reasoning within AI and mathematical logic.They are one of the most important tools for modeling decision-making and have been a popular area of research for many years.A constraint satisfaction problem is composed of three fundamental components:variables,domains,and constraints,which correspond to the objects that require reasoning,the set of other objects that will be assigned to the variables,and the relations that restrict the values that can be taken by a number of variables,respectively.The goal of solving a constraint satisfaction problem is to assign a value to each variable or to prove that no value can be assigned,provided that these relations are satisfied.Currently,the mainstream algorithm used for solving this problem is the backtracking search algorithm,which finds the solution by performing a depth-first search on the search tree.One of the key reasoning techniques of the backtracking search algorithm is constraint propagation,which aims to utilize consistency to reason about constraints,reduce the domains of unassigned variables associated with that constraint,and thus prune the search tree.Constraint propagation occurs after the domains of the variables have been reduced,and its high frequency of execution results in a significant portion of its runtime in the overall backtracking search.The smallest callback function of constraint propagation is the inference algorithm of various types of constraints.Therefore,improving the efficiency of the inference algorithm of various types of constraints is crucial for solving constraint satisfaction problems.Since all Different constraint,regular constraint and graph constraint are some of the most frequently used and classical constraints in the modelling scenarios of constraint satisfaction problems,improving the reasoning efficiency of these constraints can significantly enhance the performance of solving constraint satisfaction problem.Therefore,this paper aims to enhance the efficiency of solving constraint satisfaction problems by focusing on constraint propagation.It improves the reasoning efficiency of all Different and regular constraints,and extends the types of graph constraints and their propagation algorithms through scientific methods such as theoretical analysis,proposing new algorithms,providing theoretical proofs,and conducting experimental validation.The main researches of this paper are as follows:ⅰ.In order to improve the inference efficiency of the all Different constraint,this paper presents a generalized arc consistency algorithm for all Different constraint that eliminates the computation of strongly connected components and improve reasoning efficiency.Firstly,the concept named Reachable Set is defined as a set of vertices in the value graph of all Different constraint.After that,it is proven that any edge with an ending vertex is in the reachable set and a starting vertex out of the reachable set is redundant.Finally,an efficient generalized arc consistency algorithm was designed based on the new finding,the algorithm filters values in the all Different constraint that do not satisfy generalized arc consistency by computing the reachable sets.In the first run,the algorithm calculates the reachable sets for all variables in the constraint.After that,the algorithm recalculates the reachable sets only for the variables whose domains have been changed.The experimental results demonstrate that the new algorithm outperforms all state-ofthe-art generalized arc consistency algorithms.The new algorithm significantly improves not only all Different constraints but also indirectly improves the propagation algorithms for other constraints.It is believed that this new algorithm could be a candidate propagator for constraint solvers to handle the all Different constraint.ⅱ.In order to improve the inference efficiency of regular constraints,this paper proposes a new generalized arc consistency filtering algorithm for it.In the new proposed algorithm,the state transitions in a deterministic finite automaton are stored in a number of bit vectors,and the algorithm represents the automaton in regular constraints by special bit vectors,after which the algorithm utilizes bitwise operations to speed up the enforcement of generalized arc consistency.The algorithm proposed in this paper follows a specific rule: if a value is valid in the domain to which it belongs,the bit vector corresponding to that value must not be the empty vector after a logical and operation with the bit vector representing the automaton.In addition,this paper proposes an incremental algorithm that effectively enforces generalized arc consistency,which further improves the reasoning efficiency.The experimental results suggest that the proposed algorithm outperforms the classical algorithm in terms of time and memory consumption.The new propagation algorithm for regular constraints could be a valuable addition to constraint solvers for handling regular constraints.ⅲ.Although there are numerous graph constraints that cover most scenarios modeled using constraint satisfaction problems,existing graph constraints cannot express variable relationships in some scenarios,such as requiring adjacent vertices in a path on a graph to satisfy a certain distance relation,which is known as a transitive relation.This paper proposes two new constraints for expressing the transitive relation.These constraints restrict several variables by formal paths that require the sum of the weights of the shortest paths between two adjacent variables to be equal to a fixed value or within a given interval.In addition,two propagation algorithms based on generalized arc consistency are proposed for these constraints.Finally, the comparison experiments with table constraints demonstrate that enforcing consistency directly is more effective than transforming to table constraints and then enforcing consistency.In summary,this paper provides a theoretical and algorithmic in-depth study of constraint propagation and consistency.The specific work involves improving the existing generalized arc consistency algorithms for three types of constraints,which accelerates the process of constraint propagation.These studies ultimately greatly improve the efficiency of solving constraint satisfaction problems and become an important part of the key technologies in constraint solvers.