分布式人工智能與mas

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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