分布式人工智能與mas

1、分布式人工智能與多Agent系統(tǒng),計(jì)算機(jī)科學(xué)技術(shù)發(fā)展趨勢(shì),1、智能化2、個(gè)性化3、網(wǎng)絡(luò)化4、并行化,分布式人工智能(DAI),一、基本概念 研究在邏輯上或物理上分散的智能系統(tǒng)如何并行地、相互協(xié)作地實(shí)現(xiàn)問(wèn)題求解。,分布式人工智能(DAI),二、特點(diǎn) 1)系統(tǒng)中的數(shù)據(jù)、知識(shí)以及控制不但在邏輯上，而且在物理上分布的，既沒(méi)有全局控制，也沒(méi)有全局的數(shù)據(jù)存儲(chǔ)。 2)各個(gè)求解機(jī)構(gòu)由計(jì)算機(jī)網(wǎng)絡(luò)互連，在問(wèn)題求解過(guò)程中，通信代價(jià)要比

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

3、結(jié)點(diǎn)之間劃分。2)多Agent系統(tǒng)(MAS) 主要研究自主的智能Agent之間智能行為的協(xié)調(diào)，為了一個(gè)共同的全局目標(biāo)，也可能是關(guān)于各自的不同目標(biāo)，共享有關(guān)問(wèn)題和求解方法的知識(shí)，協(xié)作進(jìn)行問(wèn)題求解。 注：基于Agent的計(jì)算將成為軟件開(kāi)發(fā)的下一個(gè)重要的突破口。,分布式問(wèn)題求解(DPS),一、協(xié)作方式 任務(wù)分擔(dān)(task sharing)和結(jié)果共享(results sharing)二、求解過(guò)程1、任務(wù)分解2、任務(wù)分配

4、3、子問(wèn)題求解4、結(jié)果綜合注：1)典型的任務(wù)分解和任務(wù)分配的方法有：合同網(wǎng)絡(luò)(類(lèi)似于“招標(biāo)”)、動(dòng)態(tài)層次控制、自然分解、固定分解、部分全局規(guī)劃； 2)在DPS中常用的通信方式有：共享全局存儲(chǔ)器、消息傳遞及二者的結(jié)合。 3)黑板模型是DPS中使用較多的框架結(jié)構(gòu)。,Agent及多Agent系統(tǒng)(MAS),智能體最早出現(xiàn)在20世紀(jì)70年代的人工智能領(lǐng)域，它所具有的智能性和靈活性，使得該技術(shù)成為研究復(fù)雜系統(tǒng)的重要手段。單個(gè)智能體的能力、

5、知識(shí)和計(jì)算資源都很有限，而多個(gè)智能體組成的多智能體系統(tǒng)已成為解決大型、復(fù)雜、分布式及難預(yù)測(cè)問(wèn)題的重要手段。90年代以來(lái)，多智能體系統(tǒng)已經(jīng)成為分布式人工智能研究的熱點(diǎn)，對(duì)智能體以及MAS的研究已經(jīng)成為人工智能的核心問(wèn)題。多智能體系統(tǒng)對(duì)許多學(xué)科和技術(shù)的發(fā)展起到了很大的指導(dǎo)和促進(jìn)作用，由于Agent的出現(xiàn)，人們可以對(duì)人工智能進(jìn)行以下全新的詮釋?zhuān)?“人工智能是計(jì)算機(jī)科學(xué)的一個(gè)分支，其目標(biāo)是構(gòu)造能表現(xiàn)出一定智能行為的智能體”。計(jì)算智能體甚至被認(rèn)為

6、是人工智能研究的最初和最終目標(biāo)。,Agent及多Agent系統(tǒng)(MAS),多智能體理論對(duì)于促進(jìn)經(jīng)濟(jì)、工業(yè)、社會(huì)、軍事等方面的進(jìn)步都具有深遠(yuǎn)的意義。主要研究?jī)?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通信語(yǔ)言、Agent交互與協(xié)商、Agent協(xié)作與合作、多Agent知識(shí)交互與信息共享、多Agen

