Increasing Tree Search Efficiency for Constraint Satisfaction Problems

1. INTRODUCTION

Assoc iated with search procedures are heuris­ tics. In this paper we provide a theory which explains why two heuristics used in constraint satisfaction searches work. The heuristics we discuss can be given a variety of one line des­ criptions such as:

Lookahead and remember your future in order to succeed in the present.

To succeed, try first where you are most likely to fail.

Remember what you have done to avoid repeat­ ing the same mistake.

Lookahead to the future in order not to worry about the past.

We will attempt to show that for a suitably defined random constraint satisfaction problem, the average number of consistency checks per­ formed by a search procedure which employs these principles will be smaller than that required by the standard backtracking tree search .

To begin our discussion, we need a precise des­ c ription of the constraint satisfaction problem we a re att empting to solve by a search proce­ dure. We assume that the re are M units (some authors call these variables instead of units). Each unit has a set of L possible values or

labels for each pair of units. The constraint satisfaction problem we consider is t o deter­ mine all possible assignments f of labels to units such that for every pair of units, the corresponding label assignments satisfy the constraints . More formally , if U is the set of units and L is the set of labels, then the binary constraint R can be represented as a binary relation on U x L: R S: (U x L) x (U x L). If a pair of unit labels (u 1 , t 1 ,u 2 ,t 2 ) E R, then labels ! 1 and 1. 2 are said to be consistent or compatible for units u 1 and u 2 . A l abeling f of all the units satisfies the constrai nts if for every pair u 1 ,u 2 of units (u 1 f(u 1 ),u 2 , f(u 2 )) E R. Haralick et. al. (1978) call such a labeling a consistent labeling.

The problem of determining consistent labelings is a general f orm of many problems related to artificial intelligence. For example, scene labeling and mat ching (Barrow and Tenenbaum, 1976, and Rosenfeld et. al., 1976), line in­ terpretation (Waltz, 1972), edge l abeling (Haralick, 1978), graph homomorphisms and iso­ morphisms (Ullman, 1969), graph coloring (Harary, 1969) boolean satisfiability (Hara l i ck et. al., 1978), and proposition theorem proving (Kowalski, 1975) are all special cases of the general consistent labeling problem. Ullman (1966), Waltz (1972), Rosenfeld et . al. (1978 and 1979), and Gaschnig (1977 and 1978) attempt to find efficient methods to solve the consis­ tent labeling problem. Knuth (1975) also analyzes the backtracking tree search, which is the basis of most methods used to solve the cons istent labeling problem.

For the purpose of illustrating the search required to solve this problem, we choose the N-Queens problem. Here, the unit set corre­ sponds to the row coordinates on a checkerboard and we denote them by positive integers. The label set corresponds to the column coordinates on a checkerboard and we denote them by alpha­ betic characters. Hence, the unit-label pair (l,A,2,D) satisfies the constraint R, [(l,A,2, D)ER], since a queen on row 1 column A cannot take a queen on row 2 column D. But, the unit label pair (l,A,3,C) does not satisfy the con­ straint R because queens can take each other diagonally.

Using the number letter convention for unit­ label pairs, Figure 2 illustrates a portion of a backtracking tree trace for the 6 Queens pro­ blem. Notice how the unit 5 labels A, C, E, and F occur twice in the trace, each time being tested and failing for the same reason: incom­ patibility with uni ts 1 or 2. These redundant tests can be eliminat ed if the fact they fai led can be remembered or if units 1 or 2 could lookahead and prevent 5 from taking the labels A, C, E, or F. The r emembering done by Gas chnig's backmarking (1977) and the forward checking approach described in th is paper help eliminate these problems. Notice that once unit 3 takes label E (Figure l a) the only labels left for units 4 and 6 are incompatible. The forward checking algariihm will not dis­ cover this future incompatibility. However, the first time label B is associated with un i t 4, there is absolutely no label possible for unit 6. Hence, the search through the l abels fur 5 and 6 are enti rely superflous and forward dwcklng will discove r this (Figure Jb). The luukahead procedures (discrete r elaxation) uf Ullman (1966), Wa ltz (1972), Rosenfeld (1976), Mackworth (1977), and Montanari (1974) help alleviate the problem illustrated in Figure la as well as in Figure lb.

