Research On Constraint Solving Methods Based On Local Consistencies And Retaining Instantiation Values

The method of solving a problem is one of the research topics in the field ofartificial intelligence, and constraint solving is a very important research direction,which attracts close attention from relative experts and scholars in this field all overthe world. The mainly idea of constraint solving is to abstract a real world problemwhich is a constraint satisfaction problem into a constraint network, and in order toimprove the efficiency of constraint solving, some constraint reasoning techniques areadded into traditional algorithms of finding solution.Looking-ahead and looking-back are the major schemes to improve theefficiency of constraint solving, and both of them contain many constraint reasoningtechniques. Looking-ahead scheme means adding some constraint reasoningtechniques including local consistencies and heuristic methods after instantiatingsome variables. A local consistency is used to remove values in the domain ofvariables which will never appear in the solution from the current constraint network,thus compressing the constraint network to a certain extent before we instantiate anew variable, and a heuristic method is used to select the variable and value withrelatively high priority according to the heuristic function in order to find the rightsearching path. Looking-back scheme refers to the methods of choosing thebacktracking point when a dead-end node occurs during the searching process, whichcontains back-jumping technique, conflict-directed back-jumping technique anddynamic backtracking technique. However, both of these schemes are alwayscounterproductive to each other. As a result, the efficiency will be determined directlyby the appropriate choice of these two schemes. With the highly development ofresearch on constraint solving methods, maintaining local consistency combined withthe heuristic called dom/wdeg and LC scheme becomes the state-of-the-art algorithm for constraint solving. In this paper, we optimize some techniques in these schemesafter analyzing the partial weakness of some techniques mentioned above. All work inthis paper is as follows.(1)Max-Restricted Path Consistency based on half range of domain. Accordingto the characteristics of constraint network which correspond to an unsatisfiedproblem, we combine the stronger power of revision for domains of max-RestrictedPath Consistency compared with Arc Consistency and the faster speed of constraintpropagation of the latter one with the former one, and we propose a stable localconsistency algorithm called Hmax-RPC which is based on the half range of domain.We also apply it into the framework of constraint solving method, and prove thehigher efficiency compared with arc consistency on solving unsatisfied problems byexperimental results.(2)Constraint solving method based on retaining instantiation values. We proposea constraint solving method based on retaining instantiation values after analyzing theshortcomings of LC1scheme and LC2scheme. This method keeps the most recentlyinstantiation values which are between the variable corresponds to dead-end node andthe variable corresponds to culprit decision, and provides higher priority of thesevalues for the next assignment. After showing the pseudo code of this method, we alsoverify its ability to improve efficiency of constraint solving on most problems byperforming experiment.