第15章-主體計算

2023/2/3史忠植高級人工智能1高級人工智能第十四章

主體計算

史忠植

中國科學院計算技術所2023/2/3史忠植高級人工智能2內(nèi)容提要14.1概述14.2分布式問題求解14.3主體14.4主體理論14.5主體結構14.6主體通信14.7主體的協(xié)調(diào)與協(xié)作14.8多主體環(huán)境MAGE2023/2/3史忠植高級人工智能3概述分布式人工智能主要研究在邏輯上或物理上分散的智能系統(tǒng)如何并行的、相互協(xié)作地實現(xiàn)問題求解。兩種解決問題的方法：自頂向下：分布式問題求解自底向上：基于主體的方法2023/2/3史忠植高級人工智能4分布智能系統(tǒng)的特色系統(tǒng)中的數(shù)據(jù)、知識,以及控制不但在邏輯上,而且在物理上是分布的,既沒有全局控制,也沒有全局的數(shù)據(jù)存儲。各個求解機構由計算機網(wǎng)絡互連,在問題求解過程中,通信代價要比求解問題的代價低得多。系統(tǒng)中諸機構能夠相互協(xié)作,來求解單個機構難以解決,甚至不能解決的任務。2023/2/3史忠植高級人工智能5分布智能系統(tǒng)的主要優(yōu)點提高問題求解能力。提高問題求解效率。擴大應用范圍。降低軟件的復雜性。2023/2/3史忠植高級人工智能6分布式人工智能分布式人工智能的研究可以追溯到70年代末期。早期分布式人工智能的研究主要是分布式問題求解，其目標是要創(chuàng)建大粒度的協(xié)作群體，它們之間共同工作以對某一問題進行求解。2023/2/3史忠植高級人工智能7合同網(wǎng)

1980年Davis和Smith提出了合同網(wǎng)(CNET)CNET使用投標---合同方式實現(xiàn)任務在多個節(jié)點上的分配。合同網(wǎng)系統(tǒng)的重要貢獻在于提出了通過相互選擇和達成協(xié)議的協(xié)商過程實現(xiàn)分布式任務分配和控制的思想。2023/2/3史忠植高級人工智能8分布式車輛監(jiān)控測試系統(tǒng)

DVMT1980年麻薩諸塞大學的Lesser,Corkill和Durfee等人主持研制DVMT該系統(tǒng)對市區(qū)內(nèi)行駛的車輛軌跡進行監(jiān)控,并以此環(huán)境為基礎,對分布式問題求解系統(tǒng)中許多技術問題進行研究。DVMT是以分布式傳感網(wǎng)絡數(shù)據(jù)解釋為背景，對復雜的黑板問題求解系統(tǒng)之間的相互作用進行了研究，提供了抽象和模型化分布式系統(tǒng)行為的方法。2023/2/3史忠植高級人工智能9ACTOR模型1983年Hewitt和他的同事們研制了基于ACTOR模型的并發(fā)程序設計系統(tǒng)。ACTOR模型提供了分布式系統(tǒng)中并行計算理論和一組專家或ACTOR獲得智能行為的能力。在1991年Hewitt提出開放信息系統(tǒng)語義,指出競爭、承諾、協(xié)作、協(xié)商等性質(zhì)應作為分布式人工智能的科學基礎，試圖為分布式人工智能的理論研究提供新的基礎。2023/2/3史忠植高級人工智能10MACE系統(tǒng)是一個實驗型的分布式人工智能系統(tǒng)開發(fā)環(huán)境(Gasser1987)。MACE中每一個計算單元都稱作主體，它們具有知識表示和推理能力，主體之間通過消息傳送進行通信。MACE是一個類面向對象環(huán)境，但避開了并發(fā)對象系統(tǒng)中難于理解和實現(xiàn)的繼承問題。MACE的各個機構并行計算,并提供了描述機構的描述語言,具有跟蹤的demons機制。該課題研究的重點是在實際并行環(huán)境下運行分布式人工智能系統(tǒng)，保持概念的清晰性。2023/2/3史忠植高級人工智能11分布式運輸調(diào)度系統(tǒng)DTDS-I1989年清華大學石純一等主持研制了分布式運輸調(diào)度系統(tǒng)DTDS-I(石純一1989)。該系統(tǒng)以運輸調(diào)度為背景，提出了分布式問題求解系統(tǒng)的體系結構，對問題分解、任務分布算法和基于元級通信的協(xié)作機制等方面進行了探討。2023/2/3史忠植高級人工智能12分布式知識處理系統(tǒng)DKPS1990中國科學院計算技術研究所史忠植等研究了分布式知識處理系統(tǒng)DKPS。該系統(tǒng)采用邏輯------對象知識模型，研究了知識共享和協(xié)作求解等問題。2023/2/3史忠植高級人工智能13多主體系統(tǒng)

