ch7 邏輯智能體 人工智能課程 北大計(jì)算機(jī)研究所

1、第七章、邏輯智能體p邏輯智能體：基于知識(shí)的智能體p知識(shí)和推理的重要性l部分可觀(guān)察的環(huán)境l自然語(yǔ)言理解l基于知識(shí)的智能體的靈活性主要內(nèi)容p基于知識(shí)的智能體總體的智能體設(shè)計(jì)pwumpus世界關(guān)于基于知識(shí)的智能體運(yùn)轉(zhuǎn)的例子p邏輯p命題邏輯p命題邏輯的推理形式p有效的命題推理p基于命題邏輯的智能體基于知識(shí)的智能體p核心構(gòu)件是其知識(shí)庫(kù)（KB）p將新語(yǔ)句添加到知識(shí)庫(kù)以及查詢(xún)目前所知內(nèi)容的途徑lTELL和ASK：可能涉及推理l當(dāng)ASK知識(shí)庫(kù)一個(gè)問(wèn)題時(shí)，答案必須遵循（follow）事先被告知的知識(shí)庫(kù)的內(nèi)容基于知識(shí)的智能體的一個(gè)通用程序 TELLASKTELL 表示語(yǔ)言的細(xì)節(jié)隱含于MAKE-PETCEPT-SE

2、NTENCE和MAKE-ACTION-QUERY中 推理機(jī)制的細(xì)節(jié)隱藏于TELL和ASK中 KB的構(gòu)造：TELL；智能體自我學(xué)習(xí)主要內(nèi)容p基于知識(shí)的智能體總體的智能體設(shè)計(jì)pwumpus世界關(guān)于基于知識(shí)的智能體運(yùn)轉(zhuǎn)的例子p邏輯p命題邏輯p命題邏輯的推理形式p有效的命題推理p基于命題邏輯的智能體wumpus世界wumpus世界任務(wù)環(huán)境的精確定義（PEAS） 性能度量：gold+1000, death-1000, action-1, using the arrow -10. 環(huán)境 44網(wǎng)格 智能體初始在1,1，面向右方 金子和wumpus在1,1之外隨機(jī)均勻分布 1,1之外的任意方格是陷阱的概率是0

3、.2 執(zhí)行器 智能體可向前、左轉(zhuǎn)或右轉(zhuǎn) 智能體如果進(jìn)入一個(gè)有陷阱或者活著的wumpus的方格，將死去。 如果智能體前方有一堵墻，那么向前移動(dòng)無(wú)效 Grab：撿起智能體所在方格中的一個(gè)物體 Shoot：向智能體所正對(duì)方向射箭（只有一枝箭）PEAS（續(xù)） 傳感器 在wumpus所在之處以及與之直接相鄰的方格內(nèi)，智能體可以感知到臭氣。 在與陷阱直接相鄰的方格內(nèi)，智能體可以感知到微風(fēng)。 在金子所處的方格內(nèi)，智能體可以感知到閃閃金光。 當(dāng)智能體撞到墻時(shí)，它感受到撞擊。 當(dāng)wumpus被殺死時(shí)，它發(fā)出洞穴內(nèi)任何地方都可感知到的悲慘嚎叫。 以5個(gè)符號(hào)的列表形式將感知信息提供給智能體，例如(stench, b

4、reeze, none, none, none)。例子：wumpus世界中智能體行動(dòng)序列行動(dòng)序列（續(xù)）主要內(nèi)容p基于知識(shí)的智能體總體的智能體設(shè)計(jì)pwumpus世界關(guān)于基于知識(shí)的智能體運(yùn)轉(zhuǎn)的例子p邏輯p命題邏輯p命題邏輯的推理形式p有效的命題推理p基于命題邏輯的智能體邏輯pLogics are formal languages for representing information such that conclusion can be drawn.p語(yǔ)法語(yǔ)法定義了語(yǔ)言中的語(yǔ)句p語(yǔ)義語(yǔ)義定義了每個(gè)語(yǔ)句關(guān)于每個(gè)可能世界的真值l例如，算術(shù)采用的通常語(yǔ)義表明語(yǔ)句“x+y=2”在x=2和y=2時(shí)為真。

