1Constraint Satisfaction Constraint Satisfaction ProblemsProblemsRussell and Norvig: Chapter 5CMSC 421 – Fall 2003Intro Example: 8Intro Example: 8--QueensQueens• Purely generate-and-test• The “search” tree is only used to enumerate all possible 648combinationsIntro Example: 8Intro Example: 8--QueensQueensAnother form of generate-and-test, with noredundancies Æ “only”88 combinationsIntro Example: 8Intro Example: 8--QueensQueens2What 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 ProblemConstraint Satisfaction ProblemSet 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 ProblemConstraint Satisfaction ProblemSet 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 variablesAssign a value to every variable such that all constraints are satisfiedExample: 8Example: 8--Queens ProblemQueens Problem64 variables Xij, i = 1 to 8, j = 1 to 8Domain 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 diagonals3Example: 8Example: 8--Queens ProblemQueens Problem8 variables Xi, i = 1 to 8Domain 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 Puzzle12345Ni = {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 Puzzle12345Ni = {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?4Example: 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 tasksT1T2T3T4Your turn… Define a CSP ProblemConstraint Satisfaction ProblemConstraint Satisfaction ProblemSet 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 variablesAssign a value to every variable such that all constraints are satisfiedConstraint GraphConstraint GraphBinary constraintsTWANTSAQNSWVTwo variables are adjacent or neighbors if theyare connected by an edge or an arcT1T2T3T45CSP as a Search ProblemCSP as a Search ProblemInitial state: empty assignmentSuccessor function: a value is assigned to any unassigned variable, which does not conflict with the currently assigned variablesGoal test: the assignment is completePath cost: irrelevantCSP as a Search ProblemCSP as a Search ProblemInitial state: empty assignmentSuccessor function: a value is assigned to any unassigned variable, which does not conflict with the currently assigned variablesGoal test: the assignment is completePath cost: irrelevantn variables of domain size dÆ O(dn) distinct complete assignmentsRemarkRemarkFinite CSP include 3SAT as a special case3SAT is known to be NP-completeSo, in the worst-case, we cannot expect to solve a finite CSP in less than exponential timeCommutativityCommutativityof CSPof 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 node6ÆÆBacktracking SearchBacktracking Searchempty assignment1stvariable2ndvariable3rdvariableAssignment = {}ÆÆBacktracking SearchBacktracking Searchempty assignment1stvariable2ndvariable3rdvariableAssignment = {(var1=v11)}ÆÆBacktracking SearchBacktracking Searchempty assignment1stvariable2ndvariable3rdvariableAssignment = {(var1=v11),(var2=v21)}ÆÆBacktracking SearchBacktracking Searchempty assignment1stvariable2ndvariable3rdvariableAssignment = {(var1=v11),(var2=v21),(var3=v31)}7ÆÆBacktracking SearchBacktracking Searchempty assignment1stvariable2ndvariable3rdvariableAssignment = {(var1=v11),(var2=v21),(var3=v32)}ÆÆBacktracking SearchBacktracking Searchempty assignment1stvariable2ndvariable3rdvariableAssignment = {(var1=v11),(var2=v22)}ÆÆBacktracking SearchBacktracking Searchempty assignment1stvariable2ndvariable3rdvariableAssignment = {(var1=v11),(var2=v22),(var3=v31)}Backtracking AlgorithmBacktracking AlgorithmCSP-BACKTRACKING({})CSP-BACKTRACKING(a) If a is complete then return a X Å select unassigned variable D Å select an ordering for the domain of X For each value v in D do If v is consistent with a then  Add (X= v) to a result Å CSP-BACKTRACKING(a) If result ≠failurethen return result Return