• Nu S-Au Găsit Rezultate

Constraint Satisfaction Problems (CSPs)

N/A
N/A
Protected

Academic year: 2022

Share "Constraint Satisfaction Problems (CSPs)"

Copied!
131
0
0

Text complet

(1)

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

(2)

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

(3)

tocopying this thesis. Please sign below, and give address and date.

iii

(4)

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

(5)

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

(6)

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 . . . 30

2.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

(7)

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 . . . 62

3.2 Algorithm . . . 64

3.3 Analysis . . . 65

4 Empirical Results 69

4.1 Experimental design . . . 69

4.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

(8)

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

(9)

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

(10)

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

(11)

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

(12)

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

(13)

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

(14)

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

(15)

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.

(16)

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.

(17)

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

(18)

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,

(19)

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.

(20)

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.

(21)

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

(22)

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.

(23)

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.

(24)

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.

(25)

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

(26)

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.

(27)

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

(28)

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

(29)

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.

(30)

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.

(31)

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.

(32)

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)

(33)

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

(34)

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

(35)

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

(36)

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,

(37)

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.

(38)

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.

(39)

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.

(40)

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

(41)

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,

Referințe

DOCUMENTE SIMILARE

I will only tackle the first level of analysis, in other words the information displayed on the cover, and the strategic pages of two of the RR issues which

Lack of knowledge of the marketing cost advantage of natural gas over other alternative fuels by potential users is a major gas demand constraint in the country (Aluko,

The evolution to globalization has been facilitated and amplified by a series of factors: capitals movements arising from the need of covering the external

Using a case study designed for forecasting the educational process in the Petroleum-Gas University, the paper presents the steps that must be followed to realise a Delphi

Key Words: American Christians, Christian Right, Christian Zionism, US-Israel Relations, Conservative Christians Theology, State of Israel, Jews, Millennial beliefs,

Joseph Kim’s book titled Reformed Epistemology and the Problem of Religious Diversity (Cambridge: James Clarke &amp; Co, 2012), subtitled Proper Function, Epistemic Disagreement,

If philosophy became a transfigured laudator tempori acti or unconsciously contributes to the preservation of status quo, this happens because of the constraint of (the

Authors’ contribution to the workshop focuses on the constraint programming as- pects of Chemera, namely constrained docking, which allows the user to restrict the search