Last update: February 25, 2010Constraint Satisfaction ProblemsCMSC 421, Chapter 5CMSC 421, Chapter 5 1Outline♦ CSP examples♦ Backtracking search for CSPs♦ Problem structure and problem decomposition♦ Local search for CSPsCMSC 421, Chapter 5 2Constraint satisfaction problems (CSPs)Standard search problem:state is any data structure that supports goal test, eval, successorCSP:state is a set of assignments of valuesto variables {Xi}ni=1with domains {Di}ni=1goal test is a set of constraints specifyingallowable combinations of values for various sets of variablesSimple example of a formal representation languageAllows useful general-purpose algorithms with more powerthan standard search algorithmsCMSC 421, Chapter 5 3Example: map coloringWant to color the map ofAustralia, using at mostthree colorsVariables: WA, NT, Q,NSW, V, SA, TEach variable’s domainis {red,green,blue}WesternAustraliaNorthernTerritorySouthAustraliaQueenslandNew South WalesVictoriaTasmaniaConstraints: adjacent regions must have different colors,e.g., WA 6= NT if the language allows this, or else(WA, NT ) ∈ {(red, green), (red, blue), (green, red),(green, blue), (blue, red), (blue, green)}CMSC 421, Chapter 5 4Example: map coloring, continuedWesternAustraliaNorthernTerritorySouthAustraliaQueenslandNew South WalesVictoriaTasmaniaSolutions are assignments that satisfy all the constraints, e.g.,{WA = red, NT = green, Q = red, NSW = green, V = red, SA = blue,T = green}CMSC 421, Chapter 5 5Constraint graphBinary CSP: each constraint relates at most two variablesConstraint graph: nodes are variables, edges represent constraintsVictoriaWANTSAQNSWVTGeneral-purpose CSP algorithms use the graph structure tospeed up search. E.g., Tasmania is an independent subproblemCMSC 421, Chapter 5 6Varieties of CSPsDiscrete variablesfinite domains of size d ⇒ O(dn) complete assignments for n variables♦ e.g., Boolean CSPs, incl. 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♦ linear constraints solvable but NP-hardnonlinear constraints undecidableContinuous variables♦ e.g., start/end times for Hubble Space Telescope observations♦ linear constraints solvable using Linear Programming (LP) methodscan be done in polynomial time, but very high overheadusually use a low-overhead algorithm with exponential worst-caseCMSC 421, Chapter 5 7Varieties of constraintsUnary constraints involve a single variable,e.g., SA 6= greenBinary constraints involve pairs of variablese.g., SA 6= WAPreferences (soft constraints), e.g., red is better than greenoften representable by a cost for each variable assignmente.g., cost(red) = 1 , cost(green) = 5→ constrained optimization problemsHigher-order constraints involve 3 or more variables,e.g., cryptarithmetic (next slide)CMSC 421, Chapter 5 8Example: CryptarithmeticFind distinct digits Each box represents a constraint:F, O, R, T, U, Wsuch thatOWTF U R+OWTOWTF O U RX2X1X3Solution: 469+469=0938Variables: F , T , U, W , R, O, X1, X2, X3Domain: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}Constraints:alldiff(F, T, U, W, R , O)O + O = R + 10 · X1,etc.CMSC 421, Chapter 5 9Real-world CSPsAssignment problemse.g., who teaches what classTimetabling problemse.g., which class is offered when and where?Hardware configurationSpreadsheetsTransportation schedulingFactory schedulingFloorplanning (e.g., factory layouts)Notice that many real-world problems involve real-valued variablesCMSC 421, Chapter 5 10Standard search formulation (incremental)Let’s start with the straightforward, dumb approach, then fix itStates are defined by the values assigned so far♦ Initial state: the empty assignment, { }♦ Successor function: choose an unassigned variable vassign a value to v that doesn’t conflict with the other variables⇒ fail if no legal assignments♦ Goal test: the current assignment is complete1) This is the same for all CSPs2) With n variables, every solution is at depth n ⇒ use depth-first search3) Path is irrelevant4) If there are d possible values for each variable, then for i = 1, . . . , n,branching factor at depth i is bi= (n − i)d,so there are b0b1. . . bn= n!dnleaves!CMSC 421, Chapter 5 11Backtracking searchVariable assignments are commutative[W A = red then NT = green] same as [NT = green then W A = red]Only need to consider assignments to a single variable at each node⇒ b = d and there are dnleavesDepth-first search for CSPs with single-variable assignmentsis called backtracking searchBacktracking search is the basic uninformed algorithm for CSPsCan solve n-queens for n ≈ 25CMSC 421, Chapter 5 12Backtracking searchfunction Backtracking-Search(csp) returns solution/failurereturn Recursive-Backtracking({ }, csp)function Recursive-Backtracking(assignment, csp) returns soln/failureif assignment is complete then return assignmentvar ← Select-Unassigned-Variable(Variables[csp], assignment, csp)for each value in Order-Domain-Values(var, assignment, csp) doif value is consistent with assignment given Constraints[csp] thenadd {var = value} to assignmentresult ← Recursive-Backtracking(assignment, csp)if result 6= failure then return resultremove {var = value} from assignmentreturn failureCMSC 421, Chapter 5 13Backtracking exampleCMSC 421, Chapter 5 14Backtracking exampleCMSC 421, Chapter 5 15Backtracking exampleCMSC 421, Chapter 5 16Backtracking exampleCMSC 421, Chapter 5 17Improving backtracking efficiencyThere are general-purpose methods that can give huge gains in speed:1. Which variable should be assigned next?2. In what order should its values be tried?3. Can we detect inevitable failure early?4. How to take advantage of problem structure?CMSC 421, Chapter 5 181. Which variable to assign next?Minimum remaining values (MRV) heuristic:♦ choose the variable with the fewest legal valuesAn abstract example: a has 2 possible values and b has 4 possible values:a=2a=1b=2b=3a=2a=1b=1b=4b=2b=3b=1b=4b=2b=3b=1b=4a=2a=1a=2a=1a=2a=1Australia example:CMSC 421, Chapter 5 191. Which variable to assign next?Degree heuristic: ⇒ Use this as a tie-breaker among MRV variables♦ Choose the variable with the most constraints on remaining variablesAbstract example: a and c both have 2 possible values,and c constrains b but a doesn’t:b=2b=3a=2a=1b=1b=4b=2b=3b=1b=4b=2b=3c=2c=1b=1b=2b=1b=4Australia example:CMSC 421, Chapter 5 202. In what order should its