基于異質(zhì)網(wǎng)絡(luò)的蜂擁控制研究

張金春，叢 凱，王帥磊

(海軍航空大學(xué)， 山東 煙臺 264001)

蜂擁行為是指蜂群、魚群、鳥群等生物群體利用簡單的幾條規(guī)則和環(huán)境信息，通過個體之間的相互影響，最終形成穩(wěn)定有秩序的群體運動[1-7]。1987年，Reynolds[8]提出了具有代表性的蜂擁控制三條規(guī)則：分離、聚合和速度匹配。后來，Olfati-Saber[9]也對蜂擁控制算法改進(jìn)和優(yōu)化?，F(xiàn)在，蜂擁控制已經(jīng)在無線傳感器網(wǎng)絡(luò)、機(jī)器人編隊、無人機(jī)等各領(lǐng)域應(yīng)用。1995年，Vicsek等[10]提出了均質(zhì)感知模型：在二維平面上，存在一群初始位置隨機(jī)分布的質(zhì)點，它們的運動速率相同但是運動方向隨機(jī)分布，并且感知半徑相同。因為質(zhì)點的感知半徑相同，所以稱為均質(zhì)感知模型。對于任意一個質(zhì)點，它下一時刻的運動方向受到其感知半徑內(nèi)其他質(zhì)點的運動影響。

在實際生活中，很多智能體系統(tǒng)應(yīng)該是異質(zhì)的，即智能體的影響半徑各不相同。比如在生物群體中因為年齡和權(quán)威等個體差異使得每個個體對其他個體的影響能力各不相同。近年關(guān)于異質(zhì)多智能體的研究中，文獻(xiàn)[11]在“跟隨者-領(lǐng)導(dǎo)者”的框架下，分別針對有外界干擾和存在多個虛擬領(lǐng)導(dǎo)者的情況，在異質(zhì)多智能體系統(tǒng)中研究如何設(shè)計不同的控制策略使跟隨者能夠很好地跟蹤領(lǐng)導(dǎo)者。文獻(xiàn)[12]研究了異質(zhì)多智能體系統(tǒng)的分組一致性，推導(dǎo)出了異質(zhì)多智能體系統(tǒng)實現(xiàn)分組一致性的充分條件。文獻(xiàn)[13]研究了混合類型多智能體組成的異質(zhì)多智能體系統(tǒng)的組一致性問題，得出了通信延遲與分組一致性無關(guān)的結(jié)論。本文主要研究當(dāng)智能體系統(tǒng)異質(zhì)時，異質(zhì)性的強(qiáng)弱對于多智能體系統(tǒng)最終蜂擁狀態(tài)的影響。

1 蜂擁控制

1.1 預(yù)備知識

在二維平面上，假設(shè)存在n個智能體，全部視為質(zhì)點。第i個智能體的運動方程為：

(1)

其中:qi∈Rn為第i個智能體的位置；pi∈Rn為速度；ui∈Rn為加速度，也就是控制輸入。

對于智能體i，在任意時刻t，將它感知半徑內(nèi)的所有智能體的集合記為Ni(t)={j|||qi-qj||≤r2,j∈N且j≠i}，其中，||·||為歐幾里得范數(shù)，r為感知半徑，稱Ni(t)為智能體i的鄰居。把智能體i視為節(jié)點，將它與其他能感知到的節(jié)點用無向邊連接，則由系統(tǒng)內(nèi)所有節(jié)點和無向邊組成的網(wǎng)絡(luò)構(gòu)成了一個無向圖G(t)。其鄰接矩陣為A(G(t))=[aij(t)]，其中

(2)

冪律分布最早由Zipf發(fā)現(xiàn)，他發(fā)現(xiàn)英文單詞的出現(xiàn)頻率與其序號的常數(shù)次冪存在反比關(guān)系：

P(r)=r-α

(3)

本研究中，智能體的影響半徑服從冪律分布。

1.2 傳統(tǒng)蜂擁控制模型

