分布式人工智能與MAS

分布式人工智能與MAS第一頁，共31頁。計(jì)算機(jī)科學(xué)技術(shù)發(fā)展趨勢(shì)1、智能化2、個(gè)性化3、網(wǎng)絡(luò)化4、并行化第二頁，共31頁。分布式人工智能(DAI)一、基本概念研究在邏輯上或物理上分散的智能系統(tǒng)如何并行地、相互協(xié)作地實(shí)現(xiàn)問題求解。第三頁，共31頁。分布式人工智能(DAI)二、特點(diǎn)

1)系統(tǒng)中的數(shù)據(jù)、知識(shí)以及控制不但在邏輯上，而且在物理上分布的，既沒有全局控制，也沒有全局的數(shù)據(jù)存儲(chǔ)。

2)各個(gè)求解機(jī)構(gòu)由計(jì)算機(jī)網(wǎng)絡(luò)互連，在問題求解過程中，通信代價(jià)要比求解問題的代價(jià)低得多。

3)系統(tǒng)中諸機(jī)構(gòu)能夠相互協(xié)作，來求解單個(gè)機(jī)構(gòu)難以解決，甚至不能解決的任務(wù)。注：DAI的實(shí)現(xiàn)可克服原有專家系統(tǒng)、學(xué)習(xí)系統(tǒng)等弱點(diǎn)，極大提高知識(shí)系統(tǒng)的性能，可提高問題求解能力和效率，擴(kuò)大應(yīng)用范圍、降低軟件復(fù)雜性。第四頁，共31頁。分布式人工智能(DAI)三、主要內(nèi)容分布式問題求解(DPS)和多Agent系統(tǒng)(MAS)。1)分布式問題求解(DPS)

主要考慮怎樣將一個(gè)特殊問題求解工作在多個(gè)合作的、知識(shí)共享的模塊或結(jié)點(diǎn)之間劃分。2)多Agent系統(tǒng)(MAS)

主要研究自主的智能Agent之間智能行為的協(xié)調(diào)，為了一個(gè)共同的全局目標(biāo)，也可能是關(guān)于各自的不同目標(biāo)，共享有關(guān)問題和求解方法的知識(shí)，協(xié)作進(jìn)行問題求解。注：基于Agent的計(jì)算將成為軟件開發(fā)的下一個(gè)重要的突破口。第五頁，共31頁。分布式問題求解(DPS)一、協(xié)作方式任務(wù)分擔(dān)(tasksharing)和結(jié)果共享(resultssharing)二、求解過程1、任務(wù)分解2、任務(wù)分配3、子問題求解4、結(jié)果綜合注：1)典型的任務(wù)分解和任務(wù)分配的方法有：合同網(wǎng)絡(luò)(類似于“招標(biāo)”)、動(dòng)態(tài)層次控制、自然分解、固定分解、部分全局規(guī)劃；

2)在DPS中常用的通信方式有：共享全局存儲(chǔ)器、消息傳遞及二者的結(jié)合。

3)黑板模型是DPS中使用較多的框架結(jié)構(gòu)。第六頁，共31頁。Agent及多Agent系統(tǒng)(MAS)智能體最早出現(xiàn)在20世紀(jì)70年代的人工智能領(lǐng)域，它所具有的智能性和靈活性，使得該技術(shù)成為研究復(fù)雜系統(tǒng)的重要手段。單個(gè)智能體的能力、知識(shí)和計(jì)算資源都很有限，而多個(gè)智能體組成的多智能體系統(tǒng)已成為解決大型、復(fù)雜、分布式及難預(yù)測(cè)問題的重要手段。90年代以來，多智能體系統(tǒng)已經(jīng)成為分布式人工智能研究的熱點(diǎn)，對(duì)智能體以及MAS的研究已經(jīng)成為人工智能的核心問題。多智能體系統(tǒng)對(duì)許多學(xué)科和技術(shù)的發(fā)展起到了很大的指導(dǎo)和促進(jìn)作用，由于Agent的出現(xiàn)，人們可以對(duì)人工智能進(jìn)行以下全新的詮釋：“人工智能是計(jì)算機(jī)科學(xué)的一個(gè)分支，其目標(biāo)是構(gòu)造能表現(xiàn)出一定智能行為的智能體”。計(jì)算智能體甚至被認(rèn)為是人工智能研究的最初和最終目標(biāo)。第七頁，共31頁。Agent及多Agent系統(tǒng)(MAS)多智能體理論對(duì)于促進(jìn)經(jīng)濟(jì)、工業(yè)、社會(huì)、軍事等方面的進(jìn)步都具有深遠(yuǎn)的意義。主要研究內(nèi)容1、微觀

