多智能體系統(tǒng)及其協(xié)同控制研究進(jìn)展

1、- -多智能體系統(tǒng)及其協(xié)同控制研究進(jìn)展摘要：對多智能體系統(tǒng)及其協(xié)同控制理論研究和應(yīng)用方面的發(fā)展現(xiàn)狀進(jìn)行了簡要概述.首先給出Agent及多Agent系統(tǒng)的概念和特性等，介紹了研究多 Agent系統(tǒng)協(xié)同控制時通常用到的代數(shù)圖論 ；然后綜述了近年來多 Agent系統(tǒng)群集運(yùn)動和協(xié)同控制一致性方面的研究狀況 ，并討論了其在軍事、交通運(yùn)輸、智能機(jī)器人等方面的成功應(yīng)用；最后,對多Agent系統(tǒng)未來的發(fā)展方向進(jìn)行了探討和分析 ，提出幾個具有理論和實(shí)踐意義的研究方向 ，以促使多Agent系 統(tǒng)及其協(xié)同控制理論和應(yīng)用的深入研究 .關(guān)鍵詞：多Agent系統(tǒng)(MAS);協(xié)同控制；代數(shù)圖論；群集運(yùn)動；一致性協(xié)議Adva

2、nces in Multi-Agent Systems and Cooperative ControlAbstract: Progress in multi-Age nt systems with cooperative con trolwas reviewed in terms of theoretical research and its applicati ons. Firs,t con cepts and features used to defi ne Age nts and multi-Age nts were an alyzed. Then graph theory was in

3、 troduced, since it is ofte n used in research on cooperative con trol of multi-Age nt systems. Then adva nces in swarm in g/flock ing as well as the means used to derive a consensus among multi-Agents under cooperative control were summarized. The application of these abilitieswas discussed for the

4、 military, tran sportatio n systems,a nd robotics. Fin ally, future developme nts for multi-Agent systemswere considered and significant research problems proposed to help focus research on key questi ons formulti-Age nt systemswith cooperative con trol.Key words: Multi -Agent system (MAS) ; Coopera

5、tive control; Graph theory; Swarming/ flocking; Consen sus protocol分布式人工智能是人工智能領(lǐng)域中一個重要的研究方向，而多Age nt系統(tǒng)(multi-Age nt systemMAS)則是其一個主要的分支.20世紀(jì)90年代，隨著計(jì)算機(jī)技術(shù)、網(wǎng)絡(luò)技術(shù)、通信技術(shù)的飛速發(fā)展,Agent及MAS的相關(guān)研究已經(jīng)成為控制領(lǐng)域的一個新興的研究方向.由于Age nt體現(xiàn)了人類的社會智能，具有很強(qiáng)的自治性和適應(yīng)性，因此，越來越多的研究人員開始關(guān)注對其理論及應(yīng)用方面的研究.目前，人們已經(jīng)將 MAS的相關(guān)技術(shù)應(yīng)用到交通控制電子商務(wù)、多機(jī)器人系統(tǒng)、軍

6、事等諸多領(lǐng)域.而在MAS中,Agent之間如何在復(fù)雜環(huán)境中相互協(xié)調(diào)，共同完成任務(wù)則成為這些應(yīng)用的重要前提.近年來，從控制的角度對MAS進(jìn)行分析與研究已經(jīng)成為國內(nèi)外眾多學(xué)術(shù)機(jī)構(gòu)的關(guān)注熱點(diǎn)，人們在MAS協(xié)同控制問題上做了大量的研究工作，特別是在MAS群集運(yùn)動控制和協(xié)同控制一致性問題方面取得了很大的進(jìn)展.目前對MAS的研究總體上來說還處于發(fā)展的初步階段，離真正的實(shí)用化還有一定的距離；但其廣泛的應(yīng)用性預(yù)示著巨大的發(fā)展?jié)摿?，這必將吸引更多專家、學(xué)者投入到這一領(lǐng)域的研究工作中，對MAS的理論及應(yīng)用做進(jìn)一步探索.根據(jù)上述目的，本文主要概述了多智能體系統(tǒng)(MAS)在協(xié)同控制方面的研究現(xiàn)狀及其新進(jìn)展.1 Age

7、 nt與MAS的相關(guān)概念A(yù)ge nt的概念A(yù)gent 詞最早可見于 Min sky于1986年出版的Social of Mi nd一書中.國內(nèi)文獻(xiàn)中經(jīng)常將 Age nt翻 譯為:智能體、主體、代理等，但最常見的仍是采用英文“ Age nt；因?yàn)锳ge nt的概念尚無統(tǒng)一標(biāo)準(zhǔn)，人們對于漢語中哪個詞能更好地表達(dá)其含義還沒有達(dá)到共識介紹兩種引用較多的定義形式：Maes在文獻(xiàn)1中將Age nt定義為:試圖在復(fù)雜的動態(tài)環(huán)境中實(shí)現(xiàn)一組目標(biāo)的計(jì)算機(jī)統(tǒng)：Wooldrige和Jennings在文獻(xiàn)2中，從Age nt的特性方面給出其弱定義和強(qiáng)定義Age nt接受從環(huán)境中感知的輸入,并產(chǎn)生輸出動作作用于環(huán)境，這種