1986年，Reynolds[9]提出了一種蜂擁控制模型，并提出了三條規(guī)則：分離、聚合、速度匹配。根據(jù)Reynolds提出的模型，Olfati-Saber[10]提出了如下控制輸入算法：

(4)

▽qiψα(|||qij-qγij||σ)

(5)

φα(z)=ρh(z/rα)·φ(z-dα)

(6)

控制輸入ui的具體形式為：

hi[c1(qγ-qi)+c2(pγ-pi)+uγ]

(7)

這里，hi可以用來描述智能體i是否擁有領(lǐng)導(dǎo)者的引導(dǎo)信息。當(dāng)hi=1時，智能體i為信息智能體，當(dāng)hi=0時，智能體為自由智能體。

人工勢函數(shù)ψα(z)滿足：① 當(dāng)||qij||σ→0時，ψα為最大值；② 當(dāng)||qij||σ趨近于某一期望值時，ψα為最小值；③ 當(dāng)||qij||σ≥||r||σ時，ψα恒為很小的正常數(shù)。人工勢函數(shù)ψα如圖1所示。

圖1 人工勢函數(shù)

1.3 影響半徑服從冪律分布的蜂擁控制算法

在Reynold和Olfati-Saber等提出的蜂擁控制算法中，ri表示的是智能體的感知半徑，即智能體i能夠感知到感知半徑ri內(nèi)的其他鄰居的位置信息和速度信息，影響自己的控制輸入。但是在智能體系統(tǒng)異質(zhì)時，感知半徑的概念無法表達(dá)智能體的影響能力，所以本文將ri重新定義為智能體i的影響半徑，即智能體i能夠?qū)⒆约旱奈恢眯畔⒑退俣刃畔鬟f給影響半徑ri內(nèi)的其他智能體。當(dāng)智能體系統(tǒng)均質(zhì)時，感知半徑和影響半徑的意義相同，但是當(dāng)智能體系統(tǒng)異質(zhì)時，感知半徑和影響半徑的不同會對結(jié)果產(chǎn)生不同的影響，所以要對控制輸入進(jìn)行改造。

當(dāng)智能體系統(tǒng)異質(zhì)時，智能體i是否能夠接收到智能體j的信息取決于智能體j的影響半徑，所以新的鄰居定義如下：

且j≠i}

新的鄰接矩陣定義如下：

(8)

當(dāng)智能體系統(tǒng)均質(zhì)時，鄰接矩陣是對稱陣；當(dāng)智能體系統(tǒng)異質(zhì)時，因為影響半徑不相同，所以鄰接矩陣不是對稱陣。

除了鄰居和鄰接矩陣，異質(zhì)網(wǎng)絡(luò)對于勢能函數(shù)也會產(chǎn)生影響。對于碰撞函數(shù)式(6)，因為影響半徑不同，所以自變量應(yīng)該替換為z/||rj||σ，而不是z/||r||σ。

最后，因為本文主要研究在異質(zhì)網(wǎng)絡(luò)下多智能體系統(tǒng)的自主演化行為，所以本文不研究帶有領(lǐng)導(dǎo)者的蜂擁控制輸入，因為領(lǐng)導(dǎo)者具有全局信息，所以無論初始分布如何，最終肯定能夠形成穩(wěn)定的蜂擁行為。在對鄰居、鄰接矩陣和碰撞函數(shù)進(jìn)行改造以后，新的控制輸入如下：

其中，c3為系數(shù)，主要影響智能體之間的分離聚合作用，c3=0.25。

其中，xmin為系數(shù)，用以保證ri>d。

當(dāng)冪律指數(shù)變化時，生成的智能體影響半徑分布也會發(fā)生變化。圖2是當(dāng)s=55時不同冪律指數(shù)對應(yīng)的影響半徑分布圖。

圖2 不同冪律指數(shù)下的影響半徑分布

2 仿真結(jié)果與分析