5、p當(dāng)需要精確描述時(shí)，用術(shù)語(yǔ)模型取代“可能世界”l例如，“m是的一個(gè)模型”表示語(yǔ)句在模型m中為真。蘊(yùn)涵關(guān)系：一個(gè)語(yǔ)句邏輯上追隨另一個(gè)語(yǔ)句而出現(xiàn)p數(shù)學(xué)符號(hào)表示：|=意為語(yǔ)句蘊(yùn)涵語(yǔ)句。p形式化定義：|= iff 在為真的每個(gè)模型中也為真。l例子1：語(yǔ)句xy4蘊(yùn)涵4xy。l例子2： wumpus世界在已知1, 1中什么也沒(méi)觀(guān)察到，及2, 2有微風(fēng)的情況下，1, 2、2, 2和3, 1中有陷阱的可能模型。（a）知識(shí)庫(kù)和1的模型（1, 2無(wú)陷阱）；（b）知識(shí)庫(kù)和2的模型（2, 2無(wú)陷阱）結(jié)論：KB|= 1；KB|2推理p比喻：KB的所有推論集合視為一個(gè)大干草堆，而則視為一根針。p如果推理算法i可以根據(jù)KB

6、導(dǎo)出，我們表示為：KB|=i ，讀為“i從KB導(dǎo)出”。p只導(dǎo)出蘊(yùn)涵句的推理算法稱(chēng)為可靠的或真值保持的推理p推理算法是完備的，如果它可以生成任一蘊(yùn)涵句。邏輯推理過(guò)程和智能體生存的正式環(huán)境之間的聯(lián)系pQ：如何知道KB在現(xiàn)實(shí)世界中為真？p(simple)A：智能體的傳感器創(chuàng)造了這一聯(lián)系。主要內(nèi)容p基于知識(shí)的智能體總體的智能體設(shè)計(jì)pwumpus世界關(guān)于基于知識(shí)的智能體運(yùn)轉(zhuǎn)的例子p邏輯p命題邏輯p命題邏輯的推理形式p有效的命題推理p基于命題邏輯的智能體語(yǔ)法p原子語(yǔ)句不可分割的句法元素構(gòu)成一個(gè)命題符號(hào)，用P, Q, R表示l例子，用W1,3表示“wumpus位于1, 3”。p復(fù)合句由更簡(jiǎn)單的語(yǔ)句用邏輯連接

7、符構(gòu)造而成l連接符：，（稱(chēng)為規(guī)則或if-then) ，。命題邏輯語(yǔ)句的BNF語(yǔ)法SentenceAtomicSentence|ComplexSentenceAtomicSentenceTrue|False|SymbolSymbolP|Q|R|ComplexSentenceSentence |(SentenceSentence) |(SentenceSentence) |(SentenceSentence) |(SentenceSentence) 命題邏輯的優(yōu)先級(jí)次序?yàn)椋ǜ叩降停?， 。 語(yǔ)義PQPPQ PQ PQ PQfalsefalsetruetruefalsetruefalsetruet

8、ruetruefalsefalsefalsefalsefalsetruefalsetruetruetruetruetruefalsetruetruefalsefalsetrue知識(shí)庫(kù)的例子：wumpus世界中的陷阱p對(duì)于每個(gè)i，j：l如果i, j中有陷阱，令Pi,j為真。l如果i, j中有微風(fēng)，令Bi,j為真。p那么，知識(shí)庫(kù)中包含：l1, 1中沒(méi)有陷阱，R1：P1,1l在與陷阱直接相鄰的方格內(nèi)，智能體可以感知到微風(fēng)nR2: B1,1 (P1,2P2,1)nR3: B2,1 (P1,1P2,2P3,1)lR4: B1,1lR5: B2,1推理 目標(biāo)：給定語(yǔ)句，KB|= ?判斷命題蘊(yùn)涵的真值表枚舉

9、算法HWp7.2, 7.4主要內(nèi)容p基于知識(shí)的智能體總體的智能體設(shè)計(jì)pwumpus世界關(guān)于基于知識(shí)的智能體運(yùn)轉(zhuǎn)的例子p邏輯p命題邏輯p命題邏輯的推理形式p有效的命題推理p基于命題邏輯的智能體證明的方法p模型檢查l真值表枚舉：時(shí)間復(fù)雜度為O(2n)。p推理規(guī)則的應(yīng)用l從初始知識(shí)庫(kù)正向出發(fā)，應(yīng)用推理規(guī)則以生成目標(biāo)語(yǔ)句，或從目標(biāo)語(yǔ)句反向出發(fā)，試圖找到由初始知識(shí)庫(kù)引出的推理規(guī)則鏈。n通常需要將句子轉(zhuǎn)換成范式l尋找證明的過(guò)程與搜索問(wèn)題中尋找解的過(guò)程非常類(lèi)似：定義后繼函數(shù)以便生成推理規(guī)則所有可能的應(yīng)用。l命題邏輯的推理是NP完全的邏輯系統(tǒng)的單調(diào)性p單調(diào)性：對(duì)于任意語(yǔ)句和，如果KB|= ，那么KB |= 。

