高级人工智能之约束推理

高级人工智能第三章约束推理史忠植

中国科学院计算技术所10/2/1史忠植高级人工智能高级人工智能之约束推理第1页第三章约束推理3.1概述3.2回溯法3.3约束传输3.4回跳法3.5约束推理系统COPS3.6ILOGSOLVER10/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分钟)5001650电视台b(晚上,30钞)10001080每日晨报/(半版)1002430星期日报/(半版)300440广播电台/(1分钟)80251510/2/7史忠植高级人工智能高级人工智能之约束推理第7页10/2/8史忠植高级人工智能高级人工智能之约束推理第8页

10/2/9史忠植高级人工智能高级人工智能之约束推理第9页

10/2/10史忠植高级人工智能高级人工智能之约束推理第10页求解--单纯形法将所给问题化为标准形找出一个初始可行基,建立初始单纯形表检验全部检验数(若全为非负,则已得到最优解,计算停顿.不然继续下一步)考查是否无解(若是,计算停顿,不然继续下一步)确定入基变量,出基变量对初始单纯形表进行单纯形变换10/2/11史忠植高级人工智能高级人工智能之约束推理第11页3.1概述一个约束满足问题(ConstraintSatisfactionProblem,简称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页约束语言CONSTRAINTSCHIPCOPSILOG10/2/17史忠植高级人工智能高级人工智能之约束推理第17页CONSTRAINTS约束语言

CONSTRAINTS是一个面向电路描述约束表示语言。作为一个约束表示语言， 它使用了符号处理技术来求解数学方程。在CONSTRAITS中，物理部件功效及器件结构都用约束表示。这些约束普通是线性方程与不等式,也包含条件表示式。约束变量普通是表示物理量实变量。也有一些取离散值变量。如开关状态、三极管工作状态等。系统采取表示式推理与值推理。并实现相关制导回溯。

10/2/18史忠植高级人工智能高级人工智能之约束推理第18页CONSTRAINTS约束语言

CONSTRAINTS一个优点是在类型层次中表示约束，用约束来表示物理对象功效与结构。其缺点是该语言缺乏类似于面向对象语言中方法那样成份，不能定义特定于某个类概念。同时，约束传输方法比较单一，既缺乏实域上区间传输机制，也缺乏有限域上域传输机制。

10/2/19史忠植高级人工智能高级人工智能之约束推理第19页约束逻辑程序设计语言CHIP

CHIP(ConstrainthandlinginProlog)就是这么较有影响一个约束逻辑程序设计语言，其目标是简便、灵活而有效地处理一大类组合问题。它经过提供几个新计算域而增强逻辑程序设计能力；有限域、布尔项及有理项，对于每个计算域，都提供有效约束求解技术，即有限域上一致性技术，布尔域布尔合一技术及有理数域上单纯型法。除此以外，CHIP还包含一个普通延迟计算机制。CHIP主要应用于两个领域:运筹学与硬件设计。CHIP缺乏类型机制，而这种机制对于表示领域概念是极其重要。10/2/20史忠植高级人工智能高级人工智能之约束推理第20页面向对象约束语言COPS

COPS系统利用面向对象技术，将说明性约束表示与类型层次结合起来。在形式上吸收了常规语言，主要是面向对象程序设计语言基本形式。内部求解时采取约束推理机制，使说明性约束表示式与类型层次相结合，实现知识结构化封装，充分发挥二者优点，力图实现一个含有较强表示能力和较高求解效率约束满足系统。10/2/21史忠植高级人工智能高级人工智能之约束推理第21页面向对象约束语言COPSCOPS设计考虑了软件工程应用要求，尽可能将一个不确定问题确定化：它允许条件语句与循环语句，而不是单纯以递归形式来实现迭代计算；经过类方法重栽实现同一约束不一样实现，提升了程序执行效率。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){wherePisaCSPoftheform(V,D,C)}1.f:=thenullassignment2.returnExhaustive-Search(f,P)10/2/25史忠植高级人工智能高级人工智能之约束推理第25页穷尽搜索方法

Exhaustive-Search(f,P)1.iffisatotalassignmentofthevariablesinP2.iffsatisfiestheconstraintsinP3.answer:=f4.else5.answer:=Unsat6.else7.v:=somevariableinPthatisnotyetassignedavaluebyf8.answer:=Unsat9.foreachvaluewhileanswer=Unsat10.f(v):=11.answer:=Exhaustive-Search(f,P)12.returnanswer10/2/26史忠植高级人工智能高级人工智能之约束推理第26页贪心法贪心法把结构可行解工作分阶段来完成。在各个阶段，选择那些在一些意义下是局部最优方案，期望各阶段局部最优选择带来整体最优。例：Dijkstra最短路径算法、Kruskal求最小生成树算法、信号灯问题10/2/27史忠植高级人工智能高级人工智能之约束推理第27页回溯算法有些问题需要彻底搜索才能处理问题，然而，彻底搜索要以大量运算时间为代价，对于这种情况能够经过回溯法来去掉一些分支，从而大大降低搜索次数。八皇后问题迷宫问题深度优先周游树或图10/2/28史忠植高级人工智能高级人工智能之约束推理第28页回溯算法

