人工智能英文版課件：05 Constraint Satisfaction Prbolems

1、Chapter 5 Constraint Satisfaction Problems2OutlineConstraint Satisfaction ProblemsBacktracking Search for CSPsLocal Search for CSPThe Structure of Problems3Constraint Satisfaction ProblemsConstraint satisfaction problems (CSPs) is defined byA set of variables: X1, X2, , XnEach variable Xi has a none

2、mpty domain DiA set of constraints: C1, C2, , CmEach constraint Ci involves some subset of the variables Specifies the allowable combinations of values for that subset4Constraint Satisfaction ProblemsAssignmentA state of the problem is defined by an assignment of values to some or all of the variabl

3、esXi = vi, Xj = vj, An assignment that does not violate any constrains is called a consistent or legal assignmentA complete assignment is one in which every variable is mentionedA solution to a CSP is a complete assignment that satisfies all the constraintsSome CSP requires a solution that maximizes

4、 an objective function5Constraint Satisfaction ProblemsAssignmentA state of the problem is defined by an assignment of values to some or all of the variablesXi = vi, Xj = vj, An assignment that does not violate any constrains is called a consistent or legal assignmentA complete assignment is one in

5、which every variable is mentionedA solution to a CSP is a complete assignment that satisfies all the constraintsSome CSP requires a solution that maximizes an objective function6Constraint Satisfaction ProblemsColoring the map of AustraliaThere are 7 regions on the Australia mapColor regions in eith

6、er blue, red or green in such a way that no neighboring regions have the same colorVariables: regions on the mapWA, NT, Q, NSW, V, SA and TDomain is the set of blue, red, greenConstraints: Neighboring regions have distinct color7Constraint Satisfaction ProblemsConstraint graphVisualize constraints o

7、f a CSPNodes on the graph corresponding to variables of the problemArcs corresponding to constraints8Constraint Satisfaction Problems9Constraint Satisfaction ProblemsBenefits of treating a problem as CSPRepresentation of states in a CSP conforms to a standard patternA set of variables with assigned

8、valuesThe successor function and goal test can be written in a generic way that applies to all CSPsWe can develop effective, generic heuristics that require no additional, domain-specific expertiseThe structure of the constraint graph can be used to simplify the solution processSometimes give an exp

9、onential reduction10Constraint Satisfaction ProblemsIncremental formulation of CSPInitial state: the empty assignment All variables are unassignedSuccessor functions: a value can be assigned to any unassigned variableProvided that it does not conflict with previously assigned variablesGoal test: the

10、 current assignment is complete or notPath cost: a constant cost for every stepE.g. 111Constraint Satisfaction ProblemsEvery assignment must be a complete assignment, so it appears at depth n if there are n variablesDepth first search is popular for CSPComplete-state formulation could also be usedWe

11、 do not care the solution pathEvery state corresponding to a assignment of all n variablesMight or might not satisfy the constraintsLocal search works well in this formulation12Constraint Satisfaction ProblemsThe simplest kind of CSP involves variables that areDiscreteFinite domainsExample:Map-color

12、ing8-queensVariables are Q1 to Q8Domain 1,2,3,4,5,6,7,8, position of queen in a column13Constraint Satisfaction ProblemsIf the domain size of any variable in a CSP is d, then the number of possible complete assignments is O(dn) Exponential in the number of variablesBoolean CSPsA kind of inite domain

13、 CSPsVariables can be either true or falseSpecial case of NP-complete problemsIn the worst case, exponential time is needed to solve finite domain CSPsGeneral purpose CSP algorithms can solve problems orders of magnitude larger than those solvable with general purpose search algorithms14Constraint S

14、atisfaction ProblemsInfinite domainsDiscrete variables can also have infinite domainsSet of integersSet of stringsThis is impossible for us to enumerate all allowed combinations of valuesConstraint language Designed for infinite domainsExample: if Job1, which takes five days, must preceded job3Start

