1、2022-6-26史忠植 高級(jí)人工智能1高級(jí)人工智能高級(jí)人工智能第十四章第十四章 主體計(jì)算主體計(jì)算 史忠植史忠植 中國(guó)科學(xué)院計(jì)算技術(shù)所2022-6-26史忠植 高級(jí)人工智能2內(nèi)容提要內(nèi)容提要14.1 概述14.2 分布式問(wèn)題求解14.3 主體14.4 主體理論14.5 主體結(jié)構(gòu)14.6 主體通信14.7 主體的協(xié)調(diào)與協(xié)作14.8 多主體環(huán)境MAGE2022-6-26史忠植 高級(jí)人工智能3概概 述述分布式人工智能主要研究在邏輯上或物理上分散的智能系統(tǒng)如何并行的、相互協(xié)作地實(shí)現(xiàn)問(wèn)題求解。兩種解決問(wèn)題的方法： 自頂向下：分布式問(wèn)題求解 自底向上：基于主體的方法2022-6-26史忠植 高級(jí)人工智能4

2、分布智能系統(tǒng)的特色分布智能系統(tǒng)的特色 系統(tǒng)中的數(shù)據(jù)、知識(shí), 以及控制不但在邏輯上, 而且在物理上是分布的, 既沒(méi)有全局控制, 也沒(méi)有全局的數(shù)據(jù)存儲(chǔ)。 各個(gè)求解機(jī)構(gòu)由計(jì)算機(jī)網(wǎng)絡(luò)互連, 在問(wèn)題求解過(guò)程中, 通信代價(jià)要比求解問(wèn)題的代價(jià)低得多。 系統(tǒng)中諸機(jī)構(gòu)能夠相互協(xié)作, 來(lái)求解單個(gè)機(jī)構(gòu)難以解決, 甚至不能解決的任務(wù)。2022-6-26史忠植 高級(jí)人工智能5分布智能系統(tǒng)的主要優(yōu)點(diǎn)分布智能系統(tǒng)的主要優(yōu)點(diǎn) 提高問(wèn)題求解能力。 提高問(wèn)題求解效率。 擴(kuò)大應(yīng)用范圍。 降低軟件的復(fù)雜性。2022-6-26史忠植 高級(jí)人工智能6分布式人工智能分布式人工智能 分布式人工智能的研究可以追溯到分布式人工智能的研究可以追溯

3、到7070年代末期。早期分布式人工智能年代末期。早期分布式人工智能的研究主要是分布式問(wèn)題求解，其的研究主要是分布式問(wèn)題求解，其目標(biāo)是要?jiǎng)?chuàng)建大粒度的協(xié)作群體，目標(biāo)是要?jiǎng)?chuàng)建大粒度的協(xié)作群體，它們之間共同工作以對(duì)某一問(wèn)題進(jìn)它們之間共同工作以對(duì)某一問(wèn)題進(jìn)行求解。行求解。2022-6-26史忠植 高級(jí)人工智能7合同網(wǎng)合同網(wǎng) 19801980年年Davis Davis 和和 SmithSmith提出了合同網(wǎng)提出了合同網(wǎng)(CNET) (CNET) CNET CNET使用投標(biāo)使用投標(biāo)-合同方式實(shí)現(xiàn)任務(wù)在多合同方式實(shí)現(xiàn)任務(wù)在多個(gè)節(jié)點(diǎn)上的分配。合同網(wǎng)系統(tǒng)的重要貢獻(xiàn)個(gè)節(jié)點(diǎn)上的分配。合同網(wǎng)系統(tǒng)的重要貢獻(xiàn)在于提出了通過(guò)

4、相互選擇和達(dá)成協(xié)議的協(xié)在于提出了通過(guò)相互選擇和達(dá)成協(xié)議的協(xié)商過(guò)程實(shí)現(xiàn)分布式任務(wù)分配和控制的思想。商過(guò)程實(shí)現(xiàn)分布式任務(wù)分配和控制的思想。2022-6-26史忠植 高級(jí)人工智能8分布式車(chē)輛監(jiān)控測(cè)試系統(tǒng)分布式車(chē)輛監(jiān)控測(cè)試系統(tǒng) DVMT19801980年麻薩諸塞大學(xué)的年麻薩諸塞大學(xué)的Lesser, Corkill Lesser, Corkill 和和 Durfee Durfee 等人主持研制等人主持研制DVMTDVMT該系統(tǒng)對(duì)市區(qū)內(nèi)行駛的車(chē)輛軌跡進(jìn)行監(jiān)控該系統(tǒng)對(duì)市區(qū)內(nèi)行駛的車(chē)輛軌跡進(jìn)行監(jiān)控, , 并以此環(huán)境為基礎(chǔ)并以此環(huán)境為基礎(chǔ), , 對(duì)分布式問(wèn)題求解對(duì)分布式問(wèn)題求解系統(tǒng)中許多技術(shù)問(wèn)題進(jìn)行研究。系統(tǒng)中

5、許多技術(shù)問(wèn)題進(jìn)行研究。DVMTDVMT是以是以分布式傳感網(wǎng)絡(luò)數(shù)據(jù)解釋為背景，對(duì)復(fù)雜分布式傳感網(wǎng)絡(luò)數(shù)據(jù)解釋為背景，對(duì)復(fù)雜的黑板問(wèn)題求解系統(tǒng)之間的相互作用進(jìn)行的黑板問(wèn)題求解系統(tǒng)之間的相互作用進(jìn)行了研究，提供了抽象和模型化分布式系統(tǒng)了研究，提供了抽象和模型化分布式系統(tǒng)行為的方法。行為的方法。2022-6-26史忠植 高級(jí)人工智能9ACTORACTOR模型模型19831983年年Hewitt Hewitt 和他的同事們研制了基于和他的同事們研制了基于ACTORACTOR模型的并發(fā)程序設(shè)計(jì)系統(tǒng)。模型的并發(fā)程序設(shè)計(jì)系統(tǒng)。ACTORACTOR模型提供了分布式系統(tǒng)中并行計(jì)算理論模型提供了分布式系統(tǒng)中并行計(jì)算理

6、論和一組專(zhuān)家或和一組專(zhuān)家或ACTORACTOR獲得智能行為的能力。獲得智能行為的能力。在在19911991年年HewittHewitt提出開(kāi)放信息系統(tǒng)語(yǔ)義提出開(kāi)放信息系統(tǒng)語(yǔ)義, , 指出競(jìng)爭(zhēng)、承諾、協(xié)作、協(xié)商等性質(zhì)應(yīng)作指出競(jìng)爭(zhēng)、承諾、協(xié)作、協(xié)商等性質(zhì)應(yīng)作為分布式人工智能的科學(xué)基礎(chǔ)，試圖為分為分布式人工智能的科學(xué)基礎(chǔ)，試圖為分布式人工智能的理論研究提供新的基礎(chǔ)。布式人工智能的理論研究提供新的基礎(chǔ)。2022-6-26史忠植 高級(jí)人工智能10MACE系統(tǒng)系統(tǒng)是一個(gè)實(shí)驗(yàn)型的分布式人工智能系統(tǒng)開(kāi)發(fā)環(huán)境是一個(gè)實(shí)驗(yàn)型的分布式人工智能系統(tǒng)開(kāi)發(fā)環(huán)境(Gasser 1987)(Gasser 1987)。MACEM

7、ACE中每一個(gè)計(jì)算單元都稱(chēng)作主體，它們具有知識(shí)表示和中每一個(gè)計(jì)算單元都稱(chēng)作主體，它們具有知識(shí)表示和推理能力，主體之間通過(guò)消息傳送進(jìn)行通信。推理能力，主體之間通過(guò)消息傳送進(jìn)行通信。MACEMACE是是一個(gè)類(lèi)面向?qū)ο蟓h(huán)境，但避開(kāi)了并發(fā)對(duì)象系統(tǒng)中難于一個(gè)類(lèi)面向?qū)ο蟓h(huán)境，但避開(kāi)了并發(fā)對(duì)象系統(tǒng)中難于理解和實(shí)現(xiàn)的繼承問(wèn)題。理解和實(shí)現(xiàn)的繼承問(wèn)題。MACEMACE的各個(gè)機(jī)構(gòu)并行計(jì)算的各個(gè)機(jī)構(gòu)并行計(jì)算, , 并提供了描述機(jī)構(gòu)的描述語(yǔ)言并提供了描述機(jī)構(gòu)的描述語(yǔ)言, , 具有跟蹤的具有跟蹤的demonsdemons機(jī)制。機(jī)制。 該課題研究的重點(diǎn)是在實(shí)際并行環(huán)境下運(yùn)行該課題研究的重點(diǎn)是在實(shí)際并行環(huán)境下運(yùn)行分布式人工智

