CSP Search with Responsibility Sets and Kernels

1 Introduction

The present paper introduces a modi�cation of the forward checking algorithm (FC) [Haralick and Elliott, 1980] that associates every removed value with two data structures: the responsibility set and the kernel. Having introduced the structures, we describe how they help to prune the search space. We de�ne a notion of �ltering value. Next, we prove the central theorem of the paper which claims that the existence of a �ltering value in some state that occurs during work of FC means that the current partial solution of the state is a nogood. We modify FC so that every time after lookahead or backtrack, it checks whether there is a �ltering value in the current state. If there is, it backtracks again. We call the resulting modi�cation FC-RK.

The rest of the paper is organized as follows. Section 2 provides the necessary de�nitions and notations. Section 3 formulates the main theorem and introduces FC-RK. Section 4 brie�y discusses the results of preliminary evaluation.

2 Preliminaries and Notations

A binary constraint network (CN) Z = 〈V,D,C〉 is a triple consisting of a set of variables V , a set of domains D and a set of constraints C. Let V = {v1, . . . , vn}. Then D = {Dv1 , . . . ,Dvn }, where Dvi is the domain of values of variable vi, C = {Cvi,vj |i ̸= j, 1 ≤ i, j ≤ n}, where cvi,vj ⊆ Dvi ×Dvj is the set of all compatible pairs of values of vi and vj. We refer to the parts of Z as V (Z), D(Z), and C(Z). To emphasize that a value val belongs to the domain of a variable v, we refer to this value as val v . An assignment of a CN Z is a pair 〈vi, val〉 such that vi ∈ V (Z), val ∈ Dvi . A consistent set of assignments is a partial solution of Z. A partial solution that assigns all the variables of Z is a solution of Z. A CN that has no solution is insoluble. Let P be a partial solution of Z. We denote the set of variables assigned by P by V (P). A nogood of a CN Z is a partial solution of Z that cannot be extended to a full solution.

Throughout the paper we use the CN shown in Figure 1. The ellipses represent the domains of variables and incompatible pairs of values are connected by arcs. For example, value 2 of V0 is incompatible with value 1 of V100.

3 Responsibility sets, kernels, and FC-RK

In this section we develop a modi�cation of FC called FCRK. First we de�ne two structures maintained by these algorithms.

De�nition 1 Let P be a nogood of a CN Z. A responsibility set R of P is a subset of V (Z) \ V (P) such that there is no consistent extension of P that assigns all the variables of R.

De�nition 2 Let P be a nogood of a CN Z, let R be a responsibility set of P and let 〈u, val〉 ∈ P . The kernel of val u with respect to P and R is the subset of R which contains all the variables whose domains have values incompatible with valu but compatible with the rest of assignments of P .

Consider the CN shown on Figure 1. The nogood {〈V0, 2〉〈V1, 1〉} has a responsibility set {V2, V100, V200}, while the kernel of 〈V1, 1〉 is {V200}.

Now we present a modi�cation of FC that maintains responsibility sets and kernels associated with removed values. The proposed method is a slight modi�cation of the technique described in [Schiex and Verfaillie, 1994].

Recall that FC detects that the current partial solution P is a nogood if the current domain of some future variable is emptied or if the current domain of the variable being assigned is wiped out [Prosser, 1993]. In both of these cases, FC discards the last assignment 〈u, val〉 of the current partial solution and removes val from the current domain of u. We say that P is the nogood associated with valu . The modi�ed version of FC associates valu with two sets denoted by rs(valu) and ker(valu). These are the responsibility set and the kernel of the nogood associated with valu . The additional operations performed by the modi�ed version of FC are the following.

• The rs and ker sets are initialized to ∅ for all the values of the CN.
• If a value valv 1 is deleted during the lookahead stage performed after assigning val to u then v is inserted into ker(valu).
• Consider a value valu that is deleted during backtrack and let v be the variable whose empty domain caused the backtrack. Then rs(valu) is set to S ∪ {v}, where S is the union of the rs-sets of all values of v. Also ker(valu) is updated to the intersection of the current value of ker(valu) with rs(valu). (Note that the preliminary value of ker(valu) is computed at the lookahead stage in order to avoid recomputation of values that are incompatible with valu .)
• Once a discarded value is restored to the current domain, the rs and ker sets of the value are re-initialized to ∅.

Let us illustrate the method by simulating a few iterations of the modi�ed FC that processes the CN of Figure 1. It starts by assigning 〈V0, 1〉 〈V1, 1〉 and then 〈V2, 1〉. The last assignment empties the current domain of V100 and FC backtracks. The rs-set of 1V2 is set to {V100} so is ker(1V2 ). Note that the assignment 〈V2, 1〉 can remove values from many other variables of the CN but the kernel is restricted to {V100} during the backtrack. In the next step, FC assigns V2 with 2 and backtracks again because V200 is emptied. Then the domain of V2 is emptied therefore FC backtracks yet another time and produces a nogood {〈V0, 1〉, 〈V1, 1〉} with rs(1V1 ) = {V2, V100, V200} and ker(1V1 ) = ∅.

Consider a state of FC that occurs just after lookahead or backtrack. Denote the current partial solution by P and its last assignment by 〈u, val〉. For the given state, de�ne a �ltering value.

De�nition 3 A value valv 1 removed by backtrack is a �ltering value if the following conditions hold.

• Compatibility condition. The assignments of variables of V (P ) ∩ ker(valv 1 ) are compatible with valv 1 .
• Inclusion condition. For every unassigned w ∈ ker(valv 1 ), all values of the current domain of w are compatible with valv 1 .

Now we are ready to formulate the central theorem.

Theorem 1 Assume that in the given state there is a �ltering value valv 1 . Then P is a nogood with a responsibility set S = rs(valv 1 )\V (P)∪S ∗ , where S ∗ is the union of rs-sets of all values that belong to the domains of unassigned variables of ker(valv 1 ).

Let us illustrate the theorem on the CN in Figure 1. Consider a state of a CSP solver in which the value 1V0 is removed and associated with the rs-set {V2, V100, V200} and the kerset {V100, V200}. Continuing the simulation, we assign V0 with 2 and V1 with 1. For the obtained partial solution, 1V0 is a �ltering value, all values of the current domains of V100 and V200 are compatible with 1V0 (the inclusion condition).

Theorem 1 suggests a pruning procedure that discards the current partial solution if it �nds a �ltering value. The procedure is applied every time after lookahead or backtrack. Algorithm 1 presents the pseudocode of the procedure.

Algorithm 1 PRUNING PROCEDURE OF FC-RK

• 1: for every removed value valv 1 do
• 3: Let 〈u, val〉 be the last assignment of the current partial solution
• 2: if valv 1 is a �ltering value then
• 4: Backtrack with setting rs(valu) to S (S is de�ned in Theorem 1)
• 5: end if
• 6: end for

We call the modi�cation of FC that computes rs and ker sets and applies Algorithm 1 every time after lookahead and backtrack, FC-RK (RK abbreviates Responsibility sets and Kernels).

4 Preliminary Evaluation

The experimental evaluation shows that, FC-RK outperforms FC-CBJ on the majority of instances of graph k-coloring problem and on binary random CSPs with low density. For dense random CSPs, FC-RK performs more consistency checks than FC-CBJ but visits less nodes on the search tree. We believe that performance of FC-RK could be improved by an algorithm for checking the existence of �ltering values, that takes less consistency checks than our current implementation.