高級人工智能之約束推理

高級人工智能第三章約束推理史忠植

中國科學(xué)院計算技術(shù)所10/2/1史忠植高級人工智能高級人工智能之約束推理第1頁第三章約束推理3.1概述3.2回溯法3.3約束傳輸3.4回跳法3.5約束推理系統(tǒng)COPS3.6ILOGSOLVER10/2/2史忠植高級人工智能高級人工智能之約束推理第2頁3.1概述最優(yōu)化問題經(jīng)濟學(xué)所推崇帕累托最優(yōu):幾個人拎著水桶在一個水龍頭前面排隊打水，水桶有大有小。他們怎樣排隊，才能使得總排隊時間最短。這是一個尋求“最優(yōu)化”題目，目標是節(jié)約總排隊時間，到達最優(yōu)。10/2/3史忠植高級人工智能高級人工智能之約束推理第3頁3.1概述

優(yōu)化問題

運籌學(xué)

遺傳算法

神經(jīng)網(wǎng)絡(luò)

約束推理10/2/4史忠植高級人工智能高級人工智能之約束推理第4頁運籌學(xué)工作步驟1）提出和形成問題，2）建立模型，3）求解，4）解檢驗，5）解控制，6）解實施。10/2/5史忠植高級人工智能高級人工智能之約束推理第5頁線性規(guī)劃問題例1(廣告方式選擇)中華家電企業(yè)推銷一個新型洗衣機,相關(guān)數(shù)據(jù)見下表.銷售部第一月廣告預(yù)算為0元,要求最少有8電視商業(yè)節(jié)目,15家報紙廣告/電視廣告費不得超出1元,電臺廣播最少隔日有一次.現(xiàn)問該企業(yè)銷售部應(yīng)該采取怎樣廣告宣傳計劃,才能取得最好效果?10/2/6史忠植高級人工智能高級人工智能之約束推理第6頁表1廣告方式廣告費用(元/次)可用最高次數(shù)/月期望宣傳效果/單位電視臺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頁求解--單純形法將所給問題化為標準形找出一個初始可行基,建立初始單純形表檢驗全部檢驗數(shù)(若全為非負,則已得到最優(yōu)解,計算停頓.不然繼續(xù)下一步)考查是否無解(若是,計算停頓,不然繼續(xù)下一步)確定入基變量,出基變量對初始單純形表進行單純形變換10/2/11史忠植高級人工智能高級人工智能之約束推理第11頁3.1概述一個約束滿足問題(ConstraintSatisfactionProblem,簡稱CSP)包含一組變量與一組變量間約束。?變量表示領(lǐng)域參數(shù)，每個變量都有一個固定值域。一個變量值域可能是有限，比如一個布爾變量值域包含兩個值；也可能是離散無限，如整數(shù)域；也可能是連續(xù)，如實數(shù)域。{x1,x2,…xn},{D1,D2,…Dn},.{4,5,6,7}red,green,blue}

10/2/12史忠植高級人工智能高級人工智能之約束推理第12頁3.1概述?約束可用于描述領(lǐng)域?qū)ο笮再|(zhì)、相互關(guān)系、任務(wù)要求、目標等。約束滿足問題目標就是找到全部變量一個（或多個）賦值，使全部約束都得到滿足。

一元謂詞。

序關(guān)系語言，只包含偏序關(guān)系或?qū)嵶兞可洗笮￡P(guān)系。

形如“x-y>c”方程。

單位系數(shù)線性方程與不等式，即全部系數(shù)為-1,0,1。

任意系數(shù)線性方程與不等式。

約束布爾組合。