Backtracking-Top(P)1f:=thenullassignment2returnBacktracking(f,P)10/2/29史忠植高级人工智能高级人工智能之约束推理第29页回溯算法

Backtracking(f,P)1iffisatotalassignmentofthevariablesinP2answer:=f3else4v:=somevariableinPthatisnotyetassignedavaluebyf5answer:=Unsat6foreachvaluewhileanswer=Umsat7f(v):=x8iffsatisfiestheconstraintsinP9answer:=Backtracking(f,P)10returnanswer10/2/30史忠植高级人工智能高级人工智能之约束推理第30页回溯算法

尽管回溯法好于生成测试法，但对于非平凡问题依然是低效。其原因在于搜索空间中不一样路径搜索重复相同失败子路径。一些研究者认为，造成这种重复原因是所谓局部不一致性。最简单情形是所谓结点不一致性。对一个变量vi一个一元约束。存在域中一个值vi不满足该约束。这么，每当vi取到a时就会出现不一致性。另一个重复情形是所谓弧不一致性。10/2/31史忠植高级人工智能高级人工智能之约束推理第31页3.3约束传输

CONSTRAINTPROPAGATION弧一致性Arcconsistency

10/2/32史忠植高级人工智能高级人工智能之约束推理第32页弧一致性Arcconsistency

假如对vi当前域中全部值x，存在vj当前域中某值y使得vi=x和vj=y是vi与vj之间约束所允许，则弧(vi,vj)是弧一致。弧一致性概念是有向。即(vi,vj)是弧一致并不自动地意味着(vj,vi)是一致。10/2/33史忠植高级人工智能高级人工智能之约束推理第33页3.3CONSTRAINTPROPAGATIONAlloftheMackworthalgorithmsmakeuseofaReviseprocedure.LetDvbethecurrentdomainofv,LetDwbethecurrentdomainofw,LetPbetheconstraintpredicatethatholdsbetweenvandw,thenReviseupdatesDvasfollows:10/2/34史忠植高级人工智能高级人工智能之约束推理第34页CONSTRAINTPROPAGATIONMackworth1977AC-1

AC-2AC-310/2/35史忠植高级人工智能高级人工智能之约束推理第35页约束传输修改算法REVISE(Vi,Vj)1DELETE

false; 2foreachx

Dido 3ifthereisnosuchyj

Dj4 suchthat(x,yj)isconsistent,5then 6 deletexfromDi; 7 DELETE

true; 8endif 9endfor 10returnDELETE; 11endREVISE10/2/36史忠植高级人工智能高级人工智能之约束推理第36页AC-11Q

;2repeat 3CHANGE

false;4foreach(Vi,Vj)

Qdo5 CHANGE

REVISE(Vi,Vj)

CHANGE;6endfor;7untilnot(CHANGE);8endAC-110/2/37史忠植高级人工智能高级人工智能之约束推理第37页AC-31Q

;2WhileQnotempty 3Selectanddeleteanyarc(Vk,Vm)fromQ;4If(REVISE(Vk,Vm))ThenQ

{(Vi,Vk)suchthat(Vi,Vk)arcs(G),ik,im};6endfor;7endwhile;8endAC-310/2/38史忠植高级人工智能高级人工智能之约束推理第38页BackjumpingBackjumping-Top(P)1f:=thenullassignment2<answer,conflict-set>:=Backjumping(f,P)3returnanswer

10/2/39史忠植高级人工智能高级人工智能之约束推理第39页BackjumpingBackjumping(f,P)1iffisatotalassignmentofthevariablesinP2answer:=<f,

>3else4v:=somevariableinPthatisnotyetassignedavaluebyf5answer:=Unsat6conflict-set:=

7foreachvalue8f(v):=x9iffsatisfiestheconstraintsinP10<answer,new-conflicts>:=Backjumping(f,P)

10/2/40史忠植高级人工智能高级人工智能之约束推理第40页Backjumping11else12new-conflicts:=thesetofvariablesinaviolatedconstraint13ifanswer

Unsat14return<answer,

>15elseifv

new-conflicts16return<Unsat,new-conflicts>17else18conflict-set:=conflict-set

(new-conflicts{v})19return<Unsat,conflict-set>10/2/41史忠植高级人工智能高级人工智能之约束推理第41页COPS

Constraint:predicateexpression

P(t1,...,tn)wherePisbuiltinfunction,suchas

sumtimeseq(equal)neq(notequal)ge(greatthanorequalto)gt(greatthan)alsocanbedefinedbyusers10/2/42史忠植高级人工智能高级人工智能之约束推理第42页COPS

Conditionalconstraint

condition1:constraint1;..conditionn:constraintn

wherecondition1,...,conditionnarebooleanexpressions.constraint1,...constraintnareconstraintsorcontraintstable.

10/2/43史忠植高级人工智能高级人工智能之约束推理第43页COPS

RULE

Ruleisusedtodefinenewfunction,method,predicate,oraddnewconstraintintoobject.

RULE[class::]predicate(varibles)(booleanexpression){constraint_1; ­constraint_n;CASE booleanexpression_1:constraint_1; ­ booleanexpression_m:constraint_m;}