本研究模仿了50個智能體在二維平面中的運動情況。參數(shù)分別設(shè)置為：智能體初始速度為[-1,1]和[-1,1]，初始分布范圍為[0,55]和[0,55]，智能體最小影響半徑xmin=6，智能體間期望距離d=5，σ范數(shù)的參數(shù)ε=0.1，式(8)中參數(shù)h=0.9，φ(z)中a=1,b=2，控制輸入中c1=0.1,c2=0.9,c3=0.25，程序運行步數(shù)loop=300。為了更好地體現(xiàn)不同影響半徑下智能體之間的相互影響，本文不要求智能體的初始分布必須為初始連通。通過計算機(jī)數(shù)值仿真驗證當(dāng)冪律系數(shù)分別等于γ1=4,γ2=5,γ3=7,γ4=10,γ5=50對智能體系統(tǒng)蜂擁狀態(tài)好壞和收斂速度的影響。

首先本文對γ1=4時的智能體系統(tǒng)進(jìn)行了數(shù)值仿真，研究系統(tǒng)隨程序運行時的演化過程。

圖3(a)是智能體的初始分布圖。從圖中可以看出智能體的速度是隨機(jī)分布的，網(wǎng)絡(luò)的連通性也不強(qiáng)，其中有3個影響半徑r>18的智能體，因為影響半徑較大的原因，所以它們對其他智能體的運動有較強(qiáng)的引導(dǎo)作用，它們可以充當(dāng)“中心智能體”的作用。當(dāng)t=50時，可以看出所有影響半徑較小的智能體都受到幾個影響半徑較大的智能體的影響，向中心智能體運動。當(dāng)t=100和t=150時，智能體已經(jīng)基本完成了Reynolds提出的三條規(guī)則中的分離聚合作用，開始按照同一方向開始運動。當(dāng)t=300時，所有智能體已經(jīng)形成了穩(wěn)定的α-晶格結(jié)構(gòu)，并且在幾個中心智能體的影響下按照同一方向進(jìn)行運動，形成了穩(wěn)定的蜂擁狀態(tài)。

通過對上圖的分析可知，當(dāng)冪律指數(shù)較小時，智能體系統(tǒng)中存在極少數(shù)影響半徑極大的智能體，它們可以充當(dāng)“中心智能體”甚至“領(lǐng)導(dǎo)者”的作用，它們的速度和位置會對其他影響半徑較小的智能體產(chǎn)生決定性的作用，最終蜂擁狀態(tài)的好壞取決于極少數(shù)中心智能體的初始分布狀態(tài)。

下面比較當(dāng)冪律指數(shù)分別取γ1=4,γ2=5,γ3=7,γ4=10,γ5=50時對智能體系統(tǒng)的影響，每種情況分別取10次實驗數(shù)據(jù)取平均值。本文采用最大簇系數(shù)S來判斷蜂擁狀態(tài)的好壞，S為智能體節(jié)點網(wǎng)絡(luò)中所有連通子圖中最大連通子圖的智能體個數(shù)與所有智能體個數(shù)的比值，0

從圖4可以看出，當(dāng)冪律指數(shù)較小時，智能體系統(tǒng)的初始最大簇系數(shù)比較大，這是因為系統(tǒng)中存在少數(shù)中心智能體，以這些中心智能體為節(jié)點更容易形成連通網(wǎng)絡(luò)；相反當(dāng)冪律指數(shù)較小時，所有智能體的影響半徑都比較小，所以很難形成節(jié)點很多的連通網(wǎng)絡(luò)。