Sec tion 2 gives a brief description of the full and partial looking ahead, forward check­ ing, backchecking , and backmarking procedures and concludes with a comparison of these pro­ blems created randomly. These results show that standard backtracking is least efficient in most cases, and backmarking and forward checking are the most efficient for the cases tried.

Figure lb illustrates how the labeling A,C,E,B for units 1,2,3,4 implies that there is no label for unit 6 in the 6 Queens problem.

In section 3, we give a statistical analysis of constraint satisfaction searches and demon­ strate the statistical reason why forward checking requires fewer expected consistency checks than standard backtracking. In section 4 we explore other application& of the fail first or prune early tree search strategies and show that such particular strategies as choosing the next unit to be that unit having fewest labels left and testing first against units whose labels are least likely to succeed reduce the expected number of consistency tests required to do the tree search. Finally, by changing the unit search order dynamically in every tree branch so that the next unit is always the one with fewest labels left, we show experimentally that not only does performance improve for each procedure, but that forward checking now does better than backmarking in the larger problems tested.

2. SOHE PROCEDURES FOR TREE SEARCH REDUCING

In this section we give brief descriptions of five procedures which can be used within the standard backtracking framework to reduce tree search operations. They are called full and partial looking ahead, forward checking, back­ checking, and backmarking. Each of these pro­ cedures invests resources in additional consis­ tency tests at each point in the tree search in order to save (hopefully) more consistency tests at some point later in the tree search.

For ease in explaining these procedures, we call those units already having labels assigned to them the past units. We call the unit currently being assigned a label the current unit and we call units not yet assigned labels the future units. We assume the existence of a unit label table which at each level in the tree search indicates which labels are still possible for which units. Past units will of course have only one label associated with each of them. Future units will have more than one. The tree search reducing procedures invest early to gain later. Hence, the result of applying any of them in the tree search will be to decrease the number of possible labels for any future unit or reduce the number of tests against past units.

The section concludes with a comparison among the tree search reducing procedures which indi­ ·cates that backtracking is least efficient in most cases, and that backmarking and forward checking are the most efficient for the cases tested. The lookahead procedures can be ordered in increasing order of efficiency as full looking ahead, partial looking ahead, and for­ ward checking.

2.1 Looking Ahead

Waltz filtering (Waltz, 1972), a procedure by Ullman (1966), discrete relaxation (Rosenfeld, Hummel, Zuckor, 1976), and the~ operacor of Haralick et. al. (1978) are all examples of algorithms that look ahead to make sure that (1) each future unit has at least one label which is compatible with the labels cur rently held by the past and present units and (2) each future unit has at least one label which is com­ patible with one of the possible l abels for each other future unit. Looking ahead prev~nt the tree search from repeatedly going forward and then backtracking between units u and v, v < u, only to ultimately discover that the l<bels held by units 1 through v cause incompatibility of all labels between some unit w, w > u, and some past, current, or future ·unit.

Because looking ahead in this manner cannot remember and save most of the results of tests performed in the lookahead of future urits with future units for use in futur e lookaheads, the full savings of looking ahead are not realized for many problems. A partial look ahead that does not do all the checks of full look ahead will perform better than backtracking and one that checks only future with past and present units (neglec ts future with futures) will do much better because all tests it performs can be usefully remembered.