7、t學(xué)習(xí)。,Agent,一、Agent的定義（尚未形成統(tǒng)一定義）關(guān)于Agent有多種稱(chēng)呼：代理、主體 、智能體、智能主體、艾真體等。 能夠自主連續(xù)地在一可動(dòng)態(tài)變化的、存在其它Agent的環(huán)境中運(yùn)行的，并可與環(huán)境進(jìn)行交互的實(shí)體，稱(chēng)為Agent。 廣義地講，Agent是具有自主性、社會(huì)能力(交互性)和反應(yīng)特征的計(jì)算機(jī)軟/硬件系統(tǒng)。Agent是可以感知其所處環(huán)境，并能根據(jù)自身的目標(biāo)作用于環(huán)境的計(jì)算實(shí)體。在沒(méi)有人的干預(yù)下能夠自主地

8、完成給定任務(wù)的對(duì)象都可以稱(chēng)為Agent。在人工智能領(lǐng)域，Agent被定義為具有感知能力、問(wèn)題求解能力和與外界通信能力的實(shí)體，是完全自治或半自治的。,Agent,三、Agent特性1、自治性 對(duì)自己的行為和內(nèi)部狀態(tài)有一定的控制權(quán)。2、社會(huì)性或稱(chēng)可通信性 能夠通過(guò)某種Agent通信語(yǔ)言與其它Agent進(jìn)行信息交換。 注：任務(wù)的承接、多Agent的協(xié)作、協(xié)商等均以通信為基礎(chǔ)。3、交互性 對(duì)環(huán)境的感知，并通過(guò)行為改變環(huán)境。

9、4、主動(dòng)性 主動(dòng)感知周?chē)h(huán)境的變化，并作出基于目標(biāo)的行為。,Agent,5、協(xié)作性 通過(guò)協(xié)作提高多Agent系統(tǒng)的性能。6、持久性 在“相當(dāng)長(zhǎng)”的時(shí)間內(nèi)連續(xù)運(yùn)行。7、自適應(yīng)性 根據(jù)過(guò)去的經(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è)。,Agent,10、可移動(dòng)性 可從一個(gè)地方移動(dòng)到另一個(gè)地方而

10、保持其內(nèi)部狀態(tài)不變。注：Agent可以攜帶數(shù)據(jù)，且可在遠(yuǎn)處執(zhí)行智能指令。11、誠(chéng)實(shí)性 不會(huì)故意提供錯(cuò)誤信息。12、友善性 Agent之間不存在互相沖突的目標(biāo)，總是盡力幫助其它Agent。13、理性總是盡力實(shí)現(xiàn)自己的目標(biāo)。,Agent,,四、智能體分類(lèi)本地智能體或網(wǎng)絡(luò)智能體集中式智能體或分布式智能體固定智能體或移動(dòng)智能體,多Agent,,多智能體系統(tǒng)是在邏輯上或物理上呈分布狀態(tài)的多個(gè)智能體組成的較為松散的聯(lián)合體，

11、各智能體按照預(yù)先規(guī)定的協(xié)議，根據(jù)系統(tǒng)的目標(biāo)狀態(tài)及自身的目的、資源和知識(shí)，利用通信網(wǎng)絡(luò)，相互之間通過(guò)協(xié)商來(lái)確定各自的任務(wù)，并通過(guò)協(xié)調(diào)和協(xié)作來(lái)共同完成任務(wù)并達(dá)到整體目標(biāo)。,多Agent,,基于多智能體系統(tǒng)研究復(fù)雜系統(tǒng)時(shí)，首先要根據(jù)系統(tǒng)的特點(diǎn)對(duì)單個(gè)智能體作出定義，賦予其一定的行為能力和參數(shù)，并對(duì)各個(gè)智能體之間以及智能體與環(huán)境之間的交互規(guī)則作出規(guī)定，以此描述系統(tǒng)及其變化過(guò)程。在復(fù)雜的動(dòng)態(tài)環(huán)境下，由于存在時(shí)間和資源的約束，多智能體系統(tǒng)需要解決的關(guān)

