ConstraintReasoning

《ConstraintReasoning》由会员分享，可在线阅读，更多相关《ConstraintReasoning（28页珍藏版）》请在装配图网上搜索。

1、Constraint Reasoning Florida Institute of TechnologyComputer Science1Chapter 1)IntroductionConstraint Satisfaction Problem(CSP)is an important sub-field of the artificial intelligence.CSP appears in many areas,for instance in computer vision,in resource allocation,in scheduling and in temporal reaso

2、ning.What is a constraint satisfaction problemA CSP is a problem composed of a finite set of variables,each of which is associated with a finite domain,and a set of constraints.The task is to assign a value to each variable satisfying all the constraints.For example the“N-queens problem”:the problem

3、 is to place eight queens on an 8x8 chessboard satisfying the constraint that no two queens should be on the same row,column or diagonal.2Example 2-car sequencing problemIn a car production scenario,cars are placed on conveyor belts which move through different work areas.A production line is normal

4、ly required to produce cars of different models.The number of cars required for each model is called the production requirement.Each work area is constrained by its resource constraint or Capacity constraint.variable-the car model of one position in the conveyor belt(I.e.if there are n cars to be sc

5、heduled,the problem consists of n variables).domain-the set of car models,for example from model A to D.The task-to assign a value(a car model)to each variable(a position in the conveyor belt),satisfying both the production requirements and capacity constraints.34Definition of domain and labelsDefin

6、ition 1-1:The domain of a variable is a set of all possible values that can be assigned to the variable.If x is a variable,then we use Dx to denote the domain of it.Definition 1-2:A label is a variable-value pair that represents the assignment of the value to the variable.We use to denote the label

7、of assigning the value v to the variable x.is only meaningful if v is in the domain of x(I.e.v Dx).Definition 1-3:A compound label is the simultaneous assignment of values to a(possibly empty)set of variables.We use()to denote the compound label of assigning v1,v2,vn to x1,x2,xn respectively.Definit

8、ion 1-4:A k-compound label is a compound label which assigns k values to k variables simultaneously.5Definition of domain and labelsDefinition 1-5:If m and n are integers such that m=n,then a projection of an n-compound label N to an m-compound label M,written as projection(N,M),(read as:M is a proj

9、ection of N)if the labels in M all appear in N.Definition 1-6:The variables of a compound label is the set of all variables which appear in that compound label.6Definition of constraintsDefinition 1-7:A constraint on a set of variables is conceptually a set of compound labels for the subject variabl