代數(shù)與三角方程。10/2/13史忠植高級人工智能高級人工智能之約束推理第13頁3.1概述約束表示易于了解、編碼及有效實現(xiàn)，它含有以下優(yōu)點:約束表示允許以說明性方式來表示領(lǐng)域知識，表示能力較強，應(yīng)用程序只需指定問題目標條件及數(shù)據(jù)間相互關(guān)系。因而含有邏輯表示類似性質(zhì)。約束表示允許變量域包含任意多個值，而不像命題只取真假二值。所以它保留了問題一些結(jié)構(gòu)信息，如變量域大小、變量間相關(guān)性等，從而為問題求解提供啟發(fā)式信息。易于并行實現(xiàn)。因為約束網(wǎng)絡(luò)上信息傳輸能夠認為是同時。

適合于遞增型系統(tǒng)。約束能夠遞增式地加入到約束網(wǎng)絡(luò)。易于與領(lǐng)域相關(guān)問題求解模型相銜接。各種數(shù)學(xué)規(guī)劃技術(shù)，方程求解技術(shù)等,都能夠自然地嵌入約束系統(tǒng)。10/2/14史忠植高級人工智能高級人工智能之約束推理第14頁3.1約束推理

約束搜索約束搜索主要研究有限域上約束滿足。對有限域而言，約束滿足問題普通情況下是一個NP問題。

約束語言10/2/15史忠植高級人工智能高級人工智能之約束推理第15頁3.1約束搜索

回溯法。

約束傳輸。

智能回溯與真值維護。

可變次序例示。

局部修正法。10/2/16史忠植高級人工智能高級人工智能之約束推理第16頁約束語言CONSTRAINTSCHIPCOPSILOG10/2/17史忠植高級人工智能高級人工智能之約束推理第17頁CONSTRAINTS約束語言

CONSTRAINTS是一個面向電路描述約束表示語言。作為一個約束表示語言， 它使用了符號處理技術(shù)來求解數(shù)學(xué)方程。在CONSTRAITS中，物理部件功效及器件結(jié)構(gòu)都用約束表示。這些約束普通是線性方程與不等式,也包含條件表示式。約束變量普通是表示物理量實變量。也有一些取離散值變量。如開關(guān)狀態(tài)、三極管工作狀態(tài)等。系統(tǒng)采取表示式推理與值推理。并實現(xiàn)相關(guān)制導(dǎo)回溯。

10/2/18史忠植高級人工智能高級人工智能之約束推理第18頁CONSTRAINTS約束語言

CONSTRAINTS一個優(yōu)點是在類型層次中表示約束，用約束來表示物理對象功效與結(jié)構(gòu)。其缺點是該語言缺乏類似于面向?qū)ο笳Z言中方法那樣成份，不能定義特定于某個類概念。同時，約束傳輸方法比較單一，既缺乏實域上區(qū)間傳輸機制，也缺乏有限域上域傳輸機制。

10/2/19史忠植高級人工智能高級人工智能之約束推理第19頁約束邏輯程序設(shè)計語言CHIP

CHIP(ConstrainthandlinginProlog)就是這么較有影響一個約束邏輯程序設(shè)計語言，其目標是簡便、靈活而有效地處理一大類組合問題。它經(jīng)過提供幾個新計算域而增強邏輯程序設(shè)計能力；有限域、布爾項及有理項，對于每個計算域，都提供有效約束求解技術(shù)，即有限域上一致性技術(shù)，布爾域布爾合一技術(shù)及有理數(shù)域上單純型法。除此以外，CHIP還包含一個普通延遲計算機制。CHIP主要應(yīng)用于兩個領(lǐng)域:運籌學(xué)與硬件設(shè)計。CHIP缺乏類型機制，而這種機制對于表示領(lǐng)域概念是極其重要。10/2/20史忠植高級人工智能高級人工智能之約束推理第20頁面向?qū)ο蠹s束語言COPS

