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 , 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 , 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 = {{}}
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
Case Study: Course Scheduling 40 courses(8.01,8.0 6.840),and 0 terms(Fall 1, Spring 1 Spring 5) Fin ind a legal schedule Constraints Pre-requisites satisfied Courses offered on limited terms Limited number of courses taken per term (say 4) · Avoid time conflicts Note, traditional CSPs are not for expressing(soft) preferences g. minimize difficulty, balance subject areas, etc Alternative choices for variables values VARIABLES DOMAINS A. 1 per Term All legal combinations of 4 courses (Fall 1)(Spring 1) all offered during that term (Fall 2) (Spring 2) B. 1 per Term-slot subdivide each term All courses offered during that term into 4 course slots (Fal1,1)(Fa1,2) (Fa1,3)(Fal|1,4 C. 1 per Course Terms or term-slots (Term-slots make it easier to express constraints on limited number of per term
11 Given: Find a legal schedule. Constraints (say 4) Note, traditional CSPs are not for expressing (soft) preferences e.g. minimize difficulty, balance subject areas, etc. Case Study: Course Scheduling 12 Alternative choices for variables & values A. All legal combinations of 4 courses, all offered during that term. C. 1 per Course Terms or term-slots (Term-slots make it easier to express constraints on limited number of courses per term.) B. subdivide each term All courses offered during that term into 4 course slots: (Fall 1,1) (Fall 1, 2) (Fall1, 3) (Fall 1, 4) VARIABLES DOMAINS (Fall 1) (Spring 1) (Fall 2) (Spring 2) . . . • 40 courses (8.01, 8.02, . . . . 6.840), and • 10 terms (Fall 1, Spring 1, . . . . , Spring 5). • Pre-requisites satisfied • Courses offered on limited terms • Limited number of courses taken per term • Avoid time conflicts 1 per Term 1 per Term-Slot
Encoding constraints Assume: Variables Courses. Domains term-slots At least Constraints term Prerequisite→ 16.41 For pairs of courses that must be ordered AAt least term after Courses offered only during certain terms " Filter domain Term-slots not equal Limit# courses→ Use term-slots only once for all pairs of vars. term not equal Avoid time conflicts→ For course pairs offered at same or overlapping times Good News/ Bad News Good News -very general interesting classes of problems Bad News includes NP-Hard (intractable) problems
13 Encoding Constraints Assume: Variables = Courses, Domains = term-slots Prerequisite ¨ must be ordered. 16.070 16.410 At least term before At least term after Limit # courses ¨ Use term-slots only once for all pairs of vars. Term-slots not equal term not equal Avoid time conflicts ¨ For course pairs offered at same or overlapping times Courses offered only during certain terms ¨ Filter domain Constraints: 14 Good News / Bad News Good News - - very general & interesting classes of problems Bad News includes NP-Hard (intractable) problems For pairs of courses that