1CS 2710 Foundations of AICS 2710 Foundations of AILecture 6Milos [email protected] Sennott SquareConstraint-satisfaction searchCS 2710 Foundations of AISearch problemA search problem:• Search space (or state space): a set of objects among which we conduct the search;• Initial state: an object we start to search from;• Operators (actions): transform one state in the search space to the other;• Goal condition: describes the object we search for• Possible metric on a search space:– measures the quality of the object with regard to the goal Search problems occur in planning, optimizations, learning2CS 2710 Foundations of AIConstraint satisfaction problem (CSP)Constraint satisfaction problem (CSP) is a configuration search problem where:• A state is defined by a set of variables• Goal condition is represented by a set constraints on possible variable valuesSpecial properties of the CSP allow more specific procedures to be designed and applied for solving themCS 2710 Foundations of AIExample of a CSP: N-queensGoal: n queens placed in non-attacking positions on the boardVariables:• Represent queens, one for each column:–• Values: – Row placement of each queen on the board{1, 2, 3, 4}Constraints:4321,,, QQQQjiQQ ≠|||| jiQQji−≠−Two queens not in the same rowTwo queens not on the same diagonal4,221== QQ3CS 2710 Foundations of AISatisfiability (SAT) problemDetermine whether a sentence in the conjunctive normal form (CNF) is satisfiable (can evaluate to true)– Used in the propositional logic (covered later)Variables:• Propositional symbols (P, R, T, S)• Values: True, FalseConstraints:• Every conjunct must evaluate to true, at least one of the literals must evaluate to trueK)()()( TQPSRPRQP¬∨∨¬∧∨¬∨¬∧¬∨∨K,)(,)( TrueSRPTrueRQP≡∨¬∨¬≡¬∨∨CS 2710 Foundations of AIOther real world CSP problemsScheduling problems:– E.g. telescope scheduling– High-school class scheduleDesign problems:– Hardware configurations– VLSI designMore complex problems may involve:– real-valued variables– additional preferences on variable assignments – the optimal configuration is sought4CS 2710 Foundations of AIMap coloringColor a map using k different colors such that no adjacent countries have the same color Variables: ?• Variable values: ?Constraints: ?CS 2710 Foundations of AIMap coloringColor a map using k different colors such that no adjacent countries have the same color Variables:• Represent countries–•Values:– K -different colors{Red, Blue, Green,..}Constraints: ?EDCBA ,,,,5CS 2710 Foundations of AIMap coloringColor a map using k different colors such that no adjacent countries have the same color Variables:• Represent countries–•Values:– K -different colors{Red, Blue, Green,..}Constraints:An example of a problem with binary constraintsEDCBA ,,,,etc,,, ECCABA≠≠≠CS 2710 Foundations of AIConstraint satisfaction as a search problemFormulation of a CSP as a search problem:• States. Assignment (partial, complete) of values to variables.• Initial state. No variable is assigned a value.• Operators. Assign a value to one of the unassigned variables.• Goal condition. All variables are assigned, no constraints are violated.• Constraints can be represented:– Explicitly by a set of allowable values– Implicitly by a function that tests for the satisfaction of constraints6CS 2710 Foundations of AISolving CSP as a standard searchUnassigned:Assigned:4321,,, QQQQUnassigned:Assigned:432,, QQQ11=QUnassigned:Assigned:432,, QQQ21=QUnassigned:Assigned:43, QQ4,221== QQCS 2710 Foundations of AISolving a CSP through standard search• Maximum depth of the tree (m): ?• Depth of the solution (d) : ?• Branching factor (b) : ?Unassigned:Assigned:4321,,, QQQQUnassigned:Assigned:432,, QQQ11=QUnassigned:Assigned:432,, QQQ21=QUnassigned:Assigned:43, QQ4,221==QQ7CS 2710 Foundations of AISolving a CSP through standard search• Maximum depth of the tree: Number of variables of the CSP• Depth of the solution: Number of variables of the CSP• Branching factor: if we fix the order of variable assignments the branch factor depends on the number of their valuesUnassigned:Assigned:4321,,, QQQQUnassigned:Assigned:432,, QQQ11=QUnassigned:Assigned:432,, QQQ21=QUnassigned:Assigned:43, QQ4,221==QQCS 2710 Foundations of AISolving a CSP through standard search• What search algorithm to use: ?Depth of the tree = Depth of the solution=number of varsUnassigned:Assigned:4321,,, QQQQUnassigned:Assigned:432,, QQQ11=QUnassigned:Assigned:432,, QQQ21=QUnassigned:Assigned:43, QQ4,221==QQ8CS 2710 Foundations of AISolving a CSP through standard search• What search algorithm to use: Depth first search – Since we know the depth of the solution– DFS in context of CSP is also referred to as backtrackingUnassigned:Assigned:4321,,, QQQQUnassigned:Assigned:432,, QQQ11=QUnassigned:Assigned:432,, QQQ21=QUnassigned:Assigned:43, QQ4,221==QQCS 2710 Foundations of AIChecking constraint consistencyThe violation of constraints needs to be checked for each node, either during its generation or before its expansionConsistency of constraints:• Current variable assignments together with constraintsrestrict remaining legal values of unassigned variables;• The remaining legal and illegal values of variables may be inferred (effect of constraints propagates)• To prevent “blind” exploration it is necessary to keep track of the remaining legal values, so we know when the constraints are violated and when to terminate the search9CS 2710 Foundations of AIConstraint propagationA state (more broadly) is defined by a set variables and their legal and illegal assignments Legal and illegal assignments can be represented through variable equations and variable disequationsExample: map coloringRed=ARed≠CEquationDisequationConstraints + assignmentscan entail new equations and disequationsRed Red≠→= BACS 2710 Foundations of AIConstraint propagation• Assign A=RedABCDEFRed Blue Green- equations - disequations10CS 2710 Foundations of AIConstraint propagation• Assign A=RedABCDEFRed Blue Green- equations - disequationsCS 2710 Foundations of AIConstraint propagation• Assign E=BlueABCDEFRed Blue Green11CS 2710 Foundations of AIConstraint propagation• Assign E=BlueABCDEFRed Blue GreenCS 2710 Foundations of AIConstraint propagation• Assign F=Green ABCDEFRed Blue Green12CS 2710 Foundations of AIConstraint propagation• Assign