8、能系統(tǒng)，保持概念的清晰性。分布式人工智能系統(tǒng)，保持概念的清晰性。2022-6-26史忠植 高級(jí)人工智能11分布式運(yùn)輸調(diào)度系統(tǒng)分布式運(yùn)輸調(diào)度系統(tǒng)DTDS-I19891989年清華大學(xué)石純一等主持研制了分布式年清華大學(xué)石純一等主持研制了分布式運(yùn)輸調(diào)度系統(tǒng)運(yùn)輸調(diào)度系統(tǒng)DTDS-I(DTDS-I(石純一石純一 1989) 1989)。該系統(tǒng)以運(yùn)輸調(diào)度為背景，提出了分布式問(wèn)該系統(tǒng)以運(yùn)輸調(diào)度為背景，提出了分布式問(wèn)題求解系統(tǒng)的體系結(jié)構(gòu)，對(duì)問(wèn)題分解、任題求解系統(tǒng)的體系結(jié)構(gòu)，對(duì)問(wèn)題分解、任務(wù)分布算法和基于元級(jí)通信的協(xié)作機(jī)制等務(wù)分布算法和基于元級(jí)通信的協(xié)作機(jī)制等方面進(jìn)行了探討。方面進(jìn)行了探討。2022-6-26史

9、忠植 高級(jí)人工智能12分布式知識(shí)處理系統(tǒng)分布式知識(shí)處理系統(tǒng)DKPS19901990中國(guó)科學(xué)院計(jì)算技術(shù)研究所史忠植等研中國(guó)科學(xué)院計(jì)算技術(shù)研究所史忠植等研究了分布式知識(shí)處理系統(tǒng)究了分布式知識(shí)處理系統(tǒng)DKPSDKPS。該系統(tǒng)采用邏輯該系統(tǒng)采用邏輯-對(duì)象知識(shí)模型，研究對(duì)象知識(shí)模型，研究了知識(shí)共享和協(xié)作求解等問(wèn)題。了知識(shí)共享和協(xié)作求解等問(wèn)題。2022-6-26史忠植 高級(jí)人工智能13多主體系統(tǒng)多主體系統(tǒng) 90年代，多主體系統(tǒng)年代，多主體系統(tǒng)Multiagent systems)的研究成為分布式人的研究成為分布式人工智能研究的熱點(diǎn)。多主體系統(tǒng)主要研究自主的智能主體之間工智能研究的熱點(diǎn)。多主體系統(tǒng)主要研究自

10、主的智能主體之間智能行為的協(xié)調(diào)，為了一個(gè)共同的全局目標(biāo)，也可能是關(guān)于各智能行為的協(xié)調(diào)，為了一個(gè)共同的全局目標(biāo)，也可能是關(guān)于各自的不同目標(biāo)，共享有關(guān)問(wèn)題和求解方法的知識(shí)，協(xié)作進(jìn)行問(wèn)自的不同目標(biāo)，共享有關(guān)問(wèn)題和求解方法的知識(shí)，協(xié)作進(jìn)行問(wèn)題求解。題求解。 基于智能主體的概念，人們提出了一種新的人工智能定義：基于智能主體的概念，人們提出了一種新的人工智能定義：“人工智能是計(jì)算機(jī)科學(xué)的一個(gè)分支，它的目標(biāo)是構(gòu)造能表現(xiàn)人工智能是計(jì)算機(jī)科學(xué)的一個(gè)分支，它的目標(biāo)是構(gòu)造能表現(xiàn)出一定智能行為的主體出一定智能行為的主體”。所以，智能主體的研究應(yīng)該是人工。所以，智能主體的研究應(yīng)該是人工智能的核心問(wèn)題。智能的核心問(wèn)題。斯

11、坦福大學(xué)計(jì)算機(jī)科學(xué)系的斯坦福大學(xué)計(jì)算機(jī)科學(xué)系的 Hayes-Roth在在IJCAI95的特邀報(bào)的特邀報(bào)告中談到：告中談到：“智能的計(jì)算機(jī)主體既是人工智能最初的目標(biāo)，也智能的計(jì)算機(jī)主體既是人工智能最初的目標(biāo)，也是人工智能最終的目標(biāo)。是人工智能最終的目標(biāo)。”2022-6-26史忠植 高級(jí)人工智能14多主體系統(tǒng)多主體系統(tǒng) 關(guān)于主體的研究不僅受到了人工智能研究關(guān)于主體的研究不僅受到了人工智能研究人員的關(guān)注，也吸引了數(shù)據(jù)通信、人機(jī)界人員的關(guān)注，也吸引了數(shù)據(jù)通信、人機(jī)界面設(shè)計(jì)、機(jī)器人、并行工程等各領(lǐng)域的研面設(shè)計(jì)、機(jī)器人、并行工程等各領(lǐng)域的研究人員的興趣。有人認(rèn)為：究人員的興趣。有人認(rèn)為：“基于主體的基于主

12、體的計(jì)算（計(jì)算（Agent-Based ComputingAgent-Based Computing， 簡(jiǎn)稱(chēng)簡(jiǎn)稱(chēng)ABCABC）, , 將成為軟件開(kāi)發(fā)的下一個(gè)重要的將成為軟件開(kāi)發(fā)的下一個(gè)重要的突破。突破?！?022-6-26史忠植 高級(jí)人工智能15 分布式問(wèn)題求解分布式問(wèn)題求解特點(diǎn)：數(shù)據(jù)、知識(shí)、控制均分布在系統(tǒng)的各節(jié)點(diǎn)上，既無(wú)全局控制，也無(wú)全局?jǐn)?shù)據(jù)和知識(shí)存儲(chǔ)。2022-6-26史忠植 高級(jí)人工智能16 分布式問(wèn)題求解分布式問(wèn)題求解兩種協(xié)作方式：兩種協(xié)作方式： 任務(wù)分擔(dān)任務(wù)分擔(dān) 結(jié)果共享結(jié)果共享2022-6-26史忠植 高級(jí)人工智能17任務(wù)分擔(dān)任務(wù)分擔(dān) Smith Smith 和和Davis Da

13、vis 提出了任務(wù)分擔(dān)方式。提出了任務(wù)分擔(dān)方式。在任務(wù)分擔(dān)系統(tǒng)中在任務(wù)分擔(dān)系統(tǒng)中, , 結(jié)點(diǎn)之間通過(guò)分擔(dān)結(jié)點(diǎn)之間通過(guò)分擔(dān)執(zhí)行整個(gè)任務(wù)的子任務(wù)而相互協(xié)作執(zhí)行整個(gè)任務(wù)的子任務(wù)而相互協(xié)作, , 系統(tǒng)系統(tǒng)中的控制以目標(biāo)為指導(dǎo)中的控制以目標(biāo)為指導(dǎo), , 各結(jié)點(diǎn)的處理各結(jié)點(diǎn)的處理目標(biāo)是為了求解整個(gè)任務(wù)的一部分。目標(biāo)是為了求解整個(gè)任務(wù)的一部分。 任務(wù)分擔(dān)的問(wèn)題求解方式適合于求解具有層任務(wù)分擔(dān)的問(wèn)題求解方式適合于求解具有層次結(jié)構(gòu)的任務(wù)次結(jié)構(gòu)的任務(wù), , 如工廠(chǎng)聯(lián)合體生產(chǎn)規(guī)劃、如工廠(chǎng)聯(lián)合體生產(chǎn)規(guī)劃、 數(shù)數(shù)字邏輯電路設(shè)計(jì)、字邏輯電路設(shè)計(jì)、 醫(yī)療診斷。醫(yī)療診斷。2022-6-26史忠植 高級(jí)人工智能18結(jié)果共享結(jié)果