The procedure L A TREE SEARCH and its associated subroutines CHECK=FORWARD and LOOK FUTCRE (Figure 3 a,b, and c) is a formal description of the full looking ahead algorithm, whi ch can easily be translated into any structur£d recur­ sive language. U is an integer representing the unit, and will increment at each level of the tree search. It takes on the valu£ 1 at the initial call. F is a one dimension array indexed by unit,.where entry f(u) for unit u is the label assigned to u. T and NEW T are tables, which can be thought of as an array of lists, T(u) is a list of labels which have not yet been determined to be not possible for unit U. (We implemented T as a 2 dimension array , with the number of entries in each list (or row) stored in the first position of the row. This implementation uses approximately (NUMBER OF UNITS)2 x (NUMBER OF LABELS) words of mem;ry­ for table storage"). - The tree search is ini­ tially called with T containing all labels for each unit. All other variables can be integers. EMPTY TABLE and NUMBER OF UNITS have obvious meanings.

The function RELATION(Ul,Ll,U2,L2) returns TRUE

if (U 1 ,L 1 ,u 2 ,L 2 ) c R, otherwise it returns

FALSE. CHECK FORWARD checks that each future unit label pair is consistent with the present label F(u) for unit u as it copies the table T into the next level table NEWT, LOOK FUTURE then checks that each future ~nit label pair in NEW T is consistent with at least one label for every other unit, and deletes those that are not.

In this implementation CHECK_FORWARD and LOOK_ FUTURE return a flag, EMPTY ROW FLAG, if a unit is found with no possible c~nsistent labels. Thus the next level of the tree search will not be called, otherwise each entry in NEW_T is con­ sistent with U,F,(u), and therefore, all the past unit-label pairs.

RECURSIVE PROCEDURE LA TREE SEARCH(U,F,T); POR F(U) = each element-of T(U) BEGIN IF U < NUMBER OF UNITS THEN BEGIN NEWT= CHECK-FORWARD(U,F(U),T); CALL LOOK FUTURE(U,NEW T); IF NEW T is not EMPTY ROW FLAG CALL L_A_TREE_SEARCH(U+l,F,NEW_T) END; ELSE Output the labeling F; END; 1'-'ND L_A_TREE_SEARCH;

Figure (3a)

PROCEDURE CHECK_FORWARD(U,L,T); NEW T = empty table; FOR-U2 = U+l TO NUMBER_OF_UNITS BEGIN FOR L2 · each element of T(U2) IF RELATION(U,L,U2,L2) THEN ENTER L2 in the list NEW_T(U2); IF NEW T(U2) is empty THEN RETURN (EMPTY ROW FLAG); /*NO consistent Labels */ - - END; RETURN (NEW T); END CHECK_FORWARD;

Figure (3b)

PROCEDURE LOOK FUTURE(U,NEW T); IF U+l > NUHBER OP U!HTS THEN RETURN; FOR Ul : U+l TO-NUMBER OF UNITS BEGIN Ll CONSISTENT · FALSE;- FOR Ll · each element of NEW T(Ul) FOR U2 · U+l TO NUMBER_OF=UNITS except skipping Ul BEGIN L2 CONSISTENT · FALSE; FOR L2 · each element of NEW T(U2); IF RELATION(Ul,Ll,U2,L2) THEN BEGIN L2 CONSISTENT · TRUE; BREAK for L2 loop; END; IF NOT L2 CONSISTENT THEN BREAK for U2 loop; END for U2 loop; IF L2 CONSISTENT rHEN Ll-CONSISTENT · ~RUE; ELSE - Delete Ll from list NEW_T(Ul); END for Ll loop; IF NOT Ll CONSISTENT THEN BEGIN NEW T · EMPTY_ROW_FLAG; RETURN; END; END for Ll loop; RETURN; END LOOK_FUTURE;

Figure (3c)

2.2 Partial Looking Ahead

Partial looking ahead is a variation of looking ahead which does approximately half of the con­ sistency that full looking ahead does while checking future with future units. Each future unit label pair is checked only with units in its own future, rather than all other future units. Thus partial looking ahead is less powerful than full looking ahead in the sense that it will not delete as many unit label pairs from the lists of potential future labels. We will, however, see that partial looking ahead does fewer total consistency checks than full looking ahead and standard backtracking in all

cases tested.

The checks of future with future units do not discover inconsistencies often enough to justify the large number of tests required, and these results cannot be u&~fully remembered. Since partial looking ahead does fewer of these less useful tests, it is more efficient. A look ahead that checks only future with current or past units can have better performance since these more powerful tests can also be usefully remembered.

The formal algorithm for partial looking ahead requires only a minor modification of the LOOK FUTURE procedure (Figure 3b). To change LOOK­ FUTURE into PARTIAL LOOK FUTURE, the second a~d fifth lines must be-changed. The "FOR Ul. .. " loop becomes "FOR Ul = U+l TO NUMBER OF UNITS -1 BEGIN" and "FOR U2 ... " becomes "FOR U2 ;;;- Ul+l TO NUMBER OF UNITS "

2.3 Forward Checking

Forward checking is a partial lookahead of future units with past and present units, in which all consistency checks can be remembered for a while. This method is similar to looking ahead, except that future units are not checked with future units, and the checks of future units with past units are remembered from checks done at past levels in the tree search. Forward checking begins with a state of affairs in which there is no future unit having any of its labels inconsistent with any past unit-label pairs. This is certainly true at the base of the tree search, since there are no past units with which to be inconsistent. Because of this state of affairs, to get the next label for the current unit, forward checking just selects the next label from the unit label table for the current unit. That label is guaranteed to be consistent with all past unit label-pairs. Forward check­ ing tries to make a failure occur as soon as possible in the tree search by determining if there is any future unit having no label which is consistent with the current unit-label pair. If each future unit has consistent labels, it remembers by copying all consistent future unit­ label pairs to the next level's unit label table. If every future unit has some label in the unit label table which is consistent with the current unit-label pair, then the tree search can move forward to the next unit with a state of affairs similar to how it started. If there is some future unit having no label in the unit label table which is consistent with the current unit-label pair, then tree search remains at the current level with the current unit and continues by selecting the next label from the table. If there is no label then it backtracks to the previous unit label table.

The formal algorithm for forward checking is the Procedure L A TREE SEARCH (Figure 3a) with line 5, the call-t;; LOOK_FUTURE, removed. Forward checking is just looking ahead, omitting the future with future checks.

2.4 Backchecking

Backchecking is similar to forward checking in the way it remembers unit label pairs which are known to be inconsistent with the current or any previous unit label. However, it keeps track of them by testing the current unit label only with past unit label pairs and not future ones. So if, for instance, labels A, B, and C for unit 5 were tested and found incompa tible with label B for unit 2, then the next time unit 5 must choose a label, it should never have A, B, or C as label possibilities as long as unit 2 still has the label B.

Each test that backchecking performs while look­ ing back from the current unit u to some past unit v, forward checking will have performed at the time unit v was the current unit. Of course, at that time, f orward checking will also have checked all future units beyoP.d unit u. Hence, backchecking perfo~ms fewe r consistency tests, an advantage. But backchecking pays the price of having more backtracking and at least as large a tree as forward checking. Back­ checking by itself is not as good as forward checking.

2.5 Backmarking

Backmarking (defined in Gaschnig, 1977, and also discussed in Gaschnig, 1978) is backchecking with an added feature. Backchecking eliminates per­ forming some consistency checks that were pre­ viously done, had not succeeded, and if done again would again not succeed. Backmarking also eliminates performing some cons istency checks that were previously done, had succeeded, and if done again would again succeed. To understand how backmarking works, recall that the tree search by its very nature goes forward, then backtracks, and goes forward again. We focus our attention on the current unit u. We let v be the lowest ordered unit to which we have backtracked (has changed its label) since the last visit to the current unit u. Backmarking remembers v. If v = u, then backmarking pro­ ceeds as backchecking. If v < u, then since all the labels for unit u had been tested in the last visit to unit u, any label now needing testing, needs only to be tested against the labels for units v to u-1, which are the ones whose labels have changed since the last visit to unit u. That is, the tests done previously against the labels for units I through v-1 were successful and if done again would again be successful because labels for units 1 through v-1 have not changed and the only labels per­ mitted for the current unit u are those which have passed the earlier tests .

In this section we compare the six procedures, partia l and full looking ahead, backtracking, backchecking, forward checking, and backmarking, on the N-Queens problem for 4~N~l0, and on a random constraint problem, finding all solu­ tions. We assume that the unit order is fixed in its natural order from 1 to N and that all consistency tests of the current unit with past units or future units begin with the lowest ordered unit . The label sets will consist of all N co lumns; no consideration is given to the various symmetries peculiar to the N-Queens pro­ blem.

Our comparison will be in terms of three kinds of gr aphs and tables:

1. The number of nodes visited is largest for the middle leve ls of the tree search, with the looking ahead procedure having fewest nodes at each level. (Figures 4 and 6)
2. The bulk of the consistency tests are done at shallow depths of the tree · search for the look ahead types of peocedures (Figure 5)
3. Forward checking and backmarking do the few­ est consistency tests among the algorithms using the normal unit orders in most cases tested. (Tables 1 and 2)

3. STATISTICAL MODEL FOR CONSTRAINT SATISFAC­ TION SEARCHES

Our stat istical model for random constraint sat isfact i on is simple . . The probability that a given cons ist ency check succeeds is independent of the pair of units or labels involved and is independent of whatever labels may already have been assigned to past units. Hence, P((uK+l'

In our analysis, we will assume that a given pair of units with a given pair of labels is consi stent with probability p, p being indepen­ dl·tH of which units, whl.ch labels, or any past pr<H' l'SS ing; and then· wi 11 he M units total. If each unil has the saml' number L of possible labels, then any K-tuple of labels for any K . h b bil ' K(K-l)/ 2 f b · · un1ts as pro a 1ty p o e1ng conslstent since each labeling must satisfy K(K-1)/2 consis tency checks. Since there are LK possible l abe l ings of K units, the expected number of consistent l~belings is

Using our statistical model, the expected number of consistency checks at level K in the tree search can be derived:

We might note that the N-Queens problem differs some from the assumption of our statistical model. In terms of number of solutions, N­ Queens has fewer solutions than the expected number of solutions of its associated random constraint satisfaction problem. In terms of consistency checks, N-Queens requires more checks than the expected number of checks of its associated random constraint satisfaction pro­ blem.

The computation of the number of labelings at any depth K for the forward checking algorithm is considerably more complicated, but the result is nearly as simple as for backtracking. The expected number of consistent labelings at level K out of M units will be

Notice that for K = M this is the expected num­ ber of solutions to the problem, and the compu­ tation agrees with the one for the standard backtracking tree search. The expected number of consistency checks at level K will be

Figure 6 shows that the expected number of con­ sistent labelings for random constraint satis­ faction problems agrees closely with the actual number in the average of several experiments.

4. 1 g_pt imiz ing the Consi!tency Check Order in Tree Searching

Suppose we are solving a constraint satisfaction problem and suppose units l, ..· ,K have already been assigned labels ! 1 , ... ,{K are we are trying to find a label {K+l for unit K+l. The label fK+l must come from some set SK+l of labels and it must be consistent with each of the previous labels f 1 , ... ,fK' that is, we must have (k,{k,K+l,fK+lhR for k=l, ... ,K. To deter­ mine the label e 1' we sequentially go through K+ all the labels in SK+l and perform the K consist ency checks: (k,fk,K+l,fK+l)rR. If one check fails, then we try the next label in SK+l' all checks succeed, then we can continue the If depth first search with the next unit.

The optimizing problem for consistency checking is to determine an order in whi ch to perform the tests which minimizes the expected number of tests performed. To set up the optimizing problem, we must have some knowledge about the degree to which a previous unit's label con­ strains unit (K+l)'s label. For this purpose we let P(k) be the probability that the label !k for unit k is consistent with some label for

unit K+l. We assume that the consistency checks are independent events so that the pro­ bability of the tests succeed ing on units 1

For each order of testing, these probabilities determine the expected number of tests in the following way. Let k 1 , ... ,kK be a permutation of l, .. . ,K designating the order in which the consist ency checks will be performed. The ex­ pect ed number of tests performed can be shown to be We can minimize the expected number having k 1 , ... ,kK be any permutation satisfying P(k 1 )~P(k 2 )~, ... ,~P(kK). of tests by of 1, ... ,K Hence, we must choose to test against those past units whose label is most likely to fail against the cur rent unit label pair.

To illustrate the advantage of using an optimum consistency test order, we consider the 10 Queens problem for the standard back tracking procedure whi ch checks the current units' label agains t the pas t units' labels. In theN-Queens problem when the units are naturally ordered from 1 to N and the current unit is K, then the fail first principle states that tests with past units must be done in the order of decreasing constraints. Hence, the test order should be first unit K-1, then K-2, up to unit 1. Back­ tracking requires 1,297,448 tests when done in the wrong order (unit 1, 2, ... ,K-l) and 1,091,856 tests when done in the right order.

4 . 2 Optimizing Tree Search Order

Every tree search must assume some order for the units to be sea r ched in. The order may be uni­ form throughout the tree or may vary from branch to branch. It is clear from experimental results that changing the search order can in­ fluence the average efficiency of the search. In this section we adopt the efficiency criter­ ion of branch depth and we show how by always choosing the nex t unit having smallest number of label cho i ces we can minimize the expected branch depth.

Let k 1 , ... ,kM be the order in which theM units are senr~hed on t he tree. Let P (k lk 1 , ... , n n k 1 ) be the ~ondltionnl probability that some nlabl'l for unit k will succeed when unit k is n n the nth cine in the tree search order given that units k , ... , k 1 are the first n-1 un i ts 1 nsearched in the branch. We assume that the probabili ty of a label for unit kn succeeding depends only on the number of units preceding it in the tree search and not upon whi ch par­ ticular units they are. That is,

This conditional independence assumption justi­ fies the use of the notation P (k ) to designate n n the probability that some label succeeds for unit k when it is the nth unit in the tree n search, and we will call the probability that an arbitrary label for unit u will succeed when checked against another arbitrary unit's label the success probability for unit u.

Units which are searched later in the tree typi­ cally have lower probability for a label suc­ ceeding since the label must be consistent with the labels given all the earlier units. We want some way to compare the probability of success for the same unit in different tree searches. Since the success probability depends only on the unit and its level in the tree and since units later in the tree have lower success pro­ babilities, we assume that the success probabil­ ity for a unit u when it is at level i in one tree search is related to the success probabil­ ity of unit u when it is at the first level of i-1 another tree search by a constant factor a where O<a~l:

The best search order is the one which minimizes the expected length or depth of any branch. When the units are searched in the order k 1 , ... ,km' the expected branch depth is given by

This is minimized when the unit chosen at each level is that unit whose success probability is smallest. Thus at level j we choose unit kj' where

Letting the unconditioned success probability of one unit with another be q we have, Pj(kj) = a j-l[l- (1- qn(k)j)]. Since O~q~ l, this ex­ pression is minimized by choosing kj to be that unit having the smallest number of possible labels.

To illustrate the advantage of using a locally optimal unit order for each branch in the tree search, we consider the improvement achieved on the N Queens problem and the order N random relation problem for 4~N~l0. The number of con­ sistency tests required is given in Tables 1 and 2.

the reason why optimal unit order usually im­ proves forward checking more than backmarking is that forward checking has more information about future units than backmarking. Therefore, for­ ward checking's choice of the next unit most likely to fail is more likely to produce a unit which fails than backmarking's choice.

Some improvement is shown in the larger N-Queens problems, and considerable improvement appears in the larger order N random constraint problems. This improvement increases with problem size in the random constraint problem with p = .65.

V. CONCLUSION

We have shown analytically and experimentally the efficacy of the remembering and fail first principles in constraint satisfaction tree search problems. A new search procedure called forward checking has been described and it combined with optimal unit order choice leads to a more effi­ cient tree search than looking ahead or back­ marking in the large problems t es ted. This sug­ gests that the entire set of look ahead opera­ tors described by Haralick et. al. ( 1978), Haralick and Shapiro (1979a, 1979b), the dis­ crete relaxation described by Waltz (1972) and Rosenfeld et. al. (1976) would be more effi­ ciently implemented by omitting the consistentcy tests required by future units against future units. Future analytic and experimental work needs to be done to determine if this in fact fs generally true. Further work also needs to be done to explore the tradeoff between data struc­ ture overhead and number of consistency tests so that the lowest CPU time algorithms can be determined.

Table 2 Number of Operations in Average of 5 Random Constraint Satisfaction Problems with Consistency Check Success Probability .65, for Normal and Optimal Unit Order

N a number of units · number of labels