90年代，多主體系統(tǒng)Multiagentsystems)的研究成為分布式人工智能研究的熱點。多主體系統(tǒng)主要研究自主的智能主體之間智能行為的協(xié)調(diào)，為了一個共同的全局目標，也可能是關于各自的不同目標，共享有關問題和求解方法的知識，協(xié)作進行問題求解?；谥悄苤黧w的概念，人們提出了一種新的人工智能定義：“人工智能是計算機科學的一個分支，它的目標是構造能表現(xiàn)出一定智能行為的主體”。所以，智能主體的研究應該是人工智能的核心問題。斯坦福大學計算機科學系的Hayes-Roth在IJCAI'95的特邀報告中談到：“智能的計算機主體既是人工智能最初的目標，也是人工智能最終的目標。”2023/2/3史忠植高級人工智能14多主體系統(tǒng)關于主體的研究不僅受到了人工智能研究人員的關注，也吸引了數(shù)據(jù)通信、人機界面設計、機器人、并行工程等各領域的研究人員的興趣。有人認為：“基于主體的計算（Agent-BasedComputing，簡稱ABC）,將成為軟件開發(fā)的下一個重要的突破?！?023/2/3史忠植高級人工智能15

分布式問題求解特點：數(shù)據(jù)、知識、控制均分布在系統(tǒng)的各節(jié)點上，既無全局控制，也無全局數(shù)據(jù)和知識存儲。2023/2/3史忠植高級人工智能16

分布式問題求解兩種協(xié)作方式：任務分擔結果共享2023/2/3史忠植高級人工智能17任務分擔

Smith和Davis提出了任務分擔方式。在任務分擔系統(tǒng)中,結點之間通過分擔執(zhí)行整個任務的子任務而相互協(xié)作,系統(tǒng)中的控制以目標為指導,各結點的處理目標是為了求解整個任務的一部分。

任務分擔的問題求解方式適合于求解具有層次結構的任務,如工廠聯(lián)合體生產(chǎn)規(guī)劃、數(shù)字邏輯電路設計、醫(yī)療診斷。2023/2/3史忠植高級人工智能18結果共享

Lesser和Corkill提出了結果共享方式。在結果共享方式的系統(tǒng)中,各結點通過共享部分結果相互協(xié)作,系統(tǒng)中的控制以數(shù)據(jù)為指導,各結點在任何時刻進行的求解取決于當時它本身擁有或從其它結點收到的數(shù)據(jù)和知識。結果共享的求解方式適合于求解與任務有關的各子任務的結果相互影響,并且部分結果需要綜合才能得出問題解的領域。如分布式運輸調(diào)度系統(tǒng)、分布式車輛監(jiān)控實驗系統(tǒng)DVMT

2023/2/3史忠植高級人工智能19分布式問題求解系統(tǒng)分類根據(jù)組織結構，分布式問題求解系統(tǒng)可以分為三類：層次結構類平行結構類混合結構類2023/2/3史忠植高級人工智能20分布式問題求解過程分布式問題求解過程可以分為四步：任務分解任務分配子問題求解結果綜合2023/2/3史忠植高級人工智能21任務分解

合同網(wǎng)絡動態(tài)層次控制自然分解,固定分配部分全局規(guī)劃2023/2/3史忠植高級人工智能22分布式問題求解系統(tǒng)中協(xié)作的分類按節(jié)點間協(xié)作量的多少，協(xié)作分為三類：全協(xié)作系統(tǒng)無協(xié)作系統(tǒng)半?yún)f(xié)作系統(tǒng)常用的通信方式有：共享全局存儲器信息傳遞黑板模型2023/2/3史忠植高級人工智能23

主體多主體系統(tǒng)主要研究在邏輯上或物理上分離的多個主體協(xié)調(diào)其智能行為，即知識、目標、意圖及規(guī)劃等，實現(xiàn)問題求解?？梢钥醋魇且环N由底向上設計的系統(tǒng)。Theagent

functionmapsfrompercepthistoriestoactions:[f:P*A]2023/2/3史忠植高級人工智能24主體的思想智能主體的幾個典型的實例：Microsoft的Office助手計算機病毒（破壞主體）計算機游戲或模擬中的智能角色貿(mào)易和談判主體（如Ebay的拍賣主體）網(wǎng)絡蜘蛛WebSpider（搜索引擎中的數(shù)據(jù)搜集和索引主體，如Google）

2023/2/3史忠植高級人工智能25主體程序設計面向過程的方法面向實體的方法面向對象的方法面向主體的方法軟件開發(fā)方法的進化2023/2/3史忠植高級人工智能26主體的定義在計算機和人工智能領域中，主體可以看作是一個實體，它通過傳感器感知環(huán)境，通過效應器作用于環(huán)境。Anagentisanythingthatcanbeviewedasperceivingitsenvironmentthroughsensorsandactinguponthatenvironmentthroughactuators2023/2/3史忠植高級人工智能27主體的特性主體弱概念：自治性交互性協(xié)作性可通信性長壽性2023/2/3史忠植高級人工智能28主體的特性主體強概念：知識、信念、意圖、承諾等心智狀態(tài)其它屬性：移動性推理能力規(guī)劃能力學習和適應能力誠實、善意、理性2023/2/3史忠植高級人工智能29