Agent本身，包括Agent基本特性、相應(yīng)理論、內(nèi)部實(shí)現(xiàn)框架。2、宏觀

Agent與環(huán)境及其它Agent的關(guān)系，包括，多Agent系統(tǒng)體系結(jié)構(gòu)、Agent通信語言、Agent交互與協(xié)商、Agent協(xié)作與合作、多Agent知識(shí)交互與信息共享、多Agent學(xué)習(xí)。第八頁，共31頁。Agent一、Agent的定義（尚未形成統(tǒng)一定義）關(guān)于Agent有多種稱呼：代理、主體、智能體、智能主體、艾真體等。能夠自主連續(xù)地在一可動(dòng)態(tài)變化的、存在其它Agent的環(huán)境中運(yùn)行的，并可與環(huán)境進(jìn)行交互的實(shí)體，稱為Agent。廣義地講，Agent是具有自主性、社會(huì)能力(交互性)和反應(yīng)特征的計(jì)算機(jī)軟/硬件系統(tǒng)。Agent是可以感知其所處環(huán)境，并能根據(jù)自身的目標(biāo)作用于環(huán)境的計(jì)算實(shí)體。在沒有人的干預(yù)下能夠自主地完成給定任務(wù)的對(duì)象都可以稱為Agent。在人工智能領(lǐng)域，Agent被定義為具有感知能力、問題求解能力和與外界通信能力的實(shí)體，是完全自治或半自治的。第九頁，共31頁。Agent三、Agent特性1、自治性對(duì)自己的行為和內(nèi)部狀態(tài)有一定的控制權(quán)。2、社會(huì)性或稱可通信性能夠通過某種Agent通信語言與其它Agent進(jìn)行信息交換。注：任務(wù)的承接、多Agent的協(xié)作、協(xié)商等均以通信為基礎(chǔ)。3、交互性對(duì)環(huán)境的感知，并通過行為改變環(huán)境。4、主動(dòng)性主動(dòng)感知周圍環(huán)境的變化，并作出基于目標(biāo)的行為。第十頁，共31頁。Agent5、協(xié)作性通過協(xié)作提高多Agent系統(tǒng)的性能。6、持久性在“相當(dāng)長”的時(shí)間內(nèi)連續(xù)運(yùn)行。7、自適應(yīng)性根據(jù)過去的經(jīng)驗(yàn)積累知識(shí)，并且修改其行為以適應(yīng)新的環(huán)境。8、情態(tài)特性具有信念、意圖、愿望等情態(tài)。9、可推理性可根據(jù)當(dāng)前知識(shí)和經(jīng)驗(yàn)，以理性的方式進(jìn)行推理或預(yù)測(cè)。第十一頁，共31頁。Agent10、可移動(dòng)性可從一個(gè)地方移動(dòng)到另一個(gè)地方而保持其內(nèi)部狀態(tài)不變。注：Agent可以攜帶數(shù)據(jù)，且可在遠(yuǎn)處執(zhí)行智能指令。11、誠實(shí)性不會(huì)故意提供錯(cuò)誤信息。12、友善性

Agent之間不存在互相沖突的目標(biāo)，總是盡力幫助其它Agent。13、理性總是盡力實(shí)現(xiàn)自己的目標(biāo)。第十二頁，共31頁。Agent四、智能體分類本地智能體或網(wǎng)絡(luò)智能體集中式智能體或分布式智能體固定智能體或移動(dòng)智能體第十三頁，共31頁。

多Agent

多智能體系統(tǒng)是在邏輯上或物理上呈分布狀態(tài)的多個(gè)智能體組成的較為松散的聯(lián)合體，各智能體按照預(yù)先規(guī)定的協(xié)議，根據(jù)系統(tǒng)的目標(biāo)狀態(tài)及自身的目的、資源和知識(shí)，利用通信網(wǎng)絡(luò)，相互之間通過協(xié)商來確定各自的任務(wù)，并通過協(xié)調(diào)和協(xié)作來共同完成任務(wù)并達(dá)到整體目標(biāo)。第十四頁，共31頁。

