Constraint Satisfaction Problems: Formulation Brian C. Williams 16.410-13 September 29 th , 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 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 V i ?D is a set of variable domains, ? i is denoted D i ?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>}} 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 Q i <> Q j On different rows Domains {1, 2, 3, 4} Q 1 , Q 2 , Q 3 , Q 4 , 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. |Q i -Q j Stay off the diagonals Example: C 1,2 Encodings Are Essential: 4 Queens | <> |i-j| = {(1,3) (1,4) (2,4) (3,1) (4,1) (4,2)} 7 Encodings Are Essential: 4 Queens Variables Constraints Q i <> Q j On different rows Domains {1, 2, 3, 4} Q 1 , Q 2 , Q 3 , Q 4 , 1 2 3 4 1 2 3 4 Q Place queens so that no queen can attack another. Q Q Q |Q i -Q j Stay off the diagonals Example: C 1,2 What is C 13 ? 8 Binary CSP most two variables Binary constraint arc Unary constraints just cut down domains Unary constraint arc. Variable V i with domain D i 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 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 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. All courses offered during that termsubdivide each 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 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 includes NP-Hard (intractable) problemsBad News For pairs of courses that