Constraint Satisfaction ProblemsConstraint satisfaction problems (CSPs)Example: Map-ColoringSlide 4Constraint graphVarieties of CSPsVarieties of constraintsBacktracking searchBacktracking exampleSlide 14Slide 15Slide 16Improving backtracking efficiencyMost constrained variableMost constraining variableLeast constraining valueForward checkingSlide 22Slide 23Slide 24Constraint propagationArc consistencySlide 27Slide 28Slide 29Arc consistency algorithm AC-3k-consistencyOther techniques for CSPsStructured CSPsTree-structured CSPsAlgorithm for tree-structured CSPsNearly tree-structured CSPsTree decompositionAn example CSP application: satisfiabilityDavis-Putnam-Logemann-Loveland (DPLL) tree search algorithmA helpful observation for the DPLL procedureProof of the thrmVariable ordering heuristic for DPLL [Crawford & Auton AAAI-93]Constraint learning aka nogood learning aka clause learning used by state-of-the-art SAT solvers (and CSP more generally)Conflict-directed backjumpingClassic readings on conflict-directed backjumping, clause learning, and heuristics for SATMore on conflict-directed backjumping (CBJ)Random restartsPhase transitions in CSPs“Order parameter” for 3SAT [Mitchell, Selman, Levesque AAAI-92]Slide 53How would you capitalize on the phase transition in an algorithm?Generality of the order parameter b…but the complexity peak does not occur (at least not in the same place) under all ways of generating SAT instancesIterative refinement algorithms for SATGSAT [Selman, Levesque, Mitchell AAAI-92] (= a local search algorithm for model finding)BREAKOUT algorithm [Morris AAAI-93]Constraint Satisfaction ProblemsTuomas SandholmCarnegie Mellon UniversityComputer Science Department[Read Chapter 6 of Russell & Norvig]Constraint satisfaction problems (CSPs)•Standard search problem: state is a "black box“ – any data structure that supports successor function and goal test–state is defined by variables Xi with values from domain Di–goal test is a set of constraints specifying allowable combinations of values for subsets of variables•Simple example of a formal representation language•Allows useful general-purpose algorithms with more power than standard search algorithms•CSP: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, or (WA,NT) in {(red,green),(red,blue),(green,red), (green,blue),(blue,red),(blue,green)}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 constraintsVarieties of CSPs•Discrete variables–finite domains:•n variables, domain size d  O(dn) complete assignments•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•Continuous variables–e.g., start/end times for Hubble Space Telescope observations–linear constraints solvable in polynomial time by LPVarieties 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 constraintsBacktracking search•Variable assignments are commutative, i.e.,[ WA = red then NT = green ] same as [ NT = green then WA = red ]•=> Only need to consider assignments to a single variable at each node•Depth-first search for CSPs with single-variable assignments is called backtracking search•Can solve n-queens for n ≈ 25•Backtracking exampleBacktracking exampleBacktracking exampleBacktracking exampleImproving 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•A good idea is to use it as a 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 to assign, 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•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–Constraint propagation•Forward checking propagates information from assigned to unassigned variables, but doesn't provide early detection for all failures:•NT and SA cannot both be blue!•Constraint propagation algorithms repeatedly enforce constraints locally…•Arc consistency•Simplest form of propagation makes each arc consistent•X Y is consistent ifffor every value x of X there is some allowed y–•Arc consistency•Simplest form of propagation makes each arc consistent•X Y is consistent ifffor every value x of X there is some allowed y–•Arc consistency•Simplest form of propagation makes each arc consistent•X Y is consistent ifffor every value x of X there is some allowed y•If X loses a value, neighbors of X need to be rechecked–•Arc consistency•Simplest form of propagation makes each arc consistent•X Y is consistent ifffor every value x of X there is some allowed y•If X loses a value, neighbors of X need to be rechecked•Arc consistency detects failure earlier than forward checking•Can be run as a preprocessor or after each assignment•–•Arc consistency algorithm AC-3•Time complexity: