多智能體技術(shù)

1、多智能體技術(shù)多智能體技術(shù) 摘 要 當(dāng)今，分布式人工智能研究的一個熱點是多智能體系統(tǒng)，它是分布式問題求解 的進一步發(fā)展。隨著多智能體理論與技術(shù)的發(fā)展，其應(yīng)用范圍也在不斷擴大著，但是由 于其理論與應(yīng)用研究剛起步不久，還有不少問題有待解決。本論文回顧了多智能體技術(shù) 的發(fā)展歷史，指出了多智能體理論及應(yīng)用的研究方向，介紹了多智能體技術(shù)的基本概念 和特點，多智能體系統(tǒng)的體系結(jié)構(gòu)，多智能體中的協(xié)調(diào)與協(xié)作方法等內(nèi)容。 關(guān)鍵詞 多智能體系統(tǒng)；多智能體結(jié)構(gòu)；多目標(biāo)優(yōu)化；協(xié)調(diào)協(xié)作Multi-agent technologyAbstract Nowadays, one of the hot points in dis

2、tributed artificial intelligence research is multi-agent system, which is the further development in distributed problem solving. With the development of multi-agent theory andtechnology, its application is being expanded.As the theory and applicationis just starting, there are manyissues to be reso

3、lved. In this paper, the thesis reviews the development of EGCS, points out the research directions of multi-agent theory and application, and introduces the basic concepts and characteristics, Multi-agent system architecture ， the coordination and collaboration on Multi-agent system.Keywords Multi-

4、agent systems； Multi-agent architecture ；Multi-objective optimization ；Coordination and collaboration/、八1. 前言目前的工業(yè)系統(tǒng)正向大型、復(fù)雜、動態(tài)和開放的方向轉(zhuǎn)變，傳統(tǒng)的工業(yè)系統(tǒng)和多機 器人技術(shù)在許多關(guān)鍵問題上遇到了嚴(yán)重的挑戰(zhàn)。分布式人工智能 (DAI ，Distributed Artificial Intelligence) 與多智能體系統(tǒng) (MAS, Multi-Agent System) 理論為解決這 些挑戰(zhàn)提供了一種最佳途徑。智能體系統(tǒng)是分布式人工智能的一個重要分支，是 20 世

5、紀(jì)末至 21 世紀(jì)初國際上人工智能的前沿學(xué)科。研究的目的在于解決大型、復(fù)雜的現(xiàn)實 問題，而解決這類問題已超出了單個智能體的能力，將DAT MAS充分應(yīng)用于工業(yè)系統(tǒng)和多機器人系統(tǒng)的結(jié)果，便產(chǎn)生了一門新興的機器人技術(shù)領(lǐng)域一多智能體機器人系統(tǒng) (MARS， MultiAgent Robot System) ?？偟膩碚f，多智能體系統(tǒng)領(lǐng)域正在蓬勃發(fā)展。2. 多智能體2.1 多智能體理論的發(fā)展歷史智能體 Agent 的概念最早可以追溯到 1977 年的 Carl Hewitt 的“ Viewing Con trol Structure as Patter ns of Pass ing Messages&#

6、39; 一 文。在此文中， Carl Hewitt 給出了一個稱為“Actor ”的對象，它具有自身的內(nèi)在狀態(tài)，又能與其他同類對象發(fā)送和反饋信息。而正式采用“ Age nt ”一詞可見于 M. Min sky于1986年出版的“ Society of Mind” 一書，文中用“ Age nt ”稱呼一些具有特別技能的個體，它們存在于社會中，并 通過競爭或協(xié)商求解矛盾 1 。多智能體系統(tǒng)(簡稱 MAS是由多個單 Age nt組成的集合，該系統(tǒng)可以協(xié)調(diào)一組 Agent 的行為(知識、目標(biāo)、方法和規(guī)劃) ，以協(xié)同完成一個任務(wù)或是求解問題，各個單Age nt可以有同一個目標(biāo)，也可以有多個相互作用的不同

7、目標(biāo)，它們不僅要共享有關(guān)問 題求解方法的指示，而且要就單 Age nt間的協(xié)調(diào)過程進行推理。多智能體理論的應(yīng)用研 究開始于20世紀(jì)80年代中期，近些年呈明顯增長的趨勢。尤其是近10年來，Age nt和 多智能體系統(tǒng)理論和技術(shù)頻繁出現(xiàn)在大量應(yīng)用系統(tǒng)的設(shè)計中，對Age nt的研究已成為人工智能學(xué)科的一個熱點，是人工智能學(xué)科的核心內(nèi)容。目前， Age nt方法和MAS等相關(guān) 技術(shù)已經(jīng)日益應(yīng)用于智能機器人、交通控制、制造系統(tǒng)、網(wǎng)絡(luò)智能化、電子商務(wù)、軟件 系統(tǒng)等領(lǐng)域，成為一種對復(fù)雜系統(tǒng)進行分析、設(shè)計的有力思想方法和工具。2.2多智能體技術(shù)的基本概念和特點2.2.1多智能體技術(shù)的基本概念多智能體系統(tǒng)（Mu

8、lti-Age nt System ， MAS是由多個 Age nt組成的集合，Age nt 之間及Age nt與環(huán)境之間通過通訊、協(xié)商與協(xié)作來共同完成單個 Age nt不能解決的問題。 也可以簡單地說，多智能體系統(tǒng)是指由多個自主或半自主的構(gòu)件所構(gòu)成的各種大型的系 統(tǒng)。在多智能體系統(tǒng)中，數(shù)據(jù)是分散的，沒有系統(tǒng)的全局控制。多智能體技術(shù)提供了一 種適合分布式計算和不確定問題求解的新方法， 這是因為多智能體系統(tǒng)放松了對集中式 規(guī)劃、順序控制的限制，提供了分散控制、應(yīng)急和并行處理的能力，并且它是一個高度交叉的研究領(lǐng)域，它吸取了不同領(lǐng)域的內(nèi)容，如計算機科學(xué)、人工智能、經(jīng)濟學(xué)、社會學(xué)等22.2.2多智能體

9、技術(shù)的特點多智能體系統(tǒng)不同于傳統(tǒng)的分布式處理系統(tǒng)，它要求系統(tǒng)中每Age nt及Age nt之間的交流具有智能性或自組織能力（如推理、規(guī)劃、學(xué)習(xí)等）。其主要特點如下3:（1）社會性在MAS中，Age nt可能處于由多個Age nt構(gòu)成的社會環(huán)境中，擁有其他 Age nt的信 息和知識，能通過Age nt通信語言與其他Age nt實施靈活多樣的交互和通信，實現(xiàn)與其 他Age nt的合作、協(xié)調(diào)、協(xié)商等，以完成自身的問題求解或幫助其他Age nt完成任務(wù)。（2）自治性在MAS中，一個Age nt發(fā)出服務(wù)請求后，其他Age nt只有同時具備提供此服務(wù)的能 力和興趣，才能接受動作委托。因此，一個Age n

10、t不能強制其他Age nt提供某項服務(wù)。（3）協(xié)作性在MAS中，具有不同目標(biāo)的各個Age nt必須相互協(xié)同、協(xié)商未完成問題的求解。通 常的協(xié)作有：資源共享協(xié)作、生產(chǎn)者/消費者關(guān)系協(xié)作、任務(wù)/子任務(wù)關(guān)系協(xié)作等。 2.3多智能體理論應(yīng)用的研究方向作為分布式人工智能的重要組成部分，多智能體技術(shù)的理論與應(yīng)用研究剛起步不 久，還有不少問題有待解決。今后多智能體的研究方向主要集中在以下幾個方面5:（1）多智能體系統(tǒng)的實時性：一般的實時條件下，需要集中于對多智能體系統(tǒng)通訊層、協(xié)作層和控制層的設(shè)計及 性能（不確定性、可靠性、魯棒性、推理機制、學(xué)習(xí)機制及各種規(guī)劃算法等）的提高。 而在復(fù)雜實時動態(tài)條件下，對 Ag

11、e nt結(jié)構(gòu)、表達(dá)方法以及協(xié)調(diào)機制的研究與設(shè)計也是多 智能體的研究方向之一；對于開放式綜合多級的多智能體系統(tǒng)結(jié)構(gòu)，要求該結(jié)構(gòu)反映復(fù) 雜環(huán)境下多層次、實時、動態(tài)的特點，并隨問題性質(zhì)的變化而改變；另外，在實時動態(tài) 環(huán)境下，建立定性和定量相結(jié)合的局部一全局不精確多智能體推理模型，并將時序推理、非單調(diào)推理、時限推理和異步事件處理技術(shù)溶入多智能體系統(tǒng)推理中，以及采用模糊集 理論，研究多智能體系統(tǒng)中各 Age nt的不一致性和不確定性，探討多智能體可信度協(xié)調(diào) 4多智能體技術(shù)模型亦作為今后的主要研究內(nèi)容，提出有效解決實時動態(tài)環(huán)境下仍能保持系統(tǒng)良好性能 的解決方法。（2）網(wǎng)絡(luò)環(huán)境下的多智能體系統(tǒng)研究基于多智能

12、體技術(shù)的網(wǎng)絡(luò)智能化方法，探討建立和完善基于多智能體的分布式 仿真系統(tǒng)和測試平臺所面臨的軟件和硬件問題。（3）多智能體系統(tǒng)的協(xié)調(diào)在復(fù)雜的實時動態(tài)環(huán)境下，因存在時間及資源上的約束，需要解決Age nt系統(tǒng)在有限時間和資源的前提下進行資源分配、任務(wù)調(diào)度、行為協(xié)調(diào)、沖突消解等協(xié)調(diào)合作問題， 因而研究多智能體系統(tǒng)也需要將重點放在對于功能獨立的各個Age nt通過協(xié)調(diào)及協(xié)作，完成復(fù)雜的控制任務(wù)或解決復(fù)雜問題方面上。具體研究內(nèi)容主要是參與協(xié)調(diào)Age nt對系 統(tǒng)所做的貢獻、Age nt信息的可靠度以及各 Age nt之間的影響問題。此外，對參與協(xié)調(diào) Age nt的重視程度和將多目標(biāo)協(xié)調(diào)問題轉(zhuǎn)化為單目標(biāo)協(xié)調(diào)問

13、題亦是其研究方向之一。（4）實際應(yīng)用的多智能體系統(tǒng)考核指標(biāo)在多智能體系統(tǒng)應(yīng)用于實際的過程中，會有多個考核指標(biāo)來對多智能體系統(tǒng)的應(yīng)用 價值進行評價，并且在用戶界面、系統(tǒng)的穩(wěn)定性、安全性、學(xué)習(xí)機制的準(zhǔn)確性、可靠性 及學(xué)習(xí)的延時性、實時性以及魯棒性等問題上都需要進一步的研究與改進，以達(dá)到考核 指標(biāo)的綜合優(yōu)化。（5）邏輯符號與數(shù)學(xué)計算相結(jié)合的多智能體系統(tǒng)研究多智能體的符號和數(shù)學(xué)方式的表達(dá)方法，探討符號運算與數(shù)學(xué)計算的相互結(jié)合 與轉(zhuǎn)換，并將其應(yīng)用于以機器和操作者構(gòu)成的人機共存的多智能體系統(tǒng)。（6）基于多智能體系統(tǒng)的分布智能控制探討將多智能體技術(shù)應(yīng)用于實際的智能控制中所面臨的問題，進一步研究具有分布和協(xié)調(diào)

14、功能的智能控制系統(tǒng)的性能。2.4多智能體中的協(xié)調(diào)與協(xié)作在開放的多智能體系統(tǒng)中，每個 Age nt都具有自主性，在求解和運行過程中會按照 自己的目的、知識與能力進行活動，經(jīng)常會出現(xiàn)矛盾沖突，其根源在于Age nt間的知識不完備性、目標(biāo)不一致性、不兼容性等方面。因此，MAS的Age nt之間需要進行協(xié)作與協(xié)調(diào)。多智能體協(xié)作（cooperation ）是指多個Age nt通過協(xié)調(diào)各自的行為，合作完 成共同的目標(biāo)。多智能體協(xié)調(diào)（coordi nat ing ）是指具有不同目標(biāo)的多個 Age nt對其目 標(biāo)、資源等進行合理安排，以協(xié)調(diào)各自行為，最大限度地實現(xiàn)各自目標(biāo)。2.4.1多智能體中的協(xié)調(diào)。有效的協(xié)

15、調(diào)是自主的Age nt在MAS中達(dá)到目標(biāo)的關(guān)鍵。MAS中存在Age nt相互依 賴的行為時，由于有多個Age nt的意圖存在，當(dāng)發(fā)生沖突時，就要進行協(xié)調(diào)。協(xié)調(diào)是保 證多智能體系統(tǒng)中Age nt合作的主要方法。通過協(xié)調(diào)多智能體系統(tǒng)中Age nt的個體行為， 使得多智能體系統(tǒng)的整體行為得到改進，提高系統(tǒng)的性能，或是減少系統(tǒng)的沖突 3。 2.4.1.1多智能體協(xié)調(diào)類型多智能體系統(tǒng)的協(xié)調(diào)分為顯式協(xié)調(diào)和隱式協(xié)調(diào)兩種4。顯式協(xié)調(diào)是指Age nt被設(shè)計 成能夠?qū)赡艿慕换ミM行推理，必要時與其他 Age nt進行協(xié)商。隱式協(xié)調(diào)是指Age nt被 設(shè)計成遵循某局部的行為規(guī)則。（1）顯式協(xié)調(diào)顯式協(xié)調(diào)以協(xié)調(diào)控制行為

16、的執(zhí)行者在系統(tǒng)中的分布程度可分為完全集中的協(xié)調(diào)、完全分布的協(xié)調(diào)以及集中與分布相結(jié)合的協(xié)調(diào)三類。完全集中的協(xié)調(diào)是指主控 Age nt完全控制從屬者的行為，由主控 Age nt內(nèi)部的規(guī)劃器保證從屬 Age nt的行為彼此協(xié)調(diào)，這種 協(xié)調(diào)方法在機器世界中已有應(yīng)用。集中協(xié)調(diào)方法降低了系統(tǒng)的復(fù)雜性，減少了用于協(xié)調(diào) 的通信開銷，但卻要求中心規(guī)劃器有極強的處理能力，要處理各種可能沖突來形成一個 全局一致的方案。在完全分布的協(xié)調(diào)方法中，各 Age nt處于平等的地位，彼此行為的協(xié) 調(diào)通過各Age nt內(nèi)部的推理機制或Age nt之間的多次交互，必要時進行協(xié)商實現(xiàn)。這種 協(xié)調(diào)方法適合于研究理性Age nt的多智

17、能體系統(tǒng)。(2) 隱式協(xié)調(diào)由于處理大量的可能沖突以形成一個全局一致的方案，交互通信或中心規(guī)劃器的方法是可行的，因此多智能體系統(tǒng)中出現(xiàn)了關(guān)于社會規(guī)則、過濾、標(biāo)準(zhǔn)等隱式的研究。 Shoham提出人工Age nt社會規(guī)定一套規(guī)則，每個 Age nt必須遵守，同時相信其他 Age nt 也會遵守。這些規(guī)則一方面會限制每一個Age nt所選擇的動作，另一方面也可確保其他Age nt的社會行為的協(xié)調(diào)。多智能體過濾是指過濾掉與任意Age nt的已知目標(biāo)或與既定目標(biāo)不相容的選項。過濾策略與社會規(guī)則的原則相同，都是根據(jù)一定的原則將Age nt可選動作中相容的一部分視為合理的而保留下來，從而協(xié)調(diào)Age nt的行為

18、。標(biāo)準(zhǔn)化是指在某些情況下，協(xié)調(diào)Age nt通過標(biāo)準(zhǔn)化進行協(xié)調(diào)，即建立受控 Age nt在一些情況下必須遵 守的標(biāo)準(zhǔn)規(guī)則。如計算機程序就是標(biāo)準(zhǔn)化協(xié)調(diào)的例子。241.2多智能體協(xié)調(diào)方法目前多智能體協(xié)調(diào)方法主要有如下四種5:(1) 基于集中規(guī)劃的協(xié)調(diào)如果MAS中至少有一個Age nt具備其他Age nt的知識、能力和環(huán)境資源知識，那么 該Age nt可作為主控Age nt對該系統(tǒng)的目標(biāo)進行分解，對任務(wù)進行規(guī)劃，并指示或建議 其他Age nt執(zhí)行相關(guān)任務(wù)。這種基于集中規(guī)劃的協(xié)調(diào)方法特別適合于環(huán)境和任務(wù)相應(yīng)固 定、動態(tài)行為集可預(yù)計和需要集中監(jiān)控的情況，如機器人協(xié)調(diào)和智能控制。(2) 基于協(xié)商的協(xié)調(diào)當(dāng)協(xié)商

19、時，系統(tǒng)中沒有作為規(guī)劃的主控Age nt。協(xié)商是Age nt交換信息、討論和達(dá)成一致的方式。具體協(xié)商方法有合同網(wǎng)協(xié)商、功能精確的協(xié)作和基于對策論的協(xié)商等等。(3) 基于對策論的協(xié)調(diào)此協(xié)調(diào)方法包括無通信協(xié)調(diào)和有通信協(xié)調(diào)兩類。無通信協(xié)調(diào)是在沒有通信的情況 下，Age nt根據(jù)對方及自身的效益模型，按照對策論選擇適當(dāng)行為。在這種協(xié)調(diào)方式中， Age nt至多只能達(dá)到協(xié)調(diào)的平衡解。在基于對策論的有通信協(xié)調(diào)中可以得到協(xié)作解。(4) 基于社會規(guī)則的協(xié)調(diào)這是一類以每個Age nt都必須遵循的社會規(guī)則、過濾策略、標(biāo)準(zhǔn)和管理為基礎(chǔ)的協(xié) 調(diào)方法。這些規(guī)則對各Age nt的行為加以限制，過濾某些有沖突的意圖和行為，

