Constraint Satisfaction Problems (CSPs)
by
Zhe Liu
A thesis
presented to the University of Waterloo in fullment of the
thesis requirement for the degree of Master of Mathematics
in
Computer Science
Waterloo, Ontario, Canada, 1998
c Zhe Liu 1998
I authorize the University of Waterloo to lend this thesis to other institutions or individuals for the purpose of scholarly research.
I further authorize the University of Waterloo to reproduce this thesis by pho- tocopying or by other means, in total or in part, at the request of other institutions or individuals for the purpose of scholarly research.
ii
tocopying this thesis. Please sign below, and give address and date.
iii
Many problems in AI can be modeled as constraint satisfaction problems (CSPs).
Hence the development of eective solution techniques for CSPs is an important research problem. Forward checking (FC) with some other heuristics has been traditionally considered to be the best algorithm for solving CSPs while recently there have been a number of claims that maintaining arc consistency (MAC) is more ecient on large and hard CSPs. In this thesis, we provide a systematic comparison empirically of the performances of the MAC and FC algorithms on large and hard CSPs. In particular, we compare their performance with regard to the size, constraint density and constraint tightness of the problems. Though there is a trend that MAC eventually outperforms FC on hard problems as we increase the problem size, we found that the superiority of MAC over FC would not be revealed on the hard problems with low constraint tightness and high constraint density until the size of these problems is quite large. We also devised a new FC algorithm | FC4, which shows good performance on the hard problems with low constraint tightness and high constraint density.
iv
This work was carried out under the supervision of Dr. Fahiem Bacchus. I am greatly indebted to Dr. Bacchus for giving me the opportunity and subsequently providing support and guidance. I would greatly appreciate all his patience, under- standing, encouragement and inspiration.
Special acknowledgment is due to my readers Dr. Nick Cercone and Dr. Ian Munro for sparing their precious time to read my thesis and providing valuable comments and suggestions.
I would also like to thank Jean-Charles Regin of ILOG for providing his pro- grams, and his assistance in my understanding his algorithms.
v
Contents
1 Introduction 1
1.1 What is a CSP? . . . 1
1.2 General approaches for CSP solving . . . 6
1.2.1 Tree Search . . . 6
1.2.2 Constraint propagation . . . 11
1.2.3 Combining backtracking search and constraint propagation . 20 1.3 Summary . . . 29
2 Previous Work on MAC 30
2.1 Improved arc consistency algorithms . . . 302.1.1 AC4 . . . 30
2.1.2 AC6 . . . 37
2.1.3 AC7 . . . 41
2.2 MAC . . . 42
2.2.1 MAC4 - embedding AC4 in backtracking search . . . 42 vi
search . . . 47
2.2.3 Summary . . . 53
2.3 Improving MAC: using heuristics . . . 54
2.3.1 Variable ordering . . . 54
2.3.2 Singleton variables . . . 59
3 FC reconsidered 62
3.1 Using non-support sets . . . 623.2 Algorithm . . . 64
3.3 Analysis . . . 65
4 Empirical Results 69
4.1 Experimental design . . . 694.1.1 Problem generation . . . 69
4.1.2 The algorithms . . . 70
4.1.3 The empirical studies . . . 71
4.2 Results . . . 72
5 Conclusions and future work 118
Bibliography 120
vii
List of Figures
1.1 A possible solution to the 4-queens problem . . . 2
1.2 A map-coloring problem . . . 3
1.3 Graph representation of the 4-queens problem . . . 5
1.4 Graph representation of the map-coloring problem in Figure 1.2 . . 6
1.5 Search tree of the 4-queens problem using BT . . . 10
1.6 An example of arc consistency and inconsistency . . . 12
1.7 After obtaining arc consistency for the example in Figure 1.6 . . . . 15
1.8 No solution after obtaining arc consistency . . . 18
1.9 Two solutions after obtaining arc consistency: (brg) and (yrg) . 18 1.10 No solution . . . 19
1.11 One solution: (brg) . . . 19
1.12 Two solutions: (brg) and (bgr) . . . 19
1.13 Search tree of the 4-queens problem using FC . . . 27
1.14 Search tree of the 4-queens problem using MAC . . . 28
2.1 Solving the 6-queens problem using MAC with refutation . . . 56 viii
3.1 Using non-support sets . . . 63
3.2 Solving a map-coloring problem using FC4 . . . 66
3.3 Non-support sets analysis . . . 67
4.1 N=30, K=10 . . . 73
4.2 N=30, K=10 . . . 74
4.3 N=30, K=10 . . . 75
4.4 N=30, K=10 . . . 76
4.5 N=30, K=10 . . . 77
4.6 N=30, K=10 . . . 78
4.7 N=30, K=10 . . . 79
4.8 N=30, K=10 . . . 80
4.9 N=30, K=10 . . . 81
4.10 K=10 with increasing N . . . 84
4.11 K=10 with increasing N . . . 85
4.12 K=10 with increasing N . . . 86
4.13 K=10 with increasing N . . . 87
4.14 K=10 with increasing N . . . 88
4.15 K=10 with increasing N . . . 89
4.16 K=10 with increasing N . . . 90 ix
4.18 N=30, K=10 . . . 96
4.19 N=30, K=10 . . . 97
4.20 N=30, K=10 . . . 98
4.21 N=30, K=10 . . . 99
4.22 N=30, K=10 . . . 100
4.23 N=30, K=10 . . . 101
4.24 N=30, K=10 . . . 102
4.25 N=30, K=10 . . . 103
4.26 N=40, K=10 . . . 106
4.27 N=40, K=10 . . . 107
4.28 N=40, K=10 . . . 108
4.29 N=60, K=10 . . . 109
4.30 N=60, K=10 . . . 110
4.31 N=60, K=10 . . . 111
4.32 N=30, K=10 . . . 114
4.33 N=60, K=10 . . . 115
4.34 N=75, K=10 . . . 116
4.35 N=75, K=10 (enlarged) . . . 117
x
Chapter 1 Introduction
Many problems in AI can be modeled as constraint satisfaction problems (CSPs).
Hence the development of eective solution techniques for CSPs is an important research problem. In this thesis, we rst review some algorithms for CSP solving, and then provide an empirical analysis of some recently suggested techniques using randomly generated problems.
1.1 What is a CSP?
Examples and applications of CSPs can be found in many areas, such as resource allocation in scheduling, temporal reasoning, natural language processing, query optimization in database, etc.
In general, a CSP is a problem composed of a nite set of variables, each of which has a nite domain of values, and a set of constraints. Each constraint is dened over some subset of the original set of variables and restricts the values these variables can simultaneously take. The task is to nd an assignment of a value for each variable such that the assignments satisfy all the constraints. In some problems, the goal is to nd all such assignments.
A great many \real-world" problems can be formulated as CSPs. For example, we can take a look at the area of resource allocation. One application is exami- nation scheduling. Examinations are to be scheduled in a number of given time slots. With a limited number of classrooms, each examination needs a classroom.
1
Dierent classrooms are of dierent capacity and an examination can only be sched- uled in a classroom that has enough seats for students who are going to take that examination. Some students may take part in several examinations and these ex- aminations cannot be scheduled in the same time slot. To model this problem, we can make each examination a variable, the possible time slots and classrooms are its domain, and the constraints are that certain examinations cannot be held together. A more complicated but more realistic example of resource allocation is airport gate allocation. Usually both the physical constraints (e.g., certain jet-ways can only accommodate certain types of aircraft) and user preferences (e.g., dierent airlines prefer to park in certain parts of an airport) need to be considered. This problem can be modeled as a CSP so that a solution to the CSP would be a solu- tion to the airport gate allocation problem. In all areas of industry and business, resource allocation is a key factor to making a prot and a loss. Hence modeling these problems as CSPs to nd an eective solution is an interesting research topic.
In this thesis, we will focus on how to solve a given CSP.
Since modeling of realistic problems as CSPs is not the topic of this thesis, we illustrate the formalization of a CSP by two simple examples.
The N-queens problem can be modeled as a CSP. Given an integer N, the problem is to place N queens on N distinct squares in an N N chess board, satisfying the constraint that no two queens should threaten each other. Two queens threaten each other if and only if they are on the same row, column or diagonal. Figure 1.1 gives one possible solution to the 4-queens problem.
1 2 3 4
V1 V2 V3 V4
Figure 1.1: A possible solution to the 4-queens problem
Another example of a CSP is the map-coloring problem 6]. In this problem, we need to color each region of the map with one of a given set of colors such that no two adjacent regions have the same color. Figure 1.2 shows a simple map-coloring problem. The map has four regions that are to be colored red, green, or blue.
00000 00000 00000 11111 11111 11111
000000000 000000000 000000000 111111111 111111111 111111111
00000000000000 00000000000000 00000000000000 00000000000000 00000000000000 00000000000000 00000000000000 00000000000000 00000000000000 00000000000000 00000000000000
11111111111111 11111111111111 11111111111111 11111111111111 11111111111111 11111111111111 11111111111111 11111111111111 11111111111111 11111111111111 11111111111111
000000000000 000000000000 000000000000 000000000000 000000000000 000000000000
111111111111 111111111111 111111111111 111111111111 111111111111 111111111111
00 00 00 11 11 11
00000000 0000 11111111 1111
00000 00000 00000 00000 00000 11111 11111 11111 11111 11111
V2 V1
V3 V4
red green blue
Figure 1.2: A map-coloring problem
A CSP is called an n-ary CSP when n is the maximum number of distinct variables over which a constraint is specied. For instance, a binary CSP only has constraints involving two variables. It is well known that any n-ary CSP can be converted to a binary CSP 8] 4] and in this thesis we restrict our attention to binary CSPs. Both the N-queens and map-coloring problems are binary CSPs.
More formally, a binary CSP can be dened to consist of a triple (VDR) where:
V is a set fV1:::Vi:::Vng of n variables
D is a set fD1:::Di:::Dng of domains, such that, 8i, 1 i n, Di =
fvi1:::vij:::vikig is the nite set of possible values for Vi
R is a sequencef:::Rij:::gof binary constraint relations such that8Rij 2R, Rij constrains the two variables Vi and Vj and is dened by a subset of the Cartesian product Di Dj. The set of pairs of values in R species the allowed pairs of values for variables Vi and Vj. If (vilvjm) 2Rij, we say that the assignment fVi vilVj vjmg is consistent.
Thus, we can encode the 4-queens problem as a CSP as follows:
Make each of the 4 rows a variable: V =fV1V2V3V4g.
The value of each variable will represent the column in which the queen in rowi (1 i4) is placed
Domains: D =fD1D2D3D4g
Each of these 4 variables can take one of the 4 columns as its value, with labels 1 to 4. The domains of the 4 variables are:
D1 =D2 =D3 =D4 =f1234g
Constraints: R =fRijji < j and 1ij 4g For each constraint Rij:
1. No two queens on the same row: This constraint becomes trivial given the variable encoding
2. No two queens on the same column : Vi 6=Vj
3. No two queens on the same diagonal: ji;jj6=jVi;Vjj.
In a similar manner, the map-coloring problem in Figure 1.2 can be represented as a CSP as follows:
Variables: V
Each variable represents a region in the map: V =fV1V2V3V4g.
The value of each variable will represent the color assigned to that region
Domains: D =fD1D2D3D4g
The domain Di of variable Vi will be the set of legal colors for regioni(1 i 4). Assuming that we have three possible colors r (red), b (blue) and g (green) for each region, the domains of the four variables become:
D1 =D2 =D3 =D4 =frgbg
Constraints: R =fR12R14R23R24R34g
There is a constraint between two adjacent regions.
For each constraint Rij: Vi 6=Vj.
Associated with every binary CSP is a constraint graph. The constraint graph contains a node for each variable and an edge between each pair of nodes for which there is a constraint between the corresponding two variables.
V1
V3 {1,2,3,4} {1,2,3,4}
{1,2,3,4} {1,2,3,4}
V2
V4
Figure 1.3: Graph representation of the 4-queens problem
Figure 1.3 is the constraint graph for the 4-queens problem which is a complete graph because there is a constraint for each pair of variables. Figure 1.4 shows the constraint graph for the map-coloring problem in Figure 1.2. Each edge represents two adjacent regions in the map.
Finding a solution to a CSP is an NP-complete problem. On one hand, we can guess the assignments of all variables and it is not dicult to check whether all the constraints are satised given these assignments. So it is in NP. On the other hand, the satisability problem (SAT), which is known to be NP-hard, can be encoded as a CSP problem.
Therefore, it is unlikely to have a polynomial time solution for CSPs. Never- theless, there is great interest in nding algorithms for solving CSPs that perform well empirically.
V1
V2
V3 {r,g,b} V4
{r,g,b}
{r,g,b}
{r,g,b}
Figure 1.4: Graph representation of the map-coloring problem in Figure 1.2
1.2 General approaches for CSP solving
A most naive approach to solving a CSP is the \generate-and-test" method. Each possible assignment of values to variables is systematically generated and then tested to see if it satises all the constraints. The rst assignment that satises all the constraints is the solution. In the worst case (or when we are trying to nd all the solutions for a CSP), the number of assignments to be considered is the size of the Cartesian product of all the variable domains. Thus the time complexity of this approach is exponential in the number of variables. Empirically this method performs very poorly.
Randomized \generate-and-test" algorithms that select the assignments to test at random in accord with some biased distribution (e.g., the distribution might be biased by the most recently tested assignments as in randomized hill-climbing 11]) can sometimes perform extremely well, but unfortunately, lose systematicity. That is, these randomized methods are unable to prove that no solution exists since they do not necessarily test all assignments.
In general, there are three standard approaches for CSP solving.
1.2.1 Tree Search
Tree search is a standard technique for solving CSPs. The basic algorithm is sim- ple backtracking (BT) 12], a general search strategy which has been widely used in problem solving. In solving CSPs, it also serves as the basis for many other algorithms.
In BT, variables are instantiated one by one. When a variable is instantiated, a value from its domain is picked and assigned to it. Then constraint checks are performed to make sure that the new instantiation is compatible with all the in- stantiations made so far. If all the completed constraints are satised, this variable has been instantiated successfully and we can move on to instantiate the next vari- able. If it violates certain constraints, then an alternative value, when available, is picked. If all the variables have a value, noting that all the assignments are consis- tent, the problem is solved. If at any stage no value can be assigned to a variable without violating a constraint, backtracking occurs. That means, the most recent instantiated variable has its instantiation revised and a new value, if available, is assigned to it. At this point we continue on to try instantiating the other variables, or we backtrack farther. This carries on until either a solution is found or all the combinations of instantiation have been tried and have failed which means that there is no solution.
Here is the BT algorithm specied in pseudo code:
01 function CONSISTENT(Vivil)
% Check against past variables 02 for each (Vjvjm)2Solution 03 if Rij 2R and (vilvjm)62Rij
04 returnFALSE
05 return TRUE
01 function SEARCH BT(V arsLevel)
% Try to instantiate Vi, then recurse 02 select a variable Vi 2V ars
03 for each value vil 2Di
04 if CONSISTENT(Vivil)
05 SolutionSolution+ (Vivil) 06 if Vi is the only variable in V ars
% Found a solution
07 return TRUE
08 else
09 if SEARCH BT(V arsnfVigLevel+ 1)
10 returnTRUE
% No solution down this branch 11 return FALSE
01 function BT 02 Solution
03 return SEARCH BT(V1)
The CSP to be solved is given as (VDR) and we assume that ifRij 2R, then we also have Rji 2R. The BT algorithm is made up of three functions. BT is the main function. It calls SEARCH BT(V1) to solve the problem. It returnsTRUE if it nds a solution and returns FALSE if there is no solution. SEARCH BT calls itself recursively to explore the search tree. Each invocation ofSEARCH BT corresponds to a node in the search tree, except the root. SEARCH BT has two parameters. V ars is a subset of V. It contains all the uninstantiated vari- ables. Level indicates the recursive level of the current invocation of the function SEARCH BT. Level is 1 when it is rst invoked by BT. Each invocation of SEARCH BT tries to assign a value to an uninstantiated variable. At this point, we call the (Level;1) variables which have already been successfully instantiated the past variables, the variable currently being instantiated the current variable, and the remaining variables the future variables. If the assignment is successful,
it calls itself with increasing Level to search for a consistent assignment of the re- maining variables. Otherwise, it tries the next value of the current variable. If all of the values of the current variable are tried and fail, the current invocation of SEARCH BT exits and returns FALSE. This returns as to the previous invoca- tion of SEARCH BT at Level;1, where the next value of the previous variable is tried. If the return is from the the rst invocation of SEARCH BT, we return to the main function BT with value FALSE and we know that no solution to the CSP exists. On the other hand, if all the variables are instantiated successfully, a solution is found and the current SEARCH BT which has the deepest Level exits and returns TRUE. It will keep on going back to previous invocations of SEARCH BT until it returnsTRUE to the main functionBT. CONSISTENT is called bySEARCH BT to check whether the current instantiation is consistent with the instantiation of all the past variables. Only those constraints between the current variable and the past variables need to be checked. (Constraints that involve only past variables were checked in the previous stages and constraints that involve any future variables cannot be checked now because these variables have not yet been instantiated.) If any of the constraints fail, it returnsFALSE. Other- wise, it returns TRUE. Solution is a global variable used to remember the current partial assignment. Initially it is empty and it will contain the solution in the end if one is found.
Figure 1.5 shows the tree searched by BT on the 4-queens problem. The node in a circle is the solution found by BT:V1 = 2V2 = 4V3 = 1V4 = 3. The number of constraint checks performed is often used as a measurement of the eciency of a CSP algorithm as this corresponds quite closely to the number of atomic operations performed by the algorithm. In the graph, the number beside each node indicates the number of constraint checks for that instantiation and total number of constraint checks and total number of nodes visited are also calculated.
BT is strictly better than generate-and-test in that it is able to eliminate a subspace from the Cartesian product of all the variable domains whenever a partial assignment of variables violates any of the constraints. However, since it essen- tially performs a depth-rst search of the space of potential CSP solutions, its time complexity for most problems is still exponential.
Previous studies 6] have shown that there are two main reasons for the poor performance of BT: thrashing and redundant constraint checks. Some rened al- gorithms of BT have been developed to avoid these problems.
3
0 0
1 1 1 1 1 1 1 1
1 2 2 2 2 2
3 3
Total nodes visited: 27
assigned value still possible value
1 1
1 2 1
1
1
Total constraint checks: 36
Figure 1.5: Search tree of the 4-queens problem using BT
BT suers from thrashing. That is, search in dierent parts of the space keeps failing for the same reasons. Thrashing can be avoided by using some strategies so that backtracking is done directly to the variable that caused the failure. Back- jumping (BJ) is an algorithm developed by Gaschnig 7] that jumps back multiple levels, directly to the cause of a conict to avoid thrashing. Conict-directed back- jumping (CBJ) is an improvement of BJ that can perform multiple backjumps. In both algorithms, the number of nodes visited in the search tree can be reduced, resulting in a reduction in the number of constraint checks.
Sometimes BT has to perform redundant constraint checks. Backmarking (BM) also developed by Gaschnig 7] is aimed at eliminating redundant constraint checks by preventing the same constraint from being tested repeatedly.
All of these algorithms improve the performance of BT to a certain level but still cannot avoid the problem of thrashing and redundant constraint checks completely.
1.2.2 Constraint propagation
Constraint propagation is aimed at transforming a CSP into an equivalent prob- lem that is hopefully easier to solve. Constraint propagation works by reducing the domain size of the variables in such a manner that no solutions are ruled out. It involves removing redundant values from the domains of the variables and propagating the eects of these removals throughout the constraints. Constraint propagation can be performed to dierent degrees.
As mentioned earlier, binary CSPs have associated constraint graphs, where the nodes represent variables and the edges binary constraints. Constraint propagation algorithms are best described in terms of these constraint graphs. Hence the related consistency concepts are named using terminology borrowed from graph theory.
As we know, binary CSPs have only two kinds of constraints: unary constraints and binary constraints. The simplest degree of consistency that can be enforced on a CSP is node consistency which concerns only the unary constraints. A CSP is node consistent if and only if for all variables all values in its domain satisfy the unary constraints on that variable. If a CSP is not node consistent, then there exists a certain variable Vi, and a certain value ain its domain such that valuea does not satisfy the unary constraints on variable Vi. That means, the instantiation of Vi to a always results in an immediate failure. In other words, value a is redundant and will not be in any solution tuples. Hence it can be removed.
In this thesis, we assume that all our CSPs are already node consistent. If a variable has a value in its domain that does not satisfy the unary constraints on it, then that value is regarded to not be in its domain. All the values in the domains of all the variables have to satisfy the unary constraints on these variables.
A stronger degree of consistency is arc consistency. Arc consistency concerns the binary constraints in a CSP and considers binary constraints between one pair of variables at a time. An edge (ViVj) in the constraint graph can be seen as a pair of arcs (ViVj) and (VjVi). We say arc (ViVj) is arc consistent if and only if for every value a in the current domain of Vi, there exists some value b in the
domain of Vj such that Vi =a and Vj = bare permitted by the binary constraint between Vi and Vj. The concept of arc consistency is directional that is, if an arc (ViVj) is consistent, then it does not automatically mean that (VjVi) is also arc consistent. For example, given the map-coloring problem in Figure 1.6, (V1V3) is arc consistent, because b is the only value in the domain of V1 and there exists a value g in the domain of V3 that V1 = b and V3 = g are compatible. However, (V3V1) is not arc consistent. ForV3 =b,V1 =bis not compatible with it and there is no other value in the domain of V1.
V1
V3
V2 not-same
not-same
{r,g}
{b}
not-same
{g,b}
Figure 1.6: An example of arc consistency and inconsistency
An arc (ViVj) can be made consistent by simply deleting those values from the domain ofVi for which there is no value in the domain of Vj compatible with them.
Those values will not be in any solutions and therefore are redundant.
FunctionREV ISE(ViVj) makes arc (ViVj) consistent. It deletes all the values in the domain of Vi that are redundant and returns TRUE. Otherwise, if (ViVj) is initially arc consistent and no value needs to be removed, it returns FALSE.
01 function REV ISE(ViVj) 02 DeletedFALSE 03 for each vil 2Di
04 FoundFALSE 05 for each vjm 2Dj
06 if (vilvjm)2Rij
07 FoundTRUE
08 break
09 if not Found
10 Di Di;vil
11 DeletedTRUE
12 return (Deleted)
A CSP is arc consistent if and only if every arc in the constraint graph is arc consistent. This can be done by executing REV ISE for each arc. But because the removal of some values of one domain may aect the consistency of other arcs and make more values redundant, it is not sucient to executeREV ISE just once for each arc. Again consider the example in Figure 1.6, (V2V3) is initially arc consistent. After arc (V3V1) is made consistent by deleting b from the domain of V3, arc (V2V3) is no longer arc consistent and g in the domain of V2 becomes redundant. In order to make the whole graph fully arc consistent, we have to propagate the removal of values throughout the graph until no more values can be removed.
A naive algorithm AC1 12] for achieving arc consistency is given below:
01 function AC1
% First part: initialization
02 Q
03 for each variable Vi 2V 04 for each variable Vj 2V
05 if Rij 2R
06 QQ(ViVj)
% Second part: examination and propagation
07 repeat
08 ChangedFALSE 09 for each (ViVj)2Q 10 if REV ISE(ViVj)
11 if Di =
12 returnFALSE
13 ChangedTRUE
14 until not (Changed)
15 returnTRUE
Qis a list of arcs to be examined. For each constraint Rij in the problem, both arc (ViVj) and arc (VjVi) are put into Q. AC1 examines every arc (ViVj) in Q and calls REV ISE to delete from the domain of Vi all those values that do not satisfy Rij. If any value is removed, all the arcs will be examined again. The loop will be repeated until no arc is revised.
Applying AC1 on the example in Figure 1.6, we get:
REVISE
Arcs 1st Iteration 2nd Iteration 3rd Iteration
(V1V2) FALSE FALSE FALSE
(V1V3) FALSE FALSE FALSE
(V2V1) FALSE FALSE FALSE
(V2V3) FALSE TRUE FALSE
(V2g) is removed
(V3V1) TRUE FALSE FALSE
(V3b) is removed
(V3V2) FALSE FALSE FALSE
Changed? TRUE TRUE FALSE
The reduced problem which is made arc consistent is given in Figure 1.7. Clearly, we have a solution for this problem with V1 =b, V2 =r and V3 =g.
V1
V3
V2 not-same
not-same
{b}
not-same
{r} {g}
Figure 1.7: After obtaining arc consistency for the example in Figure 1.6 AC1 could be very inecient because the removal of any value from any domain causes all the elements of Q to be re-examined. A simple examining shows that the removal of a value will not aect all the arcs and only the possibly aected arcs need to be re-examined. In the above example, the removal of (V2g) has no eect on arc (V1V3), thus arc (V1V3) need not to be re-examined. An improved
algorithm AC3 12] is given below:
01 function AC3
% First part: initialization
02 Q
03 for each variable Vi 2V 04 for each variable Vj 2V
05 if Rij 2R
06 QQ(ViVj)
% Second part: examination and propagation 07 while Q6=
08 select and remove (ViVj) fromQ 09 if REV ISE(ViVj)
10 if Di =
11 return FALSE
12 else
13 for each variable Vk 2V such that k 6=j
14 ifRki 2R
15 QQ(VkVi)
16 return TRUE
In this algorithm, if REV ISE(ViVj) removes any value from the domain of Vi, then only the domain of any variable Vk that is constrained with Vi has to be re-examined. This is because the removed value in the domain of Vi may be the only one that is compatible with some value ofVk. Therefore arcs (VkVi) are added to Qto be re-examined for all k such that there is an arc from Vk to Vi. However, arc (VjVi) does not need to be re-examined as the removed values of Vi have no compatible values in the domains of Vj. In fact, this is the reason that they are removed. Their removal will not cause any values of Vj to lose compatible value in the domain of Vi. It is clear that we do not need to worry about the domains of other variables that are not constrained with Vi.
Applying AC3 on the example in Figure 1.6, we get:
Arcs REVISE
(V1V2) FALSE
(V1V3) FALSE
(V2V1) FALSE
(V2V3) FALSE
(V3V1) TRUE
(V3b) is removed
Arcs (V1V3), (V2V3) are added
(V3V2) FALSE
(V1V3) FALSE
(V2V3) TRUE
(V2g) is removed
Arcs (V1V2), (V3V2) are added
(V1V2) FALSE
(V3V2) FALSE
We have the same result as using AC1. However, the number of arcs we need to check for revising is reduced.
In general, achieving arc consistency alone rarely generates solutions except for three special cases:
1. If any of the domains is wiped out during the execution, then no solution exists.
2. If the domain size of each variable becomes exactly one after obtaining arc consistency, then there is one solution.
3. If the domain size of N ;1 variables becomes one (N is the total number of variables) and the other domain hask(>1) values, then there arek solutions.
We have already seen an example of case 2. Figure 1.8 and Figure 1.9 are examples of case 1 and case 3 respectively.
On the other hand, in some cases, even after obtaining arc consistency, we still do not know the solution(s). Figure 1.10, Figure 1.11 and Figure 1.12 show three
V1
V3 V2
{r}
{r,g}
{g}
not-same
not-same
not-same not-same not-same
not-same V1
V3 V2
{}
{r} {g}
Figure 1.8: No solution after obtaining arc consistency
V1
V3 V2
{r} {g}
not-same
not-same
not-same not-same not-same
not-same V3
V2
{r} {g}
{r,g,b,y} {b,y}
V1
Figure 1.9: Two solutions after obtaining arc consistency: (brg) and (yrg) examples that are all arc consistent but have no solution, one solution and two solutions respectively.
The 4-queens problem we discussed earlier is initially arc consistent, so the arc consistency algorithms have no eect.
Besides node consistency and arc consistency, there are even stronger degrees of consistency. In general, we say a constraint graph isK-consistentif the following is true: Choose values of any (K;1) variables that satisfy all the constraints among these variables, then choose any K'th variable. A value for this variable exists that satises all of the constraints among these K variables. Furthermore, we can achieve K-consistency by pruning away any values of the K' s variable that fail to satisfy this condition (doing the pruning in a repeated manner as when achieving arc consistency). A constraint graph is strongly K consistent if it is J consistent for all J K. Node consistency and arc consistency are actually equivalent to strong 1-consistency and strong 2-consistency respectively.
An N-variable CSP can be solved by achieving N-consistency. However, this
V1
V3 V2
{r,g}
not-same
not-same not-same
{r,g} {r,g}
Figure 1.10: No solution
V1
V3
V2 not-same
not-same
{r,g} {r,g}
{b,g}
not-same + V1=b & V2=r
not allowed
Figure 1.11: One solution: (brg)
V1
V3 V2
not-same
not-same not-same
{r,g} {r,g}
{b,g}
Figure 1.12: Two solutions: (brg) and (bgr)
approach is seldom used due to its high cost (considerably more expensive than simple backtracking). Usually it is only useful to achieve arc consistency when performing constraint propagation. As pointed out above, however, this does not guarantee we will nd the solution(s). To nd solution(s) when employing arc consistency we must combine constraint propagation with backtracking search.
1.2.3 Combining backtracking search and constraint prop- agation
In the previous two sections, two rather dierent approaches are discussed for solv- ing CSPs: backtracking search and constraint propagation. Backtracking search guarantees that a solution will be found if one exists, but it suers from thrashing and redundant constraint checks. Constraint propagation may simplify the prob- lem, but such simplication is usually insucient to actually solve the problem.
A third approach is to combine these two approaches by embedding a constraint propagation algorithm inside a backtracking search algorithm.
The basic idea is as follows. In the search tree of the backtracking algorithm, whenever a node is visited, a constraint propagation algorithm is performed to at- tain a desired level of consistency by removing inconsistent values from the domains of the as yet uninstantiated variables. If in the process of constraint propagation at the node, the domain of any variable becomes empty, then the node is pruned.
The purpose of doing this is to detect a \dead end" as early as possible. This way, potential thrashing can be reduced, and the size of the search tree is reduced.
This approach turns out to be very eective and quite a few important CSP algorithms, such as forward checking (FC) and maintaining arc consistency (MAC) are in fact of this type. FC with some other heuristics has been traditionally considered to be the best algorithm for solving CSPs while recently there have been a number of claims that MAC is more ecient on large and hard CSPs. The dierence between them lies in the extent of constraint propagation each algorithm performs. In FC, only partial arc consistency is achieved at each node during search while in MAC, full arc consistency is guaranteed. Furthermore, in MAC, the arc consistency algorithm is also performed as preprocessing before search.
Pseudo code for the FC (called FC31) and MAC (called MAC3 1) algorithms is given below. These two functions are used in both the FC3 and MAC3 algorithms:
01 function DWO(Vi)
02 for each value vil 2Di
03 if Domainil is not marked
04 returnTRUE
05 return FALSE
01 function RESTORE(V arsLevel)
% Restore Domain to previous state 02 for each variable Vi 2V ars
03 for each value vil 2Di
04 if Domainil is marked at Level 05 Domainil unMarked These functions are used in the FC3 algorithm:
01 function CHECK FORWARD3(V arsLevelVivil) 02 for each variable Vj 2V ars
03 if Rij 2R
04 for each value vjm 2Dj such that Domainjm is not marked 05 if (vilvjm)62Rij
06 Domainjm Marked atLevel 07 if DWO(Vj)
08 return FALSE
09 return TRUE
1To make them distinct from other improved FC and MAC algorithms which we will discuss later, we call them FC3 and MAC3 respectively.
01 function SEARCH FC3(V arsLevel) 02 select a variable Vi 2V ars
03 for each value vil 2Di such that Domainil is not marked 04 SolutionSolution+ (Vivil)
05 if Vi is the only variable in V ars
% Found a solution
06 return TRUE
07 else
% Try to achieve partial arc-consistency
08 if CHECK FORWARD3(V arsnfVigLevelVivil) and SEARCH FC3(V arsnfVigLevel+ 1)
09 return TRUE
10 else
11 SolutionSolution;(Vivil) 12 RESTORE(V arsnfVigLevel)
% No solution down this branch 13 return FALSE
01 function FC3
02 for each variable Vi 2V 03 for each value vil 2Di
04 Domainil unMarked 05 Solution
06 return SEARCH FC3(V1)
These functions are used in the MAC3 algorithm (assuming AC3 is the algorithm used to maintain arc consistency):
01 function REV ISE(ViVjLevel) 02 DeletedFALSE
03 for each vil2Di such thatDomainil is not marked 04 FoundFALSE
05 for each vjm 2Dj such thatDomainjm is not marked 06 if (vilvjm)2Rij
07 FoundTRUE
08 break
09 if not Found
10 Domainil Marked atLevel 11 DeletedTRUE
12 return (Deleted)
01 function PROPAGATE AC3(V arsLevel) 02 while Q6=
03 select and remove (ViVj) fromQ 04 if REV ISE(ViVjLevel)
05 if DWO(Vi)
06 return FALSE
07 else
08 for each variable Vk 2V ars such that k6=j
09 ifRki 2R
10 QQ(VkVi)
11 return TRUE
01 function SEARCH MAC3(V arsLevel) 02 select a variable Vi 2V ars
03 for each value vil 2Di such that Domainil is not marked 04 SolutionSolution+ (Vivil)
05 if Vi is the only variable in V ars
% Found a solution
06 return TRUE
07 else
% Eliminate all the other values of Vi
08 for each value vil0 2Dinfvilg such thatDomainil0
is not marked
09 Domainil0 Marked atLevel 10 for each variable Vj 2V ars
11 if Rji 2R
12 QQ(VjVi)
13 if PROPAGATE AC3(V arsnfVigLevel) and SEARCH MAC3(V arsnfVigLevel+ 1)
14 return TURE
15 else
16 SolutionSolution;(Vivil) 17 RESTORE(V arsLevel)
% No solution down this branch 18 return FALSE
01 function MAC3
02 for each variable Vi 2V 03 for each value vil 2Di
04 Domainil unMarked 05 Solution
06 Q
07 for each variable Vi 2V 08 for each variable Vj 2V
09 if Rij 2R
10 QQ(ViVj)
11 if PROPAGATE AC3(V0) 12 return SEARCH MAC3(V1)
13 else
% No solution due to arc inconsistency
14 return FALSE
Since we use BT as the algorithm for backtracking search and embed a constraint propagation algorithm inside it, the frameworks of the FC and MAC algorithms are similar to that of BT. All of the three algorithms are made up of three parts:
the main routine, the search routine and the constraint satisfaction routines. The corresponding functions in the three algorithms are:
Algorithm Main Routine Search Routine Constraint Satisfaction Routine
BT BT SEARCH BT CONSISTENT
FC FC3 SEARCH FC3 CHECK FORWARD3 MAC MAC3 SEARCH MAC3 PROPAGATE AC3 The main routine makes the necessary initializations and starts the search. The search routine explores the search tree. It tries to instantiate one of the variables and determines the success of the instantiation by employing the constraint satis- faction routine: if the instantiation is successful, it calls itself recursively to search further otherwise, it backtracks. The constraint satisfaction routine maintains the
constraints at each node of the search tree in a certain way according to dierent algorithms. In fact this is the part where the constraint propagation algorithms are embedded for the FC and MAC algorithms respectively.
The constraint satisfaction parts of the FC and MAC algorithms are dierent from that of the BT algorithm. Instead of checking the constraints between current variable and all past variables which CONSISTENT (in BT) does, in FC and MAC, constraints are checked forward against future variables. In FC, partial arc consistency is achieved in such a way that all values incompatible with the current instantiation are removed from the domains of the future variables. In other words, each future variable is made arc consistent with the current variable. In MAC, full arc consistency is achieved among the newly instantiated variable and all future variables.
When a variable is going to be instantiated, both the FC and MAC algorithms guarantee that any value remaining in its domain is compatible with all the in- stantiations made so far, no backward consistency check is required. However, RESTORE has to be performed to regain the previous state when an instantia- tion fails. An instantiation fails if the domain of a future variable becomes empty (called domain wipe-out or DWO) as a result of constraint propagation.
In order to restore those values pruned due to constraint propagation after a certain instantiation once that instantiation fails, both the FC and MAC algorithms use an extra data structure Domain which is a two dimensional array that keeps track of the status of all the values in the original domains of the variables. Initially all entries ofDomainare unMarkedwhich means all the values in the domains are possible in some solutions. Later on, whenever a value is removed from its domain, the relevant entry of Domain will be labeled as Marked. Moreover, we can mark it using dierent ags (e.g., numbers) according to the level at which it is pruned.
By this way, when we need to perform RESTORE, we can determine whether a pruned value is removed due to the current instantiation and should be put back to its domain, by the ag of its relevant entry in Domain. A utility function DWO is also given to check whether all the values in a domain are marked | in which case a domain wipe-out occurs.
Since we use AC3 as the algorithm to achieve arc consistency in MAC3, relevant code is borrowed from AC3 with some minor changes (mainly to make it work with Domain). Line 6-10 in functionMAC3 corresponds to the rst part ofAC3 in AC3,
which initializes Q. FunctionPROPAGATE AC3 corresponds to the second part of function AC3 in AC3. It is used to restore full arc consistency. It is called not only in function SEARCH MAC3, but also in the main function MAC3 to make sure that the problem is made arc consistent before search starts. Line 10-12 in function SEARCH MAC3 initializes Q for arc consistency propagation when the current variable is revised, since all the other values are removed except the assigned one.
00 11 00 11 00 11 00 11 00 11 00 11
00 1100
11 00 11 00 11 00 11 00 11
00 11 00 11
00 11 00 11
00 11 00 11
00 11
00 11 00 11
00 11 00 11 00
11 00
11 00 1100
11 00 11
00 11 00 11 00
11 00 11
00 11 00 11
00 11
00 11
00 11 00 11
00 11 00 11
00 11 00 11 00 11
00 11 00 11
00 11 00 11 00 11 00 11
00 11 00 11 00 11 00 11 00 11 00 11 00 11
00 1100
11 00 11
00 11 00 11 00 11 00 11 00 11 00 11
12
2 4
1
12
5
2
Total nodes visited: 9 0
Total constraint checks: 38
in current assignment removed value still possible value assigned value
removed value in previous assignments
Figure 1.13: Search tree of the 4-queens problem using FC
We have seen the performance of applying BT on the 4-queens problem and as we have pointed out, since it is initially arc consistent, arc consistency algorithms cannot solve it. Figure 1.13 and Figure 1.14 show solving the 4-queens problem using FC and MAC.
00 11 00 11 00 11 00 11 00 11
00 11 00 11 00 11 0000 1111
00 11 00 11
00 11
00 11 00
11 00
11 0000
1111 0000 1111 00 11 0000 1111
00 11
0000 1111 0000 1111
00 11
0000 1111 0000 1111 0000 1111
00 11 00 11 00 11 00 11
0000 1111
0000 1111 00 11
0000 1111
0000 1111 00 11 0000 1111 00 11 00 11 0000 1111
0000 1111
00 11 00 11
00 11 0000 1111 0000 1111 0000 1111 00 11 0000 1111
0000 1111
0000 1111 00 11 0000 1111 00 11 00 11 0000 1111 00 11 00 11 00 11 0000 1111 0000 1111
0
still possible value assigned value removed value
in current assigment removed value in previous assignments
2 90
23 22
1
Total constraint checks: 138 Total nodes visited: 6
Figure 1.14: Search tree of the 4-queens problem using MAC
The following table is a summary of the performance of the three algorithms.
Algorithm Constraint Checks Nodes Visited Checks per Node
BT 36 27 1.33
FC 38 9 4.22
MAC 138 6 23.00
From this table, we see that FC visits more nodes while MAC does more work at each node. In fact, it is not hard to prove that these conditions hold in general.
In particular, if FC detects a future variable with an empty domain, or a DWO, MAC will also detect a DWO, and may in fact detect a DWO at some parent of the node.
1.3 Summary
Three classes of algorithms have been discussed. In practice, there is consider- able evidence that the third approach which combines backtracking search and constraint propagation is the most eective solution technique for CSPs.
The question now is how much constraint propagation need to do at each node.
More constraint propagation at each node will result in the search tree containing fewer nodes but the overall eort can be higher because the processing at each node will be more expensive. There is a trade-o between the number of nodes visited and the work at each node. The rest of this thesis will concentrate on this question and will address the specic question of comparing the FC and MAC algorithms.
In Chapter 2, we will review some recently suggested improved implementations of the MAC algorithm. In Chapter 3, we will propose an improved implementation of the FC algorithm. Empirical results of comparing FC and MAC are given in Chapter 4. The last chapter is on conclusions and future work.
Chapter 2
Previous Work on MAC
Recently, claims have appeared in the literature that MAC is the most ecient general CSP algorithm for solving large and hard problems 3] 9]. To support this claim, empirical evidence is supplied using improved implementations of MAC.
These improved versions of MAC rely on improved arc consistency algorithms. In this chapter, we review several of these improved arc consistency algorithms and discuss their implementations in MAC.
2.1 Improved arc consistency algorithms
2.1.1 AC4
AC4 12] is an arc consistency algorithm that improves on AC3. AC4 is based on the notion of support. Let a be a value in the domain of Vi, and Vj be a variable constrained with Vi. Value a is supported by Vj if there is at least one value b in the domain of Vj such thatVi =a andVj =bare compatible. Clearly, if each value in the domain of Vi is supported by Vj, then arc (ViVj) is consistent. Values that are not supported are redundant and can be removed.
AC4 keeps track of support explicitly, by maintaining two additional data struc- tures.
1. For each value of every variable there is aCounterfor each arc starting from that variable representing the number of values in the domain of the variable at the other end of the arc that this value is compatible with.
30
For example, Counter(ViVj)a] represents the number of values in the do- main of Vj supporting the assignment Vi =a.
Whenever a Counter for some assignment becomes zero, that domain value can be removed.
2. For each value of every variable, there is a support set S, that contains all of the variable-value pairs that it supports.
For example, for value a in the domain of Vi, a set
SVia =f(Vjb)jVi =a supports Vj =bg
is constructed. This data structure will be used to updateCountereciently.
Again consider the example in Figure 1.6. The domain of V3 has two values, g and b. For V3, two support sets are constructed:
SV3g =f(V1b)(V2r)g SV3b =f(V2r)(V2g)g
The support setSV3g records the fact that the value g in the domain of variable V3 supports the assignment V1 = b and V2 = r. This set helps to identify those assignments that need to be re-examined should the value g be removed from the domain ofV3. In this case, onlybofV1 androf V2 need to be considered. No other value will be aected by the removal of g from the domain of V3.
Similarly, the support sets for V1 and V2 are:
SV1b =f(V2r)(V2g)(V3g)g SV2r =f(V1b)(V3g)(V3b)g SV2g =f(V1b)(V3b)g.
ACounteris maintained for each arc-value pair. For variable V1, there are two arcs starting from it: arc (V1V2) and arc (V1V3). For value b in the domain of variable V1, the arc (V1V2) provides two supports from V2 | namely V2 = r and V2 =g the arc (V1V3) provides one supports from V3 |V3 =g. Therefore,