多Agent

基于多智能體系統(tǒng)研究復(fù)雜系統(tǒng)時(shí)，首先要根據(jù)系統(tǒng)的特點(diǎn)對(duì)單個(gè)智能體作出定義，賦予其一定的行為能力和參數(shù)，并對(duì)各個(gè)智能體之間以及智能體與環(huán)境之間的交互規(guī)則作出規(guī)定，以此描述系統(tǒng)及其變化過程。在復(fù)雜的動(dòng)態(tài)環(huán)境下，由于存在時(shí)間和資源的約束，多智能體系統(tǒng)需要解決的關(guān)鍵問題就是如何進(jìn)行資源分配、任務(wù)調(diào)度、行為協(xié)調(diào)和沖突消解，使功能獨(dú)立的智能體通過協(xié)商、協(xié)調(diào)來完成復(fù)雜的控制任務(wù)或解決復(fù)雜的問題。第十五頁，共31頁。

多智能體系統(tǒng)體系結(jié)構(gòu)和協(xié)調(diào)機(jī)制

多智能體系統(tǒng)體系結(jié)構(gòu)及其協(xié)調(diào)機(jī)制是多智能體系統(tǒng)理論研究的核心問題，它研究如何把多個(gè)智能體組織為一個(gè)群體并使各個(gè)智能體有效地進(jìn)行協(xié)調(diào)合作，從而達(dá)到解決整體問題的目標(biāo)。對(duì)于多智能體系統(tǒng)體系結(jié)構(gòu)及其協(xié)調(diào)機(jī)制的研究，目前大致可以分為三種學(xué)派：基于符號(hào)推理系統(tǒng)的體系結(jié)構(gòu)及協(xié)調(diào)機(jī)制，基于行為主義的體系結(jié)構(gòu)及協(xié)調(diào)機(jī)制，基于協(xié)作進(jìn)化方法的體系結(jié)構(gòu)及協(xié)調(diào)機(jī)制。第十六頁，共31頁?；诜?hào)推理系統(tǒng)的體系結(jié)構(gòu)及協(xié)調(diào)機(jī)制

