多智能體系統(tǒng)體系結構及其協(xié)調(diào)機制研究綜述

多智能體系統(tǒng)體系結構及其協(xié)調(diào)機制研究綜述

1用武之地，以武之地自20世紀90年代以來，研究多智能網(wǎng)絡系統(tǒng)（mas，多智能網(wǎng)絡）成為嵌入式人工智能研究的熱點。多智能網(wǎng)絡理論是繼對象方法之后的另一種重要的思想方法和工具，在數(shù)據(jù)分析和設計方面發(fā)揮著重要作用。促進經(jīng)濟、工業(yè)、社會和軍事發(fā)展。此外，多智能網(wǎng)絡理論對于促進經(jīng)濟、工業(yè)、社會和軍事發(fā)展也具有以下深遠意義。(1)在信息時代的今天,Internet已經(jīng)強烈地沖擊著人們的生活,而MAS研究成果的最大應用場合就正是在Internet上的應用,這無疑會對國家的長遠發(fā)展產(chǎn)生深遠的影響;(2)多智能體系統(tǒng)的研究成果已經(jīng)和正在廣泛地應用到工業(yè)系統(tǒng)的改造中,并取得了巨大的經(jīng)濟和社會效益.(3)對多智能體的研究直接涉及到社會現(xiàn)象及其規(guī)律,無疑會在社會活動中大有用武之地;(4)現(xiàn)代戰(zhàn)爭表現(xiàn)為多兵種、多武器、多方位的綜合協(xié)同作戰(zhàn),對于多智能體系統(tǒng)特別是多智能體協(xié)調(diào)、合作方法的研究,無疑可為現(xiàn)代協(xié)同作戰(zhàn)提供直接的理論支撐和技術支持.因此,世界發(fā)達國家如美、日、德、英、法等都投入巨資支持多智能體理論與方法的研究,特別指出的是,發(fā)達國家軍方對多智能體系統(tǒng)的研究尤為重視.國際上關于多智能體系統(tǒng)的研究雖然只有很短的時間,但發(fā)展相當迅速.目前,主要的研究方向包括:智能體和多智能體系統(tǒng)的理論、通信和交互技術、智能體體系結構和組織、多智能體系統(tǒng)中的協(xié)作和協(xié)商、智能體語言、多智能體應用系統(tǒng)設計等.其應用已經(jīng)擴展到了工業(yè)(包括制造、過程控制、遠程通訊、空中交通控制、運輸系統(tǒng)等)、商業(yè)(包括信息過濾、信息收集、電子商務、商業(yè)過程管理等)、娛樂(游戲、交互式劇院和影院)、醫(yī)療(病人看護、健康照料等)等相當廣泛的各個領域.目前多智能體系統(tǒng)理論的最重要應用是在Internet網(wǎng)上,多智能體理論與Internet獲得了相得益彰的發(fā)展,一方面,多智能體理論在Internet上獲得了極其廣泛地應用(信息過濾、信息收集、電子商務等);另一方面,Internet網(wǎng)相關業(yè)務的迅猛發(fā)展也極大地推動了多智能體理論的創(chuàng)新和進步.多智能體理論的另一個典型應用就是國際機器人足球比賽,從1996年開始的機器人世界杯足球賽能夠十分典型地體現(xiàn)多智能體系統(tǒng)的許多特點,如動態(tài)、實時、多人協(xié)調(diào)、只有不完全的信息等,并具有對抗性及較強的可觀賞性.主要代表球隊有:美國CMU大學的CMUnited球隊、德國漢堡大學隊、及日本、韓國、荷蘭等國的球隊,我國也已準備參賽.多智能體理論在國內(nèi)的研究開始時間大約落后十多年,其中清華大學石純一、王學軍等采用對策論研究了多智能體之間的協(xié)作,吉林大學劉大友等對多智能體間的協(xié)商進行了研究,中科院計算所史忠植等對智能體認知模型和理論進行了研究,國防科技大學吳泉源等對多智能體協(xié)調(diào)等問題進行了研究.但總的來說,目前國內(nèi)的研究與國外有比較大的差距,研究很有限.在多智能體系統(tǒng)理論中,關于多智能體系統(tǒng)體系結構及其協(xié)調(diào)機制的研究是處于核心的問題,它研究如何將多個智能體組織為一個群體并使各個智能體有效地進行協(xié)調(diào)合作,從而產(chǎn)生總體解決問題的能力.多智能體系統(tǒng)的組織結構與控制方法對系統(tǒng)性能的影響極大,如何組織由多個智能體構成的群體,以及在這樣的群體中如何實現(xiàn)多智能體的協(xié)調(diào)合作問題,具有重要的理論和現(xiàn)實意義.2國外發(fā)展現(xiàn)狀對于多智能體系統(tǒng)體系結構及其協(xié)調(diào)機制的研究目前國際上已經(jīng)發(fā)展了許多方法,并且形成了相對分明的幾個流派.根據(jù)這些理論方法的流派,大致可以分為三種:基于符號推理系統(tǒng)的體系結構及協(xié)調(diào)機制、基于行為主義的體系結構及協(xié)調(diào)機制以及基于協(xié)進化方法的體系結構及協(xié)調(diào)機制等.2.1基于符號推理系統(tǒng)的多智能體體系結構及協(xié)調(diào)機制這種方法以Bratman等提出的BDI(BriefDesireIntention)理論為基礎,采用傳統(tǒng)人工智能中符號推理的基本原理,試圖通過建立比較完整的符號系統(tǒng)進行知識推理來使智能體具有自主思考、決策的能力以及與其他智能體和環(huán)境進行協(xié)調(diào)行動的能力.基于符號推理系統(tǒng)的多智能體體系結構及協(xié)調(diào)機制有三種代表性的理論,下面分別簡單介紹并予以評價.2.1.1存在共同任務時的規(guī)則Cohen&Levesque基于BDI理論進一步提出了承諾(Commitment)和公約(Convention)的概念,又經(jīng)過Jennings、Wooldridge等人的進一步發(fā)展,形成了一套比較系統(tǒng)的關于多智能體協(xié)調(diào)的理論框架,這是目前最為系統(tǒng)和成熟的多智能體協(xié)調(diào)理論框架.它的基本要點是:多個智能體在完成一個共同任務時會形成一個共同承諾,如果不出現(xiàn)下列三種情況之一,智能體就應該遵守公約,即堅持承諾,直到成功完成共同任務.·智能體發(fā)現(xiàn)共同任務已經(jīng)完成;·智能體發(fā)現(xiàn)共同任務是不可能完成的;·智能體發(fā)現(xiàn)執(zhí)行該共同任務是不必要的.否則智能體就會設法通知正在合作執(zhí)行共同任務的其它智能體,自己將要退出承諾.這樣,其它智能體就能夠適時做出調(diào)整.通過這樣的承諾和公約機制,多個智能體就能協(xié)調(diào)完成一個共同任務.可見,聯(lián)合意圖理論只是側重于對智能體在完成一個共同任務時的一致性參與及堅持上面,并沒有劃定多個智能體如何就完成聯(lián)合動作的具體分工協(xié)作問題,聯(lián)合意圖理論只是提供了一個框架,針對具體應用,還有相當多的領域相關問題需要解決.2.1.2共享計劃理論和多智能體通用協(xié)調(diào)模型Grosz等提出了共享計劃理論,它是建立在一種聯(lián)合精神狀態(tài)之上的,其中最重要的概念就是它引入的概念算子:“打算”(Intentionthat)和“打算做”(Intentionto),它們通過一系列原子操作符定義,引導智能體采取包括通信在內(nèi)的行動來使得個體、子團體和整個合作團體能夠協(xié)調(diào)一致的執(zhí)行所賦予的任務.所有參與聯(lián)合任務的各個智能體首先要達成一個共享計劃,共享計劃中包含了要完成聯(lián)合行動的各種方面細節(jié)和具體步驟,每個智能體都彼此相信它們都打算要進行聯(lián)合行動并接受共享計劃.對于共享計劃中的每一步,又會有一些智能體形成子團體組合來完成,子團體之外的其他智能體都相信子團體能夠完成該步計劃,并對該步也有一個共享計劃.這樣通過共享計劃的協(xié)調(diào),各個智能體就能合作完成共同任務.共享計劃理論通過一個全隊的共享計劃實現(xiàn)多個智能體的動態(tài)組合及分工協(xié)作,這種思想是很好的,在這方面它強于聯(lián)合意圖理論,但它沒有涉及到當智能體在不能很好完成共享計劃時的保證機制,這方面又比聯(lián)合意圖理論為弱,因此,將二者結合起來研究就能揚長避短,目前關于二者的結合研究最成功的是Tambe的多智能體通用協(xié)調(diào)模型,在下面將予以介紹.2.1.3基于符號系統(tǒng)的多智能體協(xié)調(diào)模型steamKinny提出了計劃的隊行為方法,其要點是,計劃是事先由設計者賦予的,而不是由多智能體動態(tài)產(chǎn)生的,智能體在行動之前就被賦予了關于完整計劃的詳細信息,這種方法適合于對智能體的行為環(huán)境事先能夠確切把握并且精細計劃的場合,不適合于動態(tài)環(huán)境,因此應用比較有限.以上三種理論是基于符號推理系統(tǒng)的多智能體體系結構與協(xié)調(diào)機制的最典型代表,它們已經(jīng)形成各自比較完整的方法體系,并且都有自己的典型應用.上面已經(jīng)提到,Tambe在聯(lián)合意圖理論和共享計劃理論的基礎上,提出了一種多智能體協(xié)調(diào)的通用模型STEAM,并且在應用上獲得了很大的成功.它的要點是,對于參與協(xié)調(diào)的各個智能體按照角色進行組織,并且引入集體行為操作符,根據(jù)任務劃分子團體,每個智能體保留團體或子團體的集體精神狀態(tài)的一個拷貝,對于團體或子團體的共同任務,采用集體行為操作符對集體精神狀態(tài)進行操作,對于智能體的個體任務,則采用個體行為操作符對個體精神狀態(tài)進行操作.多智能體間信用的維持采用聯(lián)合意圖理論的承諾方法.在STEAM中還引入了其它一些手段,如用推測等方法促進多智能體協(xié)調(diào)一致地行動.基于符號系統(tǒng)的多智能體體系結構與協(xié)調(diào)機制雖然在目前已經(jīng)形成了幾種有代表性的比較系統(tǒng)的理論,但是在實際系統(tǒng)中也遇到了許多的問題.基于符號的系統(tǒng)強調(diào)智能體對外界有一個比較完整和復雜的模型表示,因此如何保持智能體自身模型的計算和推理與外部環(huán)境的同步便是一個比較棘手的問題.復雜的模型計算和推理往往使得智能體適應環(huán)境的能力變差,而且很難滿足模型與領域無關性的要求.況且,構造復雜的智能體符號模型表示也是一項任務繁重、效率低下的工作,對于大型的復雜動態(tài)系統(tǒng)尤其如此.2.2在多智能體上的動作選擇機制基于行為主義的多智能體系統(tǒng)以Brooks提出的基于行為的系統(tǒng)分析與設計方法為基礎,實際上,最初的自主智能體概念(AutonomousAgent)就是從基于行為的系統(tǒng)中演化發(fā)展起來的.Barry等提出了設計基于行為的系統(tǒng)的三個基本原則:最小性、無狀態(tài)性和強壯性.其中,最小性指保持系統(tǒng)的盡量簡單以便與環(huán)境快速反饋;無狀態(tài)性指基于行為的系統(tǒng)本身沒有一個外部環(huán)境模型的狀態(tài);強壯性指使得系統(tǒng)能夠與在實際環(huán)境中所遇到的不確定性并存而不是去除不確定性.基于行為的智能體設計的一般過程是,首先選定一些基本行為(basisbehavior),基本行為是一些能夠組合起來完成所要求任務的最小行為單元.基本行為的選擇通常需要反復多次才能完成,基本行為選定以后,最重要的工作就是對行為選擇機制(ASM,ActionSelectionMechanism)的研究了,即研究如何組合調(diào)度基本行為以完成復雜任務,使得智能體能夠自主行動并與其它智能體和環(huán)境相協(xié)調(diào).關于動作選擇機制的研究,是基于行為主義的多智能體協(xié)調(diào)研究的熱點和核心問題,已經(jīng)發(fā)展了許多良好的算法和理論并應用于不同的領域.其中比較系統(tǒng)和深入的一個方向是關于行為網(wǎng)(behaviornetwork)的研究,Maes提出了一種著名的行為網(wǎng)結構-MASM(MaesActionSelectionMecha-nism),這種行為網(wǎng)結構的要點是,將各種基本行為組成一個網(wǎng)狀結構,網(wǎng)結構的結點是基本行為模塊,各個基本行為之間通過行為的活性(Activation)相連結.所謂行為的活性即是指該行為對于實際目標的貢獻和效能的一種度量,若該行為能夠促使目標的實現(xiàn),則它的活性值為正,反之為負.促使目標實現(xiàn)的效能越大,其活性值就越大.各種行為之間會產(chǎn)生相互影響,包括激勵或抑制,相應的活性值也就會在行為網(wǎng)中進行傳播,通過一定的活性傳播控制算法就可以將行為進行有效地組合調(diào)度,從而完成復雜任務并產(chǎn)生協(xié)調(diào)行為.MASM有一套比較嚴密的數(shù)學理論作為支撐,并且在行為網(wǎng)的穩(wěn)定性、收斂性等方面作出了證明.德國的KlausDorer將MASM進行擴展和改進,得到REASM,使之能夠充分利用連續(xù)狀態(tài)所能提供的附加信息,并應用到機器人足球賽中,獲得了良好的效果,在1998年的RoboCup仿真比賽中取得了第二名的好成績.許多基于行為主義的智能體系統(tǒng)研究者們都極力鼓吹行為主義的好處,他們倡導采用純行為主義的方法,反對將基于符號的方法與基于行為的方法結合起來構造混合系統(tǒng)(HybridSystem).實際上,盡管基于行為的方法在某些方面的應用上產(chǎn)生了良好的效果,并且在系統(tǒng)設計實現(xiàn)上要比基于符號系統(tǒng)的方法簡單快捷.但是應該看到,基于行為的智能體系統(tǒng)目前所能夠產(chǎn)生的所謂復雜行為還是比較簡單和初級的,如避碰行為,而且往往系統(tǒng)設計缺乏卓有成效的理論指導,導致基于行為的系統(tǒng)設計算法與風格千差萬別,難以產(chǎn)生更為復雜的、高級的智能行為.基于符號系統(tǒng)和基于行為主義的智能體體系結構和協(xié)調(diào)方法各有優(yōu)缺點,二者是互補的,因此將二者結合起來研究是必然的趨勢,目前將二者結合的混合系統(tǒng)是多智能體系統(tǒng)體系結構的一個熱點,一般是在上層采用基于符號系統(tǒng)的方法,對復雜行為進行推理、決策,而在底層則采用基于行為主義的反應式系統(tǒng),處理比較簡單的、能夠與環(huán)境快速交互的行為,將二者有機結合起來.但如何將二者結合又是一個比較困難的課題,目前雖然有一些比較成功的系統(tǒng),但仍然缺乏構造混合系統(tǒng)的比較系統(tǒng)的方法.構造結構良好的混合系統(tǒng)來實現(xiàn)多智能體之間的協(xié)調(diào),往往比較困難,任務也比較繁重,而且效果不一定良好.因此,尋找其它途徑簡單而有效地實現(xiàn)多智能體系統(tǒng)體系結構與協(xié)調(diào)行為便呼之欲出,基于進化機制的方法便是這其中十分有意義和卓有成效的一種嘗試.2.3協(xié)進化方法基于自然界中生物間“自然選擇、適者生存”的進化機制,人們提出了遺傳算法,并發(fā)展成為含義更為廣泛的各種進化計算方法.由于進化算法的眾多良好特性,至今已經(jīng)獲得了很大發(fā)展并得到廣泛應用.但是,傳統(tǒng)的進化算法存在著一些內(nèi)在的問題:(1)傳統(tǒng)進化算法中的物種群體具有很強的收斂性,這導致算法到最后只保留了最“強壯”的個體,這對于那些需要給出更多信息而不是只給出峰值的問題就無能為力了.(2)傳統(tǒng)進化算法中的每個個體都代表了所要求解的完整解決方案,并且個體之間是彼此孤立的.由于沒有建立群體成員之間的交互模型,十分不利于群體產(chǎn)生共同適應環(huán)境的行為.在自然界中,各種生物和物種共存于一個生態(tài)系統(tǒng)中,每個物種都在這個生態(tài)系統(tǒng)中有自己的生存環(huán)境或稱為“生境”.在生態(tài)環(huán)境中,只有有限的資源,各種物種必須通過競爭與合作才能獲得自己生存所需的資源.通過這些競爭與合作的交互,物種們不斷進化和改變,并相互影響彼此的進化過程,這個相互適應的過程稱為協(xié)進化(Coevolution).為了克服傳統(tǒng)進化算法的不足,解決一類更為廣泛的機器學習、共同適應以及多智能體間的協(xié)調(diào)問題,人們模仿自然界中的協(xié)進化機制,提出了協(xié)進化計算(CEC,CoevolutionaryComputing)的思想.在協(xié)進化計算中,通常存在多個物種群體,每個物種群體都有自己的物種個體類型,各個物種群體都采用進化算法實現(xiàn)進化過程,而在對個體進行適應度評價時,則加入對群體間交互協(xié)調(diào)的處理.對那些有利于群體間協(xié)調(diào)的個體賦予較高的適應度,而不利的則賦予較低的適應度,這樣各個群體就會向著有利于相互協(xié)調(diào)適應的方向進化,從而產(chǎn)生協(xié)調(diào)行為.在協(xié)進化計算中,交叉和變異在一個物種內(nèi)進行,而選擇操作可以在一個或多個物種的個體中進行.可以根據(jù)生物學中物種間的關系將協(xié)進化進行分類:圖1根據(jù)物種之間的關系對協(xié)進化進行分類協(xié)進化概念是基于物種間兩種最基本的交互方式而得到的,即合作與競爭,因此,在這個意義上,協(xié)進化可以分為合作型協(xié)進化(CooperativeCoevolution)和競爭型協(xié)進化(CompetitiveCoevolution).在多智能體協(xié)調(diào)問題中,針對不同的領域背景,可以選擇合作型或競爭型的協(xié)進化方法.一般地,對于需要多智能體合作完成共同任務的場合,合作型協(xié)進化方法很常用.合作型協(xié)進化注重于群體之間的合作關系,通過對群體間有利于合作的個體進行適應度加強,促使群體向著有利于產(chǎn)生相互合作和共同適應(Coadapted)行為的方向進化.因此,將合作型協(xié)進化用于在多個智能體之間產(chǎn)生合作行為是一種極佳的方法,其思想是為參與合作的每個智能體都構造一個自身采用進化算法的群體,這樣通過各個群體間的協(xié)進化就能產(chǎn)生智能體之間的協(xié)調(diào)合作行為.對于協(xié)進化的研究,目前已經(jīng)有一些成功的范例可以借鑒.ToshioF.等采用一種細菌感染協(xié)進化算法,解決智能機器人運動規(guī)劃的決策問題;Eiji等用合作型協(xié)進化算法獲取足球機器人的協(xié)作行為;S.Luke等人則用協(xié)進化方法訓練得到了一個完整的機器人足球隊;Thomas等對著名的“捕食者-獵物”問題進行了全面研究,并采用合作型協(xié)進化方法研究了由k個異類智能體組成的團如何獲取合作策略的問題;PuppalaN.等則進一步提出了一種“共享記憶”(SharedMemory)的方法,用于存儲協(xié)進化過程中成功合作的個體對,通過與隨機選取個體對的方法相比,共享記憶方法具有較高的效率,他將這種方法應用到兩個房屋粉刷機器人的協(xié)調(diào)控制中,獲得了較好的效果;對合作型協(xié)進化進行比較系統(tǒng)研究的是M.A.Potter,在他的博士論文中,綜合以往協(xié)進化方法研究的各種問題,提出了一種通用的合作型協(xié)進化模型,并對這個模型