12、鍵問(wèn)題就是如何進(jìn)行資源分配、任務(wù)調(diào)度、行為協(xié)調(diào)和沖突消解，使功能獨(dú)立的智能體通過(guò)協(xié)商、協(xié)調(diào)來(lái)完成復(fù)雜的控制任務(wù)或解決復(fù)雜的問(wèn)題。,多智能體系統(tǒng)體系結(jié)構(gòu)和協(xié)調(diào)機(jī)制,,多智能體系統(tǒng)體系結(jié)構(gòu)及其協(xié)調(diào)機(jī)制是多智能體系統(tǒng)理論研究的核心問(wèn)題，它研究如何把多個(gè)智能體組織為一個(gè)群體并使各個(gè)智能體有效地進(jìn)行協(xié)調(diào)合作，從而達(dá)到解決整體問(wèn)題的目標(biāo)。對(duì)于多智能體系統(tǒng)體系結(jié)構(gòu)及其協(xié)調(diào)機(jī)制的研究，目前大致可以分為三種學(xué)派：基于符號(hào)推理系統(tǒng)的體系結(jié)構(gòu)及協(xié)調(diào)機(jī)制，基于

13、行為主義的體系結(jié)構(gòu)及協(xié)調(diào)機(jī)制，基于協(xié)作進(jìn)化方法的體系結(jié)構(gòu)及協(xié)調(diào)機(jī)制。,基于符號(hào)推理系統(tǒng)的體系結(jié)構(gòu)及協(xié)調(diào)機(jī)制,,這種學(xué)派的基礎(chǔ)是Bratman等提出的BDI(Brief Desire Intention)理論通過(guò)建立比較完整的符號(hào)系統(tǒng)并基于經(jīng)典人工智能的符號(hào)處理，來(lái)進(jìn)行知識(shí)推理以使智能體具有自主思考、決策以及與其他智能體和環(huán)境進(jìn)行協(xié)調(diào)行動(dòng)的能力。這種學(xué)派包括三種代表性的理論：,基于符號(hào)推理系統(tǒng)的體系結(jié)構(gòu)及協(xié)調(diào)機(jī)制,,（1）聯(lián)合意圖理論

14、 這是目前最為系統(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)沒(méi)有必要執(zhí)行該共同任務(wù)。如果發(fā)生以上情況，智能體就把“自己將要

15、退出承諾”的意圖設(shè)法通知正在聯(lián)合執(zhí)行任務(wù)的其他智能體，以便適時(shí)地進(jìn)行調(diào)整。通過(guò)這樣的承諾和公約機(jī)制，多個(gè)智能體就能協(xié)調(diào)完成共同的任務(wù)。所以，聯(lián)合意圖理論只是為了各個(gè)智能體在完成共同任務(wù)時(shí)參與和堅(jiān)持的一致性提供了一個(gè)框架，而沒(méi)有確定聯(lián)合行為中的具體分工和協(xié)作問(wèn)題。,基于符號(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é)的共

16、享計(jì)劃，并且相信所有智能體都打算參與聯(lián)合行動(dòng)并接受共享計(jì)劃；數(shù)個(gè)智能體組建形成子團(tuán)體，不同的子團(tuán)體或單獨(dú)或組合地完成共享計(jì)劃的每一個(gè)具體步驟；子團(tuán)體之外的其他智能體都相信子團(tuán)體能夠完成相應(yīng)的具體步驟，并形成相應(yīng)的共享計(jì)劃。于是，通過(guò)共享計(jì)劃的協(xié)調(diào)，各個(gè)智能體就能合作完成共同的任務(wù)。,基于符號(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ì)劃的

