多智能體蜂擁的研究

多智能體系統(tǒng)蜂擁問題的研究PAGE101緒論1.1研究背景蜂擁是一種大數(shù)量相互影響的具有普遍群體目標(biāo)的個體集體行為的一種表現(xiàn)。數(shù)十年來，依靠個體間基本的相互影響的涌現(xiàn)現(xiàn)象已經(jīng)吸引了來自不同領(lǐng)域的科學(xué)家們，他們包括動物行為、物理、生物、社會學(xué)和微機(jī)科學(xué)等[1-12]。這些主體的例子一般為鳥、魚、鴿子、螞蟻、蜜蜂和人群。這些生物在運動能力、視覺能力等方面有限，但通過相互之間的交互構(gòu)成大規(guī)模群體，能夠?qū)⒂邢薜膫€體能力聚集起來，克服單個個體能力上的不足，高效的完成覓食、遷徙、躲避天敵等活動。在這樣的群體系統(tǒng)中，由于單個個體僅具有有限的局部感知能力，僅能夠獲取存自己能力范圍內(nèi)的局部信息，而無法獲取整個群體的全局信息，因此系統(tǒng)中就不存在集中式的協(xié)調(diào)控制機(jī)制，而具有分散式、分布式系統(tǒng)的特點。如何通過局部信息交換產(chǎn)生全局的系統(tǒng)行為足近年來的一個研究熱點。一般將實際中具有上述現(xiàn)象的系統(tǒng)抽象為多智能體系統(tǒng)(Multi-AgentSystems，MAS)，該系統(tǒng)具有一個有趣的性質(zhì)：在許多由大量動態(tài)演化的個體組成的系統(tǒng)中，往往會涌現(xiàn)出全局協(xié)調(diào)一致的行為。一般而言，構(gòu)成該系統(tǒng)的個體并不知道整個系統(tǒng)的全局信息，每個個體只能根據(jù)它所擁有和感知的局部信息（如它所能夠觀察到的其它個體的行為）來調(diào)整自身的行為。也就是說，整個系統(tǒng)是通過分布式的個體凋整而不是集中控制方式實現(xiàn)全局協(xié)調(diào)一致行為的。具有這樣性質(zhì)的系統(tǒng)在實際中是普遍存在的，除了生物系統(tǒng)會表現(xiàn)出全局一致的性質(zhì)，一些非生物系統(tǒng)也會出現(xiàn)這種一致性現(xiàn)象，例如，懸掛在一個橫梁上的鐘擺在一段時間后會出現(xiàn)同步擺動，演出結(jié)束后觀眾的掌聲發(fā)生同步，網(wǎng)路上的路由器最終會以同步的方式發(fā)送路由消息，從而引起的網(wǎng)絡(luò)擁塞，以及人們通過大橋時的步伐同步，從而引起大橋的共振等。對于這類現(xiàn)象的產(chǎn)生機(jī)理，研究者將其納入復(fù)雜網(wǎng)絡(luò)的范疇內(nèi)進(jìn)行研究，得出這樣的結(jié)論：在這些復(fù)雜系統(tǒng)中，每一個個體都是一個動力學(xué)系統(tǒng)，而諸多的動力學(xué)個體之間存在著某種特殊的耦合關(guān)系，這些系統(tǒng)中的個體根據(jù)自身能夠感知的局部信息經(jīng)過動態(tài)演化而達(dá)到整個系統(tǒng)的同步。本質(zhì)上．復(fù)雜網(wǎng)絡(luò)的同步的機(jī)理與多智能體系統(tǒng)協(xié)調(diào)現(xiàn)象是一致的。截止目前對蜂擁動態(tài)行為的建模和分析按照研究方法來分類最常用的方法有三種：基于個體描述的方法，也稱為拉格朗日方法；連續(xù)流方法，也稱為歐拉方法；以及離散系統(tǒng)模型方法。以上三種方法中，基于個體描述的模型，是以常微分方程組來描述所有個體的運動，這是對連續(xù)變化對象建模的一個自然的方法。連續(xù)流模型則采用偏微分方程來描述蜂擁分布形成的密度場中局部的反應(yīng)散現(xiàn)象，研究其穩(wěn)定性和運動性質(zhì)。離散系統(tǒng)模型方法是用離散時間方程組來描述，研究其互相作用下的集體行為。第一批對蜂擁(Flocking)的從理論角度進(jìn)行研究的物理學(xué)家有Vicsek[13]等，Toner&Tu[14]，Shimoyama[15]等，和Levine[16]等。Vicsek等的研究內(nèi)容主要涌現(xiàn)在個體控制系統(tǒng)中速度匹配的勢能（這并不意味著蜂擁），而Toner&Tu采用了連續(xù)介質(zhì)力學(xué)接近。Levine等創(chuàng)造了一個基于個體的相互影響的系統(tǒng)，這種循環(huán)蜂擁系統(tǒng)被稱作循環(huán)螞蟻工廠。另一種連續(xù)模型是由Mogilner&Ekdstein-Keshet[17]和Topaz&Bertozzi[18]提出的。Helbing等使用經(jīng)驗法的基于個體的模型研究了蜂擁。1.2群體智能理論及研究方法1.2.1群體智能概述群智能理論的基本原理[19-20]是以生物社會系統(tǒng)(Biologysocialsystem)作為依托，也就是由簡單個體組成的群體與環(huán)境以及個體之間的互動行為。這種生物社會性的模擬系統(tǒng)利用局部信息產(chǎn)生難以估量的復(fù)雜群體行為。群體智能并不是所有生物種群都具有的特性，它是那些具有社會性特征的群居生物個體合作進(jìn)行某些活動時才會產(chǎn)生的涌現(xiàn)現(xiàn)象。關(guān)于群體智能行為的生物原型，Bonabeau描述了生物螞蟻群體的一些行為，如覓食、勞動分工、尸體聚集、巢穴構(gòu)造、合作運輸?shù)?，并分別對其建模，然后設(shè)計了一系列算法、多主體系統(tǒng)(MAS)和多機(jī)器人系統(tǒng)[31]。集中介紹了社會性昆蟲的行為建模和蟻群優(yōu)化算法及其性能。Kennedy通過觀察鳥群的協(xié)同運動，開創(chuàng)了微粒群優(yōu)化這一新型群體智能方法的研究領(lǐng)域，并以此為基礎(chǔ)提出了以下基本觀點[21]：1)人類智能的產(chǎn)生源于社會交往；2)文化和認(rèn)知是人類社交的結(jié)果。對魚群的研究，也屬于群體智能的理論范疇。群體智能研究成果和理論體系，可以用來指導(dǎo)我們對魚群形成、組織體系、群體行為及其涌現(xiàn)出的群體智能的研究。群體智能是一種通過模擬自然界生物群體行為來實現(xiàn)人工智能的方法。由單個簡單個體完成的任務(wù)，可以涌現(xiàn)出復(fù)雜的智能，充分體現(xiàn)了整體和大于個體的疊加。群體智能利用群體優(yōu)勢，在沒有集中控制，不提供全局模型的前提下，為復(fù)雜問題尋找解決方案[22]。普遍意義上，群體智能強(qiáng)調(diào)個體行為的簡單性、群體的涌現(xiàn)特性、以及自下而上的研究策略。群體智能的本質(zhì)是由許多簡單個體組成的群體，群體之間能夠通過簡單的交互、合作和協(xié)作，來完成某一項任務(wù)。群體智能在已有的應(yīng)用領(lǐng)域中都表現(xiàn)出較好的尋優(yōu)性能，因而引起了相關(guān)領(lǐng)域研究者的極大關(guān)注。其中涌現(xiàn)是群體智能中一個比較重要的概念，群體智能中的智能就是大量個體在無中心控制的情況下體現(xiàn)出來的宏觀有序的行為。這種大量個體表現(xiàn)出來的宏觀有序行為就是涌現(xiàn)現(xiàn)象。如果沒有涌現(xiàn)現(xiàn)象，就無法體現(xiàn)智能。因為涌現(xiàn)是簡單的個體行為在特定組織結(jié)構(gòu)下，積累到一定程度，所表現(xiàn)出來的整體現(xiàn)象，所以，對群體智能的研究必須既研究各個部分，又研究各個部分之間的相互作用關(guān)系。MillionasM.M在1994年提出群體智能應(yīng)遵循的五條基本原則[23]，分別為：1)鄰近原則，動物群體能夠進(jìn)行簡單的空間和時間計算；2)品質(zhì)原則，動物群體能夠響應(yīng)環(huán)境中的品質(zhì)因子；3)多樣性反應(yīng)原則，動物群體的行動范圍不應(yīng)該局限在小范圍內(nèi)；4)穩(wěn)定性原則，動物群體不應(yīng)該在每次環(huán)境變化時都改變自身的行為；5)適應(yīng)性原則，在所需代價不太高的情況下，動物群體能夠在適當(dāng)?shù)臅r候改變自身的行為。1.2.2群體智能的主要優(yōu)點群體智能具有以下優(yōu)點[24]：1)群體中相互合作的智能體是分布的，這樣更能夠適應(yīng)當(dāng)前網(wǎng)絡(luò)環(huán)境下的工作狀態(tài)。2)沒有中心控制與數(shù)據(jù)，這樣的系統(tǒng)更具有魯棒性，不會由于某一個或者某幾個智能體的故障而影響整個問題的求解。3)可以不通過智能體間直接通信，而采用非直接通信進(jìn)行合作，系統(tǒng)具有更好的可擴(kuò)充性，使得系統(tǒng)中由于智能體數(shù)量的增加而增加的系統(tǒng)通信耗費較小。4)系統(tǒng)中每個智能體的能力非常簡單，以至于每個智能體的執(zhí)行時間都比較短，且實現(xiàn)也較簡單，具有簡單性。5)智能體相互作用能突現(xiàn)出整體的行為，系統(tǒng)所有上層智能行為都是通過智能體的基本規(guī)則相互作用產(chǎn)生的，所以在多任務(wù)情況下，對于每一子任務(wù)可以分別編制、調(diào)試、學(xué)習(xí)。6)群體智能中，信息處理原則是基于發(fā)生在實際生命中大量并行處理過程。群體智能系統(tǒng)的強(qiáng)并行性大大地增強(qiáng)了系統(tǒng)的運算速度及能力。7)人工生命中的一個重要原則，就是整體大于部分和的思想。由于群體智能的整體行為是由智能體行為突現(xiàn)而產(chǎn)生的，智能體在相互作用中的負(fù)關(guān)系將會因智能體自身的相互作用規(guī)則而消減，正關(guān)系將得以增強(qiáng)。對于智能體之間的沖突和任務(wù)協(xié)調(diào)等問題，由底層智能體相互作用的規(guī)則解決，減少上層對智能體之間的協(xié)作、協(xié)調(diào)控制，避免了上層控制干預(yù)下層動作的情況，使得每一層次的控制任務(wù)都非常清晰，增加了系統(tǒng)協(xié)作協(xié)調(diào)效率。1.2.3群體智能的主要缺點群體智能的研究還處于萌芽階段，還存在很多不足，主要問題如下[25]：1)群體智能的思想是根據(jù)對生物群體觀察得來的，是概率算法，從數(shù)學(xué)上對于它們的正確性與可靠性的證明仍比較困難。2)這些算法都是專用算法，一種算法只能解決某一類問題，各種算法之間的相似性很差。3)系統(tǒng)高層次的行為是需要通過低層次智能體間的簡單行為交互突現(xiàn)產(chǎn)生。單個個體控制的簡單并不意味著整個系統(tǒng)設(shè)計的簡單。4)系統(tǒng)設(shè)計時也要保證多個智能體簡單行為交互能夠突現(xiàn)出所希望看到的高層次復(fù)雜行為。這可以說是群體智能中一個極為困難的問題。1.2.4群體智能的底層機(jī)制研究自組織[26]：自組織是一種動態(tài)機(jī)制，由底層單元的交互而呈現(xiàn)出系統(tǒng)的全局性的結(jié)構(gòu)。交互的規(guī)則僅僅依賴于局部信息，而不依賴于全局的模式[23]。自組織是系統(tǒng)自身涌現(xiàn)出的一種性質(zhì)。系統(tǒng)中沒有一個中心控制模塊，也不存在一個部分控制另一部分。自組織的特點就是通過利用同一種介質(zhì)或者媒體創(chuàng)建時間或空間上的結(jié)構(gòu)。比如螞蟻筑的巢、尋找食物時的路徑等。正反饋群體中的每個具有簡單能力的個體表現(xiàn)出某種行為，會遵循已有的結(jié)構(gòu)或者信息指引自己的行動，并且釋放自身的信息素，這種不斷的反饋能夠使得某種行為加強(qiáng)。盡管一開始都是一些隨機(jī)的行為，大量個體遵循正反饋的結(jié)果是呈現(xiàn)出一種結(jié)構(gòu)。自然界通過系統(tǒng)的自組織來解決問題。理解了大自然中如何使生物系統(tǒng)自組織，就可以模仿這種策略使系統(tǒng)自組織。間接通信[26]：群體系統(tǒng)中個體之間如何進(jìn)行交互是個關(guān)鍵問題。個體之間有直接的交流，如觸角的碰觸、食物的交換、視覺接觸等，但個體之間的間接接觸更為微妙，已有研究者用Stigmergy來描述這種機(jī)制：也就是個體感知環(huán)境，對此做出反應(yīng)，又作用于環(huán)境。Grasse首先引入Stigmergy來解釋白蟻筑巢中的任務(wù)協(xié)調(diào)[27]。Stigmergy在宏觀上提供了一種將個體行為和群體行為聯(lián)系起來的機(jī)制。個體行為影響著環(huán)境，又因此而影響著其它個體的行為。個體之間通過作用于環(huán)境并對環(huán)境的變化做出反應(yīng)來進(jìn)行合作。總而言之，環(huán)境是個體之間交流、交互的媒介。從螞蟻覓食到螞蟻聚集尸體到螞蟻搬運、筑巢，個體之間的通信機(jī)制總是離不開Stigmery機(jī)制，對于環(huán)境的作用，通常由各種各樣的信息素來體現(xiàn)。涌現(xiàn)[26]：群體智能中的智能就是大量個體在無中心控制的情況下體現(xiàn)出來的宏觀有序的行為。這種大量個體表現(xiàn)出來的宏觀有序行為稱之為涌現(xiàn)現(xiàn)象。沒有涌現(xiàn)現(xiàn)象，就無法體現(xiàn)出智能。因此，涌現(xiàn)是群體智能系統(tǒng)的本質(zhì)特征。只知道孤立的個體行為并不能了解整個系統(tǒng)的情況，僅僅研究孤立的部分無法有效地研究整體性質(zhì)，因此，對涌現(xiàn)現(xiàn)象的研究必須既研究各個部分，又研究各個部分之間的相互作用[28]?！斑z傳算法之父”約翰·霍蘭在文獻(xiàn)[29]中對涌現(xiàn)現(xiàn)象進(jìn)行了較為深入的探索。他認(rèn)為涌現(xiàn)現(xiàn)象的本質(zhì)是“由小生大，由簡入繁’’，并且把細(xì)胞組成生命體，簡單的走棋規(guī)則衍生出復(fù)雜的棋局等現(xiàn)象都視為涌現(xiàn)現(xiàn)象。他認(rèn)為神經(jīng)網(wǎng)絡(luò)、元胞自動機(jī)等可以算作涌現(xiàn)現(xiàn)象的模型。群體智能的涌現(xiàn)現(xiàn)象與系統(tǒng)論和復(fù)雜系統(tǒng)中闡述的涌現(xiàn)本質(zhì)上是相同的，它是基于主體的涌現(xiàn)。1979年霍夫施塔特對基于主體的涌現(xiàn)作了描述，整個系統(tǒng)的靈活的行為依賴于相對較少的規(guī)則支配的大量主體的行為。研究群體智能系統(tǒng)，要弄清涌現(xiàn)現(xiàn)象的普遍原理，建立由簡單規(guī)則控制的模型來描述涌現(xiàn)現(xiàn)象的規(guī)律。1.3MAS（Multi-AgentSystem）系統(tǒng)如果說對單個智能體的研究是將傳統(tǒng)人工智能研究領(lǐng)域的方法集成在一個實體上進(jìn)行的話，那么，對多智能體系統(tǒng)（Multi-Agentsystem，MAS)的研究，則是對群體智能的更進(jìn)一步的拓展。在MAS中，整個系統(tǒng)所表現(xiàn)出來的智能或者說行為，不僅僅是多個智能體行為的簡單疊加，它所顯示出來的整個社會的行為存在更多的不確定因素，更為復(fù)雜，難以預(yù)測。1.3.1MAS（Multi-AgentSystem）概念對于MAS[30]的研究起源于上個世紀(jì)七十年代后期的分布式人工智能DistributedArtificialIntelligence，DAI)，它有兩大研究方向：分布式問題求解(DistributedProblemsolving，DPS)與MAS。DPS主要研究的是對于一個給定的問題，如何將任務(wù)在一組節(jié)點之間進(jìn)行分配。這些問題求解節(jié)點可能因為所擁有的資源、能力、信息等的不足，而需要相互合作，以期共同完成任務(wù)。這是一種從系統(tǒng)的觀點、在設(shè)計階段就進(jìn)行問題分解、求解規(guī)劃及解答合成的方式。而在近年來得到越來越多關(guān)注的MAS，則更加強(qiáng)調(diào)了問題求解節(jié)點的自治性。研究由多個自治的智能體組成的MAS，更重要的在于研究智能體之間的聯(lián)系以及整個系統(tǒng)所表現(xiàn)出來的特性。正是由于智能體之間的聯(lián)系的多樣性，使得整個系統(tǒng)呈現(xiàn)出復(fù)雜、難以預(yù)測的現(xiàn)象。這是一個高度交叉的研究領(lǐng)域。無論是從其理論方面，還是應(yīng)用方面，均涉及到眾多領(lǐng)域的相關(guān)內(nèi)容，如計算機(jī)學(xué)科、經(jīng)濟(jì)學(xué)、哲學(xué)、社會學(xué)、心理學(xué)、生態(tài)學(xué)和組織科學(xué)，而研究者從不同的方面給予不同的側(cè)重。計算機(jī)科學(xué)：這是MAS的起源領(lǐng)域，從而有著廣泛的研究內(nèi)容。從MAS的計算理論出發(fā)，研究在分布式/并發(fā)環(huán)境下，任務(wù)的分解與分配，智能體之間的協(xié)調(diào)、協(xié)作、通信、死鎖預(yù)防與解決等。在人工智能方面，有智能體的規(guī)劃、調(diào)度以及智能體之間的協(xié)商。經(jīng)濟(jì)學(xué)：主要是應(yīng)用經(jīng)濟(jì)學(xué)中的對策論(GameTheory)來研究智能體之間的交互問題，如規(guī)劃、協(xié)商、學(xué)習(xí)等問題。當(dāng)被認(rèn)為是理性的多個智能體因為某項任務(wù)進(jìn)行協(xié)商時，從各自的利益出發(fā)，對其他智能體的信念、意圖進(jìn)行推理，選擇最優(yōu)策略。傳統(tǒng)的對策論中參預(yù)者之間沒有通信，只是根據(jù)完全的或者是不完全的信息進(jìn)行決策。當(dāng)應(yīng)用到智能體的協(xié)商過程中時，則相應(yīng)地進(jìn)行了很多改進(jìn)，如將通信行為引入?yún)f(xié)商過程。社會學(xué)：包含有兩個方面——以人類社會研究來對MAS中存在的現(xiàn)象進(jìn)行研究，以及以MAS來仿真人類社會中可能的現(xiàn)象。對于前者可包括眾多的內(nèi)容，如對倫理、規(guī)范、組織等的研究：而對于后者，包括對于人類社會秩序、合作、沖突、協(xié)商等的仿真，主要討論某種特定的社會現(xiàn)象在某種情況下是如何涌現(xiàn)出來的，并以觀察到的規(guī)律來解釋和理解人類社會中的現(xiàn)象，并加以預(yù)測。同時，對社會倫理、規(guī)范、承諾、義務(wù)、權(quán)利等約束概念的研究，智能體在社會體系中遵循的規(guī)范、以防止惡意欺詐、使得社會秩序得以維護(hù)，采用社會規(guī)范、行為規(guī)范。組織學(xué)：借鑒人類組織學(xué)原理，主要研究MAS組織的模型、結(jié)構(gòu)、角色、規(guī)則、演進(jìn)及形成等，有利于降低智能體問題求解難度和求解復(fù)雜性。1.3.2MAS主要研究方向?qū)AS的研究不是孤立的，它借鑒了許多相關(guān)學(xué)科的研究方法與成果，同時，也為其他學(xué)科提供了新的思想與技術(shù)。從宏觀上看，包括MAS的組織、涌現(xiàn)現(xiàn)象；從微觀上看，則是智能體之間的互操作。合作(Cooperation)：這是MAS研究最為重要的一個方向，也是研究成果最多的一個方向。從DAI的研究開始，研究者就致力于多個求解節(jié)點之間的合作問題。其中包括有對合作模型、合作結(jié)構(gòu)、合作過程等方面。Smith于1980年提出的合同網(wǎng)(ContractNet)方法，類似于人類社會中的合同產(chǎn)生過程，管理者將一個待求解問題通告給其他節(jié)點，并從反饋的投標(biāo)中選擇合適的工作者，建立合同，并監(jiān)督任務(wù)完成；Lesser等提出的功能精確的協(xié)同方法(FunctionallyAccurate，cooperative，F(xiàn)A/C)是一種結(jié)果共享的協(xié)作方法，通過在問題求解過程中，智能體之間相互交換中間結(jié)果，以修正錯誤的估計，并整合出問題的最終解；Jennings提出的基于承諾和約定(CommitmentsandConventions)的協(xié)作方法，是針對合作過程中的不確定環(huán)境，對智能體的行為進(jìn)行規(guī)范與約束，使得其行為即具有預(yù)見性，又具有靈活性。另外，對于合作的社會、心理、思維等方面也漸漸引起了人們的注意：合作是如何產(chǎn)生的?合作產(chǎn)生的條件是什么?自利的智能體與無私的智能體之間是怎樣的關(guān)系等等。協(xié)商(Negotiation)：協(xié)商技術(shù)主要用于解決沖突，以使各自的行為得以協(xié)商，達(dá)成一致。主要從協(xié)商過程、協(xié)商協(xié)議、協(xié)商語言、協(xié)商決策等方面進(jìn)行研究。并多采用博弈論的理論方法來計算效用、進(jìn)行決策及評估，分為面向結(jié)果的協(xié)商模型和面向過程的協(xié)商模型。Wooldridge給出協(xié)商框架的4個部分：一個協(xié)商集合、一個協(xié)議、一組策略和一條規(guī)則。Zlotkin研究了自治智能體在協(xié)商集為空和非空的情況下(分別被稱為非協(xié)作域和協(xié)作域)的協(xié)商理論模型。由于協(xié)商中存在多樣化的問題，如參預(yù)協(xié)商的智能體數(shù)目、協(xié)商問題的數(shù)目、協(xié)商包含的參數(shù)的數(shù)目等，使得協(xié)商問題更加復(fù)雜。協(xié)商技術(shù)應(yīng)用廣泛，最多的應(yīng)用在電子商務(wù)、資源調(diào)配、生產(chǎn)過程等領(lǐng)域。面向智能體的程序設(shè)計(Agent-OrientedProgramming，AOP)：AOP的概念最早由Stanford大學(xué)的Shoham等人于1990年提出，作為一種新的計算模式，是比圖靈機(jī)理論更為接近地反映當(dāng)前計算現(xiàn)實。它是將心智狀態(tài)引入到傳統(tǒng)的面向?qū)ο蟪绦蛟O(shè)計(0bject．OrientedProgramming，OOP)中作為內(nèi)部狀態(tài)，而對象之間的消息傳遞也以諸如KQML等的智能體通信語言替代。與OOP中對象必須執(zhí)行所調(diào)用的行為不同，AOP中的智能體可以根據(jù)自身要求，選擇執(zhí)行或者拒絕請求的動作。其典型代表為AGENT-0語言，它包含多模態(tài)邏輯和與之對應(yīng)的智能體語言，但它過于簡單，無法應(yīng)對現(xiàn)實問題。1.3.3研究工具為了對智能體及MAS技術(shù)進(jìn)一步地研究，不但從理論上要有更系統(tǒng)、深入地探討，而且在從理論到建立實際的多智能體系統(tǒng)的過程中，更加需要有建模、分析、設(shè)計、開發(fā)、仿真的環(huán)境與工具。針對不同的環(huán)境需要，開發(fā)了多種MAS建造工具：JADE(JavaAgentDevelopmentFramework)：是完全由Java編寫的智能體開發(fā)框架，用于開發(fā)基于智能體的系統(tǒng)及應(yīng)用。JADE遵循FIPA規(guī)范，可以與其他FIPA的多智能體系統(tǒng)進(jìn)行操作。JADE以容器的形式提供智能體的運行環(huán)境，一個容器即一個Java虛擬機(jī)，它可以容納多個智能體在其中活動。AgentBuilder：圖形化的建模工具，用于快捷構(gòu)建智能智能體的工具包。它將智能體分為五部分：主體控制、引擎、適配器、視圖及庫。Swarm：是美國SantaFeInstitute(SFI)研究所開發(fā)的一套基于復(fù)雜系統(tǒng)理論的仿真平臺，能夠有效的模擬多智能體之間的行為和消息傳遞。由模型對象、觀察者對象、探測器組成。模型對象為待觀察的智能體；觀察者對象進(jìn)行全局環(huán)境的觀察與顯示；探測器則是為了以指定的形式顯示特定的屬性或變量。這一仿真平臺多用于進(jìn)行生態(tài)學(xué)、社會學(xué)、經(jīng)濟(jì)學(xué)等方面的研究，對于模擬離散、非線性的系統(tǒng)有著顯著的優(yōu)勢。Swarm最早只支持Object-C語言，到其2．0版本以后開始支持Java語言。中國科學(xué)院計算技術(shù)研究所的多主體環(huán)境MAGE(Multi-AgentEnvironment)提供一系列工具來支撐面向主體軟件工程的整個過程；主體統(tǒng)一建模平臺AUMP(AgentUnifiedModelingPlatform)進(jìn)行系統(tǒng)分析和設(shè)計；可視化主體開發(fā)工具VAStudio(visua1Agentstudio)進(jìn)行系統(tǒng)開發(fā)、MAGE運行環(huán)境進(jìn)行系統(tǒng)部署和管理；以及以Java編寫的面向主體的軟件開發(fā)環(huán)境AOSDE(AgentOrientedSoftwareDevelopingEnvironment)。1.4群體智能的研究方法群體智能是一種研究生命的科學(xué)，是從社會性昆蟲群體中個體之間的交互作用得到啟發(fā)。最早把社會動物的機(jī)制應(yīng)用于系統(tǒng)設(shè)計中的是Tselin和Rabin。Rabin構(gòu)造了移動細(xì)胞來解決圖問題和格子問題。Tselin提出了隨機(jī)的、分散的、非直接的交互和自組織這兩種特性可以使群集方法有潛在的強(qiáng)大能量[31]。在生物學(xué)的群體智能方法中，一個最著名的例子就是觀察鳥類的飛行產(chǎn)生的集群行為模型[32]，具有基本飛行能力的鳥被稱之為Boid，每個Boid對外界只有有限的感知能力，系統(tǒng)是Boid在仿真世界中的群集行為。通過觀察Boid行為能夠得到一些實際的啟發(fā)。通過調(diào)整行為參數(shù)可以得到各種鳥類的飛行模式，這種現(xiàn)象表明了相似規(guī)則也可以得到不同的結(jié)果。Reynolds的工作對群體智能的研究具有非常深刻的影響，其研究成果被公認(rèn)為是一個體現(xiàn)突現(xiàn)概念的生動例子[33]。其對以后涂小媛的人工魚模型的產(chǎn)生起到開創(chuàng)性的引導(dǎo)作用。當(dāng)然，還有Holland的遺傳算法和Echo模型[34]，Ray的Tierra系統(tǒng)等都是應(yīng)用生物學(xué)思想實現(xiàn)的群體智能。所有這些例子都是通過對生物的一些基本行為和現(xiàn)象進(jìn)行觀察，歸納總結(jié)，并抽取一些本質(zhì)特征而產(chǎn)生的，群體智能的思想來源于生物，在這個領(lǐng)域的研究中，模擬生命占有一個很重要的位置。群體智能應(yīng)用采用的思路：(1)觀察自然界，向生物學(xué)習(xí)它們的巧妙策略(如螞蟻覓食、形成“人”字的鳥類飛行)；(2)根據(jù)這些觀察結(jié)果總結(jié)出一些抽象的底層規(guī)則，掌握住這些規(guī)則的本質(zhì)；(3)把這類觀察用隱喻的方式引用到實際系統(tǒng)中(TSP問題、數(shù)字圖像處理等)；(4)運用規(guī)則解決實際系統(tǒng)中的問題。1.5研究現(xiàn)狀對智能體及多智能體的研究從上世紀(jì)七十年代末至今已有三十多年了，研究的重點也由早期的理論研究慢慢地轉(zhuǎn)移到結(jié)合實際應(yīng)用的研究，特別是對多智能體社會、組織，以及與網(wǎng)絡(luò)應(yīng)用相結(jié)合的研究。UniversityofSouthernCalifornia的信息科學(xué)研究所(InformationScienceInstitute，ISI)主要致力于智能體的應(yīng)用以及智能體群體行為理論的研究。他們的研究成果有COM-MTDP框架。COM-MTDP與早期基于BDI的組工作模型如聯(lián)合意圖、STEAM不同，它是基于決策理論的智能體組工作模型。CarnegieMellon大學(xué)機(jī)器人研究所的智能軟件智能體實驗室主要研究智能體、MAS及其在網(wǎng)絡(luò)環(huán)境中的應(yīng)用，如智能體相互操作、MAS互操作、多智能體學(xué)習(xí)等等。他們開發(fā)出了相應(yīng)的一系列軟件：如用于電子商務(wù)的RETSINA體系結(jié)構(gòu)。MIT媒體實驗室(MITMediaLaboratory)的軟件智能體小組(SoftwareAgentGroup)的研究目標(biāo)是設(shè)計能夠作為人類助手的軟件，即致力于作為代理的智能體。通過與人類交互進(jìn)行學(xué)習(xí)，更好地了解并預(yù)測用戶的需要、目標(biāo)。其典型應(yīng)用于搜索技術(shù)、電子設(shè)備接口等。在歐洲，由歐洲委員會資助的協(xié)怍項目——AgentLinkIII，其目的是為了支持與促進(jìn)歐洲在智能體技術(shù)領(lǐng)域的研究與發(fā)展。它由192個機(jī)構(gòu)團(tuán)體組成，主要參與者有Livepool大學(xué)、Southampton大學(xué)以及一些相關(guān)學(xué)科成員；此外，還有約40％的成員來自工業(yè)領(lǐng)域以及其他研究所。AgentLinkIII項目主要致力于智能體技術(shù)的應(yīng)用，如面向服務(wù)的網(wǎng)絡(luò)，異構(gòu)系統(tǒng)的互操作，其重點放在了核心商業(yè)過程的電子化上，如供應(yīng)鏈及供應(yīng)網(wǎng)絡(luò)的完全整合，可視化及可預(yù)見性等等。國內(nèi)對智能體及MAS的研究也取得了長足的進(jìn)展。中國科學(xué)院計算技術(shù)研究所的多主體環(huán)境MAGE，與歐共體的AgentCities連接，以實現(xiàn)在不同平臺之間進(jìn)行通信，提供服務(wù)，為研究者創(chuàng)建測試平臺及資源共享平臺。此外，清華大學(xué)、中科院沈陽自動化研究所等在對智能體理論模型研究、基于多智能體系統(tǒng)的機(jī)器人研究等方面貢獻(xiàn)良多。目前國內(nèi)外研究比較多的有螞蟻優(yōu)化算法、螞蟻聚類算法、微粒群優(yōu)化算法。主要包括下面兩個方面的研究[35]：1)群體算法研究a)螞蟻優(yōu)化算法(ACO)螞蟻個體在覓食過程中，會在自己經(jīng)過的路徑留下信息素，后面的螞蟻個體通過感知信息素的濃度來決定自己的路徑。由于信息素隨時間揮發(fā)，所以比較短的路徑上信息素濃度也比較大。因此，螞蟻就可以通過這種方式找到更短的路徑覓食，為解決各種尋優(yōu)問題提供了一種新的方法。意大利學(xué)者M(jìn)acroDorigo用于求解TSP問題，以后有用于求解二次分配問題、皇后問題、函數(shù)優(yōu)化問題、背包問題。b)微粒群優(yōu)化算法(PSO)PSO由JamesKennedy和R．C．Eberhart在1995年提出的[36,37]，是一種基于種群尋優(yōu)的啟發(fā)式搜索算法，該算法源于對鳥群、魚群覓食行為的模擬。首先初始化一群隨機(jī)粒子(隨機(jī)解)，然后通過迭代尋找最優(yōu)解，每次迭代中，粒子通過跟蹤兩個極值(個體極值和全局極值)來更新自己的速度和位置。應(yīng)用在函數(shù)的優(yōu)化問題，神經(jīng)網(wǎng)絡(luò)的訓(xùn)練。2)群體機(jī)器人群體智能最初被應(yīng)用于描述細(xì)胞機(jī)器人系統(tǒng)。通過對螞蟻等社會性昆蟲行為研究，發(fā)現(xiàn)了社會性昆蟲的自組織、自組裝能力。布魯塞爾自由大學(xué)的MacroDorigo領(lǐng)導(dǎo)的項目Swarm-bots，其目標(biāo)是建立一個由多個類似于昆蟲且簡單的機(jī)器人組成的群體，由多個簡單機(jī)器人組成的群體機(jī)器人系統(tǒng)通過協(xié)調(diào)、協(xié)作可以完成單個機(jī)器人無法完成或難以完成的工作。研究群體機(jī)器人系統(tǒng)，目標(biāo)是建立經(jīng)濟(jì)、靈活、健壯的系統(tǒng)去完成復(fù)雜的任務(wù)，主要研究內(nèi)容為群體機(jī)器人之間的交互、通信、協(xié)作與控制、機(jī)器人的自組裝等。1.6小結(jié)本章綜述了群體智能的研究背景、理論研究方法、研究現(xiàn)狀等，并介紹了多智能體系統(tǒng)的涌現(xiàn)行為。涌現(xiàn)是多智能體系統(tǒng)中智能體依靠有限局部信息最終匯聚成一個集群的行為，現(xiàn)實生活中表現(xiàn)為雁群、魚群、蜂群等。本文重點針對多智能體系統(tǒng)中的蜂擁問題進(jìn)行研究，在之后的章節(jié)中會分別介紹Olfati提出的蜂擁問題的經(jīng)典算法，分別從虛擬領(lǐng)導(dǎo)者直接影響的普通智能體數(shù)目，虛擬領(lǐng)導(dǎo)者在變速度運行時普通智能體跟隨情況和多虛擬領(lǐng)導(dǎo)者情況三方面進(jìn)行研究改進(jìn)，并應(yīng)用Matlab仿真工具對經(jīng)典算法和改進(jìn)之后的算法進(jìn)行數(shù)值仿真驗證。在之后的章節(jié)中，第二章將重點介紹Olfati蜂擁算法并進(jìn)行仿真，對算法1在隨機(jī)初始條件下出現(xiàn)的分裂現(xiàn)象和算法2在隨機(jī)初始條件下出現(xiàn)的蜂擁現(xiàn)象進(jìn)行研究分析。第三章將基于Olfati的算法2展開工作，分為兩部分，第一部分為對接收虛擬領(lǐng)導(dǎo)者信息的智能體數(shù)目和蜂擁智能體數(shù)目的相關(guān)性進(jìn)行實驗仿真分析，第二部分對虛擬領(lǐng)導(dǎo)者在變速運行時的蜂擁算法進(jìn)行改進(jìn)。第四章將對Olfati算法2進(jìn)行擴(kuò)展，將虛擬領(lǐng)導(dǎo)者數(shù)目從單個擴(kuò)展到多個。最后，第五章將對本文進(jìn)行總結(jié)并對未來研究工作進(jìn)行展望。2Oflati智能體蜂擁算法介紹及仿真Olfati[1]根據(jù)Reynolds原則，提出了多智能體系統(tǒng)蜂擁的數(shù)學(xué)解析方法，為蜂擁問題提供了理論分析框架。本章將分別介紹Olfati提出的三種蜂擁算法，他們分別為基于Reynolds模型的自由蜂擁算法，擁有虛擬領(lǐng)導(dǎo)者的蜂擁算法和含有障礙物的蜂擁算法，并對前兩種算法進(jìn)行MATLAB數(shù)值仿真，通過分析比較為之后的算法改進(jìn)提供基礎(chǔ)。2.1Reynolds模型介紹1986年，Reynolds提出了一個在三維空間上用計算機(jī)來模擬群體行為的模型。這個模型要求一群智能體的群體行為滿足三條基本規(guī)則：(1)分離：與鄰域內(nèi)的智能體避免相撞；(2)聚合：與鄰域內(nèi)的智能體保持緊湊；(3)速度匹配：與鄰域內(nèi)的智能體速度保持一致。智能體的鄰域是以智能體所處位置為中心點，圍繞該中心點的一定距離范圍和角度來構(gòu)成。圖2-1所示的智能體的鄰域是以智能體所處位置為圓心的一個圓。這個鄰域可以認(rèn)為是由于有限的知覺感應(yīng)造成的。每個智能體的運動受到其鄰域范圍內(nèi)智能體的位置和速度的影響。下向?qū)eynolds提出的三條控制規(guī)則分別加以詳細(xì)介紹。圖2-1智能體i的鄰域2.1.1分離分離規(guī)則是使一個智能體能夠和它附近的智能體保持一定的分隔距離，以避免發(fā)生碰撞，如圖2-2所示。為了能夠保持分離，一個智能體首先需要獲得鄰域內(nèi)其它智能體的位置信息。劉于一個智能體來說，每一個在其鄰域范圍內(nèi)的智能體與它之間有一個排斥力，這個排斥力是與它們之間的距離成反比的。每一個智能體所受到的排斥力是它鄰域范圍內(nèi)其它智能體對它的排斥力的累加。圖2-2分離2.1.2聚合聚合規(guī)則是使智能體間具有凝聚力，保持隊列的緊湊，如圖2-3所示。為了能夠產(chǎn)生聚合的群體行為，智能體需要獲得其鄰域內(nèi)其它智能體的位置信息，并計算出鄰域內(nèi)智能體位置的平均值，由此產(chǎn)生一個作用于該鄰域內(nèi)所有智能體的吸引力，這樣使得智能體向平均位置方向運動。圖2-3聚合2.1.3速度匹配速度匹配規(guī)則使各個智能體與其鄰域內(nèi)其他智能體的速度保持一致。如圖2-4所示。為了能夠?qū)崿F(xiàn)速度匹配，每個智能體需要獲得鄰域內(nèi)其它智能體速度信息，計算出鄰域內(nèi)智能體的平均速度。通過速度匹配，可以使得智能體速度大小和方向與這個鄰域內(nèi)所有智能體速度的平均值保持一致。圖2-4速度匹配2.2智能體蜂擁算法的數(shù)學(xué)基礎(chǔ)2.2.1蜂擁的數(shù)學(xué)拓?fù)浣Y(jié)構(gòu)：共識網(wǎng)絡(luò)（ProximityNets）圖G由節(jié)點和邊的集合組成，其中節(jié)點集為，邊集為(即，圖G一般為有向圖，且不存在自我回路)。如果，則圖G為無向圖。和值分別為圖的度和模值。對于動態(tài)網(wǎng)絡(luò)系統(tǒng)，可表征系統(tǒng)的通訊復(fù)雜性。圖的鄰接矩陣（adjacencymatrix）中不包含0元素。如果鄰接矩陣的元素中含有非0和1的元素，則稱對應(yīng)的圖為加權(quán)圖。這里，我們大多使用擁有位置決定鄰接矩陣元素值的加權(quán)圖。對于一個無向圖G，鄰接矩陣A是對稱的（或者）。節(jié)點的鄰居集合定義為 （2-1）令表示節(jié)點的位置，其中。向量被稱為圖中所有節(jié)點構(gòu)成的配置。這是一個由包含圖及節(jié)點構(gòu)成的數(shù)據(jù)對組成的配置?，F(xiàn)在考慮一群動態(tài)智能體，其動力學(xué)方程如下： （2-2）這里（即m=2或3）其中。使用基于粒子的蜂擁模型點于連續(xù)模型的優(yōu)點是連續(xù)模型不能進(jìn)行進(jìn)一步智能體傳感、交流，而且，不能使用計算機(jī)計算。令表示兩個智能體之間的距離。一個半徑為r的球型空間（見圖2-5）確定智能體i的空間范圍定義為 （2-3）其中||..||是中的歐幾里德標(biāo)準(zhǔn)。給定一個匹配的邊界r>0，一個共識網(wǎng)絡(luò)可以由V定義，并且可表示如下。 （2-4）圖2-5智能體i的鄰域顯然依靠q來確定?？蚣芙凶鲟徑咏Y(jié)構(gòu)。如果所有智能體的相互作用范圍是相同的，共識網(wǎng)絡(luò)就成為了一個無向圖。N個點的共識網(wǎng)絡(luò)一般是下面的假設(shè)的一種：1）智能體的球形范圍沒有一定的半徑，或2）每個智能體使用圓錐型范圍使用確定它的鄰居。在這篇文章中，所有的共識網(wǎng)絡(luò)都是雙向的圖形。2.2.2蜂擁的幾何結(jié)構(gòu)：（格子）為了讓現(xiàn)實生活中的集群獲得明顯的空間秩序，人們使用一個結(jié)構(gòu)來建立目標(biāo)蜂擁智能體的幾何結(jié)構(gòu)。為了完成這個，人們尋求滿足所有智能體之間的距離都滿足期望值，對于每個智能體取感知范圍為共識網(wǎng)絡(luò)。以上可以用描述下列代數(shù)公式描述： （2-5）公式2-5中的解扮演蜂擁智能體構(gòu)造的期望值（即蜂擁的幾何模型）。定理1.（）一個是所有滿足方程2-5的一個結(jié)構(gòu)。我們把d和k=r/d分別作為的期望值和感知期望比。圖2-6展示了的圖形例子。結(jié)構(gòu)由以下不等式描述： （2-6）圖2-6格子的例子，其中（a）為分布式格子，（b）為節(jié)點n=150的類似格子以下方程可以計算出結(jié)構(gòu)和之間的差距 （2-7）其中被稱為成對勢能（注意其他的勢能標(biāo)準(zhǔn)也可以被使用）。他的能量偏差可以被視為n個節(jié)點的光滑勢能函數(shù)?？梢宰C明，是所有結(jié)構(gòu)中最小的勢能函數(shù)，而且達(dá)到最小值0。對于一個包含不確定的邊長的，能量偏差可以被定為這意味著是n個點的最低能量構(gòu)造。2.2.3和光滑鄰接元素為了建立光滑的蜂擁勢能和每個共識網(wǎng)絡(luò)的鄰接矩陣，人們定義了稱為的一個非負(fù)映射。其為（不只一個標(biāo)準(zhǔn)），定義為 （2-8）其中參數(shù)>0，梯度由以下定義 （2-9）的在本文之后不變。碰撞函數(shù)（bumpfunction）是變量從0光滑變到1的函數(shù)。這里，人們用碰撞函數(shù)建立光滑的勢能函數(shù)，其含有有限的間斷和光滑的鄰接矩陣。以下是一種可以選用的碰撞函數(shù) （2-10）這里。可以看出來是一個光滑函數(shù)，使用這個碰撞函數(shù)，我們可以定義鄰接矩陣，它的成員為 （2-11）其中對于任何和，，。對于，是一個指示函數(shù)，其當(dāng)在[0,1]時為1，在其它范圍為0。使用這個指示函數(shù)，可以創(chuàng)造出一個依靠0-1的鄰接網(wǎng)絡(luò)。2.2.4涌現(xiàn)勢能函數(shù)涌現(xiàn)勢能函數(shù)是含有智能體群的不定映射V:。其中所有勢能函數(shù)的解的最小值是，反之亦然。在這篇文章中，涌現(xiàn)勢能是指能量偏離函數(shù)的一個平滑的形式，其梯度勢能是離散的。是一組吸引/排斥的成對的勢能，其最小值在取得，而且定義變?yōu)?在r實現(xiàn)，之后，以下的函數(shù) （2-12）是一個涌現(xiàn)的勢能函數(shù)，但是兩個不同節(jié)點具有相同位置即的情況是不可能發(fā)生的。為了解決這個問題，人們改寫方程（5），方程如下 （2-13）其中。因此，可以得到以下勢能函數(shù) （2-14）這里是光滑的成對的吸引/排斥勢能（由公式2-16給出），其中有限的間斷在取得，全局最小值為。為了建立一個含有有限間斷的光滑的成對的勢能函數(shù)，我們加入功能函數(shù)它對于所有為0。定義這個功能函數(shù)是 （2-15）其中而且是一個s型函數(shù)滿足,從而滿足。這個成對的吸引/排斥勢能在公式（2-14）中定義為 （2-16）這個函數(shù)的曲線在圖2-7中給出。圖2-7在有限間斷的光滑勢能2.3蜂擁控制算法介紹本節(jié)首先介紹自由空間蜂擁的離散算法，其針對的是帶有動態(tài)屬性的α智能體。自然界中的α智能體可對應(yīng)于鳥類，蜜蜂，魚和螞蟻。之后，介紹考慮到了障礙和集體的影響的β智能體和γ智能體算法。這些算法的基礎(chǔ)是蜂擁中的α智能體和它們互相的影響。在自由蜂擁中，每一個智能體接收到三項信號 （2-17）其中三個分量分別是速度、障礙和反饋影響。這里有一個蜂擁中的群體向一個方向移動的例子，Olfati-Saber提出兩個離散算法來建立在三維空間中的蜂擁運動。在一個群體中的具有客觀的蜂擁表現(xiàn)的微粒/智能體稱作α智能體。這里介紹三種關(guān)于α智能體的可擴(kuò)展的蜂擁算法。第一種蜂擁算法是一種基于梯度的具有速度匹配的算法。事實表明，這種算法體現(xiàn)了Reynolds所有三個規(guī)則。第二種算法是蜂擁在自由m空間運動中的主要算法。這個算法有一個附加的條件γ-智能體，它對群體的目標(biāo)進(jìn)行考慮。在分析算法2的過程中，會提出兩個猜測，關(guān)于蜂擁的空間秩序的關(guān)鍵性解釋，和相互連接的移動智能體網(wǎng)絡(luò)的自組織性。第三算法具有避障功能。通過β-智能體表現(xiàn)障礙的影響。這些智能體是運動的而且在障礙的邊界運動。之后，通過第三種算法的設(shè)計和分析，人們可以塑造多種類涌現(xiàn)勢能?？梢员砻?，蜂擁的跟蹤問題可以通過沒有領(lǐng)導(dǎo)者的點對點架構(gòu)解決。2.3.1蜂擁控制基本算法（算法1）由于Reynolds所提出的三條基本規(guī)則實際上是基于系統(tǒng)環(huán)境中智能體的位置和速度來考慮的。因此，考慮智能體在維的歐式空間中運行，假設(shè)第個智能體的運動方程為： （2-18）其中代表智能體的位置向量，代表智能體的速度向量，代表智能體的控制輸入（加速度）向量。此時的蜂擁問題就轉(zhuǎn)化為，當(dāng)輸入值滿足什么條件時，能夠使得個智能體的群體行為滿足Reynolds所提出的三條規(guī)則。其研究的主要工具是圖的應(yīng)力元素，定義與共識網(wǎng)絡(luò)的邊相對應(yīng)的應(yīng)力為 （2-19）不相鄰智能體之間的應(yīng)力元素為0。算法1的蜂擁可以用應(yīng)力和鄰接元素表示成以下形式上述方程包含了三條Reynolds法則，代表了速度匹配，和蜂擁的聚合，分離規(guī)則。為了證明這一事實，讓我們定義我們得到 （2-20）是的智能體的相鄰位置加權(quán)平均。因此，每個智能體遵循下列規(guī)定：a）如果，則移向相鄰加權(quán)中心。b)如果，則遠(yuǎn)離加權(quán)相鄰中心。這與智能體的速度一致性一起證明了算法1滿足三項Reynolds法則。令時刻t每個智能體的鄰域為，他是智能體能感受到智能體的集合，把智能體視為節(jié)點，當(dāng)兩個智能體之間有影響時，把兩節(jié)點相連，構(gòu)成邊。這些由節(jié)點和邊組成無向圖。如果每個智能體（節(jié)點）鄰域內(nèi)的智能體都不隨時間而變化，那么該無向圖也不隨時間而變化，此時系統(tǒng)具有固定的拓?fù)浣Y(jié)構(gòu)。如果對于網(wǎng)絡(luò)中的某個智能體，上一時段在其鄰域范圍內(nèi)的一些智能體在某時刻動到了其鄰域之外，或者上一時段不在其鄰域范圍內(nèi)的一些智能體在某時刻移動到了其臨域內(nèi)，則稱系統(tǒng)具有切換拓?fù)浣Y(jié)構(gòu)。圖對應(yīng)的鄰接矩陣為，其中 （2-21）圖的拉普拉斯矩陣為，其中度矩陣是一個對角矩陣，其中第個對角元是節(jié)點的度。是一個對稱的半正定矩陣，它的零特征值的數(shù)目等于圖中的連通子圖的數(shù)目。當(dāng)圖連通時，則的零特征值數(shù)目為1，其中對應(yīng)的特征值向量為全1向量，而且其他特征值均為正。如果只考慮要求系統(tǒng)中所有的智能體的速度達(dá)到一致，就可以對智能體的速度方程通過一致算法來實現(xiàn)速度匹配。對于任意兩個智能體，若時間趨近于無窮大時，它們的速度向量趨近于相同，則稱它們的速度達(dá)到一致。連續(xù)時間系統(tǒng)的一致算法可以取為：（2-22）對于固定拓?fù)浣Y(jié)構(gòu)來說，如果無向圖為連通；或者對于切換拓?fù)浣Y(jié)構(gòu)來說，如果存在無窮多個非空時間段內(nèi)無向圖的并為連通，那么各個智能體的速度最終能夠達(dá)到一致。近年來，許多控制學(xué)者通過利用速度一致性和人工勢能函數(shù)梯度的方法構(gòu)造蜂擁控制算法以實現(xiàn)Reynolds的蜂擁規(guī)則。對于智能體，其控制輸入為： （2-23）其中右邊第一項為人工勢能函數(shù)梯度，用于實現(xiàn)分離和聚合兩條規(guī)則。第二項用速度一致性算法，用于實現(xiàn)智能體之間的速度匹配。對于固定拓?fù)浣Y(jié)構(gòu)，如果拓?fù)浣Y(jié)構(gòu)是全連通的，則所有的智能體的速度大小和方向?qū)u進(jìn)趨近于一致，系統(tǒng)智能體之間的勢能會達(dá)到最小，智能體之間不會發(fā)生碰撞；對于切換拓?fù)浣Y(jié)構(gòu)，如果智能體切換前后，拓?fù)浣Y(jié)構(gòu)圖始終能夠保持連通則所有的智能體的速度仍然會漸進(jìn)趨于一致，智能體的勢能會達(dá)到最小且不會碰撞。當(dāng)蜂擁算法1的初始條件是任意選取時，可能會產(chǎn)生分裂象，如圖2-8所示。整個群體被分為三個子組，每個子組內(nèi)的智能體只能與自己子組內(nèi)的智能體交換信息，而且在自己內(nèi)部子組中達(dá)到局部蜂擁現(xiàn)象，但對于整個群體來說產(chǎn)生了分裂現(xiàn)象；只有當(dāng)各分組在運行中碰巧相遇，這樣子組之間才會發(fā)生信息交換。蜂擁控制的實現(xiàn)此時嚴(yán)重依賴于初始值的分布。圖2-8分裂現(xiàn)象2.3.2具有單個虛擬領(lǐng)導(dǎo)者的蜂擁控制算法（算法2）Olfati-Saber針對切換拓?fù)浣Y(jié)構(gòu)的基本蜂擁算法1容易形成分裂現(xiàn)象，在其基礎(chǔ)上增加了關(guān)于位置和速度反饋項。對于智能體i，他的控制輸入函數(shù)為：或 （2-24）其中反映智能體受到來自領(lǐng)導(dǎo)者的影響，定義如下其中是領(lǐng)導(dǎo)者智能體的速度和位置，一個領(lǐng)導(dǎo)智能是動態(tài)或固定的智能體，可以被看到作為移動的匯合點。當(dāng)領(lǐng)導(dǎo)者智能體是固定的時，是一個固定的矢量對，這指出了領(lǐng)導(dǎo)者智能原始的位置和速度。當(dāng)一個領(lǐng)導(dǎo)者智能體是動態(tài)的，它有下面的模型。 （2-25）在初始能量有限的假設(shè)條件下，Olfati-saber證明了在控制算法2的作用下，Reynolds的三條規(guī)則均可以實現(xiàn)，其中包括聚合，速度匹配和避免碰撞。該算法初始值任意選取時，即使因為出是值得原因而分成了各個子組，最終也能保證實現(xiàn)蜂擁，避免發(fā)生分裂現(xiàn)象。2.3.3障礙物環(huán)境下的蜂擁算法（算法3）迄今為止，本文所介紹的多智能體的蜂擁控制都是假設(shè)在個不存在障礙物的環(huán)境中，智能體的移動不受環(huán)境的限制的。對于運動環(huán)境中存在障礙物的情形，顯然，障礙物對智能體的影響與其二者間的距離有關(guān)。智能體和障礙物之間距離存在某一臨界值，當(dāng)兩者的距離小于此臨界值時，障礙物則會對智能體“產(chǎn)生”排斥力來阻止智能體繼續(xù)接近障礙物，以避免最終相撞；而二者之間距離大于等于此臨界值時，則障礙物與智能體間不存在任何作用力。另外，如果要求智能體集中到達(dá)目標(biāo)位置，顯然，目標(biāo)點對智能體的影響與其二者問的距離也是有關(guān)。隨著距離的減小，目標(biāo)點對智能體“產(chǎn)生”吸引力越小，直至智能體到達(dá)目標(biāo)點的吸引力為零。為了方便表示，Olfati-Saber除了將真正的智能體表示成智能體，虛擬領(lǐng)導(dǎo)者表示成智能體外，當(dāng)智能體和障礙物距離小于臨界距離時，把障礙對智能體的排斥表示成智能體。智能體繞過障礙物時，如圖2-9。圖2-9（a）墻壁形障礙物，（b）球形障礙物定義智能體和障礙物的排斥力方程為 （2-26）其中。方程在距離逐漸增大到z=d時，作用力光滑變?yōu)?，之后一直為零。它們之間的人工勢能函數(shù)為 （2-27）最終，Olfati-Saber設(shè)計除了在障礙物環(huán)境下的虛擬領(lǐng)導(dǎo)者的蜂擁控制算法： （2-28）其中第一項是基本算法，第二項是避免碰撞，第三項是使智能體達(dá)到目標(biāo)點，具體表示如下 （2-29）其中，。2.4算法仿真結(jié)果本小節(jié)將應(yīng)用Matlab工具對之前介紹的Olfati-Saber提出的前兩種算法進(jìn)行數(shù)值仿真，對理論結(jié)果進(jìn)行驗證。下面具體給出仿真參數(shù)：仿真時間loop=300，參數(shù)，智能體個數(shù)，感知半徑r=6，網(wǎng)格結(jié)構(gòu)Lattice期望距離d=5，參數(shù)h=0.9，a=1，b=2，智能體初始速度范圍，智能體初始位置范圍為，領(lǐng)導(dǎo)者智能體參數(shù)c1=0.1c2=0.2，離散步長step=0.1。Matlab仿真框架如下：1）對智能體初始個數(shù)、速度、位置進(jìn)行初始化。2）實現(xiàn)各智能體對其感知半徑范圍內(nèi)智能體的感知，具體實現(xiàn)為對鄰接矩陣賦值，若智能體j在智能體i的感知半徑內(nèi)，則，否則。3）分別用Matlab實現(xiàn)算法1和算法2：，求出當(dāng)前各智能體的加速度矢量。4）用已知量求下時段的各參數(shù)，方程為q(t+1)=q(t)+step*p(t)，p(t+1)=p(t)+step*u(t)。5）通過求得的新階段智能體的速度，位置矢量，進(jìn)行下階段計算。6）進(jìn)行l(wèi)oop次運算，每次保存?zhèn)€時間段的智能體速度位置信息，并最后將圖形繪制出來。2.4.1仿真算法1分裂結(jié)果當(dāng)蜂擁算法1的初始條件是任意選取時，由于初始狀態(tài)是任意的，所有的智能體不一定能夠形成一個連通的拓?fù)浣Y(jié)構(gòu)，因此可能會產(chǎn)生分裂象，如圖2-10所示。整個群體被分為五個子組，每個子組內(nèi)的智能體只能與自己子組內(nèi)的智能體交換信息，而且在自己內(nèi)部子組中達(dá)到局部蜂擁現(xiàn)象，但對于整個群體來說產(chǎn)生了分裂現(xiàn)象；只有當(dāng)各分組在運行中碰巧相遇，這樣子組之間才會發(fā)生信息交換。蜂擁控制的實現(xiàn)此時嚴(yán)重依賴于初始值的分布。本算法無法在任一條件下實現(xiàn)蜂擁，但是其體現(xiàn)了全部Reynolds原則，為了解決這一問題，Olfati提出了算法2，加入了領(lǐng)導(dǎo)智能體的概念，以避免蜂擁的分裂現(xiàn)象。圖2-10算法1仿真分裂結(jié)果，n=502.4.2算法二仿真結(jié)果圖2-11在2維空間中，50個智能體在算法2作用下的涌現(xiàn)行為。最初，50個智能體是隨機(jī)落在平面空間中的。各個智能體的初始速度坐標(biāo)是均勻隨即從[-1,1]中選取的。與之相對用，領(lǐng)導(dǎo)智能體的初始信息與普通智能體相同。離散步長取值為step=0.1，循環(huán)次數(shù)loop=100對涌向行為進(jìn)行仿真，并記錄各時間的智能體位置速度信息，在下圖中，分別展示了采樣時間為0.1，1，2，3，5，10秒的智能體信息。從仿真結(jié)果看到，在含有領(lǐng)導(dǎo)智能體的情況下，任意狀態(tài)下智能體可以實現(xiàn)蜂擁，并使所有的智能體速度大小方向一致，并能形成Lattice結(jié)構(gòu)。圖2-11.算法2仿真結(jié)果2.5小結(jié)本章對Reynolds原則和Olfati三種算法進(jìn)行了詳細(xì)的介紹，算法1通過各智能體對周圍環(huán)境的感知形成蜂擁，算法2解決了算法1中由于感知信息不足造成的分裂現(xiàn)象。通過應(yīng)用Matlab工具對Olfati提出的算法1和算法2進(jìn)行了仿真，發(fā)現(xiàn)算法1在網(wǎng)絡(luò)初始狀態(tài)不連通的情況下會產(chǎn)生分裂，而加入虛擬領(lǐng)導(dǎo)者的算法2能較好的避免分裂實現(xiàn)蜂擁。在本章的基礎(chǔ)上，我們將針對一些在實際應(yīng)用中可能出現(xiàn)的問題對Olfati的算法進(jìn)行改進(jìn)。3Oflati蜂擁算法改進(jìn)前面的章節(jié)已經(jīng)對蜂擁問題的數(shù)學(xué)描述和Olfati算法進(jìn)行了詳細(xì)的介紹，并應(yīng)用Matlab工具對Olfati提出的算法1和算法2進(jìn)行了仿真。在此基礎(chǔ)上，本章主要針對Olfati提出的算法2從兩方面進(jìn)行改進(jìn)。首先，Olfati算法2為了使所有智能體能夠形成蜂擁避免分裂現(xiàn)象，每個智能體都知道虛擬領(lǐng)導(dǎo)者的信息，這種方法在現(xiàn)實生活中不易于實現(xiàn)。經(jīng)一些科學(xué)研究表明，在自然界的大部分群集智能體系統(tǒng)中往往只有少部分個體能夠感知虛擬領(lǐng)導(dǎo)者的信息，比如，魚群在覓食過程中只有少部分魚知道食物的信息，然后把信息傳遞給附近的智能體，形成蜂擁。本章將針對這一現(xiàn)象，研究僅有部分智能體感知虛擬領(lǐng)導(dǎo)者信息的情況下，群集系統(tǒng)的蜂擁實現(xiàn)情況。其次，Olfati算法2盡管能夠?qū)崿F(xiàn)蜂擁結(jié)果，使每個智能體的速度方向與虛擬領(lǐng)導(dǎo)者速度方向達(dá)到一致。然而，在領(lǐng)導(dǎo)者智能體速度時變時，智能體不能夠很好的跟蹤領(lǐng)導(dǎo)者的速度大小，然而在實際應(yīng)用中，虛擬領(lǐng)導(dǎo)者的速度一般均為時變。針對此問題，本章將研究當(dāng)虛擬領(lǐng)導(dǎo)者速度時變時，如何改進(jìn)蜂擁算法以期達(dá)到較好的跟蹤效果。為了開展將要進(jìn)行的工作，在此首先對Olfati算法2進(jìn)行簡要的回顧介紹。Olfati-Saber針對切換拓?fù)浣Y(jié)構(gòu)的基本蜂擁算法1容易形成分裂現(xiàn)象，因為在其基礎(chǔ)上增加了關(guān)于位置和速度的反饋項。對于智能體，他的控制輸入函數(shù)為：或 （3-1）其中反映智能體受到來自領(lǐng)導(dǎo)者的影響，為速度一致項，為人工勢能梯度函數(shù)。在初始能量有限的假設(shè)條件下，Olfati-saber證明了在控制算法2的作用下，Reynolds的三條規(guī)則均可以實現(xiàn)，其中包括聚合，速度匹配和避免碰撞。該算法初始值任意選取時，即使網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)不連通分成幾個子組，最終也能保證實現(xiàn)整體蜂擁，避免發(fā)生分裂現(xiàn)象。3.1部分智能體感知虛擬領(lǐng)導(dǎo)者時蜂擁實現(xiàn)研究3.1.1引言之前提出的算法2通過對每個智能體添加引導(dǎo)反饋來實現(xiàn)跟蹤目標(biāo)的功能，假設(shè)每個智能體都具有領(lǐng)導(dǎo)智能體的信息，這樣的假設(shè)的好處是能夠保證每個智能體都能夠內(nèi)聚并達(dá)到其玩的速度，然而，這個假設(shè)和自然中的很多實例是不相符合的。在自然界中，群體中往往只有很少的個體具有引導(dǎo)信息，比如食物所在的位置或者遷移的路線等等。例如，研究魚群中只有少量魚具有遷移的路線信息，但是他們能夠引導(dǎo)整個魚群游向期望的地點；人類社會中只有一部分人對未來有明確的認(rèn)識，但整個人類社會能不斷前進(jìn)。這說明，只需要群體中很少的一部分智能體具有引導(dǎo)信息，群體中的絕大部分智能體就可以達(dá)到期望的群體行為。3.1.2少數(shù)個體具有引導(dǎo)信息的蜂擁控制算法本算法將在算法2中進(jìn)行一些改進(jìn)，對加速度方程（2-29）改寫如下（算法A1）：（3-2）其中當(dāng)含有的信息時，，表示智能體能夠感知虛擬領(lǐng)導(dǎo)者的信息。當(dāng)不含有的信息時，，表示智能體不能感知虛擬領(lǐng)導(dǎo)者的信息。通過引入上述數(shù)學(xué)符號，我們可通過控制的值來控制接收到虛擬領(lǐng)導(dǎo)者信息的普通智能體的數(shù)目。3.1.3仿真結(jié)果本節(jié)在n個智能體之中隨機(jī)選取一定比例的智能體作為具有引導(dǎo)信息的智能體。圖3-1顯示了在n取為100和200的情況下，能夠跟隨領(lǐng)導(dǎo)智能體的普通智能體所占的百分比，這些數(shù)據(jù)都是在10次仿真后取平均值的結(jié)果。其中仿真周期loop=300，步長step=0.1。圖3-1具有引導(dǎo)信息的智能體百分比同跟隨百分比的關(guān)系圖從圖中可以看到，在一個群體中，能夠跟隨領(lǐng)導(dǎo)智能體的數(shù)目是能感知引導(dǎo)信息智能體的遞增函數(shù)，當(dāng)比例占到0.1時，有60%的智能體能夠跟隨領(lǐng)導(dǎo)智能體。通過兩條曲線的比較我們可以看出，當(dāng)智能體總數(shù)目增多時，更小比例的智能體就能夠滿足一定比例跟隨的要求。通過以上仿真結(jié)果表明，在群集系統(tǒng)中，尤其是大規(guī)模群集中，只要控制少部分智能體感知虛擬領(lǐng)導(dǎo)者的信息，群集中的大部分智能體即可達(dá)到蜂擁。這一現(xiàn)象對實際應(yīng)用具有引導(dǎo)性作用，比如應(yīng)用大規(guī)模的傳感器對某一目標(biāo)系統(tǒng)進(jìn)行跟蹤，即使僅有少量傳感器能夠檢測到目標(biāo)系統(tǒng)狀態(tài)，只要傳感器網(wǎng)絡(luò)能夠在一段時間內(nèi)保持合并連通，即可有效地對目標(biāo)系統(tǒng)進(jìn)行較好的跟蹤，這樣也可以幫助大量減少傳感器的檢測能量損耗。3.2具有變速度虛擬領(lǐng)導(dǎo)者改進(jìn)蜂擁算法3.2.1引言在虛擬領(lǐng)導(dǎo)者具有變速度的情況下，Olfati-Saber證明了他的算法最終能夠使所有的智能體達(dá)到相同的速度，但是，通過實際數(shù)值仿真表明，最終所有智能體的速度并不等于領(lǐng)導(dǎo)智能體的速度。針對該問題，本節(jié)將對Olfati-Saber算法2進(jìn)行改進(jìn)，使得所有的智能體最終能夠跟蹤上虛擬領(lǐng)導(dǎo)者的速度。這一點對跟蹤問題十分有用，比如應(yīng)用無人駕駛飛行器編隊對某一不明飛行器進(jìn)行跟蹤，如果僅僅能夠?qū)崿F(xiàn)編隊，而無法跟蹤上目標(biāo)系統(tǒng)，則無法進(jìn)行有效跟蹤。3.2.2算法描述Olfati-Saber的算法2能夠有效地實現(xiàn)蜂擁，即所有的智能體都能夠收斂到一個相同的速度。然而，這個速度在一般情況下并不等于領(lǐng)導(dǎo)智能體的速度，本節(jié)將提出一種改進(jìn)的蜂擁控制算法，該算法能夠使所有的智能體能夠準(zhǔn)確的跟蹤虛擬領(lǐng)導(dǎo)者的速度值。本節(jié)改進(jìn)的蜂擁控制算法A1如下：（3-3）其中為領(lǐng)導(dǎo)智能體的加速度信息。在控制輸入中加入領(lǐng)導(dǎo)者加速度信息，這在實際應(yīng)用中也是可實現(xiàn)的。我們可以通過檢測智能體的速度或位置應(yīng)用觀測器對加速度進(jìn)行估計。從以下的仿真結(jié)果可看出，速度跟隨情況得到了明顯的改善。3.2.3仿真及結(jié)果本節(jié)首先對原始算法的智能體速度跟隨方向情況進(jìn)行仿真，虛擬領(lǐng)導(dǎo)者原始速度為在[-1,1]之間的隨機(jī)取值，且進(jìn)行勻速直線運動，普通智能體為隨機(jī)選取的所有智能體中的10個，步長step=0.1s，周期loop=800，如圖3-2所示。之后，本節(jié)分別對原始算法（圖3-3）和改進(jìn)算法（圖3-4）進(jìn)行虛擬領(lǐng)導(dǎo)者為變速度時的仿真比較，普通智能體為隨機(jī)選取的所有智能體中的10個，此時虛擬領(lǐng)導(dǎo)者在加速度為，步長取值step=0.1，周期loop=800。最后，本節(jié)將首先對改進(jìn)算法A1在虛擬領(lǐng)導(dǎo)者為變速度時進(jìn)行仿真，并進(jìn)一步研究當(dāng)接收虛擬領(lǐng)導(dǎo)者信息數(shù)占智能體總數(shù)為10%時的蜂擁情況(圖3-5)。智能體總數(shù)目n=100。在以下的仿真結(jié)果中，原始算法為Olfati算法2。圖3-2虛擬領(lǐng)導(dǎo)者勻速運動時原始算法中速度方向與速度模的跟隨情況粗紅線為領(lǐng)導(dǎo)者速度信息，細(xì)藍(lán)線為普通智能體速度信息圖3-3虛擬領(lǐng)導(dǎo)者變速運動時原始算法中速度方向與速度模的跟隨情況粗紅線為領(lǐng)導(dǎo)者速度信息，細(xì)藍(lán)線為普通智能體速度信息圖3-4虛擬領(lǐng)導(dǎo)者變速運動時改進(jìn)算法A1中速度方向與速度模的跟隨情況粗紅線為領(lǐng)導(dǎo)者速度信息，細(xì)藍(lán)線為普通智能體速度信息圖3-5改進(jìn)算法A1在接收領(lǐng)導(dǎo)者信息智能體個數(shù)為10%時蜂擁結(jié)果從以上仿真圖中可以得到以下結(jié)論：（1）從圖3-2中可以看出，當(dāng)虛擬領(lǐng)導(dǎo)者為勻速直線運動時，采用原始算法可以使普通智能體很好地跟隨虛擬領(lǐng)導(dǎo)者的運動。（2）從圖3-3中可以看出，當(dāng)虛擬領(lǐng)導(dǎo)者為變速運動時，采用原始算法不能使普通智能體及時地跟隨虛擬領(lǐng)導(dǎo)者，只能達(dá)到大致相同。（3）從圖3-4中可以看出，當(dāng)虛擬領(lǐng)導(dǎo)者為變速運動時，采用改進(jìn)算法A1可以很好地使智能體跟隨領(lǐng)導(dǎo)者的運動情況，這是由于在控制輸入中加入了虛擬領(lǐng)導(dǎo)者加速度一項的作用。這在實際應(yīng)用中，加速度測量也是可實現(xiàn)的。因而，該算法的改進(jìn)對蜂擁算法在實際中的應(yīng)用起到了一定的擴(kuò)展作用。（4）從圖3-5中可以看出，在使用改進(jìn)算法A1后，只有少部分智能體擁有虛擬領(lǐng)導(dǎo)者信息時能夠使絕大部分智能體達(dá)到蜂擁的情況依舊成立。通過4組圖的比較可以看出，改進(jìn)算法A1能夠很好的克服原始算法不能很好地跟隨領(lǐng)導(dǎo)者變速度情況時的不足，同時也保留了原始算法的所有蜂擁特點。3.3小結(jié)本章在Olfati算法2的基礎(chǔ)上，對其進(jìn)行了兩方面的分析和改進(jìn)：（1）第一部分分別在智能體數(shù)目為100和200的情況下進(jìn)行仿真，給出了接收虛擬領(lǐng)導(dǎo)者信息的智能體百分比與蜂擁智能體總個數(shù)百分比的關(guān)系曲線。從曲線中可以看出，當(dāng)含有領(lǐng)導(dǎo)者信息智能體數(shù)目達(dá)到總數(shù)10%即可有60%智能體達(dá)到蜂擁。另外，智能體總數(shù)越多達(dá)到相同比例蜂擁所需接收引導(dǎo)信息的智能體個數(shù)百分比越小。（2）第二部分，對虛擬領(lǐng)導(dǎo)者在變速度情況下普通智能體跟隨算法進(jìn)行了改進(jìn)。通過在反饋信息中加入了領(lǐng)導(dǎo)者加速度分量，使智能體的速度模能夠較好地跟蹤虛擬領(lǐng)導(dǎo)者的速度模。最后通過仿真對兩種算法的速度模跟蹤情況進(jìn)行了比較，結(jié)果表明改進(jìn)算法相比于原始算法而言，普通智能體能夠很好地跟隨虛擬領(lǐng)導(dǎo)者的速度達(dá)到蜂擁。4多虛擬領(lǐng)導(dǎo)智能體蜂擁實現(xiàn)多智能體蜂擁控制算法中的跟蹤問題往往只涉及到具有恒定速度的單個虛擬領(lǐng)導(dǎo)者。本章將研究具有變速度的多個虛擬領(lǐng)導(dǎo)者的蜂擁問題，即群體中的智能體跟蹤各自需要跟蹤的虛擬領(lǐng)導(dǎo)者。在實際的自然界中，生物群集中往往會出現(xiàn)多個領(lǐng)導(dǎo)者，從而使得整個群集分成多個子集。在實際應(yīng)用的某些場合，比如應(yīng)用一群機(jī)器人去完成搜救工作，需要分成幾個子組分散開來去進(jìn)行搜救更好地完成復(fù)雜的任務(wù)。針對這類現(xiàn)象，我們提出了一個帶有多個虛擬領(lǐng)導(dǎo)者的多智能體蜂擁控制算法，使各智能體都能跟蹤各自的領(lǐng)導(dǎo)者并不互相影響。4.1引言對于單個虛擬領(lǐng)導(dǎo)者的情形，每個具有引導(dǎo)信息的智能體都是受到同樣的一個虛擬領(lǐng)導(dǎo)者的影響，在原算法的作用下，每個具有引導(dǎo)信息的智能體都能達(dá)到期望的運行速度。然而，對于多個虛擬領(lǐng)導(dǎo)者的情形，具有引導(dǎo)信息的智能體可能受到不同領(lǐng)導(dǎo)者信息的影響，由于智能體之間還有相互作用的影響，單個虛擬領(lǐng)導(dǎo)者情況下的蜂擁控制算法并不能直接運用到具有多個虛擬領(lǐng)導(dǎo)者的情況。在本章，我們提出了帶有多個虛擬領(lǐng)導(dǎo)者的蜂擁控制算法，解決了多個虛擬領(lǐng)導(dǎo)者的蜂擁控制問題。4.2算法介紹考慮n個智能體在2維空間中運行，可以假設(shè)第個智能體的運動方程為： （4-1）假設(shè)有m個虛擬領(lǐng)導(dǎo)者，他們滿足運動方程： （4-2）這里所要研究的問題就是如何設(shè)計控制輸入使得每個智能體速度能夠達(dá)到各自需跟蹤的虛擬領(lǐng)導(dǎo)者的速度，并且和其他智能體之間保持一個期望的距離且不相碰撞。由于每個智能體的感知能力有限，它們只能感應(yīng)到自己領(lǐng)域半徑內(nèi)的智能體狀態(tài)。在本章中，智能體的鄰域定義為方程。這里假設(shè)智能體不僅能將自己的信息傳出給在它鄰域內(nèi)的其他智能體，而且能夠?qū)⑵涓櫟奶摂M領(lǐng)導(dǎo)者的信息傳輸給他們。這個假設(shè)在實際應(yīng)用中是可行的。例如，一個機(jī)器人可以將自己的信息和他所跟蹤的目標(biāo)的信息傳輸給他鄰域內(nèi)的其他機(jī)器人。如果將智能體作為節(jié)點，并用無向邊連接節(jié)點和他的臨域中的所有節(jié)點，那么在時刻t有這些節(jié)點和邊組成的網(wǎng)絡(luò)可以用一個無向圖來表示。對于網(wǎng)絡(luò)中某個智能體，上一時段在其領(lǐng)域范圍內(nèi)的一些智能體在某時刻移動到了其鄰域之外，或者上一時刻不在其臨域范圍內(nèi)的一些智能體在某時刻移動到其鄰域之內(nèi)，因此系統(tǒng)具有切換拓?fù)浣Y(jié)構(gòu)。之后，本節(jié)提出如下蜂擁控制算法A2, （4-3）公式中為智能體的引導(dǎo)信息來源的加速度信息。在對智能體各部分反饋都加入多領(lǐng)導(dǎo)者信息影響后，通過仿真結(jié)果可以看到，這種算法對多智能體使用原方法時導(dǎo)致的相互影響有很好的抑制作用。4.3仿真結(jié)果如果我們直接用Olfati算法2來控制一群多智能體跟蹤多個具有變化速度的虛擬智能領(lǐng)導(dǎo)者，其控制出入可以記為：（4-4）下面，本文將通過數(shù)值仿真對比10個智能體在Olfati蜂擁控制算法作用下與改進(jìn)算法A2作用下跟蹤兩個虛擬領(lǐng)導(dǎo)者的控制效果。其中，10個智能體的初始位置和速度分別隨機(jī)產(chǎn)生于和；當(dāng)時，智能體跟蹤領(lǐng)導(dǎo)者1，當(dāng)時，智能體跟蹤領(lǐng)導(dǎo)者2。鄰域半徑，智能體間期望距離，兩個虛擬領(lǐng)導(dǎo)者的加速度均為。以下原始算法均為Olfati算法2。圖4-1顯示，當(dāng)使用原始方法時，智能體因為相互作用可能無法完成各自的跟蹤任務(wù)，其中各智能體并沒有5個和5個分開，這是因為智能體之間的相互影響產(chǎn)生的。圖4-1Olfati算法2的多領(lǐng)導(dǎo)者蜂擁仿真結(jié)果圖4-2顯示了使用改進(jìn)算法A2之后的效果，在圖中，各智能體能夠跟隨自己的領(lǐng)導(dǎo)智能體，其中每個虛擬領(lǐng)導(dǎo)者影響5個智能體。虛擬領(lǐng)導(dǎo)者的加速度取值為，周期選取loop=800，步長step=0.1。圖4-2改進(jìn)算法A2的多領(lǐng)導(dǎo)者蜂擁仿真結(jié)果圖4-3顯示了使用改進(jìn)算法A2后，智能體對領(lǐng)導(dǎo)者的跟隨情況，每個智能體的速度能夠很好的跟隨各自領(lǐng)導(dǎo)者的速度信息。圖4-3改進(jìn)算法A2的多領(lǐng)導(dǎo)者速度模跟隨情況其中粗實線為虛擬領(lǐng)導(dǎo)者1，粗虛線為虛擬領(lǐng)導(dǎo)者2，細(xì)線為普通智能體4.4小結(jié)本章在Olfati算法2的基礎(chǔ)上，對其進(jìn)行了擴(kuò)展，將單個虛擬領(lǐng)導(dǎo)者擴(kuò)展到多個虛擬領(lǐng)導(dǎo)者的情形。通過改進(jìn)控制輸入項，加入了各自需跟蹤虛擬領(lǐng)導(dǎo)者位置的偏差項，使得改進(jìn)算法A2很好地克服了原算法在多虛擬領(lǐng)導(dǎo)者時普通智能體之間相互影響而使得無法跟蹤各自虛擬領(lǐng)導(dǎo)者的缺陷，仿真結(jié)果也表明改進(jìn)算法確實有效。5結(jié)論及展望群體智能中的個體在無中心控制的情況下體現(xiàn)出來的宏觀有序的行為稱之為涌現(xiàn)現(xiàn)象。蜂擁問題作為一種典型的涌現(xiàn)現(xiàn)象在自然界中普遍存在，比如魚群、鳥群、蜂群等。隨著國防工業(yè)的進(jìn)一步發(fā)展，蜂擁控制被應(yīng)用于多智能體系統(tǒng)合作控制中，比如無人駕駛飛行器群的控制、海底自治潛艇群的控制，無人深入地區(qū)多機(jī)器人的群集控制等。本文重點對多智能體的蜂擁控制算法進(jìn)行了分析研究。本文的主要工作如下：（1）本文根據(jù)Reynolds法則和Olfati的經(jīng)典算法，應(yīng)用Matlab工具搭建了多智能體系統(tǒng)蜂擁控制的算法框架，實現(xiàn)了Olfati算法1和算法2。為多智能體蜂擁行為的研究提供了分析基礎(chǔ)。（2）本文對Olfati算法1和算法2進(jìn)行了仿真，仿真結(jié)果驗證了算法1的局限性，既只有在特定的初始條件下（初始狀態(tài)各個智能體構(gòu)成的拓?fù)渚W(wǎng)絡(luò)是連通的）才能夠形成群體的蜂擁，而在一般情況時，算法1會導(dǎo)致群體的分裂。通過對算法2的仿真研究發(fā)現(xiàn)，加入單個虛擬領(lǐng)導(dǎo)者能夠改善算法1的弊端，即算法不依賴于智能體初始狀態(tài)，在任意的初始條件下，多智能體系統(tǒng)都能形成蜂擁，達(dá)到格子狀結(jié)構(gòu)。（3）本文在Olfati算法2的基礎(chǔ)上，對其進(jìn)行了三方面的分析和改進(jìn)：首先Olfati算法2為了使所有智能體能夠形成連通拓?fù)浣Y(jié)構(gòu)，每個智能體都感知虛擬領(lǐng)導(dǎo)者的信息，這種方法在現(xiàn)實生活中是不易實現(xiàn)的，科學(xué)研究表明在自然界中往往只有一部分個體能夠感受到領(lǐng)導(dǎo)者信息，之后把信息傳遞給附近的智能體，進(jìn)而形成蜂擁。本文針對該現(xiàn)象，研究了僅有部分智能體具有領(lǐng)導(dǎo)者信息時的群集蜂擁問題。通過應(yīng)用Matlab工具進(jìn)行仿真，發(fā)現(xiàn)僅有部分智能體感知虛擬領(lǐng)導(dǎo)者信息時，依舊有大部分智能體能夠達(dá)到蜂擁。且當(dāng)需要實現(xiàn)相同比例的蜂擁時，規(guī)模越大的群集所需感知虛擬領(lǐng)導(dǎo)者信息的智能體比例越小。其次，Olfati算法2盡管已經(jīng)能夠?qū)崿F(xiàn)蜂擁結(jié)果，并使每個智能體的速度方向均和領(lǐng)導(dǎo)者智能體達(dá)到一致。然而，在領(lǐng)導(dǎo)者智能體具有變速度情況時，智能體不能夠很好的跟蹤領(lǐng)導(dǎo)者的速度大小。本文通過對算法進(jìn)行改進(jìn)，在反饋信息中加入了領(lǐng)導(dǎo)者加速度分量，使智能體的速度模能夠較好地跟蹤虛擬領(lǐng)導(dǎo)者的速度模。最后通過仿真對兩種算法的速度模跟蹤情況進(jìn)行了仿真，仿真結(jié)果表明改進(jìn)算法相比于原始算法而言，普通智能體的速度模量能夠更好的跟隨虛擬領(lǐng)導(dǎo)者的速度模量。最后，Olfati算法2只研究了群體中含單個虛擬領(lǐng)導(dǎo)者的情況，然而在實際應(yīng)用中，一個群集系統(tǒng)可能會受到多個虛擬領(lǐng)導(dǎo)者的影響。本文對Olfati算法2進(jìn)行改進(jìn)，將單個虛擬領(lǐng)導(dǎo)者擴(kuò)展到多個虛擬領(lǐng)導(dǎo)者情形，并通過仿真驗證了改進(jìn)算法能夠很好地克服Olfati算法在直接擴(kuò)展到多領(lǐng)導(dǎo)者時普通智能體之間相互影響的情況。對未來工作的展望：本文對Olfati算法進(jìn)行了仿真，并對其進(jìn)行了改進(jìn)，但仍存在很多問題可作為下一步的研究方向。（1）本文對多智能體系統(tǒng)的蜂擁算法進(jìn)行的實現(xiàn)和改善，已經(jīng)能夠很好的通過Reynolds原則實現(xiàn)智能群體的蜂擁活動。然而，目前的研究還局限在計算機(jī)仿真階段，沒有在實際中應(yīng)用，將蜂擁問題應(yīng)用到實際中如車隊編隊，衛(wèi)星覆蓋區(qū)域等領(lǐng)域，進(jìn)一步發(fā)現(xiàn)實際應(yīng)用存在的問題，將會對蜂擁理論有很大的推進(jìn)作用。（2）本文在繪制接收領(lǐng)導(dǎo)者信息智能百分比同蜂擁個數(shù)百分比的關(guān)系曲線時是通過多次運算取平均值的方法進(jìn)行仿真的，這種方法并不具有嚴(yán)格的可重復(fù)性，在之后的工作中，可對這部分進(jìn)行嚴(yán)格的數(shù)學(xué)分析，從而得到可重復(fù)的實驗方法將成為工作的一個重點。（3）本文的所有仿真實驗都是在二維空間中實現(xiàn)的，而現(xiàn)實生活是在三維空間中進(jìn)行的。所以將蜂擁問題擴(kuò)展到三維空間實現(xiàn)很有必要。參考文獻(xiàn)[1]RezaOlfati-Saber.FlockingforMulti-AgentDynamicSystems:AlgorithmsandTheory[J].IEEETransactionsonAutomaticControl,2006,3:401-421.[2]B.L.Partridge.Thechorus-linehypothesisofmaneuverinavianflocks[J].Nature,1984,309:344–345.[3]B.L.Partridge.Thestructureandfunctionoffishschools[J].ScientificAmerican,1982,246:114–123.[4]A.Okubo.Dynamicalaspectsofanimalgrouping:swarms,schools,flocks,andherds[J].Biophysics,1986,22:1–94.[5]C.W.Reynolds.Flocks,herds,andschools:adistributedbehaviormodel[J].ComputerGraphics,1987,21:25–34.[6]T.Vicsek,A.Cziro′ok,E.Ben-Jacob,I.Cohen,andO.Shochet.Noveltypeofphasetransitioninasystemofself-drivenparticles[J].PhysicalReviewLetters,1995,75:1226–1229.[7]J.TonerandY.Tu.Flocks,herds,andschools:Aquantitativetheoryofflocking[J].PhysicalReviewE,1998,58:4828–4858.[8]N.Shimoyama,K.Sugawara,T.Mizuguchi,Y.Hayakawa,andM.Sano.Collectivemotioninasystemofmotileelements[J].PhysicalReviewLetters,1996,76:3870–3873.[9]E.Shaw.Fishinschools[J].NaturalHistory,1975,84:40–45.[10]D.Helbing,I.Farkas,andT.Vicsek.Simulatingdynamicalfeaturesofescapepanic[J].Nature,2000,407:487–490.[11]T.Vicsek.Aquestionofscale[J].Nature,2001,411:421–421.[12]J.K.Parrish,S.V.Viscido,andD.Grunbaum.Self-organizedfishschools:anexaminationofemergentproperties[J].Biol.Bull,2002,202,296–305.[13]D.Estrin,R.Govindan,J.Heidemann,andS.Kumar.Nextcenturychallenges:scalablecoordinationinsensornetworks[J].ProceedingofMobileComputingandNetworking,1999,21:263–270.[14]A.MogilnerandL.Edelstein-Keshet.Spatio-temporalorderinpopulationsofself-aligningobjects:formationoforientedpatches[J].PhysicaD,1996,89:346–367.[15]趙建.魚群集群行為的建模與仿真[D].太原:太原工業(yè)大學(xué).2008.[16]王瀾.基于廣義相關(guān)性的多Agent交互作用研究[D].西安:西北工業(yè)大學(xué),2006.[17]王玫,朱云龍,何小賢.群體智能研究綜述[J].