COPS系統(tǒng)利用面向?qū)ο蠹夹g(shù)，將說明性約束表示與類型層次結(jié)合起來。在形式上吸收了常規(guī)語言，主要是面向?qū)ο蟪绦蛟O(shè)計語言基本形式。內(nèi)部求解時采取約束推理機制，使說明性約束表示式與類型層次相結(jié)合，實現(xiàn)知識結(jié)構(gòu)化封裝，充分發(fā)揮二者優(yōu)點，力圖實現(xiàn)一個含有較強表示能力和較高求解效率約束滿足系統(tǒng)。10/2/21史忠植高級人工智能高級人工智能之約束推理第21頁面向?qū)ο蠹s束語言COPSCOPS設(shè)計考慮了軟件工程應(yīng)用要求，盡可能將一個不確定問題確定化：它允許條件語句與循環(huán)語句，而不是單純以遞歸形式來實現(xiàn)迭代計算；經(jīng)過類方法重栽實現(xiàn)同一約束不一樣實現(xiàn)，提升了程序執(zhí)行效率。COPS系統(tǒng)同時是一個漸增式開放系統(tǒng)，用戶能經(jīng)過類型層次定義，實現(xiàn)新數(shù)據(jù)類型和新約束關(guān)系。約束語言COPS含有許多人工智能程序設(shè)計語言特點，如約束傳輸、面向目標和數(shù)據(jù)驅(qū)動問題求解、有限步回溯、對象分層中繼承等。

10/2/22史忠植高級人工智能高級人工智能之約束推理第22頁

在實際應(yīng)用中，算法表現(xiàn)形式千變?nèi)f化，不過算法情況也和數(shù)據(jù)結(jié)構(gòu)類似，許多算法設(shè)計思想含有相同之處，我們能夠?qū)λ鼈兎诸愡M行學(xué)習(xí)和研究。慣用算法大致有以下一些：貪心法分治法：如二分法檢索回溯法動態(tài)規(guī)劃法局部搜索法分支限界法10/2/23史忠植高級人工智能高級人工智能之約束推理第23頁

算法分析評價一個程序優(yōu)劣主要依據(jù)是看這個程序執(zhí)行需要占用多少機器資源。人們最關(guān)心就是程序所用算法運行時所要花費時間代價和程序中使用數(shù)據(jù)結(jié)構(gòu)占有空間代價。

算法空間代價(或稱空間復(fù)雜性)：當被處理問題規(guī)模(以某種單位計算)由1增至n時，解該問題算法所需占用空間也以某種單位由f(1)增至f(n)，這時我們稱該算法空間代價是f(n)。算法時間代價(或稱時間復(fù)雜性)：當問題規(guī)模以某種單位由1增至n時，對應(yīng)算法所花費時間也以某種單位由g(1)增至g(n)，這時我們稱算法時間代價是g(n)。

10/2/24史忠植高級人工智能高級人工智能之約束推理第24頁窮盡搜索方法窮盡搜索方法即產(chǎn)生全部可能樹，然后依據(jù)評價標準選擇一棵最優(yōu)樹。

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頁貪心法貪心法把結(jié)構(gòu)可行解工作分階段來完成。在各個階段，選擇那些在一些意義下是局部最優(yōu)方案，期望各階段局部最優(yōu)選擇帶來整體最優(yōu)。例：Dijkstra最短路徑算法、Kruskal求最小生成樹算法、信號燈問題10/2/27史忠植高級人工智能高級人工智能之約束推理第27頁回溯算法有些問題需要徹底搜索才能處理問題，然而，徹底搜索要以大量運算時間為代價，對于這種情況能夠經(jīng)過回溯法來去掉一些分支，從而大大降低搜索次數(shù)。八皇后問題迷宮問題深度優(yōu)先周游樹或圖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頁回溯算法

盡管回溯法好于生成測試法，但對于非平凡問題依然是低效。其原因在于搜索空間中不一樣路徑搜索重復(fù)相同失敗子路徑。一些研究者認為，造成這種重復(fù)原因是所謂局部不一致性。最簡單情形是所謂結(jié)點不一致性。對一個變量vi一個一元約束。存在域中一個值vi不滿足該約束。這么，每當vi取到a時就會出現(xiàn)不一致性。另一個重復(fù)情形是所謂弧不一致性。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