Domain Filtering can Degrade Intelligent Backtracking Search

1. Introduction

In the binary constraint satisfaction problem (bcsp) we are given a set of variables and a set of constraints, where each variable has a discrete and finite domain and each constraint acts between a pair of variables. The problem is to find an assignment of values to variables, from their respective domains, such that the constraints are satisfied [Dechter 1992, Kumar 1992, Mackworth 1992, Meseguer 1989]. This problem may be represented as a graph G, where V(G) is the set of variables and A(G) is the set of constraints. There are a number of tree search algorithms that address this problem, most notably chronological backtracking (BT) [Bitner and Reingold 1975, Golomb and Baumert 1965], backmarking (BM) [Gaschnig 1977 and 1979], backjumping (BJ) [Gaschnig 1979], and for­ ward checking (FC) [Haralick and Elliott 1980]. All these algorithms perform a "depth first" search, and the most primitive of these is BT. When BT instantiates a variable with a value (the current variable V;) it checks backwards against variables that have already been assigned values (the past variables). If no value can be found for the current variable that is consistent with all of the past vari­ ables, BT steps back to the previous variable V;_1 and attempt a new instantiation for that variable (and so on). It may be the case that the value assigned to V;_1 was not in conflict with V; , but some other variable higher up in the search tree, Vh, precluded some value from the domain of shown to be inconsistent with respect to the ongoing search process. current-domain[i] is initialised to be equal to domain[i]. When v[i] is to be instantiated a value is selected from current-domain[i], and if that value is found to be inconsistent with respect to the current search state, then that value is removed from current-domain[i]. When backtracking takes place from v[i] to v[h] (where h < i) current-domain[j] is reset to domain[j], for all j, where h < j ~ i. Note that current-domain[O] = nil. C is an n x n array, where C[i,j] is the name of a binary predicate (such as <, =, >, -:~:, etc) that holds between v[i] and vG]. If C[ij] = nil then there is no constraint acting between v[i] and v(j]. Therefore we have an extensional representation of constraints (rather than intensional, as a set of compati­ ble pairs). The function check(i,j) delivers a result of true if C[i,j] = nil, otherwise it delivers the result of applying the relation C[i,j] between the instantiations of v[i] and v[j] (and is counted as a consistency check).

Generally v[i] will be considered to be the current variable, v[h] will be a past variable, and v[j] a future variable (h < i < j). It is assumed that all arguments are passed by reference and that the first occurrence of a vari­ able corresponds to an implicit declaration. The algo­ rithms are described in terms of a pair of mutually recur­ sive functions (similar to the style of Dechter and Pearl [1988], and Dechter [1990]). That is, we have a forward move, such as bj-label, and a backward move, such as bj­ unlabel. In section 4, the number of "nodes visited" by the search process X is taken to be the number of calls to the forward move x-label. The algorithms address the binary constraint satisfaction search problem [Nudel 1983]. That is, they find the first solution.

2. Conflict-Directed Backjumping (CBJ)

Where BJ steps back from v[h] after jumping back from v[i], the conflict-directed backjumper (CBJ) continues to jump across conflicts which involve both v[h] and v[i]. CBJ achieves this by recording . the set of past variables that failed consistency checks with the current variable (and we refer to this as a "conflict set" as in [Dechter 1990]). If no consistent instantiation can be found for v[i], CBJ then jumps back to the deepest variable, v[h], that conflicted with v[i]. If on jumping back to v[h] CBJ dis­ covers that there are no more values to be tried in current-domain[h] CBJ then jumps back to v[g], where v[g] is the deepest variable that was in conflict with either v[i] or v[h].

CBJ maintains a conflict set conf-set[i] for each variable, where the array conf-set is declared globally. Ini­ tially each element of conf-set[i] is set to be {0}. When a consistency check fails between v[i] and v[h], h is added to the set conf-set[i]. Therefore, conf-set[i] is the subset of the past variables in conflict with v[i]. If there are no remaining values to be tried in current-domain[i], CBJ jumps back to the deepest variable v[h], where h E conf­ set[i] (that is h f- inax-list(conf-set[i]), where the function max-list delivers the largest integer in a set of integers).

When jumping back from v[i] to v[h] the information in conf-set[i] is carried upwards to v[h]. 1be array element conf-set[h] becomes conf-set[h] u conf-set[i] - h, the set of variables in conflict with v[h] or v[i]. Therefore, when further backtracking takes place from v[h], CBJ jumps back to v[g], where v[g] is the deepest variable in conflict with either v[h] or v[i].