這種學(xué)派的基礎(chǔ)是Bratman等提出的BDI(BriefDesireIntention)理論通過建立比較完整的符號(hào)系統(tǒng)并基于經(jīng)典人工智能的符號(hào)處理，來進(jìn)行知識(shí)推理以使智能體具有自主思考、決策以及與其他智能體和環(huán)境進(jìn)行協(xié)調(diào)行動(dòng)的能力。這種學(xué)派包括三種代表性的理論：第十七頁，共31頁。基于符號(hào)推理系統(tǒng)的體系結(jié)構(gòu)及協(xié)調(diào)機(jī)制（1）聯(lián)合意圖理論這是目前最為系統(tǒng)和成熟的多智能體協(xié)調(diào)理論框架，由Cohen和Levesque在BDI理論的基礎(chǔ)上，提出了承諾（Commitment）和公約（Convention）等概念。其基本思想是：多個(gè)智能體在完成共同的任務(wù)時(shí)會(huì)形成一個(gè)共同的承諾，并堅(jiān)守承諾，直到成功完成共同任務(wù)，除非出現(xiàn)下列任何一種情況：①智能體發(fā)現(xiàn)共同任務(wù)已經(jīng)完成；②智能體發(fā)現(xiàn)共同任務(wù)不可能完成；③智能體發(fā)現(xiàn)沒有必要執(zhí)行該共同任務(wù)。如果發(fā)生以上情況，智能體就把“自己將要退出承諾”的意圖設(shè)法通知正在聯(lián)合執(zhí)行任務(wù)的其他智能體，以便適時(shí)地進(jìn)行調(diào)整。通過這樣的承諾和公約機(jī)制，多個(gè)智能體就能協(xié)調(diào)完成共同的任務(wù)。所以，聯(lián)合意圖理論只是為了各個(gè)智能體在完成共同任務(wù)時(shí)參與和堅(jiān)持的一致性提供了一個(gè)框架，而沒有確定聯(lián)合行為中的具體分工和協(xié)作問題。第十八頁，共31頁?；诜?hào)推理系統(tǒng)的體系結(jié)構(gòu)及協(xié)調(diào)機(jī)制（2）共享計(jì)劃理論該理論由Grosz等提出。其基本思想是：參與聯(lián)合行動(dòng)的各個(gè)智能體先達(dá)成一個(gè)包括具體行動(dòng)步驟和各方面細(xì)節(jié)的共享計(jì)劃，并且相信所有智能體都打算參與聯(lián)合行動(dòng)并接受共享計(jì)劃；數(shù)個(gè)智能體組建形成子團(tuán)體，不同的子團(tuán)體或單獨(dú)或組合地完成共享計(jì)劃的每一個(gè)具體步驟；子團(tuán)體之外的其他智能體都相信子團(tuán)體能夠完成相應(yīng)的具體步驟，并形成相應(yīng)的共享計(jì)劃。于是，通過共享計(jì)劃的協(xié)調(diào)，各個(gè)智能體就能合作完成共同的任務(wù)。第十九頁，共31頁?；诜?hào)推理系統(tǒng)的體系結(jié)構(gòu)及協(xié)調(diào)機(jī)制（3）計(jì)劃的隊(duì)行為計(jì)劃由設(shè)計(jì)者事先確定，而不是由MAS動(dòng)態(tài)產(chǎn)生，各個(gè)智能體在行動(dòng)之前就被賦予有關(guān)完整計(jì)劃的詳細(xì)信息。這種方法要求事先對(duì)智能體的行為環(huán)境有確切了解并做詳細(xì)計(jì)劃，所以不適合于動(dòng)態(tài)環(huán)境，其應(yīng)用比較有限。第二十頁，共31頁。基于符號(hào)推理系統(tǒng)的體系結(jié)構(gòu)及協(xié)調(diào)機(jī)制

基于符號(hào)系統(tǒng)的多智能體體系結(jié)構(gòu)與協(xié)調(diào)機(jī)制存在的主要問題是：①符號(hào)主義要求對(duì)環(huán)境有比較完整和復(fù)雜的模型，而如何使智能體自身模型的計(jì)算和推理與環(huán)境保持同步就是一個(gè)棘手的問題；②復(fù)雜模型計(jì)算和推理使智能體對(duì)環(huán)境的適應(yīng)能力變差，并且難以滿足模型與領(lǐng)域無關(guān)性的要求；③對(duì)于大型復(fù)雜動(dòng)態(tài)系統(tǒng)而言，符號(hào)模型建立過程的繁瑣和效率低下等問題表現(xiàn)的尤為嚴(yán)重。第二十一頁，共31頁?；谛袨橹髁x的體系結(jié)構(gòu)及協(xié)調(diào)機(jī)制

基于行為主義的MAS以Brooks的基于行為的系統(tǒng)分析與設(shè)計(jì)方法為基礎(chǔ)，其系統(tǒng)設(shè)計(jì)有三個(gè)基本原則：最小性：系統(tǒng)應(yīng)盡量簡單以便與環(huán)境進(jìn)行快速交互；無狀態(tài)性：系統(tǒng)本身沒有關(guān)于外部環(huán)境的狀態(tài)模型，其行為是基于感知——行為的模式進(jìn)行的；魯棒性：系統(tǒng)能夠有效地處理而不是去除實(shí)際環(huán)境中的不確定性?；谛袨橹髁x的智能體設(shè)計(jì)的一般過程：首先確定一些基本行為，通過基本行為的選擇和組合來完成所要求的任務(wù)，因此，行為選擇機(jī)制的研究非常重要，也是多智能體協(xié)調(diào)研究的熱點(diǎn)和核心問題。第二十二頁，共31頁?；谛袨橹髁x的體系結(jié)構(gòu)及協(xié)調(diào)機(jī)制其基本思想是：由各種基本行為構(gòu)成一個(gè)網(wǎng)狀結(jié)構(gòu)，各個(gè)結(jié)點(diǎn)表示相應(yīng)的基本行為，而各個(gè)結(jié)點(diǎn)之間的連接表示為行為的活性，即行為對(duì)目標(biāo)的貢獻(xiàn)和效能的一種度量，如果行為促使目標(biāo)的實(shí)現(xiàn)，其活性值為正，反之為負(fù)，并且，這種效能越大，其活性值就越大。各種行為之間存在激勵(lì)或抑制的相互作用影響，于是，相應(yīng)的活性值就在行為網(wǎng)中進(jìn)行傳播，通過相應(yīng)的活性傳播控制算法就可以對(duì)行為進(jìn)行有效的組合、調(diào)度和協(xié)調(diào)，從而完成復(fù)雜任務(wù)。第二十三頁，共31頁。基于協(xié)進(jìn)化方法的體系結(jié)構(gòu)及協(xié)調(diào)機(jī)制

