CSP: Definition, Creation, and Algorithms Mr. Tianbing Lin [email protected] Dr. Goodwin Scott University of Windsor Outline Introduction of Constraint Satisfaction Problem Algorithms: Backtracking, Forward Checking, Back Jump, Dynamic Backtracking Evaluation: Random CSP, N-Queen Experimental Result Question? 2 20/2/9

Introduction of CSP Given a set of variables X={x1, x2xn} and a finite set Di of possible values (its domain) for every variable. Given some constraints restricting the values How to assign values for all the variables so that all the constraints are satisfied? 3 20/2/9 Introduction of CSP: N-Queen Variables:

Q1, Q2, Q3, Q4 Domain: {1, 2, 3, 4} Constraints: Qi<>Qj: Not in the same row |Qi-Qj|<>|i-j|: Not in diagonal Extentional Constraints: (Q1, Q2): {(1,3), (1,4), (2, 4), (3,1), (4, 1), (4, 2)} (Q1, Q3): 4 20/2/9 Introduction of CSP: Graph Coloring Paint the graph with different colors 3 Color?

5 20/2/9 Algorithms: Overview Systematic Algorithms: Backtracking, Forward Checking Search the whole solution space systematically In most cases, slow Heuristical Algorithms: Hill-climbing, Simulated

Annealing, Genetic Algorithm 6 In some cases, fast Might not get solution at all. 20/2/9 Algorithms: Backtracking 7 20/2/9 Algorithms: Forward Checking 8

20/2/9 Algorithms: Back Jumping if we find all the values of Variable C are invalid because they are conflict with the value of Variable A, then we don't need to change the value of B to check C again. We can directly jump to another value of Variable A, skip other values of B (under A1 value). N-Queen problem can not demonstrate this algorithm. 9 20/2/9 Algorithms: Dynamic Backtracking

When we back jump to A from C, we reset value of B. Do we really have to reset B, if its not conflict with A or C? We dynamically change the order of variables: Before, A->B->C. Now: B->A->C 10 20/2/9 Algorithms: Dynamic Backtracking Example of Graph Coloring:

Weve finished painting the 3 slides in the north and 2 slides in the south. We dont need to change the value of south slides. 11 20/2/9 Evaluation: N-Queen N-Queen is a nature test scheme. Normally a PC can solve 30-Queen problem in reasonable time using above algorithms. Drawback: Every assignment create (almost) same number of no-good for other variables.

12 20/2/9 Evaluation: Random CSP Randomized constraints can be created according number of variables, average number of constraints, average tightness. Use average solving time to compare different algorithms. 13 20/2/9 Experimental Results

Overal l Compari son f or one sol ut i on 70000 60000 Mi l l i seconds 50000 40000 30000 20000 BackTracki ng Forward Check

Back J ump Dynamic Backtracki ng 76 73 70 67 64 61 58 55

52 49 46 43 40 37 34 31 28

25 22 19 16 13 10 7 4 14 0

1 10000 20/2/9 Experimental Results: Sort by Variable Number 6000 5000 4000 3000 2000

1000 0 13 14 15 Back Tr acki ng 15 16 For war d Check Back J ump Dynami c Backt r ack

20/2/9 Experimental Results: Sort by Tightness Sor t By Ti ght ness ( Al l Sol ut i on) 90000 80000 70000 Mi l l i seconds 60000 50000 40000 30000 20000 10000 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

Back Tr acki ng 16 For war d Check Back J ump 20/2/9 Considering Tightness 17 Constraint density cant assure the tightness of the CSP . For example, we have CSP A and CSP B (domain size: 3, 3 variables):

Density of Constraint 1 and Density of Constraint 2 are 33.3%. Solution is empty, so the tightness is 0/27 20/2/9 Considering Tightness 18 Density of Constraint 1 and Density of Constraint 2 are 33.3%, Can have 9 solutions{(1, 1, 1) (1, 1, 2) (1, 1, 3) (2, 1, 1) (2, 1, 2) (2, 1, 3) (3, 1, 1) (3, 1, 2) (3, 1, 3)}, which means the tightness is 9/27=33%. 20/2/9

Considering Tightness The smallest constraint density of all the constraints is the maximum value of tightness the CSP can have. The exact value of the tightness depends on the relation of the constraint tables. 19 20/2/9 Reference

20 [1] Bartk, R., Constraint Programming: In Pursuit of the Holy Grail, in Proceedings of the Week of Doctoral Students (WDS99), Part IV, MatFyzPress, Prague, June 1999, pp. 555-564. [2] Malek Mouhoub, class notes of Artificial Intelligence. [3] Prosser, P., Binary constraint satisfaction problems: Some are harder than others, Proceedings ECAI-94 (11th European Conference on Artificial Intelligence) [4] White, S, Enhancing Knowledge Acquisition with Constraint Technology, PhD Thesis, University of Aberdeen [5] Pedro Meseguer, CSP: Constraint Programming [6] Joe Culberson and Toby Walsh , Tightness of Constraint Satisfaction Problems

[7] Peter van Beek and Rina Dechter, Constraint Tightness and Looseness versus Local and Global Consistency 20/2/9 Thank you Question? 21 20/2/9