主體理論智能主體的理論模型研究主要從邏輯、行為、心理、社會等角度出發(fā)，對智能主體的本質(zhì)進行描述，為智能主體系統(tǒng)創(chuàng)建奠定基礎。2023/2/3史忠植高級人工智能30理性主體（BDI主體）Belief——信念，主體對環(huán)境的基本看法。Desire——愿望，主體想要實現(xiàn)的狀態(tài)，即目標。Intention——意圖，目標的子集。2023/2/3史忠植高級人工智能31

BDI主體模型BDI主體模型可以通過下列要素描述：一組關于世界的信念；主體當前打算達到的一組目標；一個規(guī)劃庫，描述怎樣達到目標和怎樣改變信念；一個意圖結構，描述主體當前怎樣達到它的目標和改變信念。2023/2/3史忠植高級人工智能32BDI解釋器BDI-Interpreterinitialize-state();do options:=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(B,G,I);untilquit2023/2/3史忠植高級人工智能33

動作理論情景演算是描述動作的主要的形式框架。在情景演算中引入了狀態(tài)和動作的概念，并利用兩條邏輯公理來描述動作與狀態(tài)的關系。一條公理描述一個動作在滿足什么條件的狀態(tài)之下可能發(fā)生，另外一條描述在一個狀態(tài)之下某個動作發(fā)生以后當前狀態(tài)如何改變。2023/2/3史忠植高級人工智能34規(guī)劃庫的形式化表示環(huán)境狀態(tài)：State={P1,P2,…Pn}目標：Goal=<State,weightiness>動作模板：Act_template=<name,roles,preconditions,effects,resources>主體能力：

Ability=<Act_template,role,cost>2023/2/3史忠植高級人工智能35主體結構主體結構需要解決的問題包括：主體由那些模塊組成，模塊之間如何交互信息，主體感知到的信息如何影響它的行為和內(nèi)部狀態(tài)，如何將這些模塊用軟件或硬件的方式組合起來形成一個有機的整體。2023/2/3史忠植高級人工智能36主體基本結構環(huán)境主體感知作用黑箱軟件主體2023/2/3史忠植高級人工智能37智能主體的工作過程環(huán)境交互信息融合信息處理作用交互感知作用2023/2/3史忠植高級人工智能38主體骨架程序functionSkeleton-Agent(percept)returnactionstatic:memory/*主體的世界記憶*/memory←Update-Memory(memory,percept)action←Choose-Best-Action(memory)memory←Update-Memory(memory,action)returnaction2023/2/3史忠植高級人工智能39主體的分類根據(jù)人類思維的層次模型，可以將主體分成四類：反應主體形象思維主體抽象思維主體復合式主體形象思維主體和抽象思維主體也可以合稱為認知主體2023/2/3史忠植高級人工智能40

反應主體環(huán)境當前世界傳感器動作效應器條件-動作規(guī)則主體2023/2/3史忠植高級人工智能41反應主體程序functionReactive-Agent(percept)returnsactionstatic:rules,/*一組條件-動作規(guī)則*/state←Interpret-Input(percept)rule←Rule-Match(state,rules)action←Rule-Action[rule]returnaction2023/2/3史忠植高級人工智能42認知主體環(huán)境信息融合傳感器動作效應器主體規(guī)劃知識庫目標內(nèi)部狀態(tài)2023/2/3史忠植高級人工智能43認知主體程序functionCognitive-Agent(percept)returnsaction static:environment,/*描述當前世界環(huán)境*/