隨著程序運行，可以看出冪律指數(shù)較小的最大簇系數(shù)增長更快，這是因為中心智能體影響半徑更大，更容易影響其他智能體。并且可以明顯看出，冪律指數(shù)不同會對最后的最大簇系數(shù)產(chǎn)生很大的影響：當(dāng)γ1=4,γ2=5,γ3=7,γ4=10,γ5=50時，s1=0.97,s2=0.844,s3=0.742,s4=0.624,s5=0.364。當(dāng)冪律指數(shù)較小時，最大簇系數(shù)很大，收斂時間也更短，系統(tǒng)的蜂擁狀態(tài)也更好；當(dāng)冪律指數(shù)較大時，最大簇系數(shù)很小，收斂時間更長。這說明當(dāng)系統(tǒng)的異質(zhì)性很強(qiáng)時，多數(shù)智能體在極少部分中心智能體的帶領(lǐng)下，更容易形成整體的蜂擁狀態(tài)；隨著異質(zhì)性逐漸減弱，智能體變得更加均質(zhì)，在運動過程中容易受到部分影響半徑較大的智能體的影響，形成“分塊”或者“分離”現(xiàn)象，如圖5所示。從圖5能夠看出，隨著異質(zhì)性減弱，影響半徑越來越小，導(dǎo)致智能體的分離現(xiàn)象也更加明顯。

根據(jù)前面的數(shù)值仿真可知，當(dāng)系統(tǒng)異質(zhì)性很強(qiáng)時，智能體的運動主要受到極少部分中心智能體的影響，最終蜂擁狀態(tài)的好壞取決于中心智能體的運動狀態(tài)。接下來本文重點研究，在系統(tǒng)的異質(zhì)性很強(qiáng)的條件下，中心智能體的運動狀態(tài)對智能體系統(tǒng)運動的影響，以及能否通過對極少部分的中心智能體施加控制，達(dá)到對整個智能體系統(tǒng)進(jìn)行控制，最終形成統(tǒng)一的蜂擁運動。為了保證系統(tǒng)的異質(zhì)性，接下來研究的內(nèi)容中冪律指數(shù)γ=4。

為了對智能體進(jìn)行分類，本文設(shè)定影響半徑r>20的智能體稱為控制智能體，影響半徑6≤r≤20的智能體稱為一般智能體。在運動過程中，設(shè)控制智能體保持勻速直線運動，則對于控制智能體來說ui=0，對所有智能體來說，控制輸入為：

圖5 不同冪律指數(shù)對應(yīng)的分離現(xiàn)象

圖6 n1=3時不同時刻智能體分布

通過上面分析可知，在異質(zhì)性較強(qiáng)的智能體系統(tǒng)中，極少數(shù)影響半徑很大的控制智能體的運動狀態(tài)可以影響其他所有智能體的運動，當(dāng)這些控制智能體的運動方向不相同時，會對其影響半徑之內(nèi)的其他智能體產(chǎn)生影響，最終會形成穩(wěn)定的分塊式的蜂擁運動，并且影響半徑越大，形成的分塊也越大。接下來本文研究能否通過控制極少數(shù)中心智能體，讓它們按照同一方向運動，進(jìn)而達(dá)到控制所有智能體的運動，最終形成穩(wěn)定的蜂擁運動。設(shè)所有影響半徑r>20的控制智能體的速度都為(1,1)，控制輸入ui=0，則所有控制智能體都按照同一速度進(jìn)行勻速直線運動。

從圖8可以看出，t=0時，智能體的初始分布比較散亂；t=100時，所有智能體都能達(dá)到同一運動方向；t=300時，能夠形成比較緊湊的α-晶體結(jié)構(gòu)。這樣就說明了在異質(zhì)性較強(qiáng)的智能體系統(tǒng)中，即使初始分布隨機(jī)性很強(qiáng)，但是通過控制極少數(shù)控制智能體按照同一方向運動，就可以牽制絕大多數(shù)其他智能體，最終形成穩(wěn)定的蜂擁運動。

圖7 n1=2,4時形成的分塊式的蜂擁運動

圖8 同一方向運動時的智能體蜂擁運動圖

3 結(jié)論

1) 本研究提出了基于異質(zhì)網(wǎng)絡(luò)的蜂擁控制算法。

2) 對勢能函數(shù)進(jìn)行了改造，并且通過數(shù)值仿真證明了異質(zhì)性較強(qiáng)的智能體系統(tǒng)更容易達(dá)到蜂擁狀態(tài)，并且證明了可以通過控制極少數(shù)影響半徑較大的智能體控制整個智能體系統(tǒng)，使其達(dá)到預(yù)定的蜂擁狀態(tài)。