14、共享 Lesser Lesser 和和 Corkill Corkill 提出了結(jié)果共享方式。在提出了結(jié)果共享方式。在結(jié)果共享方式的系統(tǒng)中結(jié)果共享方式的系統(tǒng)中, , 各結(jié)點(diǎn)通過(guò)共享部分結(jié)果各結(jié)點(diǎn)通過(guò)共享部分結(jié)果相互協(xié)作相互協(xié)作, , 系統(tǒng)中的控制以數(shù)據(jù)為指導(dǎo)系統(tǒng)中的控制以數(shù)據(jù)為指導(dǎo), , 各結(jié)點(diǎn)在各結(jié)點(diǎn)在任何時(shí)刻進(jìn)行的求解取決于當(dāng)時(shí)它本身?yè)碛谢驈钠渌魏螘r(shí)刻進(jìn)行的求解取決于當(dāng)時(shí)它本身?yè)碛谢驈钠渌Y(jié)點(diǎn)收到的數(shù)據(jù)和知識(shí)。結(jié)點(diǎn)收到的數(shù)據(jù)和知識(shí)。 結(jié)果共享的求解方式適合于求解與任務(wù)有關(guān)的各結(jié)果共享的求解方式適合于求解與任務(wù)有關(guān)的各子任務(wù)的結(jié)果相互影響子任務(wù)的結(jié)果相互影響, , 并且部分結(jié)果需要綜合才能并

15、且部分結(jié)果需要綜合才能得出問(wèn)題解的領(lǐng)域。如分布式運(yùn)輸調(diào)度系統(tǒng)、分布式得出問(wèn)題解的領(lǐng)域。如分布式運(yùn)輸調(diào)度系統(tǒng)、分布式車(chē)輛監(jiān)控實(shí)驗(yàn)系統(tǒng)車(chē)輛監(jiān)控實(shí)驗(yàn)系統(tǒng)DVMTDVMT 2022-6-26史忠植 高級(jí)人工智能19分布式問(wèn)題求解系統(tǒng)分類(lèi)分布式問(wèn)題求解系統(tǒng)分類(lèi)根據(jù)組織結(jié)構(gòu)，分布式問(wèn)題求解系統(tǒng)可以分為三類(lèi)： 層次結(jié)構(gòu)類(lèi) 平行結(jié)構(gòu)類(lèi) 混合結(jié)構(gòu)類(lèi)2022-6-26史忠植 高級(jí)人工智能20分布式問(wèn)題求解過(guò)程分布式問(wèn)題求解過(guò)程分布式問(wèn)題求解過(guò)程可以分為四步： 任務(wù)分解 任務(wù)分配 子問(wèn)題求解 結(jié)果綜合2022-6-26史忠植 高級(jí)人工智能21任務(wù)分解任務(wù)分解 合同網(wǎng)絡(luò)合同網(wǎng)絡(luò) 動(dòng)態(tài)層次控制動(dòng)態(tài)層次控制 自然分解自然

16、分解, 固定分配固定分配 部分全局規(guī)劃部分全局規(guī)劃2022-6-26史忠植 高級(jí)人工智能22分布式問(wèn)題求解系統(tǒng)中協(xié)作的分類(lèi)分布式問(wèn)題求解系統(tǒng)中協(xié)作的分類(lèi) 按節(jié)點(diǎn)間協(xié)作量的多少，協(xié)作分為三類(lèi)： 全協(xié)作系統(tǒng) 無(wú)協(xié)作系統(tǒng) 半?yún)f(xié)作系統(tǒng)常用的通信方式有： 共享全局存儲(chǔ)器 信息傳遞 黑板模型2022-6-26史忠植 高級(jí)人工智能23 主主 體體多主體系統(tǒng)主要研究在邏輯上或物理上分離的多個(gè)主體協(xié)調(diào)其智能行為，即知識(shí)、目標(biāo)、意圖及規(guī)劃等，實(shí)現(xiàn)問(wèn)題求解?？梢钥醋魇且环N由底向上設(shè)計(jì)的系統(tǒng)。The agent function maps from percept histories to actions:f: P*

17、 A2022-6-26史忠植 高級(jí)人工智能24主體的思想主體的思想智能主體的幾個(gè)典型的實(shí)例： Microsoft的Office助手 計(jì)算機(jī)病毒（破壞主體） 計(jì)算機(jī)游戲或模擬中的智能角色 貿(mào)易和談判主體（如Ebay的拍賣(mài)主體） 網(wǎng)絡(luò)蜘蛛Web Spider（搜索引擎中的數(shù)據(jù)搜集和索引主體，如Google） 2022-6-26史忠植 高級(jí)人工智能25主體程序設(shè)計(jì)主體程序設(shè)計(jì)面向過(guò)程的方法面向?qū)嶓w的方法面向?qū)ο蟮姆椒嫦蛑黧w的方法軟件開(kāi)發(fā)方法的進(jìn)化2022-6-26史忠植 高級(jí)人工智能26主體的定義主體的定義在計(jì)算機(jī)和人工智能領(lǐng)域中，主體可以看作是一個(gè)實(shí)體，它通過(guò)傳感器感知環(huán)境，通過(guò)效應(yīng)器作用于環(huán)境

18、。An agent is anything that can be viewed as perceiving its environment through sensors and acting upon that environment through actuators2022-6-26史忠植 高級(jí)人工智能27主體的特性主體的特性主體弱概念：自治性交互性協(xié)作性可通信性長(zhǎng)壽性2022-6-26史忠植 高級(jí)人工智能28主體的特性主體的特性主體強(qiáng)概念：知識(shí)、信念、意圖、承諾等心智狀態(tài)其它屬性：移動(dòng)性推理能力規(guī)劃能力學(xué)習(xí)和適應(yīng)能力誠(chéng)實(shí)、善意、理性2022-6-26史忠植 高級(jí)人工智能29 主體理論

19、主體理論智能主體的理論模型研究主要從邏輯、行為、心理、社會(huì)等角度出發(fā)，對(duì)智能主體的本質(zhì)進(jìn)行描述，為智能主體系統(tǒng)創(chuàng)建奠定基礎(chǔ)。2022-6-26史忠植 高級(jí)人工智能30理性主體（理性主體（BDIBDI主體）主體）Belief信念，主體對(duì)環(huán)境的基本看法。Desire愿望，主體想要實(shí)現(xiàn)的狀態(tài)，即目標(biāo)。Intention意圖，目標(biāo)的子集。2022-6-26史忠植 高級(jí)人工智能31 BDIBDI主體模型主體模型BDI主體模型可以通過(guò)下列要素描述： 一組關(guān)于世界的信念； 主體當(dāng)前打算達(dá)到的一組目標(biāo)； 一個(gè)規(guī)劃庫(kù)，描述怎樣達(dá)到目標(biāo)和怎樣改變信念； 一個(gè)意圖結(jié)構(gòu)，描述主體當(dāng)前怎樣達(dá)到它的目標(biāo)和改變信念。202

20、2-6-26史忠植 高級(jí)人工智能32BDIBDI解釋器解釋器BDI-Interpreterinitialize-state();dooptions := option-generator(event-queue, B, G, I);selected-options := deliberate(options, B, G, I);update-intentions(selected-options, I);execute(I);get-new-external-events();drop-successful-attitudes(B,G,I);drop-impossible-attitudes(

21、B,G,I);until quit2022-6-26史忠植 高級(jí)人工智能33 動(dòng)作理論動(dòng)作理論情景演算是描述動(dòng)作的主要的形式框架。 在情景演算中引入了狀態(tài)和動(dòng)作的概念，并利用兩條邏輯公理來(lái)描述動(dòng)作與狀態(tài)的關(guān)系。一條公理描述一個(gè)動(dòng)作在滿(mǎn)足什么條件的狀態(tài)之下可能發(fā)生，另外一條描述在一個(gè)狀態(tài)之下某個(gè)動(dòng)作發(fā)生以后當(dāng)前狀態(tài)如何改變。2022-6-26史忠植 高級(jí)人工智能34規(guī)劃庫(kù)的形式化表示規(guī)劃庫(kù)的形式化表示環(huán)境狀態(tài)：State = P1, P2, Pn 目標(biāo)： Goal=動(dòng)作模板： Act_template = 主體能力： Ability= 2022-6-26史忠植 高級(jí)人工智能35主體結(jié)構(gòu)主體結(jié)構(gòu)主