kb,/*知識庫*/environment←Update-World-Model(environment,percept)state←Update-Mental-State(environment,state)action←Decision-Making(state,kb)environment←Update-World-Model(environment,action)returnaction2023/2/3史忠植高級人工智能44BDI結構知識信念規(guī)劃意圖目標愿望2023/2/3史忠植高級人工智能45復合式主體決策生成規(guī)劃反射建模通信感知行動其他智能主體智能主體外部世界預測協(xié)作與協(xié)商動作請求或應答信息一般情況緊急情況和簡單情況2023/2/3史忠植高級人工智能46規(guī)劃模塊世界的模型（包括其他主體的模型）經(jīng)驗庫目標集合局部規(guī)劃器決策生成重新規(guī)劃規(guī)劃規(guī)劃目標2023/2/3史忠植高級人工智能47建模模塊世界的模型（包括其他主體的模型）模型庫模型生成和維護預測規(guī)劃決策生成感知通信建模2023/2/3史忠植高級人工智能48通信模塊詞法庫語法庫詞義庫物理通信語言生成語言理解通信2023/2/3史忠植高級人工智能49主體通信策略對話消息黑板協(xié)議通信協(xié)作協(xié)議2023/2/3史忠植高級人工智能50主體通信中的主要問題語義：全部有關的主體必須知道通信語言的語義，消息的語義內(nèi)容知識是分布式問題求解的核心部分。言語行為：通信語言也是一種動作，說話是為了使世界的狀態(tài)發(fā)生改變。交互協(xié)議：主體之間消息交換的典型模式通信語言：傳遞消息的標準語法。FoundationforIntelligentPhysicalAgents2023/2/3史忠植高級人工智能51主體間的消息傳遞消息發(fā)送/傳輸服務器轉換到傳輸格式從傳輸格式轉換消息M言語行為意圖I目標GAgenti消息MAgenti2023/2/3史忠植高級人工智能52本體論本體論是概念化的明確的表示和描述。對某一領域中的概念有共同理解，可以提高交流和協(xié)作的效率，從而提高了軟件的重用性。2023/2/3史忠植高級人工智能53言語行為有關言語行為理論的研究主要集中在如何劃分不同類型的言語行為。在主體通信語言的研究中，言語行為理論主要用來考慮主體之間可以交互的信息類型。2023/2/3史忠植高級人工智能54通信語言KQML：由美國ARPA的知識共享計劃中提出，規(guī)定了消息格式和消息傳送系統(tǒng)，為多主體系統(tǒng)通信和協(xié)商提供了一種通用框架。ACL：由FIPA制定的一種規(guī)范。與KQML非常相似2023/2/3史忠植高級人工智能55KQML一個例子：(ask-all :sender A :receiver B :in-reply-to ido :reply-with idl :language Prolog :ontology foo :content “bar(X,Y)”)2023/2/3史忠植高級人工智能56FIPAACL(inform :senderagent1 :receiverhpl-auction-server :content (price(bidgood02)150) :in-reply-toround-4 :reply-withbid04 :languages1 :ontologyhpl-auction)消息結構開始通信動作類型消息參數(shù)消息內(nèi)容表達式參數(shù)表達式2023/2/3史忠植高級人工智能57FIPA通信動作庫AcceptProposal 接受提議Agree 同意Cancel 取消CallforProposal 要求提議Confirm 確認Disconfirm 確認為否定Failure 失敗Inform 通知InformIf 通知是否InformRef 通知有關對象NotUnderstood 不理解2023/2/3史忠植高級人工智能58Propagate 傳播Propose 提議Proxy 代理QueryIf 詢問是否QueryRef 詢問有關對象Refuse 拒絕（請求）RejectProposal 拒絕提議Request 請求RequestWhen 請求某個條件下執(zhí)行RequestWhenever 請求一旦某個條件成立就執(zhí)行Subscribe 預定詳細說明：/repository/cas.htmlFIPA通信動作庫2023/2/3史忠植高級人工智能59XML—eXtensibleMarkupLanguage

可擴展標記語言

XML是用于標記電子文件使其具有結構性的標記語言。XML文件本身只是將文件資料結構化。

例如：下面的ACL消息

(inform :senderjklabrou :receivergrosof :content(CPUlibretto50pentium) :ontologylaptop :languagekif)2023/2/3史忠植高級人工智能60<?xmlversion="pre-1.0"?><!DOCTYPEfipa_aclSYSTEM"fipa_acl.dtd"><message> <messagetype> inform </messagetype> <messageparameter> <senderlink="/?jklabrou"> jklabrou </sender> </messageparameter> <messageparameter> <receiverlink="/people/g/grosof/"> grosof </receiver> </messageparameter>轉換為XML格式2023/2/3史忠植高級人工智能61 <messageparameter> <ontologylink="/?jklabrou/ontology/laptop.html"> laptop </ontology> </messageparameter> <messageparameter> <content> (CPUlibretto50pentium) </content> </messageparameter> <messageparameter> <languagelink="/kif.html"> kif </language> </messageparameter></message>轉換為XML格式2023/2/3史忠植高級人工智能62主體的協(xié)調(diào)與協(xié)作協(xié)調(diào)(coordination)與協(xié)作(cooperation)是多主體研究的核心問題之一。協(xié)調(diào)是指一組智能主體完成一些集體活動時相互作用的性質(zhì)。協(xié)作是非對抗的主體之間保持行為協(xié)調(diào)的一個特例。2023/2/3史忠植高級人工智能63協(xié)調(diào)多主體系統(tǒng)中的協(xié)調(diào)是指多個主體為了以一致、和諧的方式工作而進行交互的過程。進行協(xié)調(diào)是希望避免主體之間的死鎖或活鎖。死鎖指多個主體無法進行各自的下一步動作；活鎖指多個主體不斷工作卻無任何進展。2023/2/3史忠植高級人工智能64協(xié)作目前針對主體協(xié)作的研究大體上可分為兩類：將其它領域研究多實體行為的方法和技術用于主體協(xié)作的研究。如對策論和力學研究。從主體的目標、意圖、規(guī)劃等心智態(tài)度出發(fā)來研究多主體間的協(xié)作。2023/2/3史忠植高級人工智能65協(xié)作協(xié)作的動機：某個主體相信通過協(xié)作能帶來好處（如提高效率，完成以往單獨無法完成的任務）多個主體在交流的過程中，發(fā)現(xiàn)它們能夠通過協(xié)作來實現(xiàn)更大的目標。2023/2/3史忠植高級人工智能66協(xié)作過程產(chǎn)生需求、確定目標協(xié)作規(guī)劃、求解協(xié)作結構尋求協(xié)作伙伴選擇協(xié)作方案實現(xiàn)目標評估結果2023/2/3史忠植高級人工智能67協(xié)作模式從社會心理學的角度看，多主體之間的協(xié)作情形大致可分為：

