Advanced Constraint TechniquesReviewOrdered constraint graphsTree-structured constraint graphBacktrack-free CSPs: Proof sketchSo what if we don’t have a tree?Interleaving constraint propagation and searchLocal Search for CSPMin-conflicts heuristicIntelligent backtrackingSome Challenges for Constraint ReasoningSome Challenges for Constraint Satisfaction1Advanced Constraint Advanced Constraint TechniquesTechniquesKumar, “Algorithms for constraint satisfaction problems: A survey”Barták, “Constraint programming: In pursuit of the holy grail”2Review•Represent a problem as a set of variables and constraint among those variables–For binary constraints, result is a constraint graph G = (V, C) with N variables and M constraints•Use search and/or constraint propagation to solve the constraint network•Improve efficiency of solving by–Interleaving search and constraint propagation–Variable ordering–Value ordering–Intelligent backtracking3Ordered constraint graphs•Select a variable ordering, V1, …, Vn•Width of a node in this OCG is the number of arcs leading to earlier variables:–w(Vi) = Count ( (Vi, Vk) | k < i)•Width of the OCG is the maximum width of any node:–w(G) = Max (w (Vi)), 1 <= i <= N•Width of an unordered CG is the minimum width of all orderings of that graph (“best you can do”)4Tree-structured constraint graph•An OCG with width 1 is a constraint tree rooted at V1–That is, in the ordering V1, …, Vn, every node has zero or one parents•If this constraint tree is also node- and arc-consistent (i.e., strongly 2-consistent), then it can be solved without backtracking•More generally, if the ordered graph is strongly k-consistent, and has width w < k, then it can be solved without backtrackingV1V8 V4V7V6V10V9V5V3V25Backtrack-free CSPs: Proof sketch•Given a strongly k-consistent OCG, G, with width w < k:–Instantiate variables in order, choosing values that are consistent with the constraints between Vi and its parents–Each variable has at most w parents, and k-consistency tells us we can find a legal value consistent with the values of those w parents•Unfortunately, achieving k-consistency is hard (and can increase the width of the graph in the process!)•Fortunately, 2-consistency is relatively easy to achieve, so constraint trees are easy to solve•Unfortunately, many CGs have width greater than one (that is, no equivalent tree), so we still need to improve search6So what if we don’t have a tree?•Answer #1: Try interleaving constraint propagation and backtracking•Answer #2: Try using variable-ordering heuristics to improve search•Answer #3: Try using value-ordering heuristics during variable instantiation•Answer #4: Try using intelligent backtracking methods7Interleaving constraint propagation and searchGenerate and TestNo constraint propagation: assign all variable values, then test constraintsSimple BacktrackingCheck constraints only for variables “up the tree”Forward CheckingCheck constraints for immediate neighbors “down the tree”Partial LookaheadPropagate constraints forward “down the tree”Full LookaheadEnsure complete arc consistency after each instantiation8Local Search for CSP•Start with an initial complete (but invalid) assignment•Hill climbing, simulated annealing•Min-conflicts: Select new values that minimally conflict with the other variables–Use in conjunction with hill climbing or simulated annealing or…•Local maxima strategies–Random restart–Random walk–Tabu search: don’t try recently attempted values9Min-conflicts heuristic•Local Search Method1. Find some “reasonably good” initial solution–E.g., in N-queens problem, use greedy search through rows, putting each queen where it conflicts with the smallest number of previously placed queens, breaking ties randomly2. Find a variable in conflict (randomly)3. Select a new value that minimizes the number of constraint violations–O(N) time and space4. Repeat steps 2 and 3 until done•Performance depends on quality and informativeness of initial assignment; inversely related to distance to solution10Intelligent backtracking•Backjumping: if Vj fails, jump back to the variable Vi with greatest i such that the constraint (Vi, Vj) fails (i.e., most recently instantiated variable in conflict with Vi)•Backchecking: keep track of incompatible value assignments computed during backjumping•Backmarking: keep track of which variables led to the incompatible variable assignments for improved backchecking11Some Challenges for Constraint Reasoning•What if not all constraints can be satisfied?–Hard vs. soft constraints–Degree of constraint satisfaction–Cost of violating constraints•What if constraints are of different forms?–Symbolic constraints–Numerical constraints [constraint solving]–Temporal constraints–Mixed constraints12Some Challenges for Constraint Satisfaction•What if constraints are represented intensionally?–Cost of evaluating constraints (time, memory, resources)•What if constraints, variables, and/or values change over time?–Dynamic constraint networks–Temporal constraint networks–Constraint repair•What if you have multiple agents or systems involved in constraint satisfaction?–Distributed CSPs–Localization