10/2/44史忠植高级人工智能高级人工智能之约束推理第44页COPS

Forexample:

RULEmultiple(INTEGER:*x,INTEGER:y,INTEGER:z)(neq(y,0)){ equal(x,divide(z,y)); }

z=x*y10/2/45史忠植高级人工智能高级人工智能之约束推理第45页COPS

CLASS[class_name][:superclass_name] { //attributesdefinitiondatetype:attribute_name; ... //ruledefinition rule_name; ... //functiondefinition function_name; ... //methoddefinition method_name;...}10/2/46史忠植高级人工智能高级人工智能之约束推理第46页COPS

Implementation

ProgramwrittenbyCOPSconsistsofclassesandrules.COPSconstraintprogramminglanguageisadeclarativelanguage,providingclasses,methodswhichareexistinobjectorientedlanguage.ItissimilarwithC++.COPShasthefeatures:

constraintobjectorientedlogicprogrammingproductionsystem10/2/47史忠植高级人工智能高级人工智能之约束推理第47页COPS

COPS_Compiler1{2Callyacctoparsetheprogramand3 togenerateinternalstructures.4Initializatiion5 CreateCopsConstanttrueNode;6 Allocatememoriesforglobalvariables.

10/2/48史忠植高级人工智能高级人工智能之约束推理第48页COPS7Interprtetheprogramwiththeinternalstructures.8 ConstraintnetworksarebuiltupforUnsolved9 constraintsandvariables.10whilesomeconstraintsintheconstraintnetworksaretriggered,11intepretethetriggeredconstraints.12}10/2/49史忠植高级人工智能高级人工智能之约束推理第49页COPSInterpreter:

1{2switch(constrainttype)3caseConstant:4returnConstant:5caseglobalvariable:6interpreteglobalvariable:7caselocalvariableorargument:8 interpretelocalvariableorargument:9caseobject-attributepair;10interpreteobject-attributepair:11casefunctioncall:10/2/50史忠植高级人工智能高级人工智能之约束推理第50页COPS12 interpretefunctioncall:13casemethodcall:14 interpretemethodcall:15caseCASEexpression:16 interpreteCASEexpression:17...18default:20reporterror21}10/2/51史忠植高级人工智能高级人工智能之约束推理第51页ILOGSOLVERCombinesobjectorientedprogrammingwithconstraintlogicprogramming,containinglogicvariables,incrementalconstraintsatisfactionandbacktracking.

variables:C++object

integervariableCtIntVarfloatingvariableCtFloatVarbooleanvariableCtBoolVarMemoryManagement

new:delete:10/2/52史忠植高级人工智能高级人工智能之约束推理第52页ILOGSOLVERConstraints

CtTell(x==(y+z));

Basicconstraints:=,

,

,<,>,+,-,*,/,subset,superset,union,intersection,member,booleanor,booleanand,booleannot,booleanxor,

CtTell((x==0)||(y==0));

CtIfThen(x<100,x=x+1);

Search

10/2/53史忠植高级人工智能高级人工智能之约束推理第53页ILOGSOLVERCTGOALn:howtoexecute

CTGOAL1(CtInstantiate,CtIntVar*x){CtInta=x->chooseValue();CtOr(Constraint(x==a),CtAnd(Constraint(x!=a),CtInstantiate(x)));}

10/2/54史忠植高级人工智能高级人工智能之约束推理第54页ILOGSchedule1.0Schedule

CtScheduleclass

Globalobject:timeoriginal---tineMintimehorizon---timeMax

10/2/55史忠植高级人工智能高级人工智能之约束推理第55页ILOGSchedule1.0Resources

CtResource

CtDiscreteResource

CtUnaryResource

CtDiscreteEnergy

CtStateResource

10/2/56史忠植高级人工智能高级人工智能之约束推理第56页ILOGSchedule1.0Activities

CtActivityclass

CtIntervalActivity

Anactivityisdefinedbyitsstarttime,endtimeandduration

Activitiesrequire,provide,consumeandproduceresources10/2/57史忠植高级人工智能高级人工智能之约束推理第57页SchedulingProblemPricespaidastasksbegin$1000perdayAvailability:Day0:$0,Day15:+$900010/2/58史忠植高级人工智能高级人工智能之约束推理第58页Constraints

//Tocreateaschedulewithorigin0andgivenhorizon.CtSchedule*schedule=newCtSchedule(0,horizon);

//Tocreateanactivitywiththegivenduration.CtIntervalActivity*act=newCtIntervalActivity(schedule,duration);

//Topostaprecedenceconstraintbetweenact1andact2.act2->startsAfterEnd(act1,0);

10/2/59史忠植高级人工智能高级人工智能之约束推理第59页Constraints//Tocreateatotalbudgetoflimitedcapacity(here29000).CtDiscreteResource*res=newCtDiscreteResource(schedule,CtRequiredResource,capacity);

//Tostatethatonlycap(here0)isavailablepriortoa//givendate(here15).res->setCapacityMax(0,date,cap);

//Tostatethatanactivityactconsumesc