·協(xié)作型：同時將自己的利益放在第二位。

·自私型：同時將協(xié)作放在第二位。

·完全自私型：不考慮任何協(xié)作。

·完全協(xié)作型：不考慮自身利益。

·協(xié)作與自私相混合型。2023/2/3史忠植高級人工智能68協(xié)作策略·計算生態(tài)學

·對策論

·規(guī)劃2023/2/3史忠植高級人工智能69計算生態(tài)學80年代末，在計算機中出現(xiàn)了一個嶄新的學科---計算生態(tài)學(theecologofcomputation)。計算生態(tài)學是研究關于開放系統(tǒng)中訣定計算結點的行為與資源使用的交互過程的學科。它摒棄了封閉、靜止地處理問題的傳統(tǒng)算法，將世界看作是開放的、進化的、并發(fā)的,通過多種協(xié)作處理問題的＂生態(tài)系統(tǒng)＂(ecosystem)加以研究。它的進展與開放信息系統(tǒng)的研究息息相關。2023/2/3史忠植高級人工智能70計算生態(tài)學

計算生態(tài)學將計算系統(tǒng)看作是一個生態(tài)系統(tǒng)，它引進了許多生物的機制，如變異(mutation)即物種的變化。這些變化導致生命基因的改變，從而形成物種的多樣性，增強了適應環(huán)境的能力。這類變異策略成為人工智能系統(tǒng)提高其自身能力的一種方法。Lenat與Brown成功地將變異機制引入他們的AM與Eurisko系統(tǒng)中,通過小型Lisp程序的語法變異發(fā)現(xiàn)數(shù)學概念。他們認為未來成功的系統(tǒng)應該是一系列進化的、自組織的符號知識結構的“社會”系統(tǒng)。2023/2/3史忠植高級人工智能71生物生態(tài)模型

這是最著名的生態(tài)系統(tǒng)，具有典型的進化特征和層次性。這種特性反映在“食物鏈”中。對于復雜的生物生態(tài)系統(tǒng)而言，各物種組成了緊密相連的網(wǎng)絡－食物網(wǎng)。這個系統(tǒng)的主要角色是捕食者與被食者。生命依賴于生命，共同進化，由小的生態(tài)環(huán)境組成大的生態(tài)系統(tǒng)。2023/2/3史忠植高級人工智能72物種進化模型

物種進化的“復制者”是基因。從門德爾的植物遺傳研究到現(xiàn)代遺傳學的成果，都說明了在物種進化過程中，基因的組合與變異起著關鍵作用。在一個物種的某一群體中基因的集合稱為基因池。生物組織是基因的載體。如果環(huán)境變化，選擇的機制就會改變。這種變化必然引起基因池的變化。特定種群的基因變化稱為基因流。

一個物種總是不斷地經(jīng)歷隔絕、基因流動、變化的循環(huán)。開始時，一組地理上隔絕的群體自己孤立地發(fā)展，基因在內(nèi)部快速地流動。隨著開放，通過交流和競爭，優(yōu)勝劣汰。2023/2/3史忠植高級人工智能73經(jīng)濟模型

經(jīng)濟系統(tǒng)在某種意義上類似于生物生態(tài)系統(tǒng)。在商品市場和理想市場中，進化決定于經(jīng)濟實體的決策。選擇機制是市場獎勵機制。

進化是快速的，企業(yè)與消費者之間、企業(yè)之間主要是一種互相依賴的合作關系。決策者為了追求長遠利益，可以采取各種有效的方法，甚至可以暫時做賠本買賣。2023/2/3史忠植高級人工智能74協(xié)商模型Zlotkin的面向領域的協(xié)商理論Zlotkin的協(xié)商理論假設：各主體追求本身效用最大。知識完備。無歷史信息。目標集固定。協(xié)商在兩主體之間同時進行。主體操作集相同。世界僅當主體操作之后發(fā)生變化。2023/2/3史忠植高級人工智能75面向領域的協(xié)商理論在協(xié)商過程中，若存在一個雙方滿意的分配，可以得到一個聯(lián)合規(guī)劃,使協(xié)商終止的條件是：(1)達成協(xié)議：如果Utility(P(i,t))Utility(P(i,t-1)),這一協(xié)商過程將在有限步內(nèi)結束。(2)沖突：如果Utility(P(i,t))=Utility(P(i,t-1)),則無法達成協(xié)議。2023/2/3史忠植高級人工智能76最佳平衡傳統(tǒng)的協(xié)商是基于Nash平衡的,它的缺點是Nash平衡產(chǎn)生多個平衡點,對結果約束較少。Kraus使用Rubinstein的“最佳”平衡(PerfectEquilibrium,簡稱P.E.)理論,建立了一種基于P.E.的協(xié)商方法,需要在協(xié)商的任一階段都產(chǎn)生平衡,即在協(xié)商的任一階段,假設

