Constraint satisfaction problems

1Chapter 3CONSTRAINT SATISFACTION PROBLEMS2OutlineWhat is a CSP?Posing a CSPGenerate-and-test-algorithmsStandard backtracking algorithmConsistency algorithmLook-ahead Schemes3What is a CSP?In constraint satisfaction problems (CSPs), we are given a set of variables, a domain for each variable, anda set of constraints. Each constraint is defined over some subset of the original set of variables and limits the combinations of values that the variables in this subset can take. The goal is to find one assignment to the variables such that the assignment satisfies all the constraints.CSPs can be divided into two main classes: Satisfiability problems, where the goal is to find an assignment of values to variables that satisfies some constraints. An assign-ment of values to variables either satisfies the constraints or not. Optimization problems, where each assignment of a value to each variable has a cost or an objective value associated with it. The goal is to find an assignment with the least cost or with the highest objective value. This is called the optimal assignment.4The constraints of satisfiability problems, which must be met, are called hard constraints.The costs in optimization problems, which specify preferences rather than what has to be met, are called soft constraints.A large number of problems in AI and other areas of computer science can be viewed as special cases of the constraint-satisfaction problem. Some examples are- machine vision- scheduling- temporal reasoning- floor plan design.- diagnosis of analog circuit- financial planning- constraint-based engineering design5POSING A CONSTRAINT SATISFACTION PROBLEM A CSP is characterized by a set of variables V1, V2, ,Vn. Each variable Vi has an associated domain Dvi of possible values. For satisfiability problems, there are constraint relations on various subsets of the variables which give legal combinations of values for these variables. These constraints can be specified by subsets of the Cartesian products of the domains of the variables involved.A solution to the CSP is an n-tuple of values for the variables that satisfies all the constraints.For optimization problems, there is a function that gives a cost for each assignment of a value to each variable. A solution to an optimization problem is an n-tuple of values for the variables that optimizes the cost functions.6Example 1Suppose that the delivery robot needs to schedule delivery activities a, b, c, d, and e, and that each activity happens at either time 1, 2, 3, or 4. Let A be the variable representing the time that activity a will occurs, and similarly for the other activities.Suppose it’s given these initial variable domains, which represent possible times for each of the deliveries:DA = {1,2,3,4}, DB = {1,2,3,4}, DC = {1,2,3,4}, DD = {1,2,3,4}, and DE = {1,2,3,4}And the following constraint to satisfy: (B  3 )  ( C  2)  (A B )  ( B C)  ( C ,,.Each element of D can be tested. In this case there are |D| = 45 = 1024 different assignments to be tested.If each of the variable domains has size d, then |D| = dn and if there are e constraints then the total number of tests is O(edn). As n becomes large, this very quickly becomes intractable.10THE STANDARD BACKTRACKING ALGORITHM Generate-and-test involves assigning values to all variables before checking the constraints. Constraints can be tested before all of the variables have been assigned values.We can systematically explore D by instantiating the variables in some order and evaluating each constraint as soon as all its variables are bound. If any constraint evaluates to false, the current partial assignment can’t be part of any total valid assignment. We can try another partial assignment of values. A single failure eliminates a potentially huge subspace of D.Example: In the scheduling problem the assignments A = 1 and B = 1 are inconsistent with the constraint A  B regardless of the values of the other variables. If the variables are assigned values in the order , this inconsistency can be discovered and that pair of values rejected before any values are assigned to C, D, or E, thus saving a large amount of work.11procedure BACKTRACKINGi := 1; Di’ := Diwhile 1  i  n instantiate vi := SELECTVALUE if vi is null then i := i-1 else i := i+1 Di’ := Diend while if i =0 return “inconsistent”else return instantiated values of {v1,v2,,vn}end procedureprocedure SELECTVALUEwhile Di’ is not empty select an arbitrary element a  Di’ and remove a from Di’ if value a for vi is consistent with then return a end while return nullend procedure12The BACKTRACKING procedure employs a series of domains Di’ such that each Di’  Di. Di’ holds the subset of Di that has not yet been examined under the current partial instantiation.The efficiency of backtracking algorithm depends critically on the ordering of the variables. One ordering may be much more efficient than others.Using BC algorithm, a CSP can be viewed as a graph-searching algorithm. First order the variables as V1, V2, ,Vn. A node of the graph consists of a substitution that assigns values to the first j variables for some j, such as {V1/v1,,Vj/vj} where vi Dvi. The neighbors of node are the nodes {V1/v1,,Vj/vj,Vj+1/vj+1} for each vj+1 Dvj+1. The start node is the empty substitution, and a goal node is a substitution that grounds every variable, and satisfies the constraints. We prune any node in the graph that fails the constraints, as any of its descendents also fail the constraints.13Example: Graph coloring14State space tree15State space tree16Consistency AlgorithmsAlthough backtracking is better than the generate-and-test method, its run time complexity for most problems is still exponential. One of the reasons for this poor performance is that backtracking suffers from thrashing. Thrashing means that search in different parts of the space keep failing for the same reasons.Example: In the scheduling example, variables C and D. The assignment C = 4 is inconsistent with each of the possible assignments to D since DD = {1,2,3,4} and C and in a graph. Such a network is called a constraint network.17Constraint NetworkV1V5V2V3V4V6{a}{b,c}{a,b,c.d}{b,c}{b,c,d}{b,c,d}(b,b)(c,c)(d,d)(a,b)(a,c)(a,d)(b,b)(c,c)(d,d)(c,d)(b,c)(c,c)(c,d)(b,b)(c,c)(d,d)18Domain consistency & arc-consistencyA node in a constraint network is domain consistent if no value in the domain of the node is ruled impossible by any of the constraints.Domain consistency doesn’t take into account any of the values for any of the other variables.Example: DB = {1,2,3,4} is not domain consistent as B = 3 violates the constraint that that specifies B  3.An arc is arc-consistency if for any value of X in DX there is some value for Y in DY such that P(X,Y) is satisfied. A network is arc-consistent if all its arcs are arc- consistent.If an arc is not arc-consistent, all values of X in DX for which there is no corresponding value in Dy may be deleted from DX to make the arc consistent.19AC-3 AlgorithmThe Arc-consistency algorithm AC-3 makes the entire network arc consistent by considering a queue of potentially inconsistent arcs. These initially consist of all the arcs in the graph. Note: any constraint PXY between variables X and Y makes two arcs; and . Until the queue is empty, an arc is removed from the queue and considered. If it is not consistent, it is made consistent and all consistent arcs that could have become inconsistent are placed back on the queue.Arc-consistency algorithm AC-3Input: A set of variables A domain DX for each variable X Relations PX on variable X that must be satisfied Relations PXY on variables X and Y that must be satisfiedOutput: arc-consistent domain for each variable20Algorithm: For each variable X DX := {x  DX| PX(x)} Q := {| PXY is a binary constraint } {| PXY is a binary constraint } repeat select any arc  Q; Q := Q – {}; NDX := DX – {x| x  DX and there is no y  DY such that PXY(x,y)}; if NDX  DX then Q := Q  { | Z  Y}; until Q is empty.21ExampleApply AC-3 to the scheduling example as shown in network form in Figure 3.2. The network has already been made domain consistent.CDEC C (arc 2) E E (arc 4) E E (arc 6)Consider arc 1: Remove 4 from the domain of C. C = {1,3}. We need to add arc3 to the queue. But we don’t have to do so since arc3 is already in the queue.Consider arc 3: Remove 3,4 from the domain of E. E = {1,2}. We need to add arc6 to the queue. But we don’t have to do so since arc6 is already in the queue.Consider arc 2: Remove 1 from the domain of D. D = {2,3,4}. We need to add arc5 to the queue. But we don’t have to do so since arc5 is already in the queue.Consider arc 4: Remove 1 from the domain of C. C = {3}. We need to add arc2 to the queue.Consider arc 5. No change.Consider arc 6. No change.Consider arc 2. Remove 2,3 from the domain of D. D = {4}. We need to add arc5 to the queue.Consider arc 5. No change.Now the queue becomes empty. 23So the domains of the variables now are: C: {3} D: {4} E: {1,2}Note: The order of activating constraints is unimportant. Regardless of the order in which the arcs are considered, AC-3 will terminate with the same result, namely, an arc consistent network and the same set of reduced domains. There are three possible cases depending on the state of the network on termination:In the first case, each domain is empty.  There is no solution to the CSP. In this case, as soon as any one domain becomes empty, all the domains will become empty before the algorithm terminates.In the second case, each domain has a singleton value.  There is unique solution to the CSP.In the third case, every domain is nonempty and at least one has multiple values left in it. In this case, any non-singleton domain may be split in half and the algorithm applied recursively to the two CSPs that result. Splitting the smallest nonsingleton domain is usually most effective. (So combination of AC-3 and domain splitting can solve CSPs.)24Complexity of AC-3If each variable domain is of size d and there are e relations to be tested then AC-3 is O(ed3).Various extensions to the arc-consistency technique are also possible. extending it from binary to k-ary relations is straightforward. the domains need not be finite: they may be specified using descriptions, not just lists of their values.25Look-ahead SchemesThe techniques for improving backtracking algorithms:look-ahead schemeslook-back schemesLook-ahead schemes are invoked whenever the algorithm is preparing to extend the current partial solution. Look-ahead schemes include the functions that choose the next variable to be instantiated, choose the next value to give to the current variable, and reduce the search space by maintaining a certain level of local consistency during the search.Look-back schemes are invoked whenever the algorithm encounters a dead-end and prepares for the backtracking step. Look-back schemes include the functions that decide how far to backtrack by analyzing the reasons for the dead-end and decide what new constraint to record so that the same conflicts do not arise again later in the search.26The Look-ahead Algorithm Some of the inefficiencies of the backtracking algorithm motivate the development of the filtering algorithms which works by preprocessing the domain using constraint propagation. Arc-consistency algorithm is one of the important filtering algorithms. However, the filtering algorithms themselves are not powerful enough to solve the problems alone. Therefore, a variety of hybrid combinations of the two have been suggested. (Backtracking + filtering)The basic member of the group is the forward checking algorithm. The forward checking algorithm may be viewed as augmenting standard backtracking by removing from the domain of each uninstantiated variable all values which are inconsistent with the new instantiation, and thus eliminate in advance all possible violation of constraints on the instantiated variables.27BC_FC algorithmprocedure BACKTRACKING-WITH-LOOK-AHEADDi’ := Di for 1  i  ni := 1while 1  i  n instantiate vi := SELECTVALUE-FORWARD-CHECING if vi is null then i := i-1 reset each Dk’, k> i, to its value before vi was last instantiated else i := i+1end while if i =0 return “inconsistent”else return instantiated values of {v1,v2,,vn}end procedure28procedure SELECTVALUE-FORWARD-CHECKINGwhile Di’ is not empty select an arbitrary element a  Di’ and remove a from Di’ empty_domain := false for all k, i and vi = a then remove b from Dk’ end for if Dk’ is empty then empty_domain := true end for if empty_domain then Reset each Dk’, i conflicts with all values of xi+1.Whenever backjumping discovers a dead-end, it should jump as far back as possible without skipping potential solutions. The jump should be safe and maximal.34Definition 5.1 (leaf dead-end). Given a variable ordering d = (v1,,vn), let be a tuple that is consistent. If is in conflict with xi+1 it is called leaf dead-end.Definition 5.2 (Safe jump). Let is a leaf dead-end state. We say that jumping to xj, where j  i, is safe if the partial instantiation can not extend to a solution.Definition 5.3 (culprit variable). Let is a leaf dead-end state. The culprit index relative to this dead-end state is defined by b = min{ j  i | conflicts with xi+1 }We define the culprit variable of the dead-end state to be xb.35procedure GASCHNIG’S-BACKJUMPINGi := 1Di’ := Dilatesti := 0 %initialize pointer to lastestwhile 1  i  n instantiate vi := SELECTVALUE-GBJ if vi is null then i := lastesti % backjump else i := i+1 Di’ := Di latesti := 0end while if i =0 return “inconsistent”else return instantiated values of {v1,v2,,vn}end procedure36procedure SELECTVALUE-GBJwhile Di’ is not empty select an arbitrary element a  Di’ and remove a from Di’ consistent := true for k = 1 to i-1 and while consistent if k> latesti then latesti := k % latesti : the latest variable checked for consistency if value a for vi is not consistent with vk then consistent := false end for if consistent then return a end while return nullend procedureNote: The subprocedure SELECTVALUE-GBJ identifies and records the culprit variable.37PARTIAL CONSTRAINT SATISFACTION Partial constraint satisfaction involves finding values for set of the variables that satisfy a subset of constraints. We are willing to “weaken” some of the constraint to permit acceptable values combinations. Partial constraint satisfaction problems arise in several contexts: The problem is overconstrained and admits of no complete solution. The problem is too difficult to solve completely but we are willing to accept a “good enough” solution. We are seeking the best solution obtainable within fixed resource bounds. Real time demands require an “anytime algorithm” which can bring out some partial solution almost immediately.38Definition A partial constraint satisfaction problem PCSP is a triple(V,C, ), where W is finite set of variables each associated with a finite domain, C is a set of constraints and  is total function :C   ,i.e.,  maps constraints to weights. The weigh of a constraint expresses its importance. Thus, one can describe hard constraints, which must be satisfied, as well as soft constraints, which should be satisfied. A hard constraint is given an infinite weight. A solution of the PCSP is an assignment of variables in V to their domain, such that (1) the number of all violated constraints c C is minimized or (2) the total weight of all violated constraints c C is minimized.Since we try to seek a solution that satisfies as many constraints as possible, this kind of PCSP is also called maximal constraint satisfaction problem. The solution which satisfies as many as constraint as possible is called a maximal solution.39ExampleA robot has a minimal wardrobe: sneakers or Cordovans for footwear, a white and a green shirt and three pairs of slacks: denims, blue and gray.Constraints: sneakers only go with the denim slacks; Cordovans only go with the gray slacks and the white shirtthe white shirt will go with either denim or blue slacks.the green shirt only goes with the gray slacks.Variables: There are three variables in this example (shoe, shirt and slacks)40Example: Robot clothing problemSHOESSHIRTSLACKS{(Cordovan, white)}{(Cordovans, gray), (sneakers, denims)}{(green, gray),(white, denims), (white, blue)}(Cordovan, sneakers}{green, white}{denims, blue, gray}41Branch and bound algorithm Assume that all constraints are binary constraints.Branch&Bound (BB) operates in a similar fashion to backtracking. BB basically keeps track of the best solution found so far and abandon a branch of search when it becomes clear that it cannot lead to a better solution. A version of backtracking that searches for all solutions, rather than the first solution, the most naturally compares with the BB to find the maximal solution.BB for solving PCSP uses as an evaluation function a count of the number of violated constraints, or inconsistencies.During backtracking, at any partial solution, Distance measures the number of constraints violated by the chosen values. 42The algorithm has the necessary bound N and the sufficient bound S on an acceptable distance that can be set initially based on a priori knowledge. If there are no such priori bounds, S is initially 0 and N “infinity”.Parameters:Search-path: the current search path.Distance: the number of constraints violated by the chosen values on the current search path.Variables: a list of the variables not assigned values in the current search path.Values: a list of the remaining values in the domain of the first variable in Variables.In the P-BB algorithm, N, S and Best-solution are global variables.43Search treeCordovans d = 0Sneakers d = 0 denims d =1 blue X 6 cc gray d =0 denims d =0blue X 14 ccgray X15 ccgreend = 3N = 33 ccwhited = 1N = 1 5 ccgreen X10 ccwhite X10 ccgreen X12 ccwhite X13 cc44procedure P-BB(Search-path, Distance, Vars, Values)begin if Vars =  then /*all variables have been instantiated */ begin Best-solution  Search-path; N  Distance; if N  S then return ‘finished’ else return ‘keep-searching’ /* backtrack */ end else if Values =  then return ‘keep-searching’ /* backtrack */ else begin {try to extend Search-path } Current-value  head(Values); v  head(Vars); /* v is current variable */ assign Current-value to v; New-distance  Distance; for all constraints c in C(v) do begin if checkBC(v, c) = ‘inconsistent’ then New-distance  New-distance + 1. if New-distance  N then exitfor end; 45if New-distance = 6*Z+5 boolean: e.g. A = not( B or C) membership: Color.[blue,white, red]The introduction of the constraint concept brings two advantages: (1) it allows to describe problems in a more natural way, and (2) it allows to benefit from efficient specific algorithms developed in different areas like Artificial Intelligence and Operations Research and Mathematics.53CONSTRAINT PROGRAMMING (cont.)Constraint programming is the study of computational systems based on constraints. The idea of constraint programming is to solve problems by stating constraints about the problem area and, consequently, finding solution satisfying all the constraints.As for the expressiveness of the language, Constraint Programming provides the user to manipulate directly:computational domains much closer to the user’s domain (e.g. natural numbers, rational terms, boolean formulas)different types of numerical and symbolic constraint (e.g. equality, disequality, inequalities, functional)As for the efficiency, Constraint Programming systems use more mathematical techniques, namely constraint solving techniques.54Constraint handling techniquesThe most important constraint handling techniques used in the current Constraint Programming systems are coming:From AI: constraint satisfaction, theorem proving.From OR: Linear programming, Integer Programming, Branch and Bound.From Mathematics: Equation solving (Newton method), decision procedures for polynomials.Compared to the more classical methods, Constraint Programming offers: short development time flexibility interactivity without sacrifying efficiency.55Constraint Programming Language OzThe Oz language was developed by German Research Center for Artificial Intelligence (DFKI). First version of Oz came in 1992.Oz is a concurrent constraint programming language, consists of several programming paradigms: functional programming, constraint programming, logic programming, andconcurrent object-oriented programming.DFKI Oz can be obtaind free from the following web site: