Constraint Satisfaction Problems: Formulation Brian C. Williams 16410-13 September 29th, 2003 Slides adapted fro 6. 034 Tomas lozano perez and AIMA Stuart Russell Peter Norvig Reading Assignments: Constraints Much of the material covered only in lecture slides → Read all Slides. AlMA Ch. 5-Constraint Satisfaction Problems(CSPs) AIMA Ch. 24.4 pp. 881-884-Visual Interpretation as solving a CSP ·Prob| em set Problem covers constraints Due Monday, October 6th
Constraint Satisfaction Problems: Formulation Brian C. Williams 16.410-13 September 29th, 2003 Slides adapted from: 6.034 Tomas Lozano Perez and AIMA Stuart Russell & Peter Norvig 1 1 2 Reading Assignments: Constraints • ĺ Read ALL Slides. • • solving a CSP • • • th . Much of the material covered only in lecture slides. AIMA Ch. 5 – Constraint Satisfaction Problems (CSPs) AIMA Ch. 24.4 pp. 881-884 – Visual Interpretation as Problem Set Problem covers constraints. Due Monday, October 6
Constraint Satisfaction Problems 4 Queens Problem Place 4 queens on a 4x4 隧 chessboard so that no queen can attack another Q How do we formulate? Variables Chessboard positio D ns omain Queen 1-4 or blank Constraints Two positions on a line(vertical horizontal, diagonal)cannot both be Q Constraint Satisfaction Problem(CSP) A Constraint Satisfaction Problem is a triple <V, D, C>, where ° V is a set of variables v D is a set of variable domains The domain of variable v is denoted d C is a set of constraints on assignments to v Each constraint specifies a set of allowed variable values Example °A,Bin{1,2} C={1,2><2,1 A CSP Solution: is any assignment to V, such that all constraints in c are satisfied
3 Constraint Satisfaction Problems Variables Constraints Two positions on a line (vertical, horizontal, diagonal) cannot both be Q Domains Queen 1-4 or blank Chessboard positions 1 2 3 4 1 2 3 4 Q 4 Queens Problem: Place 4 queens on a 4x4 chessboard so that no queen can attack another. How do we formulate? Q Q Q 4 Constraint Satisfaction Problem (CSP) A Constraint Satisfaction Problem is a triple <V,D,C>, where: •V is a set of variables Vi •D is a set of variable domains, • i is denoted Di •C is a set of constraints on assignments to V • values. Example: • • A CSP Solution: is any assignment to V, such that all constraints in C are satisfied. The domain of variable V Each constraint specifies a set of allowed variable A,B in {1,2} C = {{<1,2><2,1>}}
Encodings Are Essential: 4 Queens 4 Queens Problem Place 4 queens on a 4x4 隧 chessboard so that no queen can attack another Q How big is the encoding? Variables Chessboard positio D ns omain Queen 1-4 or blank Constraints Two positions on a line(vertical horizontal, diagonal)cannot both be Q Encodings Are Essential: 4 Queens Place queens so that no queen can attack another Q What is a better formulation? 123 Assume one queen per column Determine what row each queen should be in Variables Q1, Q2, Q3, Q4 Domains 1, 2, 3, 41 Constraints Q<> On different rows Q-Q1|<>|jl Stay off the diagonals EXample:C12={(1,3)(1,4)(2,4)(3,1)(4,1)(4,2)}
5 Variables Constraints Two positions on a line (vertical, horizontal, diagonal) cannot both be Q Domains Queen 1-4 or blank Chessboard positions 1 2 3 4 1 2 3 4 Q 4 Queens Problem: Place 4 queens on a 4x4 chessboard so that no queen can attack another. How big is the encoding? Q Q Q 6 Encodings Are Essential: 4 Queens Variables Constraints Qi <> Qj On different rows Domains {1, 2, 3, 4} Q1, Q2, Q3, Q4, 1 2 3 4 1 2 3 4 Q Place queens so that no queen can attack another. What is a better formulation? Q Q Q • Assume one queen per column. • Determine what row each queen should be in. |Qi - Qj Stay off the diagonals Example: C1,2 Encodings Are Essential: 4 Queens | <> |i-j| = {(1,3) (1,4) (2,4) (3,1) (4,1) (4,2)}
Encodings Are Essential: 4 Queens Place queens so that no queen can attack another Variables Q 1234 Domains 1, 2, 3, 4] Constraints Q <>Q On different rows Q-Q1|<>|j Stay off the diagonals Example:C12={(1,3)(1,4)(2,4)(3,1)(4,1)(4,2) What is C? A general class of CSPs Binary CSP Depict as a Constraint Graph each constraint relates at · Nodes are variab|es most two variables Arcs are binary constraints Variable v with Unary constraint arc values in domain D Binary Unary constraints constraint just cut down domains
7 Encodings Are Essential: 4 Queens Variables Constraints Qi <> Qj On different rows Domains {1, 2, 3, 4} Q1, Q2, Q3, Q4, 1 2 3 4 1 2 3 4 Q Place queens so that no queen can attack another. Q Q Q |Qi - Qj Stay off the diagonals Example: C1,2 What is C13? 8 Binary CSP most two variables Binary constraint arc Unary constraints just cut down domains Unary constraint arc. Variable Vi with domain Di Depict as a Constraint Graph A general class of CSPs | <> |i-j| = {(1,3) (1,4) (2,4) (3,1) (4,1) (4,2)} • each constraint relates at values in • Arcs are binary constraints • Nodes are variables
CSP Classic: Graph coloring Pick colors for map regions, without coloring adjacent regions with the same color Variables regions Domains flowed colors Constraints adjacent regions must have different colors Real World: Scheduling as a csp Choose time for activities: activity observations on Hubble telescope jobs on machine tool terms to take required classes 产 Variables are activities time Domains sets of possible start times(or"chunks"of time) Constraints 1. Activities that use the same resource cannot overlap in time 2. Preconditions are satisfied
9 CSP Classic: Graph Coloring Variables Domains Constraints regions allowed colors adjacent regions must have different colors Pick colors for map regions, without coloring adjacent regions 10 Real World: Scheduling as a CSP Variables Domains Constraints are activities sets of possible start times (or “chunks” of time) 1. Activities that use the same resource cannot overlap in time 2. Preconditions are satisfied 2 1 3 4 5 time activity Choose time for activities: • jobs on machine tools with the same color • observations on Hubble telescope • terms to take required classes