20、保證其 他Age nt必須具有的行為方式，從而確保本 Age nt行為的可行性，以實現(xiàn)整個 Age nt系 統(tǒng)的社會行為的協(xié)調(diào)。2.4.2多智能體中的協(xié)作協(xié)作，也就是合作，是Age nt社會性的表現(xiàn)，就同人類一樣，能夠共同完成復(fù)雜的 任務(wù)。多智能體的協(xié)作問題是多智能體系統(tǒng)研究的重點。2.4.2.2多智能體協(xié)作類型按照Age nt間相互依賴的關(guān)系，多智能體系統(tǒng)問題求解的協(xié)作類型分為如下四種11:(a) 水平協(xié)作一種水平協(xié)作是：協(xié)作團體中的每個 Age nt都不具有求解全局問題的能力，問題的 解決需要眾多智能體協(xié)作完成。另一種水平協(xié)作是：在協(xié)作團體中的每一個Age nt都能獨立解決問題而無需依賴其

21、他 Age nt，但如果Age nt能相互作用(用不同Age nt的知識 和數(shù)據(jù)進行推理或采用不同的推理機制)，這樣就能大大提高解的可信度。例如在給病 人診斷病情時，多個醫(yī)生之間的協(xié)作就是這種類型，將意見進行相互探討及比較，則會 大大提高最終診斷的可信度。(b) 樹型協(xié)作高一級的Age nt根據(jù)低一級的Age nt的結(jié)果做出解決問題的最后結(jié)論。例如總工程師常常根據(jù)幾位工程師的意見給出最后的方案。(c) 循環(huán)協(xié)作為了求得問題的解，不同的Age nt間相互依賴，往復(fù)協(xié)作。例如，為了解釋地質(zhì)數(shù) 據(jù)，往往需要地理專家、地質(zhì)專家、地球物理專家和地球化學(xué)專家的相互依賴、往復(fù)協(xié) 作才能做出解釋，即地球物理專

22、家和地球化學(xué)專家完成一個子任務(wù)，而地球化學(xué)專家在 完成該子任務(wù)的同時又可能要求地球地理專家的協(xié)助。由此可以看出，樹型協(xié)作時循環(huán) 協(xié)作的一個特例。(d) 混雜協(xié)作即整個系統(tǒng)在某些級上用水平協(xié)作類型，而在整體上又是樹型協(xié)作或循環(huán)協(xié)作類型，或 整體上采用水平協(xié)作而局部采用樹型或循環(huán)協(xié)作類型。242.2多智能體協(xié)作方法多智能體協(xié)作方法主要有合同網(wǎng)協(xié)作方法、黑板模型協(xié)作方法、結(jié)果共享協(xié)作方法 和功能精確的協(xié)同方法等等。(a) 合同網(wǎng)合同網(wǎng)方法的思想源自人們用于管理商品和服務(wù)的合同機制。其基本思想是：將任 務(wù)的委派通過節(jié)點之間的招投標(biāo)過程實現(xiàn)，在招投標(biāo)過程中，利用通信機制對每個任務(wù) 的分配進行協(xié)商，避免資