17、詳細(xì)信息。這種方法要求事先對(duì)智能體的行為環(huán)境有確切了解并做詳細(xì)計(jì)劃，所以不適合于動(dòng)態(tài)環(huán)境，其應(yīng)用比較有限。,基于符號(hào)推理系統(tǒng)的體系結(jié)構(gòu)及協(xié)調(diào)機(jī)制,,基于符號(hào)系統(tǒng)的多智能體體系結(jié)構(gòu)與協(xié)調(diào)機(jī)制存在的主要問(wèn)題是：①符號(hào)主義要求對(duì)環(huán)境有比較完整和復(fù)雜的模型，而如何使智能體自身模型的計(jì)算和推理與環(huán)境保持同步就是一個(gè)棘手的問(wèn)題；②復(fù)雜模型計(jì)算和推理使智能體對(duì)環(huán)境的適應(yīng)能力變差，并且難以滿(mǎn)足模型與領(lǐng)域無(wú)關(guān)性的要求；③對(duì)于大型復(fù)雜動(dòng)態(tài)系統(tǒng)而言，符號(hào)模型

18、建立過(guò)程的繁瑣和效率低下等問(wèn)題表現(xiàn)的尤為嚴(yán)重。,基于行為主義的體系結(jié)構(gòu)及協(xié)調(diào)機(jī)制,,基于行為主義的MAS以Brooks的基于行為的系統(tǒng)分析與設(shè)計(jì)方法為基礎(chǔ)，其系統(tǒng)設(shè)計(jì)有三個(gè)基本原則：最小性：系統(tǒng)應(yīng)盡量簡(jiǎn)單以便與環(huán)境進(jìn)行快速交互；無(wú)狀態(tài)性：系統(tǒng)本身沒(méi)有關(guān)于外部環(huán)境的狀態(tài)模型，其行為是基于感知——行為的模式進(jìn)行的；魯棒性：系統(tǒng)能夠有效地處理而不是去除實(shí)際環(huán)境中的不確定性。 基于行為主義的智能體設(shè)計(jì)的一般過(guò)程：首先確定一些基本行為，

19、通過(guò)基本行為的選擇和組合來(lái)完成所要求的任務(wù)，因此，行為選擇機(jī)制的研究非常重要，也是多智能體協(xié)調(diào)研究的熱點(diǎn)和核心問(wèn)題。,基于行為主義的體系結(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)的

20、活性值就在行為網(wǎng)中進(jìn)行傳播，通過(guò)相應(yīng)的活性傳播控制算法就可以對(duì)行為進(jìn)行有效的組合、調(diào)度和協(xié)調(diào)，從而完成復(fù)雜任務(wù)。,基于協(xié)進(jìn)化方法的體系結(jié)構(gòu)及協(xié)調(diào)機(jī)制,,自然界中的各個(gè)物種共同生存于同一個(gè)生態(tài)系統(tǒng)中，每個(gè)物種在其中都有自己的生存環(huán)境。由于資源有限，各個(gè)物種必須通過(guò)競(jìng)爭(zhēng)和合作才能獲得自己生存所需的資源。競(jìng)爭(zhēng)和合作又促使物種不斷進(jìn)化和改變，并影響彼此的進(jìn)化過(guò)程，這樣的過(guò)程就稱(chēng)為協(xié)進(jìn)化。 協(xié)進(jìn)化是克服傳統(tǒng)進(jìn)化算法的不足而提出的更為通

21、用的機(jī)器學(xué)習(xí)過(guò)程，并適用于多智能體的協(xié)調(diào)。在協(xié)進(jìn)化計(jì)算中，通?？紤]多個(gè)物種群體，每個(gè)物種都有相應(yīng)的個(gè)體類(lèi)型，各個(gè)物種群體采用進(jìn)化算法實(shí)現(xiàn)其進(jìn)化過(guò)程。與常規(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)行為。,多智能體技術(shù)的應(yīng)用,,MAS的應(yīng)用研究開(kāi)始于20世紀(jì)80年代中期，并表現(xiàn)出明顯增長(zhǎng)