8、交互通常是一個連續(xù)不斷的過程.Agent不能完全控制它周圍的環(huán)境，只能通過動作輸出影響環(huán)境.圖1環(huán)境中的AgentFigi the agent in environment圖1給出了一個環(huán)境中 Age nt的抽象示意圖從圖中可知,Age nt接受從環(huán)境中感知的輸入，并產(chǎn)生輸出動 作作用于環(huán)境，這種交互通常是一個連續(xù)不斷的過程.Agent不能完全控制它周圍的環(huán)境，只能通過動作輸出影響環(huán)境.1.2 MAS的概念概念：MAS是由多個Age nt組成的集合,Age nt之間以及Age nt與環(huán)境之間通過通訊、協(xié)商與協(xié)作來 共同完成單個Age nt所不能解決的問題.優(yōu)點(diǎn)：更廣泛的任務(wù)領(lǐng)域、更高的效率、改

9、良的系統(tǒng)性能、錯誤容忍、魯棒性、分布式的感知與作 用、內(nèi)在的并行性、對社會和生命科學(xué)的觀察等顯著特性。圖2描述了Fig2 Multi-Agent system in environment1.3 MAS的組織結(jié)構(gòu)MAS的組織結(jié)構(gòu)可以是集中式的或分布式的，也可以是這2種形式都存在的混合式組織結(jié)構(gòu).不同的組織結(jié)構(gòu)行為方式不同，因此性能也會有所不同.一般地,MAS的組織結(jié)構(gòu)主要分為以下 3種類型3:1）行政管理組織結(jié)構(gòu)（集中式）.2）完全自治式組織結(jié)構(gòu)（分布式）.3）問題求解組織結(jié)構(gòu)（混合式）.2 MAS協(xié)同控制研究進(jìn)展經(jīng)過20多年的發(fā)展，MAS的研究已經(jīng)在理論和應(yīng)用方面取得了很大的進(jìn)展.MAS 一

10、個顯著特征是：系統(tǒng)中每個Age nt的能力有限，而大量這樣的個體聚集到一起，通過相互作用會產(chǎn)生有意義的社會活動或完成單個Age nt所不能完成的任務(wù)因此,MAS研究領(lǐng)域中一個重要的問題就是設(shè)計(jì)正確的控制策略,使MAS完成 TOC o 1-5 h z 給定任務(wù)，即MAS的協(xié)同控制問題近年來,MAS的協(xié)同控制已經(jīng)成為國內(nèi)外諸多研究人員關(guān)注的熱點(diǎn)問題,本節(jié)先簡要介紹研究協(xié)同控制問題通常使用的代數(shù)圖論，然后從MAS群集運(yùn)動和協(xié)同控制一致性問題2個方面，論述近年來國內(nèi)外在多Age nt協(xié)同控制方面的研究發(fā)展?fàn)顩r2.1代數(shù)圖論有向圖G=(V,E,A)由一個有限頂點(diǎn)(或結(jié)點(diǎn)集合 V=v1,v2,vn、一個有

11、向邊的集合E屬于V X V和權(quán)重矩陣A所構(gòu)成.eij=(vi,vj) E叫做邊，第個元素vi稱為邊的起點(diǎn) 第2個元素vj稱為邊的終點(diǎn)，邊的方向 從vi指向vj.連接權(quán)值矩陣為 A=aij且對于i 1(1=1,2,，n)有：i豐j, aij0,對于i l:aii=O.類似地可以定義無 向圖，無向圖是由一個有限頂點(diǎn)(或結(jié)點(diǎn))集合、一個無向邊集合和權(quán)重矩陣構(gòu)成的。MAS群集運(yùn)動及控制研究MAS群集(Swarming/Flocking)行為是復(fù)雜性科學(xué)的一個焦點(diǎn)問題例如：如鳥群遷徙時會整齊編隊(duì)，在遇到障礙時，這種隊(duì)形還可以自動調(diào)整。如野生動物群和魚群在遇到攻擊時會形成一個合理的編隊(duì)逃跑，而不是一哄而散

12、。如蟻群在覓食時能夠在食物與居住地之間選取一條最優(yōu)路徑，并且，當(dāng)環(huán)境變化時，它們會對路徑進(jìn)行重新選。這些是群集行為極具代表性的例子1987年,Reynolds提出一個模仿動物聚集的計(jì)算機(jī)模型 4,這個基本的群集模型包括 3條規(guī)則1)聚集 (cohesio n):所有Age nt改變當(dāng)前位置并向其鄰近成員的平均位置運(yùn)動；2)分離(separati on):運(yùn)動過程中，相鄰的Age nt避免發(fā)生碰撞；3)調(diào)整(lig nmen t):所有Age nt速度大小和方向改變基于其鄰近成員的平均值MAS-致性問題研究一致性(con se nsus)是指在一個 MAS中,所有的Age nt最終狀態(tài)能夠趨于一