10、p單調(diào)性意味著任何時(shí)刻只要在知識(shí)庫(kù)中發(fā)現(xiàn)了合適的前提，就可以應(yīng)用推理規(guī)則規(guī)則的結(jié)論和KB中其它內(nèi)容無(wú)關(guān)。歸結(jié)p全歸結(jié)規(guī)則：假設(shè)：li lk and m1 mn，其中l(wèi)i和mj是互補(bǔ)文字。結(jié)論：li li-1 li+1 lk m1 mj-1 mj+1 . mnp任何完備的搜索算法，只使用歸結(jié)規(guī)則，就可以生成命題邏輯中被任何知識(shí)庫(kù)蘊(yùn)涵的任何結(jié)論（反證法完備性）合取范式（CNF）p命題邏輯的每個(gè)語(yǔ)句邏輯上等價(jià)于文字析取式的合取式（conjunction of disjunctions of literals）l例子：(A B) (B C D)p每個(gè)語(yǔ)句都可變換成一個(gè)具有等價(jià)模型集合的3-CNF語(yǔ)句p

11、CNF語(yǔ)句可作為歸結(jié)過(guò)程的輸入歸結(jié)算法p通過(guò)反證法而發(fā)揮作用：為了證明KB|=，只需證明KB 不可能為真。pPL-resolution是完備的PL-resolve返回對(duì)它的兩個(gè)輸入進(jìn)行歸結(jié)得到的所有可能德育據(jù)的集合Horn Clausep定義：至多只有一個(gè)正文字的文字析取式，例如P1,1P2,2P3,1。pHorn Clause的重要性l每個(gè)Horn Clause都可寫(xiě)成一個(gè)蘊(yùn)涵式n只有一個(gè)正文字的Horn Clause稱(chēng)為確定子句nP1,1P2,2等價(jià)于P1,1P2,2false，這樣的語(yǔ)句稱(chēng)為數(shù)據(jù)庫(kù)世界的完整性約束。n假定知識(shí)庫(kù)只包含確定子句，而且沒(méi)有完整性約束（Horn Form）Hor

12、n Clause的重要性（續(xù)）p使用Horn Clause的推理可在前向和反向鏈接中進(jìn)行p用Horn Clause判定蘊(yùn)涵所需的時(shí)間與數(shù)據(jù)庫(kù)大小成線(xiàn)性關(guān)系p對(duì)于HornKB，前向鏈接是可靠和完備的前向鏈接和反向鏈接的對(duì)比p前向鏈接：data-drivenp反向鏈接：goal-drivenp通常，反向鏈接的耗散遠(yuǎn)小于KB大小的線(xiàn)性值。主要內(nèi)容p基于知識(shí)的智能體總體的智能體設(shè)計(jì)pwumpus世界關(guān)于基于知識(shí)的智能體運(yùn)轉(zhuǎn)的例子p邏輯p命題邏輯p命題邏輯的推理形式p有效的命題推理p基于命題邏輯的智能體用邏輯推理尋找陷阱和wumpusp陳述“物理規(guī)則”的知識(shí)庫(kù)P1,1 W1,1 Bx,y (Px,y+1 Px,y-1 Px+1,y Px-1,y) （1）Sx,y (Wx,y+1 Wx,y-1 Wx+1,y Wx-1,y)（2）W1,1 W1,2 W4,4 W1,1 W1,2 W1,1 W1,3 64個(gè)符號(hào)和155個(gè)語(yǔ)句用命題邏輯來(lái)辨別陷阱、wumpus和安全方格的智能體命題邏輯的表達(dá)能力的局限性pKB包含以(1)和(2)（見(jiàn)再前頁(yè))中給出形式表示的每個(gè)方格的“物理規(guī)則”語(yǔ)句，環(huán)境規(guī)模越大，要求的初始KB就越大。p如果要記錄位置與方向，KB需包含以下形式的語(yǔ)句：lLx,yt FacingRightt Forw