分布式人工智能與mas

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

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

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

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

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

6、是人工智能研究的最初和最終目標(biāo)。,Agent及多Agent系統(tǒng)(MAS),多智能體理論對于促進(jìn)經(jīng)濟(jì)、工業(yè)、社會、軍事等方面的進(jìn)步都具有深遠(yuǎn)的意義。主要研究內(nèi)容1、微觀 Agent本身，包括Agent基本特性、相應(yīng)理論、內(nèi)部實現(xiàn)框架。2、宏觀 Agent與環(huán)境及其它Agent的關(guān)系，包括，多Agent系統(tǒng)體系結(jié)構(gòu)、Agent通信語言、Agent交互與協(xié)商、Agent協(xié)作與合作、多Agent知識交互與信息共享、多Agen

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

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

9、4、主動性 主動感知周圍環(huán)境的變化，并作出基于目標(biāo)的行為。,Agent,5、協(xié)作性 通過協(xié)作提高多Agent系統(tǒng)的性能。6、持久性 在“相當(dāng)長”的時間內(nèi)連續(xù)運行。7、自適應(yīng)性 根據(jù)過去的經(jīng)驗積累知識，并且修改其行為以適應(yīng)新的環(huán)境。8、情態(tài)特性 具有信念、意圖、愿望等情態(tài)。9、可推理性 可根據(jù)當(dāng)前知識和經(jīng)驗，以理性的方式進(jìn)行推理或預(yù)測。,Agent,10、可移動性 可從一個地方移動到另一個地方而

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

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

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

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

14、 這是目前最為系統(tǒng)和成熟的多智能體協(xié)調(diào)理論框架，由Cohen和Levesque在BDI理論的基礎(chǔ)上，提出了承諾（Commitment）和公約（Convention）等概念。其基本思想是：多個智能體在完成共同的任務(wù)時會形成一個共同的承諾，并堅守承諾，直到成功完成共同任務(wù)，除非出現(xiàn)下列任何一種情況：①智能體發(fā)現(xiàn)共同任務(wù)已經(jīng)完成；②智能體發(fā)現(xiàn)共同任務(wù)不可能完成；③智能體發(fā)現(xiàn)沒有必要執(zhí)行該共同任務(wù)。如果發(fā)生以上情況，智能體就把“自己將要

15、退出承諾”的意圖設(shè)法通知正在聯(lián)合執(zhí)行任務(wù)的其他智能體，以便適時地進(jìn)行調(diào)整。通過這樣的承諾和公約機制，多個智能體就能協(xié)調(diào)完成共同的任務(wù)。所以，聯(lián)合意圖理論只是為了各個智能體在完成共同任務(wù)時參與和堅持的一致性提供了一個框架，而沒有確定聯(lián)合行為中的具體分工和協(xié)作問題。,基于符號推理系統(tǒng)的體系結(jié)構(gòu)及協(xié)調(diào)機制,,（2）共享計劃理論 該理論由Grosz等提出。其基本思想是：參與聯(lián)合行動的各個智能體先達(dá)成一個包括具體行動步驟和各方面細(xì)節(jié)的共

16、享計劃，并且相信所有智能體都打算參與聯(lián)合行動并接受共享計劃；數(shù)個智能體組建形成子團(tuán)體，不同的子團(tuán)體或單獨或組合地完成共享計劃的每一個具體步驟；子團(tuán)體之外的其他智能體都相信子團(tuán)體能夠完成相應(yīng)的具體步驟，并形成相應(yīng)的共享計劃。于是，通過共享計劃的協(xié)調(diào)，各個智能體就能合作完成共同的任務(wù)。,基于符號推理系統(tǒng)的體系結(jié)構(gòu)及協(xié)調(diào)機制,,（3）計劃的隊行為 計劃由設(shè)計者事先確定，而不是由MAS動態(tài)產(chǎn)生，各個智能體在行動之前就被賦予有關(guān)完整計劃的

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

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

19、通過基本行為的選擇和組合來完成所要求的任務(wù)，因此，行為選擇機制的研究非常重要，也是多智能體協(xié)調(diào)研究的熱點和核心問題。,基于行為主義的體系結(jié)構(gòu)及協(xié)調(diào)機制,,其基本思想是：由各種基本行為構(gòu)成一個網(wǎng)狀結(jié)構(gòu)，各個結(jié)點表示相應(yīng)的基本行為，而各個結(jié)點之間的連接表示為行為的活性，即行為對目標(biāo)的貢獻(xiàn)和效能的一種度量，如果行為促使目標(biāo)的實現(xiàn)，其活性值為正，反之為負(fù)，并且，這種效能越大，其活性值就越大。各種行為之間存在激勵或抑制的相互作用影響，于是，相應(yīng)的

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

21、用的機器學(xué)習(xí)過程，并適用于多智能體的協(xié)調(diào)。在協(xié)進(jìn)化計算中，通?？紤]多個物種群體，每個物種都有相應(yīng)的個體類型，各個物種群體采用進(jìn)化算法實現(xiàn)其進(jìn)化過程。與常規(guī)模擬進(jìn)化不同的是，在對個體進(jìn)行適應(yīng)度評價時，增加對群體間交互協(xié)調(diào)作用的考慮，對于有利于協(xié)調(diào)的個體賦予較高的適應(yīng)度，反之則賦予較低的適應(yīng)度。這樣，促使各個群體向相互協(xié)調(diào)和適應(yīng)的方向進(jìn)化，從而產(chǎn)生協(xié)調(diào)行為。,多智能體技術(shù)的應(yīng)用,,MAS的應(yīng)用研究開始于20世紀(jì)80年代中期，并表現(xiàn)出明顯增長

22、的趨勢。1、智能機器人 智能機器人通常包括多個信息處理子系統(tǒng)，如二維三維視覺處理、信息融合、規(guī)劃決策以及自動駕駛等。在多機器人系統(tǒng)中，每個機器人作為一個智能體，當(dāng)多機器人同時從事同一項或多項工作時，利用多智能體技術(shù)建立多智能體機器人的協(xié)調(diào)系統(tǒng)，避免沖突的出現(xiàn)，共同完成復(fù)雜并行的作業(yè)任務(wù)。,多智能體技術(shù)的應(yīng)用,,2、交通控制如分布式路徑指導(dǎo)系統(tǒng)，把交通圖知識庫中的信息與路徑邊界搜索算法相結(jié)合，項駕駛員提供最佳路徑的行駛建議。

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

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

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