Research On Conflict Explanation Algorithm In Interactive Constraint Satisfaction Problem

Constraint Satisfaction Problem is an important part of the artificial intelligence, and its representation is a good framework, which can be used to solve many practical problems, for example configuration problem, flight scheduling problem, resource allocation problem, etc. Constraint propagation and backtracking search are the main technique of constraint satisfaction problem. Interactive constraint satisfaction problem is a special kind of constraint satisfaction problem, it refers to that the problems has not been fully defined at the beginning of the calculation and the information can be transmitted in the process of calculation. The user specifies some constraints in the process of solving interactive constraint satisfaction problem, that represents the user’s requirement.Calculating explanation is one hot research of interactive constraint satisfaction problem. Explanation can be used to restoring consistency, avoiding an undesired character or restoring an eliminated character. The present algorithm of calculating explanation is mainly divided into two categories: explanation algorithm based on solution and explanation algorithm based on conflict. Explanation algorithm based on solution correcting a subset of user constraint set, that enables a solution can be found in constraint network; explanation algorithm based on conflict calculating a subset that cause inconsistency of constraint network,explaining the cause of conflict, and generally speaking, we require that is a minimal set. Corrective Exp of Barry O’Callaghan and QUICKXPLAIN of Junker are the represent of the two kinds of algorithms respectively.QUICKXPLAIN divide the problem into two parts, and calculate conflict element included in both parts with the method of recursive respectively. Time expending of QUICKXPLAIN is mainly on the constraint propagation, so reducing the number of constraint propagation and time of constraint propagation is a way to improving the efficiency of the algorithm. Basing on QUICKXPLAIN, we propose conflict explanation algorithm based on binding, namely to bind m constraints into one and perform constraint propagation once. The scope of m is 1-n, where n is the number of user constraints; and when m=1, it is the QUICKXPLAIN algorithm itself. We study the two case of m=2 and m=n/2:(1) When m=2, we perform constraint propagation with binding two constraints into one, which we name as conflict explanation algorithm with two constraints bound. The algorithm can make two constraints sharing one constraint propagation, that makes the number of constraint propagation to half; but when a constraint propagation lead to an inconsistent state, we need to do additional work to judge which constraint that bound together belong to conflict set(maybe one of the two constraints, or maybe both).(2)when m=n/2,we perform constraint propagation with binding half of the constraints into one, which we name as conflict explanation algorithm with half of the constraints bound. The algorithm divide user constraints into two parts, and judge the conflict element’s location according to the way of two constraints; then the algorithm calculates conflict set of the two subsets till there is only one conflict element in the subset, and it belong to the conflict set. The problem can be reduced to half in this way; meanwhile, with multiple constraints propagation at the same time, time of constraint propagation can be reduced to a certain extent.Theoretically, according to the different size of user constraint set and conflict constraint set, we can not guarantee which algorithm is optimal in all cases. But the experimental result shows that in practical problems the two algorithms we proposed are better than QUICKXPLAIN; in most cases, the efficiency of conflict explanation algorithm with half of the constraints bound is better than conflict explanation algorithm with two constraints bound.