22、體結(jié)構(gòu)需要解決的問(wèn)題包括： 主體由那些模塊組成， 模塊之間如何交互信息， 主體感知到的信息如何影響它的行為和內(nèi)部狀態(tài)， 如何將這些模塊用軟件或硬件的方式組合起來(lái)形成一個(gè)有機(jī)的整體。2022-6-26史忠植 高級(jí)人工智能36主體基本結(jié)構(gòu)主體基本結(jié)構(gòu)環(huán)境主體感知作用黑箱軟件主體2022-6-26史忠植 高級(jí)人工智能37智能主體的工作過(guò)程智能主體的工作過(guò)程環(huán)境交互信息融合信息處理作用交互感知作用2022-6-26史忠植 高級(jí)人工智能38主體骨架程序主體骨架程序function Skeleton-Agent(percept) return actionstatic: memory /* 主體的世界記憶

23、 */memory Update-Memory(memory,percept)action Choose-Best-Action(memory)memory Update-Memory(memory,action)return action2022-6-26史忠植 高級(jí)人工智能39主體的分類(lèi)主體的分類(lèi) 根據(jù)人類(lèi)思維的層次模型，可以將主體分成四類(lèi)： 反應(yīng)主體 形象思維主體 抽象思維主體 復(fù)合式主體 形象思維主體和抽象思維主體也可以合稱(chēng)為認(rèn)知主體2022-6-26史忠植 高級(jí)人工智能40 反應(yīng)主體反應(yīng)主體環(huán)境當(dāng)前世界傳感器動(dòng) 作效應(yīng)器條件-動(dòng)作規(guī)則主體2022-6-26史忠植 高級(jí)人工智能41反應(yīng)

24、主體程序反應(yīng)主體程序function Reactive-Agent(percept) returns action static: rules, /* 一組條件-動(dòng)作規(guī)則 */ state Interpret-Input(percept) rule Rule-Match(state,rules) action Rule-Actionrule return action2022-6-26史忠植 高級(jí)人工智能42認(rèn)知主體認(rèn)知主體環(huán)境信息融合傳感器動(dòng) 作效應(yīng)器主體規(guī) 劃知識(shí)庫(kù)目標(biāo)內(nèi)部狀態(tài)2022-6-26史忠植 高級(jí)人工智能43認(rèn)知主體程序認(rèn)知主體程序function Cognitive-Agent

25、(percept) returns actionstatic: environment, /* 描述當(dāng)前世界環(huán)境 */ kb, /* 知識(shí)庫(kù) */ environment Update-World-Model(environment,percept) state Update-Mental-State(environment,state) action Decision-Making(state,kb) environment Update-World-Model(environment,action) return action2022-6-26史忠植 高級(jí)人工智能44BDIBDI結(jié)構(gòu)結(jié)構(gòu)知

26、識(shí)信念規(guī)劃 意 圖目 標(biāo)愿 望2022-6-26史忠植 高級(jí)人工智能45復(fù)合式主體復(fù)合式主體決策生成規(guī) 劃反 射建 模通 信感 知行 動(dòng)其他智能主體智能主體外部世界預(yù)測(cè)協(xié)作與協(xié)商動(dòng)作請(qǐng)求或應(yīng)答信息一般情況緊急情況和簡(jiǎn)單情況2022-6-26史忠植 高級(jí)人工智能46規(guī)劃模塊規(guī)劃模塊世界的模型（包括其他 主體的模型）經(jīng) 驗(yàn) 庫(kù)目標(biāo)集合局 部 規(guī) 劃 器決 策 生 成重新規(guī)劃規(guī)劃規(guī)劃目標(biāo)2022-6-26史忠植 高級(jí)人工智能47建模模塊建模模塊世界的模型（包括其他 主體的模型）模 型 庫(kù)模 型 生 成 和 維 護(hù)預(yù) 測(cè)規(guī)劃決策生成感 知通 信建模2022-6-26史忠植 高級(jí)人工智能48通信模塊通信

27、模塊詞 法 庫(kù)語(yǔ) 法 庫(kù)詞 義 庫(kù)物理通信語(yǔ)言生成語(yǔ)言理解通信2022-6-26史忠植 高級(jí)人工智能49主體通信主體通信策 略對(duì) 話(huà)消 息黑 板協(xié) 議通信協(xié)作協(xié) 議2022-6-26史忠植 高級(jí)人工智能50主體通信中的主要問(wèn)題主體通信中的主要問(wèn)題 語(yǔ)義：全部有關(guān)的主體必須知道通信語(yǔ)言的語(yǔ)義，消息的語(yǔ)義內(nèi)容知識(shí)是分布式問(wèn)題求解的核心部分。 言語(yǔ)行為：通信語(yǔ)言也是一種動(dòng)作，說(shuō)話(huà)是為了使世界的狀態(tài)發(fā)生改變。 交互協(xié)議：主體之間消息交換的典型模式 通信語(yǔ)言：傳遞消息的標(biāo)準(zhǔn)語(yǔ)法。Foundation for Intelligent Physical Agents 20

28、22-6-26史忠植 高級(jí)人工智能51主體間的消息傳遞主體間的消息傳遞消息發(fā)送/傳輸服務(wù)器轉(zhuǎn)換到傳輸格式從傳輸格式轉(zhuǎn)換消息M言語(yǔ)行為意圖I目標(biāo)GAgent i消息MAgent i2022-6-26史忠植 高級(jí)人工智能52本體論本體論本體論是概念化的明確的表示和描述。對(duì)某一領(lǐng)域中的概念有共同理解，可以提高交流和協(xié)作的效率，從而提高了軟件的重用性。2022-6-26史忠植 高級(jí)人工智能53言語(yǔ)行為言語(yǔ)行為 有關(guān)言語(yǔ)行為理論的研究主要集中在如何劃分不同類(lèi)型的言語(yǔ)行為。 在主體通信語(yǔ)言的研究中，言語(yǔ)行為理論主要用來(lái)考慮主體之間可以交互的信息類(lèi)型。2022-6-26史忠植 高級(jí)人工智能54通信語(yǔ)言通信語(yǔ)

29、言KQML：由美國(guó)ARPA的知識(shí)共享計(jì)劃中提出，規(guī)定了消息格式和消息傳送系統(tǒng)，為多主體系統(tǒng)通信和協(xié)商提供了一種通用框架。ACL：由FIPA制定的一種規(guī)范。與KQML非常相似2022-6-26史忠植 高級(jí)人工智能55KQML一個(gè)例子：(ask-all: senderA: receiverB: in-reply-toido: reply-withidl: languageProlog: ontologyfoo: content“bar (X, Y)”)2022-6-26史忠植 高級(jí)人工智能56FIPA ACL(inform: sender agent1: receiver hpl-auction-

30、server: content (price (bid good02) 150): in-reply-to round-4: reply-with bid04: language s1: ontology hpl-auction)消息結(jié)構(gòu)開(kāi)始通信動(dòng)作類(lèi)型消息參數(shù)消息內(nèi)容表達(dá)式參數(shù)表達(dá)式2022-6-26史忠植 高級(jí)人工智能57FIPAFIPA通信動(dòng)作庫(kù)通信動(dòng)作庫(kù)Accept Proposal接受提議Agree同意Cancel取消Call for Proposal要求提議Confirm確認(rèn)Disconfirm確認(rèn)為否定Failure失敗Inform通知Inform If通知 是否Inform R

31、ef通知 有關(guān)對(duì)象Not Understood不理解2022-6-26史忠植 高級(jí)人工智能58Propagate傳播Propose提議Proxy代理Query If詢(xún)問(wèn) 是否Query Ref詢(xún)問(wèn) 有關(guān)對(duì)象Refuse拒絕（請(qǐng)求）Reject Proposal拒絕提議Request請(qǐng)求Request When請(qǐng)求 某個(gè)條件下執(zhí)行Request Whenever請(qǐng)求 一旦某個(gè)條件成立就執(zhí)行Subscribe預(yù)定詳細(xì)說(shuō)明：/repository/cas.htmlFIPAFIPA通信動(dòng)作庫(kù)通信動(dòng)作庫(kù)2022-6-26史忠植 高級(jí)人工智能59XMLeXtensibl

