Constraint Satisfaction Problems CS101 FALL 2007 Lecture for Chapter 5 Constraint satisfaction problems What is a CSP Finite set of variables V1 V2 Vn Finite set of constraints C1 C2 Cm Nonempty domain of possible values for each variable DV1 DV2 DVn Each constraint Ci limits the values that variables can take e g V1 V2 A state is defined as an assignment of values to some or all variables Consistent assignment assignment does not violate the constraints Constraint satisfaction problems An assignment is complete when every value is mentioned A solution to a CSP is a complete assignment that satisfies all constraints Some CSPs require a solution that maximizes an objective function Applications Scheduling the Hubble Space Telescope Floor planning for VLSI Map coloring Cryptography Example Map Coloring Variables WA NT Q NSW V SA T Domains Di red green blue Constraints adjacent regions must have different colors e g WA NT So WA NT must be in red green red blue green red Example Map Coloring Solutions are complete and consistent assignments e g WA red NT green Q red NSW green V red SA blue T green Constraint graph Binary CSP each constraint relates two variables Constraint graph nodes are variables arcs are constraints CSP benefits Standard representation pattern Generic goal and successor functions Generic heuristics no domain specific expertise Graph can be used to simplify search e g Tasmania is an independent subproblem Varieties of CSPs Discrete variables finite domains n variables domain size d O dn complete assignments e g Boolean CSPs includes Boolean satisfiability NP complete infinite domains integers strings etc e g job scheduling variables are start end days for each job need a constraint language e g StartJob1 5 StartJob3 Continuous variables e g start end times for Hubble Space Telescope observations linear constraints solvable in polynomial time by linear programming Varieties of constraints Unary constraints involve a single variable e g SA green Binary constraints involve pairs of variables e g SA WA Higher order constraints involve 3 or more variables e g cryptarithmetic column constraints Preference soft constraints e g red is better than green can be represented by a cost for each variable assignment Constrained optimization problems Example Cryptarithmetic Variables F T U W R O X 1 X 2 X3 Domain 0 1 2 3 4 5 6 7 8 9 Constraints Alldiff F T U W R O O O R 10 X1 X1 W W U 10 X2 X2 T T O 10 X3 X3 F T 0 F 0 CSP as a standard search problem A CSP can be easily expressed as a standard search problem Initial State the empty assignment Successor function Assign value to unassigned variable provided that there is not conflict Goal test the current assignment is complete Path cost as constant cost for every step CSP as a standard search problem II This is the same for all CSP s Solution is found at depth n for n variables Hence depth first search can be used Path is irrelevant so complete state representation can also be used Branching factor b at the top level is nd b n l d at depth l hence n dn leaves only dn complete assignments Backtracking search Variable assignments are commutative Eg WA red then NT green equivalent to NT green then WA red Only need to consider assignments to a single variable at each node b d and there are dn leaves Depth first search for CSPs with single variable assignments is called backtracking search Backtracking search is the basic uninformed algorithm for CSPs Can solve n queens for n 25 Backtracking search function BACKTRACKING SEARCH csp return a solution or failure return RECURSIVE BACKTRACKING csp function RECURSIVE BACKTRACKING assignment csp return a solution or failure if assignment is complete then return assignment var SELECT UNASSIGNED VARIABLE VARIABLES csp assignment csp for each value in ORDER DOMAIN VALUES var assignment csp do if value is consistent with assignment according to CONSTRAINTS csp then add var value to assignment result RECURSIVE BACTRACKING assignment csp if result failure then return result remove var value from assignment return failure Backtracking example Backtracking example Backtracking example Backtracking example Improving backtracking efficiency General purpose methods can give huge gains in speed Which variable should be assigned next In what order should its values be tried Can we detect inevitable failure early Most constrained variable Most constrained variable choose the variable with the fewest legal values a k a minimum remaining values MRV heuristic Most constraining variable Tie breaker among most constrained variables Most constraining variable choose the variable with the most constraints on remaining variables Least constraining value Given a variable choose the least constraining value the one that rules out the fewest values in the remaining variables Combining these heuristics makes 1000 queens feasible Forward checking edge consistency is a variant Idea Keep track of remaining legal values for unassigned variables Terminate search when any variable has no legal values Forward checking Idea Keep track of remaining legal values for unassigned variables Terminate search when any variable has no legal values Forward checking Idea Keep track of remaining legal values for unassigned variables Terminate search when any variable has no legal values Forward checking Idea Keep track of remaining legal values for unassigned variables Terminate search when any variable has no legal values A Step toward AC 3 The most efficient algorithm Example 4 Queens Problem 1 2 3 4 X1 1 2 3 4 X2 1 2 3 4 X3 1 2 3 4 X4 1 2 3 4 1 2 3 4 Example 4 Queens Problem 1 2 3 4 X1 1 2 3 4 X2 1 2 3 4 X3 1 2 3 4 X4 1 2 3 4 1 2 3 4 Example 4 Queens Problem 1 2 3 4 X1 1 2 3 4 X2 3 4 X3 2 4 X4 2 3 1 2 3 4 Example 4 Queens Problem 1 2 3 4 X1 1 2 3 4 X2 3 4 X3 2 4 X4 2 3 1 2 3 4 Example 4 Queens Problem 1 2 3 4 X1 1 2 3 4 X2 3 4 X3 X4 2 1 2 3 4 Example 4 Queens Problem 1 2 3 4 X1 2 3 4 X2 1 2 3 4 X3 1 2 3 4 X4 1 2 3 4 1 2 3 4 Example 4 Queens Problem 1 2 3 4 X1 2 3 4 X2 4 X3 1 3 X4 1 3 4 1 2 3 4 Example 4 Queens Problem 1 2 3 4 X1 2 3 4 X2 4 X3 1 3 X4 1 3 4 1 2 3 4 Example 4 Queens Problem 1 2 3 4 X1 2 3 4 X2 4 X3 1 X4 1 3 1 2 3 4 Example 4 Queens Problem 1 2 3 4 X1 2 3 4 X2 4 X3 1 X4 1 3 1 2 3 4 Example 4 Queens Problem 1 2 3 4 X1 2 3 4 X2 4 X3 1 X4 3 1 2 3 4 Example 4 Queens Problem 1 2 3 4 …