主體

A使用P.E.策略,則

主體

B除了自己的

P.E.,策略外沒有更好的策略可遵循。故若有唯一的

P.E.,并假定主體要使用該策略,則它在協(xié)商的每一階段都只用這一策略?？勺C明,存在唯一的P.E.,在第一階段后就可以終止協(xié)商。Kraus還將對時間的偏好引入這一理論中。結果表明,時間偏好可以提高協(xié)商效率,并僅對某一主體有利。這一理論對于主體的構造和主體之間的協(xié)作很有用處,如果為主體提供唯一的P.E.策略,并通知其他主體,則其他主體的最佳選擇也是P.E.策略。該理論的缺陷是:缺乏動態(tài)性特色,應用面窄,因為盡管存在唯一的P.E,但如何求出仍未得到解決。2023/2/3史忠植高級人工智能77集中式協(xié)商方法

Ephrati使用了一種集中式的協(xié)商方法,用一個“masteragent”或組投票機制以達成協(xié)議。在這種方法中,一組主體的協(xié)作與組規(guī)劃進程相關。Ephrati使用一種動態(tài)的、迭代的搜索過程,通過一組約束,使主體遞增式地構成一個最大“社會效用”規(guī)劃。在每一步,各主體對于組規(guī)劃的下一個聯(lián)合行動投票。使用這一技術,主體無需完整地展示其偏好,可選狀態(tài)集在投票之前產(chǎn)生。2023/2/3史忠植高級人工智能78開放環(huán)境多智能體協(xié)作方法

Osawa

(1)需求者(requestor)向公告板主體發(fā)送需求建議RFP(2)空閑主體向公告板主體申請一個RFP(3)公告板將RFP發(fā)到提出申請的空閑主體

(4)空閑主體產(chǎn)生個體規(guī)劃

(5)空閑主體將其規(guī)劃發(fā)給需求者

(6)需求者調(diào)查協(xié)作的可能

(7)需求者發(fā)送協(xié)作獎勵

(8)申請者組成協(xié)作規(guī)劃2023/2/3史忠植高級人工智能79開放環(huán)境多智能體協(xié)作方法其效用值可用下式計算：

utility(a,g)=worth(a,g)-cost(plan(a,g))

效用的平均是協(xié)作的原則。盡管Osawa在一定程度上解決了開放環(huán)境中主體協(xié)作的問題,但將各主體效用簡單相加再平均的方法仍然太弱,因為主體效用僅是主體本身對目標偏好的一種排序關系,不同主體效用一般不能用數(shù)值比較。2023/2/3史忠植高級人工智能80交互協(xié)議主體之間的會話常常形成典型模式，這種情況下某些消息序列是可知的，這些消息交換的典型模式稱為協(xié)議。主體間交互的理想情況：主體充分地理解消息的含意和意圖，然后根據(jù)自身的信念、目標等心智狀態(tài)，做出相應的回答比較實際的實現(xiàn)：預先規(guī)范這些協(xié)議，規(guī)定好消息的順序。2023/2/3史忠植高級人工智能81FIPA英國拍賣協(xié)議2023/2/3史忠植高級人工智能82規(guī)劃規(guī)劃是主體對動作進行推理的一種主要形式，它很大程度上體現(xiàn)了主體的智能性。同時，規(guī)劃也是描述主體行為的主要方式。規(guī)劃是為了建立一個控制算法，使智能主體能夠為實現(xiàn)目標，對動作過程進行綜合。2023/2/3史忠植高級人工智能83經(jīng)典規(guī)劃問題經(jīng)典的規(guī)劃理論認為規(guī)劃要解決的問題（即規(guī)劃的輸入）是：用某種形式語言描述的初始世界狀態(tài)用某種形式語言描述的主體目標用某種形式語言描述的主體可能采用的動作，通常也叫做領域知識輸出是：可以在某個滿足初始狀態(tài)描述的世界中執(zhí)行并達到主體目標的一個動作序列2023/2/3史忠植高級人工智能84經(jīng)典規(guī)劃的假設原子執(zhí)行時間確定性結果主體全知主體唯一能動性2023/2/3史忠植高級人工智能85經(jīng)典規(guī)劃系統(tǒng)人們對經(jīng)典規(guī)劃算法進行了大量的研究，提出了許多有效的算法，如STRIPS，TWEAK，UCPOP和SNLP等。最近，其它領域中的一些有效算法被引入到規(guī)劃中來。新的進展主要在GraphPlan和SATPLAN方面。