32、e Markup Language 可擴(kuò)展標(biāo)記語(yǔ)言可擴(kuò)展標(biāo)記語(yǔ)言 XML是用于標(biāo)記電子文件使其具有結(jié)構(gòu)性的標(biāo)記語(yǔ)言。XML文件本身只是將文件資料結(jié)構(gòu)化。例如：下面的ACL消息(inform:sender jklabrou:receiver grosof:content (CPU libretto50 pentium):ontology laptop:language kif)2022-6-26史忠植 高級(jí)人工智能60informjklabrougrosof轉(zhuǎn)換為轉(zhuǎn)換為XMLXML格式格式2022-6-26史忠植 高級(jí)人工智能61laptop(CPU libretto50 pentium)kif

33、轉(zhuǎn)換為轉(zhuǎn)換為XMLXML格式格式2022-6-26史忠植 高級(jí)人工智能62主體的協(xié)調(diào)與協(xié)作主體的協(xié)調(diào)與協(xié)作協(xié)調(diào)(coordination)與協(xié)作(cooperation)是多主體研究的核心問(wèn)題之一。 協(xié)調(diào)是指一組智能主體完成一些集體活動(dòng)時(shí)相互作用的性質(zhì)。 協(xié)作是非對(duì)抗的主體之間保持行為協(xié)調(diào)的一個(gè)特例。2022-6-26史忠植 高級(jí)人工智能63協(xié)協(xié) 調(diào)調(diào)多主體系統(tǒng)中的協(xié)調(diào)是指多個(gè)主體為了以一致、和諧的方式工作而進(jìn)行交互的過(guò)程。進(jìn)行協(xié)調(diào)是希望避免主體之間的死鎖或活鎖。 死鎖指多個(gè)主體無(wú)法進(jìn)行各自的下一步動(dòng)作； 活鎖指多個(gè)主體不斷工作卻無(wú)任何進(jìn)展。2022-6-26史忠植 高級(jí)人工智能64協(xié)作目前針

34、對(duì)主體協(xié)作的研究大體上可分為兩類(lèi)： 將其它領(lǐng)域研究多實(shí)體行為的方法和技術(shù)用于主體協(xié)作的研究。如對(duì)策論和力學(xué)研究。1) 從主體的目標(biāo)、意圖、規(guī)劃等心智態(tài)度出發(fā)來(lái)研究多主體間的協(xié)作。2022-6-26史忠植 高級(jí)人工智能65協(xié)作協(xié)作協(xié)作的動(dòng)機(jī)： 某個(gè)主體相信通過(guò)協(xié)作能帶來(lái)好處（如提高效率，完成以往單獨(dú)無(wú)法完成的任務(wù)）1) 多個(gè)主體在交流的過(guò)程中，發(fā)現(xiàn)它們能夠通過(guò)協(xié)作來(lái)實(shí)現(xiàn)更大的目標(biāo)。2022-6-26史忠植 高級(jí)人工智能66協(xié)作過(guò)程 產(chǎn)生需求、確定目標(biāo) 協(xié)作規(guī)劃、求解協(xié)作結(jié)構(gòu) 尋求協(xié)作伙伴 選擇協(xié)作方案 實(shí)現(xiàn)目標(biāo) 評(píng)估結(jié)果2022-6-26史忠植 高級(jí)人工智能67協(xié)作模式從社會(huì)心理學(xué)的角度看，多主

35、體之間的協(xié)作情從社會(huì)心理學(xué)的角度看，多主體之間的協(xié)作情形大致可分為：形大致可分為： 協(xié)作型：同時(shí)將自己的利益放在第二位。協(xié)作型：同時(shí)將自己的利益放在第二位。 自私型：同時(shí)將協(xié)作放在第二位。自私型：同時(shí)將協(xié)作放在第二位。 完全自私型：不考慮任何協(xié)作。完全自私型：不考慮任何協(xié)作。 完全協(xié)作型：不考慮自身利益。完全協(xié)作型：不考慮自身利益。 協(xié)作與自私相混合型。協(xié)作與自私相混合型。2022-6-26史忠植 高級(jí)人工智能68協(xié)作策略 計(jì)算生態(tài)學(xué)計(jì)算生態(tài)學(xué) 對(duì)策論對(duì)策論 規(guī)劃規(guī)劃2022-6-26史忠植 高級(jí)人工智能69計(jì)算生態(tài)學(xué) 80 80年代末，在計(jì)算機(jī)中出現(xiàn)了一個(gè)嶄新的年代末，在計(jì)算機(jī)中出現(xiàn)了一個(gè)嶄

36、新的學(xué)科學(xué)科-計(jì)算生態(tài)學(xué)計(jì)算生態(tài)學(xué)(the ecolog of (the ecolog of computation)computation)。計(jì)算生態(tài)學(xué)是研究關(guān)于開(kāi)放。計(jì)算生態(tài)學(xué)是研究關(guān)于開(kāi)放系統(tǒng)中訣定計(jì)算結(jié)點(diǎn)的行為與資源使用的交系統(tǒng)中訣定計(jì)算結(jié)點(diǎn)的行為與資源使用的交互過(guò)程的學(xué)科。它摒棄了封閉、靜止地處理互過(guò)程的學(xué)科。它摒棄了封閉、靜止地處理問(wèn)題的傳統(tǒng)算法，將世界看作是開(kāi)放的、進(jìn)問(wèn)題的傳統(tǒng)算法，將世界看作是開(kāi)放的、進(jìn)化的、并發(fā)的化的、并發(fā)的, , 通過(guò)多種協(xié)作處理問(wèn)題的通過(guò)多種協(xié)作處理問(wèn)題的生態(tài)系統(tǒng)生態(tài)系統(tǒng)(ecosystem)(ecosystem)加以研究。它的進(jìn)加以研究。它的進(jìn)展與開(kāi)放信

37、息系統(tǒng)的研究息息相關(guān)。展與開(kāi)放信息系統(tǒng)的研究息息相關(guān)。2022-6-26史忠植 高級(jí)人工智能70計(jì)算生態(tài)學(xué) 計(jì)算生態(tài)學(xué)將計(jì)算系統(tǒng)看作是一個(gè)生態(tài)系統(tǒng)，它引計(jì)算生態(tài)學(xué)將計(jì)算系統(tǒng)看作是一個(gè)生態(tài)系統(tǒng)，它引進(jìn)了許多生物的機(jī)制，如變異進(jìn)了許多生物的機(jī)制，如變異(mutation)(mutation)即物種的變化。即物種的變化。這些變化導(dǎo)致生命基因的改變，從而形成物種的多樣性，這些變化導(dǎo)致生命基因的改變，從而形成物種的多樣性，增強(qiáng)了適應(yīng)環(huán)境的能力。這類(lèi)變異策略成為人工智能系增強(qiáng)了適應(yīng)環(huán)境的能力。這類(lèi)變異策略成為人工智能系統(tǒng)提高其自身能力的一種方法。統(tǒng)提高其自身能力的一種方法。 Lenat Lenat與與Br

38、ownBrown成功地將變異機(jī)制引入他們的成功地將變異機(jī)制引入他們的AMAM與與EuriskoEurisko系統(tǒng)中系統(tǒng)中, , 通過(guò)小型通過(guò)小型LispLisp程序的語(yǔ)法變異發(fā)現(xiàn)數(shù)程序的語(yǔ)法變異發(fā)現(xiàn)數(shù)學(xué)概念。他們認(rèn)為未來(lái)成功的系統(tǒng)應(yīng)該是一系列進(jìn)化的、學(xué)概念。他們認(rèn)為未來(lái)成功的系統(tǒng)應(yīng)該是一系列進(jìn)化的、自組織的符號(hào)知識(shí)結(jié)構(gòu)的自組織的符號(hào)知識(shí)結(jié)構(gòu)的“社會(huì)社會(huì)” ” 系統(tǒng)。系統(tǒng)。2022-6-26史忠植 高級(jí)人工智能71生物生態(tài)模型 這是最著名的生態(tài)系統(tǒng)，具有典型的進(jìn)化特征這是最著名的生態(tài)系統(tǒng)，具有典型的進(jìn)化特征和層次性。這種特性反映在和層次性。這種特性反映在“食物鏈?zhǔn)澄镦湣敝小?duì)于復(fù)中。對(duì)于復(fù)雜的生