1 PROCEDURE cbj-label (i) 2 BEGIN 3 IFi>n 4 111EN print("ao1ution") S ELSEBEGIN conaistent ~ false; 6 7 FOR v[i) ~ FACH ELEMENT OF current-domain[i) WHILE not consistent DO BEGIN cooaiatent ~ true; 8 9 10 11 12 13 14 IS 16 FOR h ~ 1 TO i-1 WHILE conaiatent DO BEGIN consistent ~ check(i,h) END; IF not cooaistent 1liEN BEGIN current-domain[i) 17 18 19 20 21 22 23 ~ remove(v[i],current-domain[i]); pushnew(h,conf-aet[i]) 24 END; END END IF cooaistent ~ cbj-label(i+l) ELSE cbj-unlabe1(i) END

In line 17 above, the call pushnew(h,conf-set[i]) adds h to the set conf-set[i] if h is not already a member of conf­ set[i]. It is assumed that the loop variable h is available to the statement in line 17, and that h is the value that caused the call to check(i,h) to deliver false.

1 PROCEDURE cbj-unlabel (i) 2 BEGIN 3 IFi=O 4 111EN print("impossible") S ELSE BEGIN 6 h ~ max-list(coof-aet[i]); 7 conf-aet[h) ~ remove(h,union(conf-aet[h),conf-aet[i])); 8 FORj~h+1TOi 9 DO BEGIN 10 conf-aet(j) ~ {0}; 11 current-domain(j) ~ domain(j] 12 END; 13 current-domain[h] ~ remove(v(h],current-domain[h]); 14 IF current-domain[h) '* nil; 1 S mEN cbj-labe1(h) 16 ELSE cbj-unlabe1(h) 17 END 18 END;

CBJ is then realised as cbj-label(l). If we move line 17 in cbj-label to line 12.1 the array element conf-set[i] is updated unconditionally, and CBJ behaves as BJ.

The reasoning behind CBJ might be better under­ stood when viewed from the perspective of de Kleer's A TMS [1986]. We can consider the past variables as a set of assumptions that are IN (currently believed), and the array element coof-set[i] as a conjunction of assumptions, and therefore an environment. Let S be the set of indices of the past variables ie. S = (1,2,3, ... ,i-1), and disallowed[i] = domain[i] - current-domain[i], the set of values in domain[i] that have been discovered to be incon­ sistent with the current search state. We then have the assumed node <disallowed[i],{coof-set[i]},{conf-set[i]}>, where disallowed[i] is the datum, and conf-set[i] is the justification for datum, and consequently the single environment within the label. If conf-set[i] s: S we then believe that the current search state cannot be extended by any instantiation of v[i] from the set disallowed[i]. Con­ versely, if conf-set[i] is not subsumed by S we can no longer believe disBllowed[i] and we must reset current­ domain[i] to be domain[i]. When current-domain[i] is empty (ie. disallowed[i] = domain[i]) we need to force OUT some assumption in conf-set[i], and we choose the most recent assumption, namely max-list(conf-set[i]). This is done implicitly when CBJ backtracks from v[i] to v[h].

CBJ is conservative when it jumps back from v[i] to v(h]. As noted above we can believe disallowed[i] when­ ever coof-set[i] is subsumed by S. However, when CBJ jumps from v[i], over v(j], to v[h] we automatically reset current-domain[j]. It may be the case that max-list(conf­ set[j]) < h and we can continue to believe disallowed[j], and thus prune the search space more efficiently. How­ ever, in order to do this we would have to examine all future conflict sets whenever backjumping takes place. CBJ would then look even more like an ATMS. In fact, such an algorithm is described by Rosiers and Bruynooghe [1987] and by Prosser [1989].

CBJ has many features in common with Dechter's graph-based backjumping algorithm GBJ [Dechter 1990]. When GBJ reaches a dead end on v[i] it jumps back to the deepest variable amoogst those connected to v[i] in the constraint graph, namely v[h], and if there are no values remaining to be tried for v[h] GBJ jumps back to v[g] where v[g] is the deepest variable coonected to either v[i] or v[h]. Therefore we might say that when jumping back BJ is directed by consistency checks that have been performed, CBJ is directed by conflicts, and GBJ is directed by the topology of the constraint graph.

3. Directed Consistency

CBJ can be modified such that it removes values from the domains of variables once and for all, when it can be deduced that these values are infeasible. We may add the following conditional to procedure cbj-unlabel.

1. IF lengtb(oonf-eet[i)) · 2
2. 1HF.N domain[h) +- remove(v[h],domain[h]);

The above modification gives us CBJ-DkC, where DkC stands for "directed k-consistency" [Dechter and Pearl 1988] (and is similar to nth order learning [Dechter 1990]). The effect of this modification can be described as follows. Let us assume that CBJ has successfully instantiated v[i-1] and that CBJ moves forwards to v[i]. At that point conf-set[i] = {0}, and current-domain[i] = domain[i]. Further assume that the call to cbj-label(i) fails to find any instantiation of v[i] that is coosistent with the past variables. If lconf-set[i] I = 2 then v[i] is in conflict with the instantiatioo of v(h] and the pseudo variable v[O]. We can then deduce that v[h] is "arc-iilconsistent" with respect to domain[i]. That is, an arc consistency algorithm [Mackworth 1977, Deville and van Hentenryck 1991] would have removed the value v[h] from domain[h].

