Reducing consistency checks in generating corrective explanations for interactive constraint satisfaction

Constraint satisfaction problem has many applications in Artificial Intelligence. Its interactive applications usually require advice from a system to help a user solve the problem. Based on maximal relaxations, the CorrectiveExp algorithm is a representative method to compute explanations. However, we found that the CorrectiveRelax algorithm, used by the CorrectiveExp algorithm to compute maximal relaxations, has a defect that it executes more consistency checks than necessary. It is very important to avoid these unnecessary consistency checks because in general each consistency check needs to resort to backtrack search. To tackle this problem, this paper proposes two improved algorithms to compute maximal relaxations, called CorrectiveRelaxReduced and CorrectiveRelaxDC respectively. The former utilizes the existing results of consistency checks to shrink the search scope for some inconsistent user constraints. Furthermore, we have proved that the number of consistency checks executed by the CorrectiveRelaxReduced algorithm is always less than or equals to that of the CorrectiveRelax algorithm. The latter uses a divide-and-conquer approach to avoid unnecessary consistency checks. Our experimental results show that the two improved algorithms execute less consistency checks than CorrectiveExp while computing maximal relaxations.