22、的趨勢(shì)。1、智能機(jī)器人 智能機(jī)器人通常包括多個(gè)信息處理子系統(tǒng)，如二維三維視覺(jué)處理、信息融合、規(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ù)。,多智能體技術(shù)的應(yīng)用,,2、交通控制如分布式路徑指導(dǎo)系統(tǒng)，把交通圖知識(shí)庫(kù)中的信息與路徑邊界搜索算法相結(jié)合，項(xiàng)駕駛員提供最佳路徑的行駛建議。

23、3、分布式預(yù)測(cè)、監(jiān)控及診斷再對(duì)暴風(fēng)雨氣象觀測(cè)中，把各區(qū)域觀測(cè)站分別作為一個(gè)智能體，各智能體根據(jù)觀測(cè)數(shù)據(jù)作出局部觀測(cè)，進(jìn)行分布式問(wèn)題求解，然后通過(guò)網(wǎng)絡(luò)和協(xié)調(diào)機(jī)制，最終形成關(guān)于整個(gè)區(qū)域的可靠一致的全局預(yù)測(cè)。,多智能體技術(shù)的應(yīng)用,,4、柔性制造：在大型分布式復(fù)雜制造系統(tǒng)中，可以把復(fù)雜的企業(yè)活動(dòng)劃分成多組任務(wù)單元，各任務(wù)單元由一個(gè)智能體執(zhí)行，同時(shí)，把人的行為也看作一類(lèi)智能體。利用多媒體界面和人-機(jī)及機(jī)-機(jī)等交互方式，通過(guò)大量智能體的交互和

24、協(xié)調(diào)，實(shí)現(xiàn)各個(gè)地域分散的生產(chǎn)部門(mén)之間的知識(shí)共享和協(xié)調(diào)，實(shí)現(xiàn)復(fù)雜問(wèn)題的求解和企業(yè)各項(xiàng)功能的集成。,多智能體技術(shù)的應(yīng)用,,5、虛擬現(xiàn)實(shí)和多智能體社會(huì)虛擬現(xiàn)實(shí)是營(yíng)造人工環(huán)境的仿真技術(shù)，用戶(hù)在該環(huán)境中能與其他對(duì)象進(jìn)行相互作用。如電子市場(chǎng)，提出了買(mǎi)和賣(mài)這兩種智能體及其直接交互和代理交互算法，實(shí)現(xiàn)了市場(chǎng)中的貨物儲(chǔ)藏和買(mǎi)賣(mài)機(jī)制以及銀行信貸和金融管理機(jī)制。,多智能體技術(shù)的應(yīng)用,,6、網(wǎng)絡(luò)自動(dòng)化和智能化在互聯(lián)網(wǎng)中為用戶(hù)自動(dòng)查找存儲(chǔ)于不同地點(diǎn)的資料，幫

25、助用戶(hù)進(jìn)行網(wǎng)絡(luò)搜索，為異地用戶(hù)建立多媒體會(huì)議進(jìn)程。以一組協(xié)同工作的智能體為核心的應(yīng)用環(huán)境下的用戶(hù)之間的協(xié)同工作。7、網(wǎng)絡(luò)化的辦公自動(dòng)化采用智能體分別實(shí)現(xiàn)信息的收集、存儲(chǔ)、交換、加工和決策，可實(shí)現(xiàn)辦公自動(dòng)化系統(tǒng)的人機(jī)一體化。,多智能體技術(shù)的應(yīng)用,,8、作戰(zhàn)智能體模型研究作戰(zhàn)系統(tǒng)是社會(huì)復(fù)雜系統(tǒng)，現(xiàn)代戰(zhàn)爭(zhēng)呈現(xiàn)許多復(fù)雜系統(tǒng)的特征，如復(fù)雜非線(xiàn)性交互作用、自組織和自適應(yīng)性、分層的體系結(jié)構(gòu)。近年來(lái)，美國(guó)等發(fā)達(dá)國(guó)家對(duì)復(fù)雜性科學(xué)和多智能體技術(shù)等新方