Assume that it is not the first time that we have visited v[i], that we successfully instantiate v[i], and that all values in domain[i] are coosistent with respect to the past variables. Therefore conf-set[i] = {0} . . Assume that we then attempt to instantiate some future variable v[j] and all values in domainG] conflict with either v[h] or v[i]. We then have conf-set[j] = {O,i,h}, ie. for all values xi in domain[j], v[j] ~ xi is inconsistent with v[h] or v[i]. CBJ will then jump back to v[i] and instantiate v[i] with the next value in current-domain[i]. Assume that this process continues until we have exhausted current­ domain[i] . We then have conf-set[i] = {O,h}, ie. for all values xi in domain[j], v(j] ~xi is inconsistent with v[h] or v[i] ~ x; , for all values x; in domain[i]. Therefore we can remove the value v[h] from domain[h].

We can adopt the same approach with respect to FC and to BJ. In FC we instantiate v[i] with the value k and check forwards against the future variables. Assume that v[i] checks against v[j] and this results in a "domain wipe out" [Nadel 1989] for v[j]. If no other variable checks against v[j] we can then remove k from domain[i] once and for all. This corresponds to "directed arc coosistency" (and corresponds to 1st order learning [Dechter 1990]), and we can realise this by maintaining a count of the number of variables forward checking against v(j] (as in [Prosser 1991]). We will call this algorithm FC-D2C.

Similarly in backjumping, if no instantiation for v[i] can be found, and all consistency checks from v[i] failed against the single instantiation v[h] ~ k, we might then remove k from domain[h]. We can do this by maintaining a flag for each variable, call it instantiated[i], which is ini­ tialised to false, and is set to true when bj-label finds an instantiation for v[i] which is consistent with the past vari­ ables. If we jump from v[i] to v[h], when length(conf­ set[h]) = 2 and instantiated[i] = false, we can remove the value v[h] from domain[h] (and when we jump from v[i] to v[h] we reset instantiatedG] to false for all j, h < j ~ i). This gives us the algorithm BJ-D2C. If we perform the following edits to cbj-label and cbj-unlabel we get BJ­ D2C:

• (a) In cbj-label move line 17 to line 12.1
• (b) In cbj-label replace line 21 with the following seg­ ment

21 1HF.N BEGIN 21.1 inmntilted[i] +- true;

21.2 dlj-l.abel(i+l)

(c) In cbj-unlabel add the following lines

6.1 IF noe(inatlntialled[i]) and length(canf-.et[i]) · 2

6.2 1HF.N domain[h] +-- remove(v[h],domain[h]);

10.1

inltmtialled(j] +-- falle;

More generally, since FC and BJ only reason over failures that occur between pairs of variables we can only detect directed arc ioconsistencies (1st order learning). On the other hand, since CBJ reasons over failures within a set of variables, it can detect directed k-inconsistencies (nth order learning).

4. Experimental Evaluation

The following algorithms were compared against each other: BT (naive/chronological backtracking), BJ (Gaschnig's backjumping routine), GBJ (Dechter's graph­ based backjumping routine), CBJ (described here), BM (Gaschnig's backmarking routine), FC (Haralick and Elliott's forward checking routine), BJ-D2C, CBJ-DkC, and FC-D2C (again, described here).

The algorithms were applied to 4.50 instances of the zebra problem, described in [Dechter 1990 and Smith 1992]. That is, 4.50 different instantiation orders of the zebra were created, and each algorithm was applied to those problems in turn. Table 1 shows the average number of consistency checks performed by an algorithm, the standard deviation, the minimum number of consistency checks performed, and the maximum number performed over the 4.50 problems. Table 2 shows the same informa­ tion but with respect to nodes visited.

If we take consistency checks performed as a measure of search effort we may rank the algorithms as follows: FC­ D2C, CBJ-DkC, FC, CBJ, BJ-D2C, BM, BJ, GBJ, BT. With respect to nodes visited the algorithms are ranked: FC-D2C, FC, CBJ-DkC, CBJ, BJ-D2C, BJ, GBJ, (BM and BT).

The algorithms were then applied again to 100 instances of the zebra problem, and the cpu time was measured. Table 3 below shows the average cpu time used (on a SPARCstation IPC, with 24 mega-bytes of memory, using Sun Common Lisp 4.0) by the algorithms for solv­ ing an instance of the problem, and the average number of consistency checks performed in a second.