39、物生態(tài)系統(tǒng)而言，各物種組成了緊密相連的雜的生物生態(tài)系統(tǒng)而言，各物種組成了緊密相連的網(wǎng)絡(luò)食物網(wǎng)。這個(gè)系統(tǒng)的主要角色是捕食者與被網(wǎng)絡(luò)食物網(wǎng)。這個(gè)系統(tǒng)的主要角色是捕食者與被食者。生命依賴(lài)于生命，共同進(jìn)化，由小的生態(tài)環(huán)食者。生命依賴(lài)于生命，共同進(jìn)化，由小的生態(tài)環(huán)境組成大的生態(tài)系統(tǒng)。境組成大的生態(tài)系統(tǒng)。2022-6-26史忠植 高級(jí)人工智能72物種進(jìn)化模型 物種進(jìn)化的物種進(jìn)化的“復(fù)制者復(fù)制者”是基因。從門(mén)德?tīng)柕闹参镞z傳研是基因。從門(mén)德?tīng)柕闹参镞z傳研究到現(xiàn)代遺傳學(xué)的成果，都說(shuō)明了在物種進(jìn)化過(guò)程中，基因究到現(xiàn)代遺傳學(xué)的成果，都說(shuō)明了在物種進(jìn)化過(guò)程中，基因的組合與變異起著關(guān)鍵作用。在一個(gè)物種的某一群體中基因的

40、組合與變異起著關(guān)鍵作用。在一個(gè)物種的某一群體中基因的集合稱(chēng)為基因池。生物組織是基因的載體。如果環(huán)境變化，的集合稱(chēng)為基因池。生物組織是基因的載體。如果環(huán)境變化，選擇的機(jī)制就會(huì)改變。這種變化必然引起基因池的變化。特選擇的機(jī)制就會(huì)改變。這種變化必然引起基因池的變化。特定種群的基因變化稱(chēng)為基因流。定種群的基因變化稱(chēng)為基因流。 一個(gè)物種總是不斷地經(jīng)歷隔絕、基因流動(dòng)、變化的循環(huán)。一個(gè)物種總是不斷地經(jīng)歷隔絕、基因流動(dòng)、變化的循環(huán)。開(kāi)始時(shí)，一組地理上隔絕的群體自己孤立地發(fā)展，基因在內(nèi)開(kāi)始時(shí)，一組地理上隔絕的群體自己孤立地發(fā)展，基因在內(nèi)部快速地流動(dòng)。隨著開(kāi)放，通過(guò)交流和競(jìng)爭(zhēng)，優(yōu)勝劣汰。部快速地流動(dòng)。隨著開(kāi)放，通

41、過(guò)交流和競(jìng)爭(zhēng)，優(yōu)勝劣汰。2022-6-26史忠植 高級(jí)人工智能73經(jīng)濟(jì)模型 經(jīng)濟(jì)系統(tǒng)在某種意義上類(lèi)似于生物生態(tài)系統(tǒng)。經(jīng)濟(jì)系統(tǒng)在某種意義上類(lèi)似于生物生態(tài)系統(tǒng)。在商品市場(chǎng)和理想市場(chǎng)中，進(jìn)化決定于經(jīng)濟(jì)實(shí)體的在商品市場(chǎng)和理想市場(chǎng)中，進(jìn)化決定于經(jīng)濟(jì)實(shí)體的決策。選擇機(jī)制是市場(chǎng)獎(jiǎng)勵(lì)機(jī)制。決策。選擇機(jī)制是市場(chǎng)獎(jiǎng)勵(lì)機(jī)制。 進(jìn)化是快速的，企業(yè)與消費(fèi)者之間、企業(yè)之間進(jìn)化是快速的，企業(yè)與消費(fèi)者之間、企業(yè)之間主要是一種互相依賴(lài)的合作關(guān)系。決策者為了追求主要是一種互相依賴(lài)的合作關(guān)系。決策者為了追求長(zhǎng)遠(yuǎn)利益，可以采取各種有效的方法，甚至可以暫長(zhǎng)遠(yuǎn)利益，可以采取各種有效的方法，甚至可以暫時(shí)做賠本買(mǎi)賣(mài)。時(shí)做賠本買(mǎi)賣(mài)。2022-

42、6-26史忠植 高級(jí)人工智能74協(xié)商模型Zlotkin的面向領(lǐng)域的協(xié)商理論的面向領(lǐng)域的協(xié)商理論Zlotkin的協(xié)商理論假設(shè)：的協(xié)商理論假設(shè)： 各主體追求本身效用最大。各主體追求本身效用最大。 知識(shí)完備。知識(shí)完備。 無(wú)歷史信息。無(wú)歷史信息。 目標(biāo)集固定。目標(biāo)集固定。 協(xié)商在兩主體之間同時(shí)進(jìn)行。協(xié)商在兩主體之間同時(shí)進(jìn)行。 主體操作集相同。主體操作集相同。 世界僅當(dāng)主體操作之后發(fā)生變化。世界僅當(dāng)主體操作之后發(fā)生變化。2022-6-26史忠植 高級(jí)人工智能75面向領(lǐng)域的協(xié)商理論在協(xié)商過(guò)程中，若存在一個(gè)雙方滿(mǎn)意的分配，在協(xié)商過(guò)程中，若存在一個(gè)雙方滿(mǎn)意的分配，可以得到一個(gè)聯(lián)合規(guī)劃可以得到一個(gè)聯(lián)合規(guī)劃, ,