2023/2/3史忠植高級人工智能86STRIPS表示法世界狀態(tài)：一個世界狀態(tài)（或簡稱為狀態(tài)）是一組謂詞的集合。目標：表示世界狀態(tài)的謂詞的合取。動作：動作用前提條件和動作效果來表示。前提條件：動作執(zhí)行前必須滿足的狀態(tài)。動作效果：動作執(zhí)行后可以保證為真的狀態(tài)。2023/2/3史忠植高級人工智能87STRIPS表示法-規(guī)劃動作模板：表示一組可能的動作，即包含自由變量的動作。動作步驟：表示一個具體的動作，由動作模板中的變量添加約束得到。規(guī)劃：規(guī)劃用動作步驟和動作步驟上的約束來表示。約束包括：動作步驟間的順序約束，根據(jù)順序約束可以分為全序規(guī)劃和偏序規(guī)劃。動作步驟中變量或常量之間的等價、不等價、大于、小于等約束。2023/2/3史忠植高級人工智能88經(jīng)典規(guī)劃舉例ABBA初始狀態(tài)目標狀態(tài)2023/2/3史忠植高級人工智能89規(guī)劃表示初始狀態(tài)：On(table,A),On(A,B)目標狀態(tài)：On(B,A),On(table,B)基本知識：動作模板：

Move(?Obj,?dest) precondition：Clear(?Obj)effect：delete：On(?Obj,?src)add：On(?Obj,?dest)2023/2/3史忠植高級人工智能90希望得到的規(guī)劃結果希望得到的結果：第一步：Move(B,table)第二步：Move(A,B)實際的表示為：Step1.Action=Move,Step1.Obj=B,Step1.dest=table,Step2.Action=Move,Step2.Obj=A,Step2.dest=B,Step1<Step22023/2/3史忠植高級人工智能91規(guī)劃算法

規(guī)劃算法實質(zhì)上是一種搜索算法。搜索一個動作步驟序列，使得經(jīng)過這個動作步驟的作用后，世界狀態(tài)由初始狀態(tài)變化為目標狀態(tài)。算法應包含以下功能：選擇動作：選擇當前狀態(tài)下能夠執(zhí)行的動作。變量綁定（匹配）：根據(jù)當前狀態(tài)，對動作中的變量進行約束?；厮荩喊l(fā)現(xiàn)死鎖狀態(tài)后，可以回退到以前的某個狀態(tài)。2023/2/3史忠植高級人工智能92規(guī)劃搜索初始狀態(tài)狀態(tài)1-1狀態(tài)1-n狀態(tài)m-k目標狀態(tài)動作1-1動作1-n動作m-k………………2023/2/3史忠植高級人工智能93規(guī)劃結果初始狀態(tài)：On(table,A),On(A,B)On(table,A),On(table,B)目標狀態(tài)：On(B,A),On(table,B)Move(B,table)Move(A,B)2023/2/3史忠植高級人工智能94沖突一個規(guī)劃正確的必要條件是，在規(guī)劃的每個實現(xiàn)中，每個動作的每個前提條件在動作執(zhí)行之前都滿足。造成規(guī)劃不正確的原因是一個動作會破壞其他動作間的因果鏈，即沖突。2023/2/3史忠植高級人工智能95因果鏈因果鏈描述一個動作為另一個動作建立一個前提條件。一個規(guī)劃中，動作E和動作U之間存在因果鏈，當且僅當1、，即E和U之間有順序約束；2、使得，其中，即E的一個效果為U的一個前提；3、，如果，并且，那么并且，即發(fā)生在E和U之間的所有動作都不影響。2023/2/3史忠植高級人工智能96沖突沖突描述的是一個因果鏈被其它規(guī)劃中的某些動作破壞。設存在因果鏈和另一個動作C，如果1、并且，即C可能在E和U之間執(zhí)行；2、使得，即C的效果之一可能破壞那么稱C為的一個威脅。當C在E和U之間被執(zhí)行時，就發(fā)生沖突。

