1Foundations of Artificial IntelligenceConstraint SatisfactionCS472 – Fall 2007Thorsten JoachimsMoving to a different formalism…SEND+ MORE-------MONEYConsider state space for cryptarithmetic (e.g. DFS).Is this (DFS) how humans tackle the problem?Human problem solving appears more sophisticated! For example, we derive new constraints on the fly.→ little or no search!Constraint Satisfaction Problems (CSP)A powerful representation for (discrete) search problemsA Constraint Satisfaction Problem (CSP) is defined by:X is a set of n variables X1, X2,…, Xneach defined by a finite domain D1, D2,…Dnof possible values.C is a set of constraints C1, C2,…, Cm. Each Ciinvolves a subset of the variables; specifies the allowable combinations ofvalues for that subset.A solution is an assignment of values to the variables that satisfies all constraints.Cryptarithmetic as a CSPProblem: TWO + TWO = FOURVariables:123112233{0,...,9}; {0,...,9}; 0 {0 ,...,9} ;{0,...,9}; {0,...,9} ; {0 ,...,9} ;{0,...,9} ; {0 ,..., 9} ; {0 ,...,9} ;00 10*10 *10 *each letter has a different digit TWFU RXX XRXXWWU XXTTO XXF∈∈∈∈∈∈∈∈∈+= +++ =+++= +=Constraints:(F T ,F U ,etc.);≠≠Cryptarithmetic Constraint GraphTWO+TWOFOURTUWROX2FX1X3Map Coloring ProblemWestern AustraliaNorthernTerritoryQueenslandNew South WalesSouth AustraliaVictoriaTasmania2Unary Constraints: Restriction on single variableBinary Constraints: Restriction on pairs of variablesHigher-Order Constraints: Restriction on more than two variablesTypes of Constraints Constraint Satisfaction Problems (CSP)For a given CSP the problem is one of the following:1. find all solutions2. find one solution· just a feasible solution, or· A “reasonably good” feasible solution, or· the optimal solution given an objective function3. determine if a solution existsInitial State - state in which all the variables are unassigned.Successor function - assign a value to a variable from a set of possible values.Goal test - check if all the variables are assigned and all the constraints are satisfied.Path cost - assumes constant cost for each stepHow to View a CSP as a Search Problem?Branching FactorApproach 1- any unassigned variable at a given state can be assigned a value by an operator: branching factor as high as sumof size of all domains.Approach 2 - since order of variable assignment not relevant, consider as the successors of a node just the different values of a single unassigned variable: max branching factor = max size of domain.Maximum Depth of Search Treen the number of variables → all solutions at depth n. Prefer DFS or BFS?CSP – Goal Decomposed into ConstraintsBacktracking Search: a DFS that• chooses values for variables one at a time•checks for consistency with the constraints.Decisions during search:• Which variable to choose next for assignment.• Which value to choose next for the variable.Forward Checking• Idea: Reduce domain of unassigned variables based on assigned variables.• Each time variable is instantiated, delete from domains of the uninstantiated variables all of those values that conflict with current variable assignment.• Identify dead ends without having to try them via backtracking.3General Purpose HeuristicsVariable and value ordering:Minimum remaining values (MRV): choose the variable with the fewest possible values. Degree heuristic: assign a value to the variable that is involved in the largest number of constraints on other unassigned variables.Least-constraining value heuristic: choose a value that rulesout the smallest number of values in variables connected to thecurrent variable by constraints.Comparison of CSP Algorithms817K(>40,000K)13,500K(>40,000K)N-queens602K(>1,000K)(>1,000K)USABT+FC+MRVBT+FCBT+MRVBTProblemArc Consistency - state is arc-consistent, if every variable has some value that is consistent with each of its constraints (consider pairs of variables)• Init: Q is queue with all (directed) arcs (Xi,Xj) in CSP• WHILE Q is not empty-(Xi,Xj) = remove_first(Q)-FOREACH *IF no satisfies constraint (Xi,Xj)·THEN remove x from dom(Xi)-IF dom(Xi) changed*THEN add all arcs Constraint Propagation (Arc Consistency)()ixdomX∈()ydom Xj∈(,) to kiXXQQ∉Constraint Propagation (K-Consistency)• K-Consistency generalizes arc-consistency (2-consistency).• Consistency of groups of K variables.Local Search for CSPs+=21231222323022Remarks• Infinite discrete domains and continuous domains• Exploiting special problem structure• Dramatic recent progress in Constraint Satisfaction. Methods can now handle problems with 10,000 to 100,000 variables, and up to 1,000,000