23、源、知識等的沖突。即節(jié)點之間通過“招標(biāo)-投標(biāo)-中標(biāo)”這 一市場投標(biāo)機制進行任務(wù)分配，使系統(tǒng)以較低的代價、較高的質(zhì)量完成分布式任務(wù)。所 有Age nt分為兩種角色：管理者和工作者。不需要預(yù)先規(guī)定Age nt的角色，任何Age nt既可以通過發(fā)布任務(wù)通知書進行招標(biāo)而成為管理者，也可以通過應(yīng)答任務(wù)通知書參與投 標(biāo)而成為工作者。這一靈活性使任務(wù)能夠被不同層次地分解分配，系統(tǒng)中的每一待求解 任務(wù)，由承擔(dān)該任務(wù)的Age nt負(fù)責(zé)。當(dāng)Age nt無法獨立完成該任務(wù)時，它就將任務(wù)分解， 并履行管理者職責(zé)，為每一任務(wù)發(fā)放任務(wù)通知書，然后從返回的投標(biāo)中選定合適的工作 者，將子任務(wù)分配給它，并建立相應(yīng)的合同。合同網(wǎng)

24、適用于任務(wù)能夠獨立分解，子任務(wù) 之間不存在相互作用的多智能體系統(tǒng)，但也存在著通信頻繁、資源浪費等問題。(b) 黑板模型黑板模型結(jié)構(gòu)是為解決分布在不同物理環(huán)境下多個實體協(xié)作完成任務(wù)的并行和分 布計算模型。在多智能體協(xié)作中，黑板模型的基本思路是：多個Age nt協(xié)作求解一個問題，黑板是一個共享的問題求解空間，多個 Age nt都能“看到”黑板上的各種信息。當(dāng) 問題和初始數(shù)據(jù)記錄到黑板上，協(xié)作求解開始。所有Age nt通過“看”黑板尋求有利于其經(jīng)驗知識發(fā)揮的信息，能夠?qū)崿F(xiàn)向問題解的靠近。當(dāng)一個Age nt發(fā)現(xiàn)黑板上的信息足以支持它進一步求解問題時，它就將求解結(jié)果記錄在黑板上。新增加的信息有可能使其

25、他Age nt繼續(xù)求解。重復(fù)這一過程直到問題徹底解決，獲得最終結(jié)果12。每個Age nt是獨立的專家，能獨立解決某一特定問題。黑板是一個共享的問題求解空間，各Age nt的交互通過黑板進行。監(jiān)控部分是根據(jù)問題求解的狀態(tài)和各知識源的求解技能，依據(jù)某種 策略，動態(tài)的選擇和激活適合的 Age nt，使各Age nt能實時響應(yīng)黑板的變化。這種方法 特別適合于事先無法確定求解次序的復(fù)雜問題，但為了正確理解由其他Age nt寫到黑板 上的信息，各Age nt要使用共同的交互語言。(c) 結(jié)果共享方法結(jié)果共享協(xié)作方法的基本思路是：各個 Age nt通過交換結(jié)果實現(xiàn)協(xié)作的問題求解， 逐步獲得最終的結(jié)果。每當(dāng)一個 Age nt求得某一問題的結(jié)果時，他就根據(jù)協(xié)作知識判斷哪些Age nt可能需要這一結(jié)果，并將結(jié)果傳送給相應(yīng)的Age nt。收到結(jié)果的Age nt可通過不同方式利用這個結(jié)果，以利于自身問題的計算或求解，從而產(chǎn)生一個更完整的求解 結(jié)果，并傳送給其他需要的 Age nt。重復(fù)此過程，直至整體任務(wù)完成。結(jié)果共享的協(xié)作求解方法可以增加正確結(jié)果的可信度，提高求解效率和資源利用 率，改善群體求解的性能。但其實現(xiàn)有一定的難度，比如不知道哪些結(jié)果該共享，不知 道利用結(jié)果做什么，怎樣將其他 Age nt的結(jié)果融合到