CSP: Constraint Satisfaction Problems PDF

CSP: Constraint Satisfaction Problems Artificial intelligence Kristóf Karacs PPKE-ITK Recap n What is intelligence? n Agent model n Problem solving by search ¨ Non-informed search strategies...

CSP: Constraint Satisfaction Problems Artificial intelligence Kristóf Karacs PPKE-ITK Recap n What is intelligence? n Agent model n Problem solving by search ¨ Non-informed search strategies ¨ Informed search strategies ¨ Search in two player games n Logic and inference ¨ Propositional logic ¨ First order predicate logic n Planning 1 Applications of CSP n Scheduling (e.g. sport events) ¨ Constraints: n given a set of teams, every pair of teams has to play twice (home and away) ¨ What is the best way of scheduling the fixtures ¨ Serious commercial interest n Packing problems ¨ e.g. loading up ships with cargo n Constraints: space, size and time Mathematical Applications n Existence of algebraic structures of certain sizes ¨ Quasigroups: some sizes are not possible, proven by Fujita et al. (1993) n Golomb rulers ¨ Put marks on a ruler at integer places such that no pair of marks have the same length between them (so called ‘all-different’ constraint) ¨ What is the smallest Golomb ruler which can accommodate a given number of marks? 2 CSP formalization n A finite set of variables X = {x1,x2,…,xn} n A finite domain of possible values for each xi : Di = {ai,1,ai,2, … , ai,n(i)} n A set of constraints ¨A constraint is a restriction on the values that variables can take simultaneously n Solution to a CSP ¨ All variables are assigned a value from their domains ¨ In consistence with the constraints Solver output n Possible needs ¨A single solution ¨ The best solution ¨ All solutions ¨ Knowing if there is any solution 3 Formal definition of a constraint n Common form: relationship between variables ¨ e.g., x1 ≠ x2, x1 > x3, x2 + x4 < x5 n A constraint Cijk between the variables xi, xj, xk,… is a subset of the set of all tuples ¨ Cijk Í {(v i, v j, v k, …) such that v 1 Î D1, v 2 Î D2, etc.} n Example ¨ Two variables: x1 and x2 ¨ Domains: x1 Î {1,2,3} x2 Î {2,3} ¨ Constraints n x1 = x2 : {(2,2), (3,3)} n x1 < x2 : {(1,2), (1,3), (2,3)} Arity of constraints n Unary constraints ¨ Can be excluded by using a subset of the domain n Binary constraints ¨ Easy graphical and matrix representations ¨ In binary CSPs all constraints are binary ¨ Every CSP can be transformed to a binary CSP 4 Binary constraint graph X1 X2 Nodes are variables {(5,7),(2,2)} X5 X3 Edges are constraints X4 Matrix representation of binary constraints n Constraint C4,5 = {(1,3), (2,4), (7,6)} ¨ Rows: values in D4; columns: values in D5 C 1 2 3 4 5 6 7 X1 X2 {(5,7),(2,2)} 1 X 2 X 3 X5 4 5 X3 6 7 X X4 5 Search in CSPs n Backtracking n Forward checking n Constraint propagation ¨ Arc consistency (for finite domains) n Intelligent backtracking ¨ Conflict-directed backtracking: Save possible conflicts for a variable value on assignment ¨ Back jump to assignment of values Backtracking n Keep trying all variables in a depth first way ¨ Attempt to instantiate the current variable ¨ If it is consistent with all of the constraints, then take the next variable ¨ If all assignments break some constraints (dead-end), then backtrack to the previous (past) variable 6 N-queens example n Standard test case in CSP research n Variables are the rows n Values are the columns n 4-queens constraints ¨ C1,2 = {(1,3),(1,4),(2,4),(3,1),(4,1),(4,2)} ¨ C1,3 = {(1,2),(1,4),(2,1),(2,3),(3,2),(3,4), (4,1),(4,3)} ¨... Backtracking in 4-queens Breaks a constraint 7 Forward Checking n Based on backtracking n In addition it looks at the future variables (without an assigned value) n Before allowing the assignment of Vc to the current variable ¨ For all future variables xf, remove (temporarily) any values in Df which, along with Vc, break a constraint ¨ If any Df gets empty, then xf does not have a legal value (assignment leads to contradiction) ® fail Forward Checking in 4-queens Rows consisting of ‘XXXX’ show that the particular assignment is not good 8 Arc consistency n Binary CSP ¨ Constraints are represented as arcs (between variables ¨ Cij: (xi, xj) n An arc (xi, xj) is consistent if ¨ For all values a in Di, there is a value b in Dj such that the assignment xi = a, xj = b satisfies Cij Making arcs consistent n Pre-processing method for CSP ¨ To make an arc (xi, xj) consistent n Remove values from Di that make it inconsistent ¨ Do this for every arc in turn before a search for a solution is undertaken n Pre-processing like this is common in AI search problems ¨ This won’t affect the solution n because (removed) values would break a constraint, so cannot possibly be assigned in any solution 9 Arc consistency algorithm n function AC-3(csp) returns the CSP, possibly with reduced domains ¨ inputs: csp, a binary CSP with variables {x1, x2,... , xn} ¨ local variables: queue ¨ add all the constraints of the csp to the queue ¨ while queue is not empty do n (xi , xj) ← REMOVE-FIRST(queue) n if REMOVE-INCONSISTENT-VALUES(xi , xj) then ¨ for each xk in NEIGHBORS[xi] do § add (xk , xi) to queue n function REMOVE-INCONSISTENT-VALUES(xi , xj) returns true iff succeeds ¨ removed ← false ¨ for each a in DOMAIN[xi] do n if no value b in DOMAIN[xj] allows (a,b) to satisfy the constraint C(xi, xj) then delete x from DOMAIN[xj]; removed ← true ¨ return removed Arc consistency example n Four tasks to complete (A,B,C,D) n Subject to the following constraints: Task Duration Precedes C1 start ≤ startA A 3 B,C C2 startA + 3 ≤ startB C3 startA + 3 ≤ startC B 2 D C4 startB + 2 ≤ startD C 4 D C5 startC + 4 ≤ startD D 2 C6 startD + 2 ≤ finish n Formulate this with variables for the start times ¨ And a variable for the global start and finish n Values for each variable are {0,1,…,11}, except start = 0 ¨ Constraints: startX + durationX ≤ startY 10 Arc consistency example n Constraint C1 = {(0,0), (0,1), (0,2), …,(0,11)} ¨ So, arc (start, startA) is arc consistent n C2 = {(0,3),(0,4),…(0,11),(1,4),…,(8,11)} ¨ These values for startA never occur: {9,10,11} n So we can remove them from DstartA ¨ These values for startB never occur: {0,1,2} n So we can remove them from DstartB n For CSPs with precedence constraints only ¨ Arc consistency will remove all the values n Which can’t appear in a solution ¨ However, one must work backwards from last tasks to the first ones ¨ In general, arc consistency is effective, but there is no guarantee Arc consistency example 11 Example n QUEUE = {c(A,B), c(A,C), c(A,D), c(B,C), c(B,D), c(C,D)}: { 1, 2, 3, 4} B=A+1 { 1, 2, 3, 4} A B A¹ D A¹ C D 1 C D { 1, 2, 3} C¹ D { 1, 3, 4} n To be added: c(A,C), c(A,D), c(B,C), c(B,D) n All already in QUEUE ! n QUEUE = {c(A,C), c(A,D), c(B,C), c(B,D), c(C,D)} Example n QUEUE = {c(A,C), c(A,D), c(B,C), c(B,D), c(C,D)}: { 1, 2, 3} B=A+1 { 2, 3, 4} A B A¹ D A¹ C D 1 C D { 1, 2, 3} C¹ D { 1, 3, 4} n QUEUE = {c(B,C), c(B,D), c(C,D)} 12 Example n QUEUE = {c(B,C), c(B,D), c(C,D)}: { 1, 2, 3} B=A+1 { 2, 3, 4} A B A¹ D A¹ C D 1 C D { 1, 2, 3} C¹ D { 1, 3, 4} n To be added: c(A,B), c(A,C), c(B,D), c(C,D) n QUEUE = {c(B,D), c(C,D), c(A,B), c(A,C)} Example n QUEUE = {c(B,D), c(C,D), c(A,B), c(A,C)}: { 1, 2, 3} B=A+1 { 3, 4} A B A¹ D A¹ C D 1 C D { 1, 2} C¹ D { 1, 3, 4} n To be added: c(A,D), c(C,D) n QUEUE = {c(C,D), c(A,B), c(A,C), c(A,D)} 13 Example n QUEUE = {c(C,D), c(A,B), c(A,C), c(A,D)}: { 1, 2, 3} B=A+1 { 3, 4} A B A¹ D A¹ C D 1 C D { 1, 2} C¹ D { 1, 3} n To be added: c(A,C), c(A,D) n QUEUE = {c(A,C), c(A,D)} Example n QUEUE = {c(A,C), c(A,D)}: { 2, 3} B=A+1 { 3, 4} A B A¹ D A¹ C D 1 C D { 1, 2} C¹ D { 1, 3} n QUEUE = empty 14 Is arc consistency all we need? n No, e.g. it cannot detect all contradictions among binary constraints X¹Y {1, 2} X Y {1, 2} X¹Z Y¹Z Z {1, 2} Further inference methods n Path consistency ¨ Looks at triples of variables n k-consistency ¨ Generalization for k nodes ¨ Arc consistency: k=2 ¨ Path consistency: k=3 (for binary constraints) ¨ However: exponential time and space complexity n Global constraints ¨ e.g. all-different ¨ resource constraints (e.g. on machines, space, people) 15 Heuristic methods n Choosing the order in which we ¨ instantiate variables ¨ choose values for the instantiation n How can we detect inevitable failure as early as possible? n Variable ordering heuristics ¨ Static methods (fix before the search) ¨ Dynamic methods (change during search) Variable ordering heuristics n Minimum Remaining Values (MRV) a.k.a. “fail first” heuristic ¨ Ittries to bring dead-ends upper in the tree ¨ Instantiates the most constrained variable (i.e. the one with fewest remaining values) n Tie-break rule: degree heuristic ¨ Choose the variable with the most constraints on remaining variables 16 Speed-ups Problem Backtracking BT+MRV Forward FC + MRV Checking N-Queens (>40000K) 13,500K (>40000K) 817K Random1 415K 3K 26K 2K Random2 942K 27K 77K 15K Value ordering heuristic n No sense in trying to rule out dead-ends ¨ Each value must be tried anyway n Least constrained value (LCV) ¨ Chooses a value which is likely to succeed, the one that rules out the fewest values in the remaining variables n Extra cost ¨ Reduction in domain sizes of future variables for every possible value must be calculated ¨ Efficiency depends on the given problem 17 Constraint solving by software n CHIP (Constraint Handling in Prolog) ¨ Developer: Mehmet Dincbas, ECRC Münich ¨ Commercialized by Cosytec n ILOG Solver ¨ INRIA ¨ Commercialized by ILOG (owned by IBM) n Prolog - CPLFD library ¨ Constraint Logic Programming over Finite Domains n All meant to be used for easy or general problems Efficient formulation of CSPs n Needs good insights into CSP formalization ¨ E.g. symmetry detection n Automated reformulation of CSPs ¨ Find another set of variables that allows for finding a solution faster ¨ Automated discovery of additional constraints 18 Extensions to CSPs n Dynamic CSPs ¨ Solving of problems that change while you are trying to solve them ¨ Packing problem: new packages may arrive that have to be fitted in Example 19 Example n Variables ¨ 25 lengths n Values ¨ Let the tiny square be of integral length 1 ¨ Others range up to about 1000 n Constraints ¨ Lengths have to add up n Solution ¨ A set of lengths for the squares n Answer ¨ The length of the eleventh largest square Prolog solution n go(Top, [L1, L2, … , L25]) :- ¨ L1 in 1..Top, L2 in 1..Top, … , L25 in 1..Top, ¨ L1 #< L2, L2 #< L3, … , L24 #< L25, ¨ all_different([L1, L2, … , L25]), ¨ L1*L1 + L2*L2 + … + L24*L24 #= L25*L25, ¨ L1 + L3 #= L4, L4 + L1 #= L5, L4 + L5 #= L7, L5 + L7 #= L8, L3 + L4 + L7 #= L9, L1 + L5 + L8 #= L11, … ¨ labeling([], [L1, L2, … , L25]), ¨ write(L1), write(L2), … , write(L25), nl. 20 Length constraints ¨ L1 + L3 #= L4, L4 + L1 #= L5, ¨ L4 + L5 #= L7, L5 + L7 #= L8, ¨ L3 + L4 + L7 #= L9, L1 + L5 + L8 #= L11, ¨ L2 + L12 #= L14, L2 + L14 #= L15, ¨ L2 + L15 #= L16, L10 + L11 #= L17, ¨ L7 + L8 + L9 #= L18, L6 + L16 #= L19, ¨ L6 + L19 #= L20, L9 + L18 #= L21, ¨ L10 + L17 #= L22, L14 + L15 #= L23, ¨ L13 + L20 #= L24, L21 + L22 + L23 #= L25, ¨ L18 + L21 + L24 #= L25, L19 + L20 + L24 #= L25, ¨ L15 + L16 + L19 + L23 #= L25, Solution n go(1000, A). n 1 2 3 4 5 8 9 14 16 18 20 29 30 31 33 35 38 39 43 51 55 56 64 81 175 21