15、_job1 + 5 start_job315Constraint Satisfaction ProblemsLinear constraints on integer variablesThis is impossible to enumerate all assignments, so we need a special solution algorithmConstraints appear in linear formsStart_job1 + 5 start_job3It can be shown that no algorithm exists for solving general

16、 nonlinear constraints on integer variablesWe can reduce integer constraint to finite domain problems simply by bounding the values of all the variables16Constraint Satisfaction ProblemsContinuous domainsVery common in real worldWidely studied in the field of operations searchLinear programmingThe b

17、est-known category of continuous-domain CSPConstraints must be linear inequalities forming a convex regionCan be solved in time polynomial in the number of variables17Constraint Satisfaction ProblemsType of constraintsUnary constraintRestrict the value of a single variablex1 10Binary constraintRestr

18、ict values of two variablesX1 nThen, any assignment must be inconsistentThe constraint can not be satisfied45Backtracking Search for CSPs Example: Alldiff constraintSo, we could create a simple algorithm for it:Remove any variable with only one possible value in its domainDelete variables value from

19、 the domain of the remaining variablesRepeat as long as there are singleton variablesIf an empty domain is produced or there are more variables than domain values left, then an inconsistency has been detectedWe can use this method to detect the inconsistency in the partial assignments of Australia m

20、ap-coloring problemNodes are connected by Alldiff constraint46Backtracking Search for CSPs Example: Alldiff constraintSo, we could create a simple algorithm for it:Remove any variable with only one possible value in its domainDelete variables value from the domain of the remaining variablesRepeat as

21、 long as there are singleton variablesIf an empty domain is produced or there are more variables than domain values left, then an inconsistency has been detected47Backtracking Search for CSPs We can use this method to detect the inconsistency in the partial assignments of Australia map-coloring prob

22、lemFor the inconsistent partial assignment WA = r, NSW = rNodes are connected by Alldiff constraintAfter applying AC-3, the domain of each variable is reduced to g, b, i.e. 3 variables SA, NT, Q and 2 colorsIt violates the Alldiff constraintFrom these examples, we find that a simple consistency proc

23、edure for a higher-order constraint is sometimes more effective than applying arc consistency to an equivalent set of binary constraints48Backtracking Search for CSPs Resource constraintPerhaps the most important higher-order constraintSometimes called the at most constraintExample: let PA1, PA2, PA

24、3 and PA4 denote the number of personnel assigned to each of four tasksThe constraint that no more than 10 personnel are assigned in totalatmost(10, PA1, PA2, PA3, PA4)We could check the consistency by the sum of the min values of the current domainsWe could enforce consistency by deleting the max v

25、alue of any domain if it is not consistent with the min values of other domains2,3,4,5,6, 5+2+2+2 1049Backtracking Search for CSPs Large resource constraint problemFor large resource-limit problems with integer values, it is usually not possible to represent the domain of each variable as a large se

26、t of integers and then gradually reduce the sets by consistency checking methodsE.g. logistical problems involves thousands of people in hundreds of vehiclesInstead, we could represent the domain by its upper and lower boundsFlight271 0, 165 and Flight272 0, 385Additional constraint that two flight

27、must carry 420 people in totalFlight271 + Flight272 420, 420By propagating the bound constraint to their own domainsFlight271 35, 165 and Flight272 255, 38550Backtracking Search for CSPs Bound propagationA CSP is bounds-consistent if for every variable X and for both the lower and upper bound values

28、 of X, there exists some values of U that satisfies the constraint between X and Y for every variable Y51Backtracking Search for CSPs Chronological backtrackingThe most recent decision point is revisitedWhen a branch of search fails, back up to the preceding variable and try a different value for it

29、Example: Australia map-coloringWe fix the variable ordering: Q, NSW, V, T, SA, WA, NTThe current partial assignment is Q = r, NSW = g, V = b, T = rWhen we try the next one: SA, every value violates constraintBack up to T and try a new colorRe-coloring T does not helpIt is isolated and have no constr

30、aint relationship with SA52Backtracking Search for CSPs Conflict setWe may go all the way back to one of the set of variables that caused the failureThe conflict set for SA is Q, NSW,VConflict set for variable X is the set of previously assigned variables that are connected to X by constraints53Back