13、致.一致性協(xié)議(算法)則是 MAS中 ,使個體狀態(tài)最終趨于一致的Age nt之間的信息傳遞規(guī)則。下面介紹兩種一致性協(xié)議(算法) ：設(shè)系統(tǒng)中有n個多Age nt用xi表示第i個Age nt的狀態(tài)，這個狀態(tài)可以是位置、速度、振幅等連續(xù)時間線性一致性協(xié)議離散時間線性一致性協(xié)議上述兩種研究工作都是假設(shè) Age nt信息交換渠道是非常理想化的 ，即每個Age nt能從與它鄰近的 Age nt 那里得到準(zhǔn)確的信息.而在實(shí)際應(yīng)用中,Agent發(fā)送、接收信息及信息傳輸過程中經(jīng)常會受到干擾，例如：熱干擾、信道衰減等。3多Agent協(xié)同控制的應(yīng)用3.1 軍事方面Li等對一種對話模式的坦克智能體之間的通訊機(jī)制進(jìn)行了

14、構(gòu)建，為在坦克分隊(duì)仿真開發(fā)中通訊機(jī)制有效性、可靠性、透明性的提高提供了有力的參考Parker已經(jīng)在早期的工作中對飛機(jī)編隊(duì)飛行問題進(jìn)行了研究，他利用局部信息和全局信息相結(jié)合的方式設(shè)計(jì)控制率以保持編隊(duì)文獻(xiàn)4還利用MAS技術(shù)構(gòu)建火力分配模型，實(shí)現(xiàn)火力模型通用化、智能化，使火力分配更精確、高效.3. 2交通運(yùn)輸控制方面文獻(xiàn)5采用多Age nt協(xié)調(diào)控制方法來協(xié)調(diào)相鄰交叉口處的控制信號,以消除網(wǎng)絡(luò)中的交通擁塞Che ng等則在文獻(xiàn)6中提出了一種基于多智能體的分布式交通信號協(xié)調(diào)控制方法澳大利亞人工智能研究所基于多Age nt的思路設(shè)計(jì)實(shí)現(xiàn)了一個空中交通管理系統(tǒng),系統(tǒng)中每個Age nt負(fù)責(zé)一個空中交通系統(tǒng)中的

15、子問題，并與其他Age nt進(jìn)行協(xié)調(diào)與協(xié)作，以便實(shí)現(xiàn)整個系統(tǒng)的目標(biāo)任務(wù) 3. 3智能機(jī)器人方面日本的機(jī)器人足球世界杯錦標(biāo)賽RoboCup就是一個非常典型的例子，在機(jī)器人足球賽中，多個機(jī)器人之間的關(guān)系相當(dāng)復(fù)雜，它們必須通過互助合作才能共同完成任務(wù)，這是MAS協(xié)同控制應(yīng)用的一個典型實(shí)例在工業(yè)方面，MAS協(xié)同控制的應(yīng)用表現(xiàn)在，人們控制多個智能機(jī)器人以特定隊(duì)形搬運(yùn)單個物體，利用多個智能機(jī)器人替代人類進(jìn)行危險(xiǎn)作業(yè)4 結(jié)束語MAS及其協(xié)同控制已經(jīng)成為當(dāng)前學(xué)術(shù)界一個新的研究熱點(diǎn)，吸引了許多不同領(lǐng)域研究人員的極大關(guān)注本文討論了與 MAS有關(guān)的一系列問題，簡要介紹了 MA勃同控制方面的研究狀況與應(yīng)用，展望了幾個

16、有待進(jìn)一步研究的方向雖然MAS及其協(xié)同控制相關(guān)問題的研究會存在很多問題和困難，但其應(yīng)用前景是十分廣闊的，相信在各領(lǐng)域?qū)＜?、學(xué)者的共同努力下，多智能體系統(tǒng)控制方面的研究定能取得新的進(jìn)展與突破參考文獻(xiàn)：TANNER H G, JADBABAIE A，PAPPASG J. Stable flocking of mobile Agents，Part II: dynamic topologyC /Proceedings of the IEEE Conference on Decision and Contro.l Mau,i HI, USA, 2003: 2016-2021TANNER H G. Flo

17、cking with obstacle avoidance in switc-hing networks of interconnected vehiclesC /Proceedingsof theIEEE InternationalConference on Robotics and Auto-mation. New Orleans, USA, 2004: 3006-3011.李 英.多Agent系統(tǒng)及其在預(yù)測控制與智能交通系統(tǒng)中的應(yīng)用M.上海:華東理工大學(xué)出版社,2004: 15-25.REYNOLDS G . Flocks, birds and schools: a distributed behavioral modelJ. ComputerGraphics, 1987, 21(1):25-34.VICSEK T, CZIROK A, BENJACOB E, et a.l Novel typeof phase-transi