43、 使協(xié)商終止的條件使協(xié)商終止的條件是：是：(1) (1) 達(dá)成協(xié)議：如果達(dá)成協(xié)議：如果 Utility(P(i,t) Utility(P(i,t) Utility(P(i,t-1), Utility(P(i,t-1), 這一協(xié)商過(guò)程將在有這一協(xié)商過(guò)程將在有限步內(nèi)結(jié)束。限步內(nèi)結(jié)束。(2) (2) 沖突：沖突： 如果如果 Utility(P(i,t) = Utility(P(i,t) = Utility(P(i,t-1), Utility(P(i,t-1), 則無(wú)法達(dá)成協(xié)議。則無(wú)法達(dá)成協(xié)議。2022-6-26史忠植 高級(jí)人工智能76最佳平衡傳統(tǒng)的協(xié)商是基于傳統(tǒng)的協(xié)商是基于Nash平衡的平衡的,它的

44、缺點(diǎn)是它的缺點(diǎn)是Nash 平衡產(chǎn)生多個(gè)平衡點(diǎn)平衡產(chǎn)生多個(gè)平衡點(diǎn), 對(duì)結(jié)果約束較少。對(duì)結(jié)果約束較少。Kraus使用使用Rubinstein的的“最佳最佳”平衡平衡(Perfect Equilibrium, 簡(jiǎn)稱(chēng)簡(jiǎn)稱(chēng)P.E.)理論理論, 建立了一種基于建立了一種基于P.E.的協(xié)商方法的協(xié)商方法, 需要在協(xié)需要在協(xié)商的任一階段都產(chǎn)生平衡商的任一階段都產(chǎn)生平衡, 即在協(xié)商的任一階段即在協(xié)商的任一階段, 假設(shè)假設(shè) 主體主體 A 使用使用P.E. 策略策略, 則則 主體主體 B 除了自己的除了自己的 P.E., 策略外沒(méi)有更好的策略可遵循。故若策略外沒(méi)有更好的策略可遵循。故若有唯一的有唯一的 P.E.,

45、并假定主體要使用該策略并假定主體要使用該策略, 則它在協(xié)商的每一階段都只用則它在協(xié)商的每一階段都只用這一策略?？勺C明這一策略?？勺C明, 存在唯一的存在唯一的 P.E.,在第一階段后就可以終止協(xié)商。在第一階段后就可以終止協(xié)商。Kraus 還將對(duì)時(shí)間的偏好引入這一理論中。結(jié)果表明還將對(duì)時(shí)間的偏好引入這一理論中。結(jié)果表明, 時(shí)間偏好可以提時(shí)間偏好可以提高協(xié)商效率高協(xié)商效率, 并僅對(duì)某一主體有利。并僅對(duì)某一主體有利。 這一理論對(duì)于主體的構(gòu)造和主體之這一理論對(duì)于主體的構(gòu)造和主體之間的協(xié)作很有用處間的協(xié)作很有用處, 如果為主體提供唯一的如果為主體提供唯一的P.E.策略策略, 并通知其他主體并通知其他主體,

46、 則則其他主體的最佳選擇也是其他主體的最佳選擇也是 P.E. 策略。策略。該理論的缺陷是該理論的缺陷是:缺乏動(dòng)態(tài)性特色缺乏動(dòng)態(tài)性特色,應(yīng)用面窄應(yīng)用面窄,因?yàn)楸M管存在唯一的因?yàn)楸M管存在唯一的P.E, 但但如何求出仍未得到解決。如何求出仍未得到解決。2022-6-26史忠植 高級(jí)人工智能77集中式協(xié)商方法 Ephrati使用了一種集中式的協(xié)商方法使用了一種集中式的協(xié)商方法, 用一個(gè)用一個(gè)“ master agent ”或組投票機(jī)制以達(dá)成協(xié)議。在這或組投票機(jī)制以達(dá)成協(xié)議。在這種方法中種方法中, 一組主體的協(xié)作與組規(guī)劃進(jìn)程相關(guān)。一組主體的協(xié)作與組規(guī)劃進(jìn)程相關(guān)。 Ephrati使用一種動(dòng)態(tài)的、迭代的搜索

47、過(guò)程使用一種動(dòng)態(tài)的、迭代的搜索過(guò)程, 通過(guò)一通過(guò)一組約束組約束,使主體遞增式地構(gòu)成一個(gè)最大使主體遞增式地構(gòu)成一個(gè)最大“社會(huì)效用社會(huì)效用”規(guī)劃。在每一步規(guī)劃。在每一步, 各主體對(duì)于組規(guī)劃的下一個(gè)聯(lián)合各主體對(duì)于組規(guī)劃的下一個(gè)聯(lián)合行動(dòng)投票。行動(dòng)投票。 使用這一技術(shù)使用這一技術(shù),主體無(wú)需完整地展示其主體無(wú)需完整地展示其偏好偏好, 可選狀態(tài)集在投票之前產(chǎn)生?？蛇x狀態(tài)集在投票之前產(chǎn)生。2022-6-26史忠植 高級(jí)人工智能78開(kāi)放環(huán)境多智能體協(xié)作方法 Osawa (1) 需求者(requestor)向公告板主體發(fā)送需求建議RFP (2) 空閑主體向公告板主體申請(qǐng)一個(gè)RFP (3) 公告板將RFP發(fā)到提出申

48、請(qǐng)的空閑主體 (4) 空閑主體產(chǎn)生個(gè)體規(guī)劃 (5) 空閑主體將其規(guī)劃發(fā)給需求者 (6) 需求者調(diào)查協(xié)作的可能 (7) 需求者發(fā)送協(xié)作獎(jiǎng)勵(lì) (8) 申請(qǐng)者組成協(xié)作規(guī)劃2022-6-26史忠植 高級(jí)人工智能79開(kāi)放環(huán)境多智能體協(xié)作方法其效用值可用下式計(jì)算：其效用值可用下式計(jì)算： utility(a,g)=worth(a,g)-cost(plan(a,g) 效用的平均是協(xié)作的原則。效用的平均是協(xié)作的原則。盡管盡管Osawa在一定程度上解決了開(kāi)放環(huán)境中主體協(xié)在一定程度上解決了開(kāi)放環(huán)境中主體協(xié)作的問(wèn)題作的問(wèn)題, 但將各主體效用簡(jiǎn)單相加再平均的方法但將各主體效用簡(jiǎn)單相加再平均的方法仍然太弱仍然太弱, 因?yàn)?/p>

49、主體效用僅是主體本身對(duì)目標(biāo)偏好因?yàn)橹黧w效用僅是主體本身對(duì)目標(biāo)偏好的一種排序關(guān)系的一種排序關(guān)系, 不同主體效用一般不能用數(shù)值比不同主體效用一般不能用數(shù)值比較。較。2022-6-26史忠植 高級(jí)人工智能80交互協(xié)議主體之間的會(huì)話(huà)常常形成典型模式，這種主體之間的會(huì)話(huà)常常形成典型模式，這種情況下某些消息序列是可知的，這些消息情況下某些消息序列是可知的，這些消息交換的典型模式稱(chēng)為協(xié)議。交換的典型模式稱(chēng)為協(xié)議。主體間交互的理想情況：主體充分地理解主體間交互的理想情況：主體充分地理解消息的含意和意圖，然后根據(jù)自身的信念、消息的含意和意圖，然后根據(jù)自身的信念、目標(biāo)等心智狀態(tài)，做出相應(yīng)的回答目標(biāo)等心智狀態(tài)，做出

50、相應(yīng)的回答比較實(shí)際的實(shí)現(xiàn)：預(yù)先規(guī)范這些協(xié)議，規(guī)比較實(shí)際的實(shí)現(xiàn)：預(yù)先規(guī)范這些協(xié)議，規(guī)定好消息的順序。定好消息的順序。2022-6-26史忠植 高級(jí)人工智能81FIPA 英國(guó)英國(guó)拍賣(mài)拍賣(mài)協(xié)議協(xié)議2022-6-26史忠植 高級(jí)人工智能82規(guī)劃 規(guī)劃是主體對(duì)動(dòng)作進(jìn)行推理的一種主要形式，它很大程度上體現(xiàn)了主體的智能性。同時(shí)，規(guī)劃也是描述主體行為的主要方式。 規(guī)劃是為了建立一個(gè)控制算法，使智能主體能夠?yàn)閷?shí)現(xiàn)目標(biāo)，對(duì)動(dòng)作過(guò)程進(jìn)行綜合。2022-6-26史忠植 高級(jí)人工智能83經(jīng)典規(guī)劃問(wèn)題經(jīng)典規(guī)劃問(wèn)題經(jīng)典的規(guī)劃理論認(rèn)為規(guī)劃要解決的問(wèn)題（即規(guī)劃的輸入）是：用某種形式語(yǔ)言描述的初始世界狀態(tài)用某種形式語(yǔ)言描述的主體

51、目標(biāo)用某種形式語(yǔ)言描述的主體可能采用的動(dòng)作，通常也叫做領(lǐng)域知識(shí)輸出是：可以在某個(gè)滿(mǎn)足初始狀態(tài)描述的世界中執(zhí)行并達(dá)到主體目標(biāo)的一個(gè)動(dòng)作序列2022-6-26史忠植 高級(jí)人工智能84經(jīng)典規(guī)劃的假設(shè)經(jīng)典規(guī)劃的假設(shè)原子執(zhí)行時(shí)間確定性結(jié)果主體全知主體唯一能動(dòng)性2022-6-26史忠植 高級(jí)人工智能85經(jīng)典規(guī)劃系統(tǒng)經(jīng)典規(guī)劃系統(tǒng)人們對(duì)經(jīng)典規(guī)劃算法進(jìn)行了大量的研人們對(duì)經(jīng)典規(guī)劃算法進(jìn)行了大量的研究，提出了許多有效的算法，如究，提出了許多有效的算法，如STRIPSSTRIPS，TWEAKTWEAK，UCPOPUCPOP和和SNLPSNLP等。等。最近，其它領(lǐng)域中的一些有效算法被最近，其它領(lǐng)域中的一些有效算法被引入

52、到規(guī)劃中來(lái)。新的進(jìn)展主要在引入到規(guī)劃中來(lái)。新的進(jìn)展主要在GraphPlanGraphPlan和和SATPLANSATPLAN方面。方面。 2022-6-26史忠植 高級(jí)人工智能86STRIPS表示法表示法世界狀態(tài)：世界狀態(tài)：一個(gè)世界狀態(tài)（或簡(jiǎn)稱(chēng)為狀一個(gè)世界狀態(tài)（或簡(jiǎn)稱(chēng)為狀態(tài)）是一組謂詞的集合。態(tài)）是一組謂詞的集合。目標(biāo)：表示世界狀態(tài)的謂詞的合取。目標(biāo)：表示世界狀態(tài)的謂詞的合取。動(dòng)作：動(dòng)作用前提條件和動(dòng)作效果來(lái)表動(dòng)作：動(dòng)作用前提條件和動(dòng)作效果來(lái)表示。示。前提條件：動(dòng)作執(zhí)行前必須滿(mǎn)足的前提條件：動(dòng)作執(zhí)行前必須滿(mǎn)足的狀態(tài)。狀態(tài)。動(dòng)作效果：動(dòng)作執(zhí)行后可以保證為動(dòng)作效果：動(dòng)作執(zhí)行后可以保證為真的狀態(tài)。真

53、的狀態(tài)。2022-6-26史忠植 高級(jí)人工智能87STRIPS表示法表示法-規(guī)劃規(guī)劃動(dòng)作模板：表示一組可能的動(dòng)作，即包含自由變量動(dòng)作模板：表示一組可能的動(dòng)作，即包含自由變量的動(dòng)作。的動(dòng)作。動(dòng)作步驟：表示一個(gè)具體的動(dòng)作，由動(dòng)作模板中的動(dòng)作步驟：表示一個(gè)具體的動(dòng)作，由動(dòng)作模板中的變量添加約束得到。變量添加約束得到。規(guī)劃：規(guī)劃用動(dòng)作步驟和動(dòng)作步驟上的約束來(lái)表示。規(guī)劃：規(guī)劃用動(dòng)作步驟和動(dòng)作步驟上的約束來(lái)表示。約束包括：約束包括：動(dòng)作步驟間的順序約束，根據(jù)順序約束可以分為動(dòng)作步驟間的順序約束，根據(jù)順序約束可以分為全序規(guī)劃和偏序規(guī)劃。全序規(guī)劃和偏序規(guī)劃。動(dòng)作步驟中變量或常量之間的等價(jià)、不等價(jià)、大動(dòng)作步驟中

54、變量或常量之間的等價(jià)、不等價(jià)、大于、小于等約束。于、小于等約束。2022-6-26史忠植 高級(jí)人工智能88經(jīng)典規(guī)劃舉例經(jīng)典規(guī)劃舉例ABBA初始狀態(tài)目標(biāo)狀態(tài)2022-6-26史忠植 高級(jí)人工智能89規(guī)劃表示規(guī)劃表示初始狀態(tài)：On(table, A), On(A, B)目標(biāo)狀態(tài)：On(B, A), On(table, B)基本知識(shí)：動(dòng)作模板： Move(?Obj, ?dest) precondition：Clear(?Obj) effect：delete：On(?Obj, ?src) add：On(?Obj, ?dest)2022-6-26史忠植 高級(jí)人工智能90希望得到的規(guī)劃結(jié)果希望得到的規(guī)劃結(jié)

55、果希望得到的結(jié)果：第一步：Move(B, table)第二步：Move(A, B)實(shí)際的表示為：Step1.Action=Move, Step1.Obj=B, Step1.dest=table,Step2.Action=Move, Step2.Obj=A, Step2.dest=B,Step1 Step22022-6-26史忠植 高級(jí)人工智能91規(guī)劃算法規(guī)劃算法 規(guī)劃算法實(shí)質(zhì)上是一種搜索算法。搜索一個(gè)動(dòng)作規(guī)劃算法實(shí)質(zhì)上是一種搜索算法。搜索一個(gè)動(dòng)作步驟序列，使得經(jīng)過(guò)這個(gè)動(dòng)作步驟的作用后，世步驟序列，使得經(jīng)過(guò)這個(gè)動(dòng)作步驟的作用后，世界狀態(tài)由初始狀態(tài)變化為目標(biāo)狀態(tài)。算法應(yīng)包含界狀態(tài)由初始狀態(tài)變化為目

56、標(biāo)狀態(tài)。算法應(yīng)包含以下功能：以下功能：選擇動(dòng)作：選擇當(dāng)前狀態(tài)下能夠執(zhí)行的動(dòng)作。選擇動(dòng)作：選擇當(dāng)前狀態(tài)下能夠執(zhí)行的動(dòng)作。變量綁定（匹配）：根據(jù)當(dāng)前狀態(tài)，對(duì)動(dòng)作變量綁定（匹配）：根據(jù)當(dāng)前狀態(tài)，對(duì)動(dòng)作中的變量進(jìn)行約束。中的變量進(jìn)行約束。回溯：發(fā)現(xiàn)死鎖狀態(tài)后，可以回退到以前的回溯：發(fā)現(xiàn)死鎖狀態(tài)后，可以回退到以前的某個(gè)狀態(tài)。某個(gè)狀態(tài)。2022-6-26史忠植 高級(jí)人工智能92規(guī)劃搜索規(guī)劃搜索初始狀態(tài)狀態(tài)1-1狀態(tài)1-n狀態(tài)m-k目標(biāo)狀態(tài)動(dòng)作1-1動(dòng)作1-n動(dòng)作m-k2022-6-26史忠植 高級(jí)人工智能93規(guī)劃結(jié)果規(guī)劃結(jié)果初始狀態(tài)： On(table, A), On(A, B)On(table, A),

57、 On(table, B)目標(biāo)狀態(tài)：On(B, A), On(table, B)Move(B, table)Move(A, B)2022-6-26史忠植 高級(jí)人工智能94沖突沖突一個(gè)規(guī)劃正確的必要條件是，在規(guī)劃的每個(gè)實(shí)現(xiàn)中，每個(gè)動(dòng)作的每個(gè)前提條件在動(dòng)作執(zhí)行之前都滿(mǎn)足。造成規(guī)劃不正確的原因是一個(gè)動(dòng)作會(huì)破壞其他動(dòng)作間的因果鏈，即沖突。2022-6-26史忠植 高級(jí)人工智能95因果鏈因果鏈因果鏈描述一個(gè)動(dòng)作為另一個(gè)動(dòng)作建立一個(gè)前提條件。因果鏈描述一個(gè)動(dòng)作為另一個(gè)動(dòng)作建立一個(gè)前提條件。一個(gè)規(guī)劃中，動(dòng)作一個(gè)規(guī)劃中，動(dòng)作 E 和動(dòng)作和動(dòng)作 U 之間存在因果鏈，當(dāng)且僅當(dāng)之間存在因果鏈，當(dāng)且僅當(dāng)1、 ，即，即

58、 E 和和 U 之間有順序約束；之間有順序約束；2、 使得使得 ，其中，其中 ，即，即E的一個(gè)效果為的一個(gè)效果為U的一個(gè)前提；的一個(gè)前提；3、 ，如果，如果 ， 并且并且 ，那么，那么 并且并且 ，即發(fā)生在，即發(fā)生在E和和U之間的所有動(dòng)作都不影響之間的所有動(dòng)作都不影響 。OOUE)(EEEe )(UEpeUUPp T)(TE )(UT TTEe )(UTpe )(UTpeUp2022-6-26史忠植 高級(jí)人工智能96沖突沖突沖突描述的是一個(gè)因果鏈被其它規(guī)劃中的某些動(dòng)作破壞。設(shè)存在因果鏈 和另一個(gè)動(dòng)作C，如果1、 并且 ，即C可能在E和U之間執(zhí)行；2、 使得 ，即C的效果之一 可能破壞那么稱(chēng)C為

59、的 一個(gè)威脅。當(dāng)C在E和U之間被執(zhí)行時(shí)，就發(fā)生沖突。 UpEU,)(EC )(CU CCEe )(UCpeCeUpUpEU,2022-6-26史忠植 高級(jí)人工智能97沖突舉例沖突舉例ABB初始狀態(tài)目標(biāo)狀態(tài)CACAC沖突狀態(tài)B2022-6-26史忠植 高級(jí)人工智能98沖突描述沖突描述規(guī)劃：Step1=Move(?obj,?dest), Step1.obj=C, Step1.destB;Step2=Move(?obj,?dest), Step2.obj=B, Step2.dest=Table;Step3=Move(?obj,?dest), Step3.obj=A, Step3.dest=B;Ste

60、p4=Move(?obj,?dest), Step4.obj=C, Step4.dest=A;Step1Step2, Step2Step3, Step3Step4當(dāng)按照下面的約束執(zhí)行時(shí)，發(fā)生沖突：Step1.dest=AStep3無(wú)法執(zhí)行。2022-6-26史忠植 高級(jí)人工智能99沖突消解方法沖突消解方法沖突威脅到規(guī)劃的正確性，消解沖突的方法就是在規(guī)劃之間添加新的約束，破壞沖突產(chǎn)生的條件。Chapman闡明了一個(gè)充分必要的沖突消解集合，其中包括“升級(jí)”、“降級(jí)”、“分離”和“引入修復(fù)”四種約束。設(shè)動(dòng)作的C一個(gè)效果 威脅因果鏈 ，那么下列任何一個(gè)約束對(duì)于消解它都是充分的：（1）升級(jí)：加入順序約束