高级人工智能之约束推理.pptx

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,高级人工智能,第三章,约束推理,史忠植,中国科学院计算技术所,10/2/,1,史忠植 高级人工智能,高级人工智能之约束推理,第1页,第三章,约束推理,3.1 概述,3.2 回溯法,3.3 约束传输,3.4 回跳法,3.5 约束推理系统COPS,3.6,ILOG SOLVER,10/2/,2,史忠植 高级人工智能,高级人工智能之约束推理,第2页,3.1,概述,最优化问题,经济学所推崇帕累托最优:,几个人拎着水桶在一个水龙头前面排队打水，水,桶有大有小。他们怎样排队，才能使得总排队,时间最短。这是一个寻求“最优化”题目，目标,是节约总排队时间，到达最优。,10/2/,3,史忠植 高级人工智能,高级人工智能之约束推理,第3页,3.1,概述,优化问题,运筹学,遗传算法,神经网络,约束推理,10/2/,4,史忠植 高级人工智能,高级人工智能之约束推理,第4页,运筹学工作步骤,1）提出和形成问题，,2）建立模型，,3）求解，,4）解检验，,5）解控制，,6）解实施。,10/2/,5,史忠植 高级人工智能,高级人工智能之约束推理,第5页,线性规划问题,例1(广告方式选择)中华家电企业推销一个新型洗衣机,相关数据见下表.销售部第一月广告预算为0元,要求最少有8电视商业节目,15家报纸广告/电视广告费不得超出1元,电台广播最少隔日有一次.现问该企业销售部应该采取怎样广告宣传计划,才能取得最好效果?,10/2/,6,史忠植 高级人工智能,高级人工智能之约束推理,第6页,表1,广告方式,广告费用(元/次),可用最高次数/月,期望宣传效果/单位,电视台a(白天,1 分钟),500,16,50,电视台b(晚上,30钞),1000,10,80,每日晨报/(半版),100,24,30,星期日报/(半版),300,4,40,广播电台/(1分钟),80,25,15,10/2/,7,史忠植 高级人工智能,高级人工智能之约束推理,第7页,10/2/,8,史忠植 高级人工智能,高级人工智能之约束推理,第8页,10/2/,9,史忠植 高级人工智能,高级人工智能之约束推理,第9页,10/2/,10,史忠植 高级人工智能,高级人工智能之约束推理,第10页,求解-单纯形法,将所给问题化为标准形,找出一个初始可行基,建立初始单纯形表,检验全部检验数(若全为非负,则已得到最优解,计算停顿.不然继续下一步),考查是否无解(若是,计算停顿,不然继续下一步),确定入基变量,出基变量,对初始单纯形表进行单纯形变换,10/2/,11,史忠植 高级人工智能,高级人工智能之约束推理,第11页,3.1,概述,一个约束满足问题(Constraint Satisfaction Problem,简称CSP)包含一组变量与一组变量间约束。,变量表示领域参数，每个变量都有一个固定值域。,一个变量值域可能是有限，比如一个布尔变量值,域包含两个值；也可能是离散无限，如整数域；也可,能是连续，如实数域。,x1,x2,xn,D1,D2,Dn,.,4,5,6,7,red,green,blue,10/2/,12,史忠植 高级人工智能,高级人工智能之约束推理,第12页,3.1,概述,约束可用于描述领域对象性质、相互关系、任务,要求、目标等。约束 满足问题 目标就是找到全部,变量一个（或多个）赋值，使全部约束都得到满足。,一元谓词。,序关系语言，只包含偏序关系或实变量上大小关系。,形如“x-y c”方程。,单位系数线性方程与不等式，即全部系数为,-1,0,1。,任意系数线性方程与不等式。,约束布尔组合。,代数与三角方程。,10/2/,13,史忠植 高级人工智能,高级人工智能之约束推理,第13页,3.1,概述,约束表示易于了解、编码及有效实现，它含有以下优点:,约束表示允许以说明性方式来表示领域知识，表示,能力较强，应用程序只需指定问题目标条件及数据间,相互关系。因而含有逻辑表示类似性质。,约束表示允许变量域包含任意多个值，而不像命题,只取真假二值。所以它保留了问题一些结构信息，如,变量域大小、变量间相关性等，从而为问题求解提供,启发式信息。,易于并行实现。因为约束网络上信息传输能够认为是,同时。,适合于递增型系统。约束能够递增式地加入到约束网络。,易于与领域相关问题求解模型相衔接。各种数学规划技,术，方程求解技术等,都能够自然地嵌入约束系统。,10/2/,14,史忠植 高级人工智能,高级人工智能之约束推理,第14页,3.1,约束推理,约束搜索,约束搜索主要研究有限域上约束满足。对有限域而言，,约束满足问题普通情况下,是 一个 NP 问题。,约束语言,10/2/,15,史忠植 高级人工智能,高级人工智能之约束推理,第15页,3.1,约束搜索,回溯法。,约束传输。,智能回溯与真值维护。,可变次序例示。,局部修正法。,10/2/,16,史忠植 高级人工智能,高级人工智能之约束推理,第16页,约束语言,CONSTRAINTS,CHIP,COPS,ILOG,10/2/,17,史忠植 高级人工智能,高级人工智能之约束推理,第17页,CONSTRAINTS约束语言,CONSTRAINTS是一个面向电路描述约束表示语言。,作为一个约束表示语言，它使用了符号处理技术来求解数学方程。,在CONSTRAITS中，物理部件功效及器件结构都用约束表示。,这些约束普通是线性方程与不等式,也包含条件表示式。约束变量,普通是表示物理量实变量。也有一些取离散值变量。如开关状,态、三极管工作状态等。系统采取表示式推理与值推理。并实现,相关制导回溯。,10/2/,18,史忠植 高级人工智能,高级人工智能之约束推理,第18页,CONSTRAINTS约束语言,CONSTRAINTS 一个优点是在类型层次中表示约束，用约束,来表示物理对象功效与结构。其缺点是该语言缺乏类似于面向,对象语言中方法那样成份，不能定义特定于某个类概念。,同时，约束传输方法比较单一，既缺乏实域上区间传输机制，,也缺乏有限域上 域传输机制。,10/2/,19,史忠植 高级人工智能,高级人工智能之约束推理,第19页,约束逻辑程序设计语言CHIP,CHIP(Constraint handling in Prolog)就是这么较有影响,一个约束逻辑程序设计语言，其目标是简便、灵活而有效地处理,一大类组合问题。它经过提供几个新计算域而增强逻辑程序设,计能力；有限域、布尔项及有理项，对于每个计算域，都提供,有效约束求解技术，即有限域上一致性技术，布尔域布尔,合一技术及有理数域上单纯型法。除此以外，CHIP还包含一个,普通延迟计算机制。,CHIP 主要应用于两个领域:运筹学与硬件设计。,CHIP 缺乏类型机制，而这种机制对于表示领域概念是极其重,要。,10/2/,20,史忠植 高级人工智能,高级人工智能之约束推理,第20页,面向对象约束语言COPS,COPS系统利用面向对象技术，将说明性约束表示与类型层次,结合起来。在形式上吸收了常规语言，主要是面向对象程序设,计语言基本形式。内部求解时采取约束推理机制，使说明性约,束表示式与类型层次相结合，实现知识结构化封装，充分发挥,二者优点，力图实现一个含有较强表示能力和较高求解效率,约束满足系统。,10/2/,21,史忠植 高级人工智能,高级人工智能之约束推理,第21页,面向对象约束语言COPS,COPS设计考虑了软件工程应用要求，尽可能将一个不确定问,题确定化：它允许条件语句与循环语句，而不是单,纯以递归形式来实现迭代计算；经过类方法重栽实现同一,约束不一样实现，提升了程序执行效率。COPS系统同时是一个,渐增式开放系统，用户能经过类型层次定义，实现新数据类,型和新约束关系。约束语言COPS含有许多人工智能程序设计语,言特点，如约束传输、面向目标和数据驱动问题求解、有限,步回溯、对象分层中继承等。,10/2/,22,史忠植 高级人工智能,高级人工智能之约束推理,第22页,在实际应用中，算法表现形式千变万化，不过算法情况也和数据结构类似，许多算法设计思想含有相同之处，我们能够对它们分类进行学习和研究。,惯用算法大致有以下一些：,贪心法,分治法：如二分法检索,回溯法,动态规划法,局部搜索法,分支限界法,10/2/,23,史忠植 高级人工智能,高级人工智能之约束推理,第23页,算法分析,评价一个程序优劣主要依据是看这个程序执行需要占用多少机器资源。人们最关心就是程序所用算法运行时所要花费,时间代价,和程序中使用数据结构占有,空间代价,。,算法空间代价,(或称,空间复杂性,)：当被处理问题规模(以某种单位计算)由1增至,n,时，解该问题算法所需占用空间也以某种单位由,f,(1)增至,f,(,n,)，这时我们称该算法空间代价是,f,(,n,)。,算法时间代价,(或称,时间复杂性,)：当问题规模以某种单位由1增至,n,时，对应算法所花费时间也以某种单位由,g,(1)增至,g,(,n,)，这时我们称算法时间代价是,g,(,n,)。,10/2/,24,史忠植 高级人工智能,高级人工智能之约束推理,第24页,穷尽搜索方法,穷尽搜索方法,即产生全部可能树，然后依据评价标准选择一棵最优树。,Exhaustive-Search-Top(P)where P is a CSP of the,form(V,D,C),1.f:=the null assignment,2.return Exhaustive-Search(f,P),10/2/,25,史忠植 高级人工智能,高级人工智能之约束推理,第25页,穷尽搜索方法,Exhaustive-Search(f,P),1.if f is a total assignment of the variables in P,2.if f satisfies the constraints in P,3.answer:=f,4.else,5.answer:=Unsat,6.else,7.v:=some variable in P that is not yet assigned a,value by f,8.answer:=Unsat,9.for each value while answer=Unsat,10.f(v):=,11.answer:=Exhaustive-Search(f,P),12.return answer,10/2/,26,史忠植 高级人工智能,高级人工智能之约束推理,第26页,贪心法,贪心法把结构可行解工作分阶段来完成。在各个阶段，选择那些在一些意义下是局部最优方案，期望各阶段局部最优选择带来整体最优。,例：,Dijkstra最短路径算法、Kruskal求最小生成树算法、信号灯问题,10/2/,27,史忠植 高级人工智能,高级人工智能之约束推理,第27页,回溯算法,有些问题需要彻底搜索才能处理问题，然而，彻底搜索要以大量运算时间为代价，对于这种情况能够经过回溯法来去掉一些分支，从而大大降低搜索次数。,八皇后问题,迷宫问题,深度优先周游树或图,10/2/,28,史忠植 高级人工智能,高级人工智能之约束推理,第28页,回溯算法,Backtracking-Top(P),1 f:=the null assignment,2 return Backtracking(f,P),10/2/,29,史忠植 高级人工智能,高级人工智能之约束推理,第29页,回溯算法,Backtracking(f,P),1 if f is a total assignment of the variables in P,2 answer:=f,3 else,4 v:=some variable in P that is not yet assigned a value,by f,5 answer:=Unsat,6 for each value while answer=Umsat,7 f(v):=x,8 if f satisfies the constraints in P,9 answer:=Backtracking(f,P),10 return answer,10/2/,30,史忠植 高级人工智能,高级人工智能之约束推理,第30页,回溯算法,尽管回溯法好于生成测试法，但对于非平凡问题依然是低效。其原因在于搜索空间中不一样路径搜索重复相同失败子路径。一些研究者认为，造成这种重复原因是所谓局部不一致性。最简单情形是所谓结点不一致性。对一个变量vi一个一元约束。存在域中一个值vi不满足该约束。这么，每当vi取到 a 时就会出现,不一致性。,另一个重复情形 是所谓弧不一致性。,10/2/,31,史忠植 高级人工智能,高级人工智能之约束推理,第31页,3.3 约束传输,CONSTRAINT PROPAGATION,弧一致性,Arc consistency,10/2/,32,史忠植 高级人工智能,高级人工智能之约束推理,第32页,弧一致性,Arc consistency,假如对vi 当前域中全部值x，存在vj当前域中某值y使得 vi=x和vj=y是vi与vj之间约束所允许，则弧(vi,vj)是弧一致。,弧一致性概念是有向。即(vi,vj),是弧一致并不自动地意味着(vj,vi)是一致。,10/2/,33,史忠植 高级人工智能,高级人工智能之约束推理,第33页,3.3 CONSTRAINT PROPAGATION,All of the Mackworth algorithms make use of a Revise procedure.,Let Dv be the current domain of v,Let Dw be the current domain of w,Let P be the constraint predicate that holds between v and w,then Revise updates Dv as follows,:,10/2/,34,史忠植 高级人工智能,高级人工智能之约束推理,第34页,CONSTRAINT PROPAGATION,Mackworth 1977,AC-1,AC-2,AC-3,10/2/,35,史忠植 高级人工智能,高级人工智能之约束推理,第35页,约束传输修改算法,REVISE(Vi,Vj),1 DELETE,false;,2 for each x,Di do,3 if there is no such yj,Dj,4such that(x,yj)is consistent,5 then,6 delete x from Di;,7 DELETE,true;,8 endif,9 endfor,10 return DELETE;,11 end REVISE,10/2/,36,史忠植 高级人工智能,高级人工智能之约束推理,第36页,AC-1,1,Q,;,2 repeat,3 CHANGE,false;,4 for each(Vi,Vj),Q do,5 CHANGE,REVISE(Vi,Vj),CHANGE;,6 endfor;,7 until not(CHANGE);,8 end AC-1,10/2/,37,史忠植 高级人工智能,高级人工智能之约束推理,第37页,AC-3,1,Q,;,2 While Q not empty,3 Select and delete any arc(Vk,Vm)from Q;,4 If(REVISE(Vk,Vm),Then Q,(Vi,Vk)such that(Vi,Vk),arcs(G),i,k,im,;,6 endfor;,7 endwhile;,8 end AC-3,10/2/,38,史忠植 高级人工智能,高级人工智能之约束推理,第38页,Backjumping,Backjumping-Top(P),1 f:=the null assignment,2 :=Backjumping(f,P),3 return answer,10/2/,39,史忠植 高级人工智能,高级人工智能之约束推理,第39页,Backjumping,Backjumping(f,P),1 if f is a total assignment of the variables in P,2 answer:=,3 else,4 v:=some variable in P that is not yet assigned a value,by f,5 answer:=Unsat,6 conflict-set:=,7 for each value,8 f(v):=x,9 if f satisfies the constraints in P,10 :=Backjumping(f,P),10/2/,40,史忠植 高级人工智能,高级人工智能之约束推理,第40页,Backjumping,11 else,12 new-conflicts:=the set of variables in a,violated constraint,13 if answer,Unsat,14 return,15 else if v,new-conflicts,16 return,17 else,18 conflict-set:=conflict-set,(new-conflicts,v),19 return ,10/2/,41,史忠植 高级人工智能,高级人工智能之约束推理,第41页,COPS,Constraint:,predicate expression,P(t1,.,tn),where,P,is built in function,such as,sum,times,eq(equal),neq(not equal),ge(great than or equal to),gt(great than),also can be defined by users,10/2/,42,史忠植 高级人工智能,高级人工智能之约束推理,第42页,COPS,Conditional constraint,condition1:constraint1;,.,.,conditionn:constraintn,where,condition1,.,conditionn are boolean expressions.,constraint1,.constraintn are constraints or contraints table.,10/2/,43,史忠植 高级人工智能,高级人工智能之约束推理,第43页,COPS,RULE,Rule is used to define new function,method,predicate,or add new constraint into object.,RULE class:predicate(varibles)(boolean expression),constraint_1;,constraint_n;,CASE,boolean expression_1:constraint_1;,boolean expression_m:constraint_m;,10/2/,44,史忠植 高级人工智能,高级人工智能之约束推理,第44页,COPS,For example:,RULE multiple(INTEGER:*x,INTEGER:y,INTEGER:z)(neq(y,0),equal(x,divide(z,y);,z=x*y,10/2/,45,史忠植 高级人工智能,高级人工智能之约束推理,第45页,COPS,CLASS class_name:superclass_name,/attributes definition,date type:attribute_name;,.,/rule definition,rule_name;,.,/function definition,function_name;,.,/method definition,method_name;,.,10/2/,46,史忠植 高级人工智能,高级人工智能之约束推理,第46页,COPS,Implementation,Program written by COPS consists of classes and rules.COPS constraint programming language is a declarative language,providing classes,methods which are exist in object oriented language.It is similar with C+.COPS has the features:,constraint,object oriented,logic programming,production system,10/2/,47,史忠植 高级人工智能,高级人工智能之约束推理,第47页,COPS,COPS_Compiler,1 ,2 Call yacc to parse the program and,3 to generate internal structures.,4 Initializatiion,5 Create Cops Constant trueNode;,6 Allocate memories for global variables.,10/2/,48,史忠植 高级人工智能,高级人工智能之约束推理,第48页,COPS,7 Interprte the program with the internal structures.,8 Constraint networks are built up for Unsolved,9 constraints and variables.,10 while some constraints in the constraint networks are,triggered,11 inteprete the triggered constraints.,12 ,10/2/,49,史忠植 高级人工智能,高级人工智能之约束推理,第49页,COPS,Interpreter:,1 ,2 switch(constraint type),3 case Constant:,4 return Constant:,5 case global variable:,6 interprete global variable:,7 case local variable or argument:,8 interprete local variable or argument:,9 case object-attribute pair;,10 interprete object-attribute pair:,11 case function call:,10/2/,50,史忠植 高级人工智能,高级人工智能之约束推理,第50页,COPS,12 interprete function call:,13 case method call:,14 interprete method call:,15 case CASE expression:,16 interprete CASE expression:,17 .,18 default:,20 report error,21 ,10/2/,51,史忠植 高级人工智能,高级人工智能之约束推理,第51页,ILOG SOLVER,Combines object oriented programming with constraint logic programming,containing logic variables,incremental constraint satisfaction and backtracking.,variables:C+object,integer variable CtIntVar,floating variable CtFloatVar,boolean variable CtBoolVar,Memory Management,new:,delete:,10/2/,52,史忠植 高级人工智能,高级人工智能之约束推理,第52页,ILOG SOLVER,Constraints,CtTell(x=(y+z);,Basic constraints:=,+,-,*,/,subset,superset,union,intersection,member,boolean or,boolean and,boolean not,boolean xor,CtTell(x=0)|(y=0);,CtIfThen(x chooseValue();,CtOr(Constraint(x=a),CtAnd(Constraint(x!=a),CtInstantiate(x);,10/2/,54,史忠植 高级人工智能,高级人工智能之约束推理,第54页,ILOG Schedule 1.0,Schedule,CtSchedule class,Global object:time original-tineMin,time horizon-timeMax,10/2/,55,史忠植 高级人工智能,高级人工智能之约束推理,第55页,ILOG Schedule 1.0,Resources,CtResource,CtDiscreteResource,CtUnaryResource,CtDiscreteEnergy,CtStateResource,10/2/,56,史忠植 高级人工智能,高级人工智能之约束推理,第56页,ILOG Schedule 1.0,Activities,CtActivity class,CtIntervalActivity,An activity is defined by its start time,end time and duration,Activities require,provide,consume and produce resources,10/2/,57,史忠植 高级人工智能,高级人工智能之约束推理,第57页,Scheduling Problem,Prices paid as tasks begin$1000 per day,Availability:Day 0:$0,Day 15:+$9000,10/2/,58,史忠植 高级人工智能,高级人工智能之约束推理,第58页,Constraints,/To create a schedule with origin 0 and given horizon.,CtSchedule*schedule=,new CtSchedule(0,horizon);,/To create an activity with the given duration.,CtIntervalActivity*act=,new CtIntervalActivity(schedule,duration);,/To post a precedence constraint between act1 and act2.,act2-startsAfterEnd(act1,0);,10/2/,59,史忠植 高级人工智能,高级人工智能之约束推理,第59页,Constraints,/To create a total budget of limited capacity(here 29000).,CtDiscreteResource*res=,new CtDiscreteResource(schedule,CtRequiredResource,capacity);,/To state that only cap(here 0)is available prior to a,/given date(here 15).,res-setCapacityMax(0,date,cap);,/To state that an activity act consumes c units of res.,act-consumes(res,c);,10/2/,60,史忠植 高级人工智能,高级人工智能之约束推理,第60页,Algorithm Program,CtBoolean IsUnScheduled(CtActivity*act),/Return true if act does not have a fixed start time.,if(act-getStartVariable()-isBound(),return CtFalse;,else,return CtTrue;,10/2/,61,史忠植 高级人工智能,高级人工智能之约束推理,第61页,Algorithm Program,CtBoolean IsMoreUrgent(CtActivity*act1,CtActivity*act2),/Returns true if act1 is more urgent than act2.,/Returns true if act2 is unbound(=0),if(act2=0),return CtTrue;,else if(act1-getStartMax()getStartMax(),return CtTrue;,else,return CtFalse;,10/2/,62,史忠植 高级人工智能,高级人工智能之约束推理,第62页,Algorithm Program,CtActivity*SelectActivity(CtSchedule*schedule),/Returns the unscheduled activity with the smallest latest,/statrt time.Returns 0 if all activities are scheduled.,CtActivity*bestActivity=0;,/Creates an iterator to iterate on all activities.,CtActivityIterator*iterator(schedule);,CtActivity*newActivity;,while(iterator.next(newactivity),if(IsUnScheduled(newActivity),&(IsMoreUgent(newActivity,bestActivity),bestactivity=newActivity;,return bestActivity;,10/2/,63,史忠植 高级人工智能,高级人工智能之约束推理,第63页,Algorithm Program,void SolveProblem(CtSchedule*schedule),/Solve the problem assuming constraints have been posted.,CtActivity*act=SelectActivity(schedule);,while(act!=0),act-setStartTime(act-getStartMin();,act=SelectActivity(schedule);,10/2/,64,史忠植 高级人工智能,高级人工智能之约束推理,第64页,Optimal Solution to the Scheduling Problem,10/2/,65,史忠植 高级人工智能,高级人工智能之约束推理,第65页,