Although BT performed on average 8 times as many con­ sistency checkS as BM (Table 1) BT took only 20% longer to run than BM (Table 3). This is due to the poor "checking rate" of BM (and this is explained more fully in [Prosser 1991 and 1993]). CBJ has a higher checking rate than BJ. 1berefore, not only does CBJ perform less checks than BJ, it performs these checks with less over­ heads (these tests used the more efficient version of BJ described in [Prosser 1991], rather than the derived ver­ sion here). This is because CBJ updates conf-set[i] condi­ tionally, and BJ updates max-check[i] unconditionally. Generally, there is an insignificant overhead associated with the modifications performed to BJ (to give us BJ­ D2C), CBJ (giving CBJ-DkC), and FC (to FC-D2C). These modifications resulted in a reduction in consistency checks performed, nodes visited, and a reduction in run time. Therefore, with respect to run time the algorithms may be ranked: FC-D2C, CBJ-DkC, FC, CBJ, BJ-D2C, BJ, BM With the exception of BM, this ranking agrees with those above, and in fact there is little to choose between CBJ-DkC and FC-D2C.

S. The Bridge (and the Long Jump)

It was expected that CBJ-DkC would always perform at least as well as CBJ. However, on analysing the experi­ mental results it was discovered that out of the 4.50 prob­ lem instances there were 2 cases where CBJ performed better than CBJ-DkC. This was a surprise. One of these problems was then examined in detail. This was the prob­ lem with the instantiation order: <Water, Tea, Coffee, Japanese, Kools, Blue, Ukranian, Chesterfield, Old-Gold, Zebra, Horse, Fox, Orange-juice, Yellow, Snails, Red, Green, Englishman, Lucky, Dog, Spaniard, Parliament, Ivory, Norwegian, Milk>. During the search process CBJ­ DkC discovers, amongst other infeasibilities, that there is no solution to the problem when Spaniard is assigned the value 1 (ie. v[21] +-- 1). Therefore, the value 1 is removed from domain[21]. In some latter stage in the search pro­ cess v[21] again becomes the current variable and CBJ­ DkC considers the instantiation v[21] +-- 2. At the same point in the search space CBJ considers the instantiation v[21] +-- 1. The two search trees now differ significantly, and in CBJ's search tree it is possible to jump back to a conflicting variable higher up in the search tree than CBJ-DkC.

More generally, CBJ-DkC may remove an infeasible value k from the domain of a variable v[i]. At some later stage in the search process CBJ may move forwards from v[i-1] to v[i], and be unable to re-instantiate v[i] with the value k. CBJ-DkC may then jump back to v[h]. At the same point in the search tree CBJ is allowed to make the instantiation v[i] f- k, and move forwards to v[j]. CBJ may then jump back from v[j] to v[g], where g < h. Therefore, the value k has acted as a bridge that allows the search process to move from one area of the search space to another, where it can then make a "long jump" back to a conflicting variable.

To confirm this analysis, the value 1 was removed from domain[21], the problem was reset, and CBJ and CBJ-DkC were re-run. It was expected that CBJ would be unable to "cross the bridge" and unable to make "a long jump". With the bridge in place CBJ performed 10,746 checks, and visited 1,974 nodes (and CBJ-DkC performed 13,097 checks, and visited 2,390 nodes). With the bridge removed CBJ performed 13,798 checks, and visited 2,532 nodes (CBJ-DkC performed 13,029 checks and visited 2,385 nodes). This implies that the removal,of an infeasi­ ble value from the domain of a variable may result in a degradation in the performance of an algorithm that jumps back to the cause of a conflict (such as BJ, CBJ, or any of the hybrid derived from these algorithms [Prosser 1991 and 1993]).

6. Conclusion

A new algorithm has been presented, CBJ. It has been shown that BJ can be derived from CBJ, and that BJ might be considered to be a degenerate form of CBJ. CBJ was then modified (the addition of a single conditional expression) such that infeasible values can be detected and removed once and for all. A similar technique was applied to backjumping and forward checking. Empirical evidence suggests that these modifications result in an improvement in the performance of these algorithms on average.

The removal of infeasible values has revealed a dis­ turbing phenomenon, namely that this can lead to a degra­ dation in the performance of a "conflict directed" backjumping algorithm. It has (almost) become an article of faith that if we remove infeasible values [Mackworth 1977, Deville and van Hentenryck 1991, Freuder 1982] or redundant values [Benson and Freuder 1992, Freuder 1991] from the domains of variables, the subsequent search algorithm will be presented with an easier task. We have been lead to believe this because "the subsequent search algorithm" is generally assumed to be a chronologi­ cal backtracker (BT, BM, FC), or the effect of removing a bridge has been masked by a reduction in thrashing. We should now assume that increased consistency, or the removal of redundancies, can only guarantee a reduction in search effort if that search is unintelligent (such as a chronological backtracker). Conversely, we should expect that we can improve the performance of an intelligent backjumping algorithm by adding an infeasible value to the domain of a variable.