自然界中的各個(gè)物種共同生存于同一個(gè)生態(tài)系統(tǒng)中，每個(gè)物種在其中都有自己的生存環(huán)境。由于資源有限，各個(gè)物種必須通過競(jìng)爭(zhēng)和合作才能獲得自己生存所需的資源。競(jìng)爭(zhēng)和合作又促使物種不斷進(jìn)化和改變，并影響彼此的進(jìn)化過程，這樣的過程就稱為協(xié)進(jìn)化。協(xié)進(jìn)化是克服傳統(tǒng)進(jìn)化算法的不足而提出的更為通用的機(jī)器學(xué)習(xí)過程，并適用于多智能體的協(xié)調(diào)。在協(xié)進(jìn)化計(jì)算中，通?？紤]多個(gè)物種群體，每個(gè)物種都有相應(yīng)的個(gè)體類型，各個(gè)物種群體采用進(jìn)化算法實(shí)現(xiàn)其進(jìn)化過程。與常規(guī)模擬進(jìn)化不同的是，在對(duì)個(gè)體進(jìn)行適應(yīng)度評(píng)價(jià)時(shí)，增加對(duì)群體間交互協(xié)調(diào)作用的考慮，對(duì)于有利于協(xié)調(diào)的個(gè)體賦予較高的適應(yīng)度，反之則賦予較低的適應(yīng)度。這樣，促使各個(gè)群體向相互協(xié)調(diào)和適應(yīng)的方向進(jìn)化，從而產(chǎn)生協(xié)調(diào)行為。第二十四頁，共31頁。多智能體技術(shù)的應(yīng)用MAS的應(yīng)用研究開始于20世紀(jì)80年代中期，并表現(xiàn)出明顯增長的趨勢(shì)。1、智能機(jī)器人智能機(jī)器人通常包括多個(gè)信息處理子系統(tǒng)，如二維三維視覺處理、信息融合、規(guī)劃決策以及自動(dòng)駕駛等。在多機(jī)器人系統(tǒng)中，每個(gè)機(jī)器人作為一個(gè)智能體，當(dāng)多機(jī)器人同時(shí)從事同一項(xiàng)或多項(xiàng)工作時(shí)，利用多智能體技術(shù)建立多智能體機(jī)器人的協(xié)調(diào)系統(tǒng)，避免沖突的出現(xiàn)，共同完成復(fù)雜并行的作業(yè)任務(wù)。第二十五頁，共31頁。多智能體技術(shù)的應(yīng)用

2、交通控制如分布式路徑指導(dǎo)系統(tǒng)，把交通圖知識(shí)庫中的信息與路徑邊界搜索算法相結(jié)合，項(xiàng)駕駛員提供最佳路徑的行駛建議。3、分布式預(yù)測(cè)、監(jiān)控及診斷再對(duì)暴風(fēng)雨氣象觀測(cè)中，把各區(qū)域觀測(cè)站分別作為一個(gè)智能體，各智能體根據(jù)觀測(cè)數(shù)據(jù)作出局部觀測(cè)，進(jìn)行分布式問題求解，然后通過網(wǎng)絡(luò)和協(xié)調(diào)機(jī)制，最終形成關(guān)于整個(gè)區(qū)域的可靠一致的全局預(yù)測(cè)。第二十六頁，共31頁。多智能體技術(shù)的應(yīng)用

4、柔性制造：在大型分布式復(fù)雜制造系統(tǒng)中，可以把復(fù)雜的企業(yè)活動(dòng)劃分成多組任