31、tracking Search for CSPs BackjumpingBacktracks to the most recent variables in the conflict setIn our example, we should backjump to V and try a new value for VWe could modify the backtracking-search algorithm by accumulating a conflict set while checking for a legal valueIf no legal value is found,

32、 returns to the most recent element of the conflict set along with the failure indicatorForward checking can provide the conflict set directlyWhenever it deletes a value from Ys domain for Xs assignment, add X to Ys conflict setEvery time that the last value is deleted from Ys domain, the variables

33、in the conflict set of Y are added to the conflict set of XWhen we get to Y, we know where to backtrack if needed54Backtracking Search for CSPs BackjumpingBackjump only occurs when every value in a domain is in conflict with current assignmentHowever, forward search will prevent it from occurringIt

34、can be shown that every branch pruned by backtracking is also pruned by forward checkingSo, backjumping is redundant in a forward checking searchAlso redundant when a stronger consistency checking is adopted55Backtracking Search for CSPs BackjumpingAlthough it may be redundant when other methods als

35、o find the same inconsistent partial assignments, it is still worth to exploreBackjumping find failure when a variables domain is emptyIn many cases, a branch is doomed long before this occursReturn to the Australia map-coloring exampleThe current partial assignment: WA = r, NSW = rWe will still fai

36、l to find a valid assignment after trying out all 3 possibility for TNo valid assignment is available for NT,Q, V and SAWhere to backtrack?56Backtracking Search for CSPs Conflict-directed backjumpingBackjump does not work in this case because NT does have values consistent with the preceding assigne

37、d variablesNT does not have a complete conflict set of preceding variablesThe four variables NT, Q, V and SA taken together failed Those preceding variables directly conflict with the fourThis leads to a deeper notion of the conflict set for a variable such as NT together with any subsequent variabl

38、es to have no consistent solutionIn our example, they are WA and NSWSo, we should jump back to NSW57Backtracking Search for CSPs Algorithm of conflict-directed backjumpingThe terminal failure of a branch of the search always occurs because a variables domain becomes emptyThis variable has a standard

39、 conflict setSA fails and its conflict set is WA, NT, QWe backjump to Q and Q absorbs the conflict set from SA, i.e. WA, NTThen, the new conflict set is WA, NT, NSWTherefore, no solution from Q onwards given the preceding assignment to WA, NT, NSWNT into its own direct conflict set WA, giving WA, NS

40、WSo, the algorithm correctly backjump to NSW!58Backtracking Search for CSPs Algorithm of conflict-directed backjumpingLet xj be the current variable and conf(xj) be its conflict setIf every possible value for fails xj, backjump to the most recent variable xi in the conf(xj) Set conf(xi) conf(xi) U c

41、onf(xj) - xiThe conflict-directed backjumping takes us back to the right point in the search treeBut it does not prevent us to make the same mistake in another branch againand againConstraint learning modifies the CSP by adding new constraints that is induced from these conflicts59Local Search for C

42、SPsLocal search algorithms are very effective in solving CSPsComplete-state formulationThe initial state assigns a value to every variableThe successor function usually works by changing the value of one variable at a timeExample of 8-queensThe initial state may have 8 queens randomly located in her

43、 own columnThe successor function picks up a queen and moving it elsewhere in her columnOr, the successor function swaps rows of two queens60Local Search for CSPs61Local Search for CSPs62Local Search for CSPsMin-conflicts heuristicObviously, we want to minimize conflicts when choosing a new value fo

44、r a variableVery effective for many CSPsEspecially when a reasonable initial state is givenIf we dont count the time for producing the initial state, the runtime is roughly independent of problem size!It solves million-queens problem in an average of 50 steps63Local Search for CSPsMin-conflicts heur

45、isticN-queens problems is easy for local search because solutions are densely distributed throughout the state spaceIt also helps to reduce the time for schedule observations for the Hubble Space TelescopeIt reduce the time taken to schedule a week of observations from 3 weeks to around 10 minutes!6

