CMSC 671 Fall 2001Today’s classAdvanced Constraint TechniquesReviewA famous example: Labelling line drawingsLabelling line drawings IILabelline line drawings (cont.)Ordered constraint graphsTree-structured constraint graphBacktrack-free CSPs: Proof sketchSo what if we don’t have a tree?Interleaving constraint propagation and searchVariable orderingVariable ordering IIValue orderingIterative repairMin-conflicts heuristicIntelligent backtrackingSome challenges for constraint reasoningSome challenges for constraint reasoning II1CMSC 671CMSC 671Fall 2001Fall 2001Class #7 – Tuesday, September 252Today’s class•Interleaving backtracking and consistency checking•Variable-ordering heuristics•Value-ordering heuristics•Intelligent backtracking3Advanced Constraint Advanced Constraint TechniquesTechniquesKumar, “Algorithms for constraint satisfaction problems: A survey”Barták, “Constraint programming: In pursuit of the holy grail”4Review•Represent a problem as a set of variables and cosntraint 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 backtracking5A famous example:Labelling line drawings•Waltz labelling algorithm – one of the earliest CSP applications–Convex interior lines are labelled as +–Concave interior lines are labeled as ––Boundary lines are labeled as•There are 208 labellings (most of which are impossible)•Here are the 18 legal labellings:6Labelling line drawings II•Here are some illegal labelings:++---7Labelline line drawings (cont.)•Waltz labelling algorithm: Propagate constraints repeatedly until a solution is foundA solution for one labelling problemA labelling problem with no solution8Ordered 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”)9Tree-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 V4V7V6V10V9V5V3V210Backtrack-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 search11So 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 methods12Interleaving 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 instantiation13Variable ordering•Intuition: choose variables that are highly constrained early in the search process; leave easy ones for later•Minimum width ordering (MWO): identify OCG with minimum width•Minimum cardinality ordering: approximation of MWO that’s cheaper to compute: order variables by decreasing cardinality•Fail first principle (FFP): choose variable with the fewest values–Static FFP: use domain size of variables–Dynamic FFP (search rearrangement method): At each point in the search, select the variable with the fewest remaining values14Variable ordering II•Maximal stable set: find largest set of variables with no constraints between them and save these for last•Cycle-cutset tree creation: Find a set of variables that, once instantiated, leave a tree of uninstantiated variables; solve these, then solve the tree without backtracking15Value ordering•Intuition: Choose values that are the least constrained early on, leaving the most legal values in later variables•Maximal options method (least-constraining-value heuristic): Choose the value that leaves the most legal values in uninstantiated variables•Min-conflicts: Used in iterative repair search16Iterative repair•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 values17Min-conflicts heuristic•Iterative repair 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 solution18Intelligent 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