10、es.For convenience,we use Cs to denote the constraint on the set of variables S.Definition 1-8:The variables of a constraint is the variables of the members of the constraint.Definition 1-9:If m and n are integers such that m=n,then an m-constraint M is subsumed-by an n-constraint N(written as subsu

11、med-by(M,N)if for all elements c in M there exists an element d in N such that c is a projection of d.7Definitions of satisfiabilityDefinition 1-10a:If the variables of the compound label x are the same as those variables of the elements of the compound labels in constraint C,then x satisfies C if a

12、nd only if X is an element of C.Definition 1-10b:satisfies(,Cx)()CxDefinition 1-11:Given a compound label L and a constraint C such that the variables of C are a subset of the variables of L,the compound label L satisfies constraint C if and only if the projection of L onto the variables of C is an

13、element of C.8Constraint satisfaction problemDefinition 1-12:A constraint satisfaction problem is a triple:(Z,D,C)where,Z=a finite set of variables x1,x2,xn;D=a function which maps every variable in Z to a set of objects of arbitrary type:D:Zfinite set of objects(of any type)We shall take Dxi as the

14、 set of objects mapped from xi by D.We call these objects possible values of xi and the set Dxi the domain of xi;C=a finite(possibly empty)set of constraints on an arbitrary subset of variables in Z.In other words,C is a set of sets of compound lables.We use csp(P)to denote that P is a constraint sa

15、tisfaction problem.9Task in a CSPDefinition 1-13:A solution tuple of a CSP is a compound label for all those variables which satisfy all the constraints.Depending on the requirements of an application,CSPs can be classified into the following categories:(1)CSPs in which one has to find any solution

16、tuple(2)CSPs in which one has to find all solution tuples.(3)CSPs in which one has to find optimal solutions,where optimality is defined according to some domain knowledge.Optimal or near optimal solutions are often required in scheduling.10 Constraint representation and binary CSPsDefinition 1-14:A

17、 binary CSP,or binary constraint problem,is a CSP with unary and binary constraints only.A CSP with constraints not limited to unary and binary will be referred to as a general CSP.Definition 1-15:A graph is a tuple(V,U)where V is a set of nodes and U(VxV)is a set of arcs.A node can be an object of

18、any type and an arc is a pair of nodes.For convenience,we use graph(G)to denote that G is a graph.An undirected graph is a tuple(V,E)where V is a set of nodes and E is a set of edges,each of which being a collection of exactly two elements in V.Definition 1-16:For all graphs(V,E),node x is adjacent

19、to node y if and only if(x,y)is in E.11Graph-related conceptsDefinition 1-17:A hypergraph is a tuple(V,E)where V is a set of nodes and E is a set of hyperedges,each of which is a set of nodes.For convenience we use hypergraph(v,E)to denote that(V,E)is a hypergraph,hyperedges(F,V)to denote that F is

20、a set of hyperedges for the nodes V(I.e.F is a set of set of nodes in V),and nodes_of(e)to denote the nodes involved in the hyperedge e.Definition 1-18:The constraint hypergraph of a CSP(Z,D,C)is a hypergraph in which each node represents a variable in Z,and each hyperedge represents a constraint in

21、 C.We denote the constraint hypergraph of a CSP P by H(P).If P is a binary CSP and we exclude hyperedges on single nodes,then H(P)is a graph.We denote the constraint graph of a CSP by G(P).12Graph-related conceptsDefinition 1-20:A path of length n is a path which goes through n+1(not necessarily dis

22、tinct)nodes.Definition 1-21:A node y is accessible from another node x if there exists a path from x to y.Definition 1-22:A graph is connected if there exists a path between every pair of nodes.Definition 1-23:A loop in a graph is an edge or an arc which goes from a node to itself,I.e.a loop is(x,x)

23、,where x is a node.Definition 1-24:A network is a graph which is connected and without loops.Definition 1-25:A cycle is a path on which end-points coincide.13Graph-related conceptsDefinition 1-26:An acyclic graph is a graph which has no cycles.Definition 1-27:A tree is a connected acyclic graphDefin

24、ition 1-28:A binary relation()on a set S is called an ordering of S when it is irreflexive,asymmetric and transitive.Definition 1-29:A set S is totally ordered if every two elements in S are ordered.Such an ordering is called a total ordering of the elements in S.14The N-queens problemThis N-queen p

25、roblem has very specific features:firstly,it is a binary constraints,secondly,every variable is constrained by every other variable,More importantly,constraint get looser as N grows larger.Such features may not be shared by many other CSPs;therefore,benchmarks on different algorithms produced using

26、this problem must be interpreted with caution.Problem formalizationThe set of variables:Z=Q1,Q2,Q8Domain:DQ1=DQ2=DQ8=1,2,3,4,5,6,7,8Constraint(1):i,j:if Qi=a and Qj=b,then abConstraint(2):i,j,if Qi=a and Qj=b,then i-j a-b,and i-j b-a.15The N-queens problemAlternative formalization of the N-queens pr

27、oblemThe set of variables:Z=Q1,Q2,Q8Domain:DQ1=DQ2=DQ8=0,1,2,3,4,63Constraints:Ri is(Ni div 8)+1,Ci is(Ni mod 8)+1Rj is(nj div 8)+1,Cj is(Nj mod 8)+1*Row=(number div 8)+1*Column=(number mod 8)+1Ri RjCi CjRi-Rj Ci-CjRi-Rj Cj-CiFormalization can be a hidden constraint.The first one allows 88 combinati

28、ons,the second one 648.A problem can be formulated as a CSP in different ways.16The graph coloring problemAs a map can be represented by a graph where each node represents an area in the map,and every pair of nodes which represent two adjacent areas in the map is connected by an edge Figure 1.5.Prob

29、lem formalizationThe set of variables:Z=w,x,y,zDomain:Dw=Dx=Dy=Dz=r,g,bConstraints:C=Cw,x,Cw,y,Cx,y,Cx,z,Cy,zCx1,x2,xn=(Vx1Vx2 Vxn)1718The scene labeling problemThe task is to label all the edges in Figure 1.7,satisfying all the constraints.The set of variables:Z=A,B,C,D,E,F,G,h,IOne way is to use o

30、ne variable to represent the value of a line in the scene.Domain:D=+,-,192021Temporal reasoningEvents are all temporally related to each other.Depending on the structure of time one uses,different types of temporal relations apply.In planning and scheduling,one has to determine the temporal relation

31、ship between events.One approach is to pick up one temporal relation per pair of events in each step,and backtrack when the hypothetical situation has been proved to be unsatisiable.The other approach is to reason with all disjunctive temporal relations simultaneously.2223Resource allocationResource

32、 allocation,especially when time and shared resources are involved,is basically a CSP.Each variable in the CSP represents one shared resource requirement.variable X may represent the machine requirement of a job(each variable in the CSP represents one shared resource requirement).The domain may be t

33、he set of machines available in the workshop which have the capacity to do the job.The allocation of resources is normally constrained in many ways.24Graph matchingGiven two graphs G1 and G2,the problem is to check whether G2 has a subgraph which matches G1.Graph(V1,E1)contains graph(V2,E2)if:(1)eve

34、ry node in V2 can be mapped to a distinct node in V1;and(2)for all x1,y1 in V1 and x2,y2 in V2,if x2 and y2 are mapped to x1 and y1,respectively,then whenever(x2,y2)is an edge in E2,then(x1,y1)is an edge in E1.2526Other applicationThe grammar of the language restricts the roles that a string of word

35、s can take simultaneously.Database query optimization is an important database research area in which CSP solving techniques can be applied.CSP techniques have also been applied to parameter setting for greenhouses in agricultural applications,and demonstrated to be successful.27Constraint programmi

36、ngCLP one of the main objectives of developing CLP is to define a class of logic programming languages with well defined semantics under a particular equational theory.Prolog III It was developed with similar goals as CLP,but with refined manipulation on trees(including infinite trees),lists and Boo

37、lean variables.CHIP It is a logic programming language for handling symbolic,Boolean as well as numerical variables.The basic search strategy used in CHIP is called forward checking(FC).It is used together with a heuristic called the fail first principle(FFP).Its success has led to the of Charme and PECOS,which are mainly built to handle symbolic variables.Charme It uses the syntax of C,and one of its merits is that it can easily be integrated into the users of the C programs.PECOS It uses LISP syntax.28