Constraint Satisfaction ProblemsIntro Example: 8-QueensSlide 3Slide 4What is Needed?Constraint Satisfaction ProblemSlide 7Example: 8-Queens ProblemSlide 9Example: Map ColoringExample: Street PuzzleSlide 12Example: Task SchedulingFinite vs. Infinite CSPSlide 15Constraint GraphCSP as a Search ProblemSlide 18RemarkCommutativity of CSP Backtracking SearchSlide 22Slide 23Slide 24Slide 25Slide 26Slide 27Backtracking AlgorithmMap ColoringYour Turn #1QuestionsSlide 32Choice of VariableSlide 34Slide 35Slide 36Choice of ValueSlide 38Constraint Propagation …Forward CheckingSlide 41Slide 42Slide 43Your Turn #2Slide 45Removal of Arc InconsistenciesArc-Consistency for Binary CSPsIs AC3 All What is Needed?Solving a CSP4-Queens ProblemSlide 63Slide 64Slide 65Slide 66Slide 67Slide 68Slide 69Slide 70Slide 71Structure of CSPSlide 73Constraint TreeSlide 75Slide 76Slide 77Local Search for CSPSlide 79Infinite-Domain CSPApplicationsStereotaxic Brain SurgerySlide 83 Constraint ProgrammingAdditional ReferencesWhen to Use CSP Techniques?SummaryConstraint Satisfaction Constraint Satisfaction ProblemsProblemsRussell and Norvig: Chapter 5CMSC 421 – Fall 2005Intro Example: 8-QueensIntro Example: 8-Queens• Purely generate-and-test• The “search” tree is only used to enumerate all possible 648 combinationsIntro Example: 8-QueensIntro Example: 8-QueensAnother form of generate-and-test, with noredundancies  “only” 88 combinationsIntro Example: 8-QueensIntro Example: 8-QueensWhat is Needed?What is Needed?Not just a successor function and goal testBut also a means to propagate the constraints imposed by one queen on the others and an early failure test Explicit representation of constraints and constraint manipulation algorithmsConstraint Satisfaction Constraint Satisfaction ProblemProblemSet of variables {X1, X2, …, Xn}Each variable Xi has a domain Di of possible valuesUsually Di is discrete and finiteSet of constraints {C1, C2, …, Cp}Each constraint Ck involves a subset of variables and specifies the allowable combinations of values of these variablesConstraint Satisfaction Constraint Satisfaction ProblemProblem Set of variables {X1, X2, …, Xn} Each variable Xi has a domain Di of possible values Usually Di is discrete and finite Set of constraints {C1, C2, …, Cp} Each constraint Ck involves a subset of variables and specifies the allowable combinations of values of these variables Assign a value to every variable such that all constraints are satisfiedExample: 8-Queens Example: 8-Queens ProblemProblem 64 variables Xij, i = 1 to 8, j = 1 to 8 Domain for each variable {yes,no} Constraints are of the forms:Xij = yes  Xik = no for all k = 1 to 8, kjXij = yes  Xkj = no for all k = 1 to 8, kISimilar constraints for diagonalsExample: 8-Queens Example: 8-Queens ProblemProblem 8 variables Xi, i = 1 to 8 Domain for each variable {1,2,…,8} Constraints are of the forms:Xi = k  Xj  k for all j = 1 to 8, jiSimilar constraints for diagonalsExample: Map ColoringExample: Map Coloring• 7 variables {WA,NT,SA,Q,NSW,V,T}• Each variable has the same domain {red, green, blue}• No two adjacent variables have the same value: WANT, WASA, NTSA, NTQ, SAQ, SANSW, SAV,QNSW, NSWVWANTSAQNSWVTWANTSAQNSWVTExample: Street PuzzleExample: Street Puzzle123 45Ni = {English, Spaniard, Japanese, Italian, Norwegian}Ci = {Red, Green, White, Yellow, Blue}Di = {Tea, Coffee, Milk, Fruit-juice, Water}Ji = {Painter, Sculptor, Diplomat, Violonist, Doctor}Ai = {Dog, Snails, Fox, Horse, Zebra}Example: Street PuzzleExample: Street Puzzle123 45Ni = {English, Spaniard, Japanese, Italian, Norwegian}Ci = {Red, Green, White, Yellow, Blue}Di = {Tea, Coffee, Milk, Fruit-juice, Water}Ji = {Painter, Sculptor, Diplomat, Violonist, Doctor}Ai = {Dog, Snails, Fox, Horse, Zebra}The Englishman lives in the Red houseThe Spaniard has a DogThe Japanese is a PainterThe Italian drinks TeaThe Norwegian lives in the first house on the leftThe owner of the Green house drinks CoffeeThe Green house is on the right of the White houseThe Sculptor breeds SnailsThe Diplomat lives in the Yellow houseThe owner of the middle house drinks MilkThe Norwegian lives next door to the Blue houseThe Violonist drinks Fruit juiceThe Fox is in the house next to the Doctor’sThe Horse is next to the Diplomat’sWho owns the Zebra?Who drinks Water?Example: Task SchedulingExample: Task SchedulingT1 must be done during T3T2 must be achieved before T1 startsT2 must overlap with T3T4 must start after T1 is complete• Are the constraints compatible?• Find the temporal relation between every two tasksT1T2T3T4Finite vs. Infinite CSPFinite vs. Infinite CSP Finite domains of values  finite CSP Infinite domains  infinite CSPFinite vs. Infinite CSPFinite vs. Infinite CSP Finite domains of values  finite CSP Infinite domains  infinite CSP We will only consider finite CSPConstraint GraphConstraint GraphBinary constraintsTWANTSAQNSWVTwo variables are adjacent or neighbors if theyare connected by an edge or an arcT1T2T3T4CSP as a Search ProblemCSP as a Search Problem Initial state: empty assignment Successor function: a value is assigned to any unassigned variable, which does not conflict with the currently assigned variables Goal test: the assignment is complete Path cost: irrelevantCSP as a Search ProblemCSP as a Search Problem Initial state: empty assignment Successor function: a value is assigned to any unassigned variable, which does not conflict with the currently assigned variables Goal test: the assignment is complete Path cost: irrelevantn variables of domain size d  O(dn) distinct complete assignmentsRemarkRemark Finite CSP include 3SAT as a special case (see class on logic) 3SAT is known to be NP-complete So, in the worst-case, we cannot expect to solve a finite CSP in less than exponential timeCommutativity of CSPCommutativity of CSPThe order in which values are assignedto variables is irrelevant to the final assignment, hence:1. Generate successors of a node by considering assignments for only one variable2. Do not store the path to node Backtracking SearchBacktracking Searchempty assignment1st variable2nd variable3rd variableAssignment = {} Backtracking SearchBacktracking Searchempty assignment1st variable2nd variable3rd variableAssignment = {(var1=v11)} Backtracking SearchBacktracking Searchempty assignment1st variable2nd variable3rd