2023/2/3史忠植高級人工智能97沖突舉例ABB初始狀態(tài)目標狀態(tài)CACAC沖突狀態(tài)B2023/2/3史忠植高級人工智能98沖突描述規(guī)劃：Step1=Move(?obj,?dest),Step1.obj=C,Step1.dest≠B;Step2=Move(?obj,?dest),Step2.obj=B,Step2.dest=Table;Step3=Move(?obj,?dest),Step3.obj=A,Step3.dest=B;Step4=Move(?obj,?dest),Step4.obj=C,Step4.dest=A;Step1<Step2,Step2<Step3,Step3<Step4當按照下面的約束執(zhí)行時，發(fā)生沖突：Step1.dest=AStep3無法執(zhí)行。2023/2/3史忠植高級人工智能99沖突消解方法沖突威脅到規(guī)劃的正確性，消解沖突的方法就是在規(guī)劃之間添加新的約束，破壞沖突產(chǎn)生的條件。Chapman闡明了一個充分必要的沖突消解集合，其中包括“升級”、“降級”、“分離”和“引入修復”四種約束。設動作的C一個效果威脅因果鏈，那么下列任何一個約束對于消解它都是充分的：（1）升級：加入順序約束，（2）降級：加入順序約束,（3）分離：加入新的變量約束使得，（4）引入修復：選擇某個規(guī)劃中已有動作或者新動作W，使得，而且或者

2023/2/3史忠植高級人工智能100沖突消解方法舉例規(guī)劃：Step1=Move(?obj,?dest),Step1.obj=C,Step1.dest≠B;Step2=Move(?obj,?dest),Step2.obj=B,Step2.dest=Table;Step3=Move(?obj,?dest),Step3.obj=A,Step3.dest=B;Step4=Move(?obj,?dest),Step4.obj=C,Step4.dest=A;Step1<Step2,Step2<Step3,Step3<Step4當按照下面的約束執(zhí)行時，發(fā)生沖突：Step1.dest=AStep3無法執(zhí)行。消解方法：添加約束Step1.dest≠A2023/2/3史忠植高級人工智能101UCPOP算法UCPOP是一個用CommonLisp寫的偏序規(guī)劃器。UCPOP算法不斷修改未完成的規(guī)劃直到所有目標和后續(xù)子目標都被滿足。修改包括向其中加入新動作步驟，向其中加入等價或不等價綁定來約束自由變量，向中加入順序約束來安排動作步驟的先后順序。

2023/2/3史忠植高級人工智能102UCPOP算法主要步驟UCPOP算法的主要步驟：1．終止條件2．選擇子目標3．選擇動作4．子目標生成5．因果鏈保護6．遞歸2023/2/3史忠植高級人工智能103GraphPlan圖規(guī)劃算法圖規(guī)劃算法包括兩個交替進行的過程：圖擴充和方案搜索。圖擴充過程對規(guī)劃圖按時間順序向前擴充，直到滿足規(guī)劃存在的必要條件（不是充分條件）。然后方案搜索過程在圖中進行反向鏈搜索，尋找解決問題的方案。如果沒有找到解決方案，則進一步擴充規(guī)劃圖，重復上述循環(huán)。

2023/2/3史忠植高級人工智能104規(guī)劃圖中的節(jié)點2023/2/3史忠植高級人工智能105規(guī)劃圖中動作間的互斥關系第i層的兩個動作實例是互斥的，如果下列條件中至少有一條成立：不一致效果：一個動作的效果是另一個動作效果的否定；干涉：一個動作刪除了另一個動作的前提；競爭的需求：兩個動作在i-1層中具有互斥的前提。第i層的兩個狀態(tài)是互斥的，如果一個狀態(tài)是另一個狀態(tài)的否定，或者獲得兩個狀態(tài)的方法（i-1層中的動作）是兩兩互斥的（不一致支持）。

2023/2/3史忠植高級人工智能106互斥關系的圖形表示2023/2/3史忠植高級人工智能107多主體環(huán)境下的規(guī)劃問題多主體系統(tǒng)規(guī)劃的特殊之處在于：主體可以請求其它主體協(xié)作執(zhí)行一個聯(lián)合動作來實現(xiàn)自己的目標。主體之間的動作沖突必須通過主體之間的協(xié)商來避免。2023/2/3史忠植高級人工智能108協(xié)作動作舉例ABBA初始狀態(tài)目標狀態(tài)agent1agent22023/2/3史忠植高級人工智能109協(xié)作動作的表示動作模板：

Move(?Obj,?dest)actor：actor1precondition：Clear(?Obj)and(Weight(?Obj,?x)and?x<=3)delete：On(?Obj,?src)add：On(?Obj,?dest)Joint-Move(?Obj,?dest)actor：actor1,actor2precondition：Clear(?Obj)and(Weight(?Obj,?x)and3<?x<=6)delete：On(?Obj,?src)add：On(?Obj,?dest)物體：Weight(A,4),Weight(B,1)初始狀態(tài)：On(table,A),On(A,B)目標狀態(tài)：On(B,A),On(table,B)2023/2/3史忠植高級人工智能110任務分配規(guī)劃結果如下：Step1.Action=Move,Step1.Obj=B,Step1.dest=table,Step2.Action=Joint-Move,Step2.Obj=A,Step2.dest=B,Step1<Step2然后根據(jù)主體能力庫，對動作步驟中的角色進行任務分配。主體能力庫如下：

agent1：CanDoMoveasactor1CanDoJoint-Moveasactor1,actor2agent2：Can