46、4Local Search for CSPsLocal search can be used in an online setting when the problem changesParticularly important in scheduling problemsSudden weather changes around Guangzhou airport requires contingency for changing flight schedulesLocal search starts from current schedule helps to minimize the n

47、umber of changes required Backtracking search with a new set of constraints usually requires much more time and might find a solution with many changes from the current schedule65The Structure of ProblemsStructure of problemsRepresented by the constraint graphIt helps to find solutions quicklyMost o

48、f the approaches are very general and are applicable to other problems besides CSPsThe only way we can hope to deal with the real world is to decompose it into many sub-problemsExample: Australia map-coloringT is not connected to the mainlandThe coloring of T and that of the mainland are independent

49、 sub-problemsAny solution for the mainland combined with any solution for T yields a solution for the whole map66The Structure of ProblemsConnected componentsIndependence can be ascertained simply by looking for connected components of the constraint graphEach component corresponds to a sub-problem

50、CSPiIf assignment Si is a solution of CSPi, then Ui Si is a solution of Ui CSPiWhy is it important?67The Structure of ProblemsConnected componentsWhy is it important?Suppose each CSPi has c variables from the total of n variablesThere are n/c sub-problems Each sub-problem takes dc works to solveThe

51、total work required is O(dcn/c)Without decomposition, the required work is O(dn), exponential to n68The Structure of ProblemsIn most cases, sub-problems are connectedThe simplest case is when the constraint graph forms a treeAny two variables are connected by at most one pathAny tree-structured CSP

52、can be solved in time linear in the number of variables69The Structure of ProblemsAlgorithm for solving tree-structured CSPChoose any variable as the root of the treeOrder the variables from the root to the leaves in such a way that every nodes parent in the tree precedes it in the orderingLabel the

53、 variables X1, X2, , Xn in orderFor j from n down to 2, apply arc consistency to the arc (Xi, Xj), where Xi is the parent of Xj removing values from DOMAINXi if neededFor j from 1 to n, assign any value for Xj consistent with the value assigned for Xi70The Structure of ProblemsAlgorithm for solving

54、tree-structured CSPAfter step 2, the CSP is directionally arc-consistentSo, no backtracking is needed for step 3By applying the arc consistency checks in reverse order in step 2, the algorithm ensures that any deleted value can not endanger the consistency of arcs that have been processed alreadyEac

55、h node has only one parent node, but may have many child nodesThe time complexity is O(nd2)71The Structure of ProblemsReducing a constraint graph to a treeBy collapsing nodes togetherTree decomposition laterBy removing nodesAssign values to some variables so that the remaining variables form a treeE

56、xample: Australia map-coloringBy assigning value to SA, the graph would become a treeSA is removed from the graph after its value is fixedThis value is deleted from the domains of the other variables that will cause inconsistency with SA72The Structure of Problems73The Structure of ProblemsExample:

57、Australia map-coloringAny solution for the CSP after SA and its constraints are removed will be consistent with the value chosen for SAIf the value chosen for SA is incorrect, we may need to try it againThis occurs when the CSP is more complicated74The Structure of ProblemsAlgorithm of reducing CSP

58、to tree-structureChoose a subset S from VARIABLEcsp such that the constraint graph becomes a tree after removal of SS is called a cycle cutsetFor each possible assignment to the variables in S that satisfies all constraints on SRemove from the domains of the remaining variables any values that are i

59、nconsistent with the assignment for SIf the remaining CSP has a solution, return it together with the assignment of S75The Structure of ProblemsSize of cycle cutsetIf the cycle cutset has size c, then the total runtime is O(dc(n - c)d2)If the graph is nearly a tree, thenThe c will be smallThe saving

60、 over straight backtracking will be hugeIn the worst case, c can be as large as n 2Finding the smallest cycle cutset is NP-hard problemSome efficient approximation algorithms are known Cutset conditioning76The Structure of ProblemsSize of cycle cutsetIf the cycle cutset has size c, then the total ru