部分具有引導(dǎo)信息的多領(lǐng)導(dǎo)者蜂擁控制算法?

叢 凱 張金春 盧 翰

（海軍航空大學(xué) 煙臺 264001）

1 引言

蜂擁行為是指大量的個體利用有限的環(huán)境信息和簡單的幾條規(guī)則，組織形成的群體運動。自然界中就有很多蜂擁行為，比如蜂群、鳥群和魚群［1～2］等。幾十年以來，蜂擁行為已經(jīng)引起生物、物理和計算機等各領(lǐng)域?qū)W者的研究興趣［3～9］，其中代表性的是 Reynolds和 Olfati-Saber［10～11］。他們提出的模型得到了廣泛的認(rèn)可。

現(xiàn)有的研究中［12～16］，大部分蜂擁控制算法都是基于跟蹤單個領(lǐng)導(dǎo)者。Reynolds［10］提出的蜂擁控制算法就是基于跟蹤的單一的領(lǐng)導(dǎo)者，并且假設(shè)所有智能體都具有領(lǐng)導(dǎo)者的位置信息和速度信息，通過理論分析證明了最終能夠形成穩(wěn)定的蜂擁行為。在實際生活中很多情況下同時具有多個領(lǐng)導(dǎo)者，比如蜂群在尋找花粉的過程中根據(jù)目的地不同形成多個小蜂群，蟻群為了尋找食物分成不同的行進(jìn)路線等，所以具有多個領(lǐng)導(dǎo)者的蜂擁控制算法具有很強的實際意義。蘇厚勝［17］提出了一種基于多個領(lǐng)導(dǎo)者的蜂擁控制算法，在假設(shè)所有智能體都擁有自己需要追蹤的領(lǐng)導(dǎo)者的位置信息和速度信息的條件下，通過理論證明了能形成結(jié)構(gòu)穩(wěn)定的蜂擁行為，并且通過仿真實驗驗證了算法的準(zhǔn)確性。在自然界中，很多情況下只有少數(shù)個體具有領(lǐng)導(dǎo)者信息，比如最典型的“毛毛蟲效應(yīng)”，以及大雁遷徙中的“人字形”（群體末尾的大雁是根據(jù)其最近鄰前方的大雁行動而不是最前方大雁）。在人類生產(chǎn)生活中，每個智能體都有領(lǐng)導(dǎo)者信息就意味著智能體具有很大的探測范圍，這對生產(chǎn)成本和技術(shù)提出了很高的要求。因此設(shè)計一種在多個領(lǐng)導(dǎo)者情況下只需要少數(shù)個體具有領(lǐng)導(dǎo)者信息就能形成穩(wěn)定蜂擁行為的算法具有很強的實際意義。在已有的研究中，文獻(xiàn)［18］設(shè)計了一種改進(jìn)的蜂擁控制算法，并將其應(yīng)用到無線傳感器網(wǎng)絡(luò)中，能夠保證在少數(shù)智能體具有領(lǐng)導(dǎo)者信息的情況下仍然具有良好的跟蹤效果。但是為了保持蜂擁網(wǎng)絡(luò)的連通性設(shè)計了無界的勢能函數(shù)，難以應(yīng)用到實際生活中。文獻(xiàn)［19～20］在蜂擁控制算法中加入了導(dǎo)航項和阻尼項，以實現(xiàn)領(lǐng)導(dǎo)者、具有引導(dǎo)信息的智能體和自由智能體之間的平衡，但是并沒有對算法進(jìn)行穩(wěn)定性分析和仿真驗證。文獻(xiàn)［21］提出了內(nèi)聚項，即自由智能體能夠通過感知其探測范圍內(nèi)的其他智能體的位置和速度，并求得平均位置和平均速度作為內(nèi)聚項，加強自由智能體對網(wǎng)絡(luò)的追蹤能力。

針對現(xiàn)有工作的不足，總結(jié)上述問題的原因，本文在不改變勢能函數(shù)的條件下，提出了一種改進(jìn)的部分具有引導(dǎo)信息的多領(lǐng)導(dǎo)者蜂擁控制算法，并且通過理論分析證明了算法的穩(wěn)定性，最后通過仿真實驗驗證了算法的有效性。

2 問題描述

2.1 預(yù)備知識

在n維平面上，假設(shè)存在N個智能體，全部視為質(zhì)點。將具有領(lǐng)導(dǎo)者信息的智能體稱為信息智能體，將不具有領(lǐng)導(dǎo)者信息的智能體稱為自由智能體。第i個智能體的運動方程為

其中，qi∈Rn為第i個智能體的位置，pi∈Rn為速度，ui∈Rn為加速度，也就是控制輸入。假設(shè)存在M個領(lǐng)導(dǎo)者，其運動方程為

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

圖G(t)的Laplacian矩陣為

其中，Δ(A(G(t))稱為度矩陣，對角元素為此節(jié)點的度，其余為0。由此定義可知L(G(t))是一個半正定矩陣。

拉薩爾不變性原理［22］：對于一個動態(tài)連續(xù)系統(tǒng)x?=f(x)，若連續(xù)函數(shù)V(x)存在一階連續(xù)偏導(dǎo)數(shù)，且滿足：1）?l∈R+，使集合有界 ；2） ?x∈Ωc，有V(·x)≤0；定義集合M是S中的最大不變集，則?x0∈Ωc，當(dāng)t→∞ 時，x(t)→M。

為了描述智能體在跟蹤領(lǐng)導(dǎo)者的過程中速度的一致性，引入極化程度［23］H，定義為

當(dāng)系統(tǒng)內(nèi)所有的智能體的速度均勻的指向不同的方向，H=0；H越大，表明速度情況越相同；當(dāng)所有智能體的速度方向相同時，H=1。

2.2 Reynolds多智能體蜂擁控制模型

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

的具體形式為的具體形式為其中，的具體形式為

控制輸入ui的具體形式為

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

對第i個智能體來說，通過人工勢函數(shù)，可以得到它的總勢能為

人工勢函數(shù)ψα(z)滿足：1）當(dāng)時，ψα為最大值；2）當(dāng)趨近于某一期望值時，ψα為最小值；3）當(dāng)時，ψα恒為很小的正常數(shù)。人工勢函數(shù)ψα如圖1所示。

圖1 人工勢函數(shù)

所有智能體總能量分為兩部分，一是所有智能體間的總勢能，包括智能體間的勢能和智能體與領(lǐng)導(dǎo)者間的勢能，二是智能體與領(lǐng)導(dǎo)者間的相對動能，具體形式為

2.3 少數(shù)信息智能體的蜂擁控制模型

蘇厚勝［17］提出了當(dāng)所有智能體都為信息智能體時的蜂擁控制算法，并且通過理論分析證明當(dāng)所有智能體都具有領(lǐng)導(dǎo)者的信息時，最終所有智能體都能跟蹤到領(lǐng)導(dǎo)者并且形成穩(wěn)定的蜂擁行為。但是當(dāng)智能體群體中存在自由智能體時，由于自由智能體在運動過程中沒有領(lǐng)導(dǎo)者的指引信息，并且同時受到不同的信息智能體以及其他自由智能體的作用，所以對于自由智能體來說最終能否跟蹤到領(lǐng)導(dǎo)者以及跟蹤到哪個領(lǐng)導(dǎo)者很難確定下來。

Couzin［24］的研究指出，在只有少數(shù)個體具有領(lǐng)導(dǎo)者信息的蜂擁算法中，蜂擁結(jié)果的好壞取決于信息智能體對其他智能體的影響，即信息智能體與領(lǐng)導(dǎo)者的作用以及信息智能體與自由智能體的作用的平衡，如圖2。因為具有領(lǐng)導(dǎo)者信息的智能體最終肯定能夠跟蹤到領(lǐng)導(dǎo)者，所以可以通過加強信息智能體與自由智能體的作用或者減弱信息智能體與領(lǐng)導(dǎo)者的作用這兩種方法使自由智能體能夠更好地跟蹤目標(biāo)。

本文提出的蜂擁控制算法中，首先對自由智能體進(jìn)行分類，使自由智能體有明確的跟蹤目標(biāo)；然后加入基于連通分支的內(nèi)聚項，通過加強信息智能體與自由智能體的作用達(dá)到更好的跟蹤效果。

圖2 智能體相互作用關(guān)系圖

本文研究具有兩個領(lǐng)導(dǎo)者的多智能體系統(tǒng)，即M=2，兩個領(lǐng)導(dǎo)者記為α和β。假設(shè)N個智能體中各有m個智能體分別跟蹤兩個領(lǐng)導(dǎo)者，都為信息智能體，其余智能體為自由智能體跟蹤領(lǐng)導(dǎo)者α，稱為第一類信息智能體跟蹤領(lǐng)導(dǎo)者β，稱為第二類信息智能體為自由智能體。為了對智能體進(jìn)行分類，本文采取優(yōu)先準(zhǔn)則，自由智能體根據(jù)運動過程中首先遇到的信息智能體的類型確定跟蹤目標(biāo)，具體實現(xiàn)方法為：對于自由智能體j，當(dāng)智能體沒有跟蹤目標(biāo)時，鄰接矩陣A中a(i，j)=0，i=1，2，…，m，m+1，m+2，…，2m；當(dāng)自由智能體j感知范圍內(nèi)出現(xiàn)其他信息智能體時，a(i，j)≠0。因為感知范圍內(nèi)同時出現(xiàn)兩類信息智能體的概率可以忽略不計，所以當(dāng)鄰接矩陣中元素1出現(xiàn)在前m列時，可以判斷自由智能體j首先遇到第一類信息智能體，確定j跟蹤領(lǐng)導(dǎo)者α，將自由智能體j稱為第一類自由智能體；當(dāng)鄰接矩陣中元素1出現(xiàn)在后m列時，可以判斷自由智能體j首先遇到第二類信息智能體，確定j跟蹤領(lǐng)導(dǎo)者β，將自由智能體j稱為第二類自由智能體。這樣就對自由智能體進(jìn)行了分類，明確了自由智能體的跟蹤目標(biāo)。

圖3 連通分支圖

接下來考慮如何加強自由智能體與信息智能體的相互作用。首先建立無向圖G(t)的連通分支。目前對圖的遍歷搜索算法中比較成熟的算法有廣度優(yōu)先搜索算法（BFS算法）和深度優(yōu)先搜索算法（DFS算法），本文使用BFS算法建立無向圖的連通分支。假設(shè)在某時刻t自由智能體O在運動過程中跟蹤到某第一類信息智能體A，如圖3所示。圖3表示的是無向圖G(t)中的一個連通分支，圖中智能體之間的連線表示智能體之間的距離小于智能體的感知范圍，即智能體能夠相互感知到。在這種情況下，智能體之間能夠相互通信，智能體i能將自己的位置信息和速度信息(pi，qi) 或者自己接收到的其他智能體的位置信息和速度信息(pj，qj)傳遞到與之相鄰的其他智能體。基于連通分支的網(wǎng)絡(luò)連通性，任意智能體都能接收到其他智能體的位置信息和速度信息。因為自由智能體O優(yōu)先遇到第一類信息智能體A，所以忽略掉第二類信息智能體和第二類自由智能體的影響，其運動受到連通分支中其他第一類信息智能體和第一類自由智能體的作用。連通分支中第一類信息智能體的集合為Niα(t)，第一類自由智能體的集合為Ni(t)，則位置質(zhì)心和速度質(zhì)心為

將qˉi和pˉi作為加強自由智能體O與信息智能體相互作用的內(nèi)聚項就可以得到作為自由智能體的控制輸入：

其中，c3，c4為系數(shù)。

3 理論證明

對于有2m個信息智能體的多智能體系統(tǒng)，它們的控制輸入滿足式（9）和式（13），假設(shè)系統(tǒng)的初始能量為有限值Q0，那么就有如下結(jié)論：

1）從t=0開始，任意一個信息智能體與領(lǐng)導(dǎo)者的距離小于

2）所有信息智能體的速度都會趨近于自身所追蹤的領(lǐng)導(dǎo)者的速度

這兩條結(jié)論就可以保證Rerynolds提出的分離、聚合和速度匹配三條規(guī)則。下面對結(jié)論進(jìn)行證明：

首先證明結(jié)論（1），它是關(guān)于分離和聚合規(guī)則的結(jié)論。記信息智能體i與它所追蹤的領(lǐng)導(dǎo)者的位置和速度差值為 Δqi=qi-qγi和 Δpi=pi-pγi，則

所以

同理，pij-pγij=Δpij。

因此，控制輸入ui，勢能函數(shù)V(q)和能量函數(shù)Q(q，p)都可以改寫為

對于能量函數(shù)Q(q，p)，其中V(qi)對時間t的導(dǎo)數(shù)為

其余兩項對時間t的導(dǎo)數(shù)為

將式（15）中的u和式（16）、（17）代入能量函

i數(shù)Q(q，p)得：

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

本文模仿了15個智能體在二維平面中的運動情況。其中，10個智能體為信息智能體，分成5個一組分別跟蹤兩個領(lǐng)導(dǎo)者，其余5個為自由智能體。參數(shù)分別設(shè)置為：智能體初始速度為[-1，1]和[-1，1]，初始分布范圍為 [0，50]和 [0，50]，智能體感知半徑r=6，智能體間期望距離d=5，σ范數(shù)的參 數(shù)ε=0.1，式（8）中 參 數(shù)h=0.9，?(z)中a=1，b=2 ，控 制 輸 入 中c1=0.1，c2=0.9，c3=c4=1，程序運行步數(shù)loop=500。

首先對傳統(tǒng)的蜂擁控制算法進(jìn)行仿真。圖4表示的是傳統(tǒng)算法的幾種運動狀況，圖中智能體之間的連線表示智能體之間能夠相互感知。從圖4中可以看出基本形成了蜂擁狀態(tài)，大多數(shù)的智能體能夠跟蹤到目標(biāo)并且形成穩(wěn)定的蜂擁運動，但是仍有少數(shù)智能體沒有跟蹤到目標(biāo)。隨著時間增加，這些智能體和目標(biāo)的距離會越來越大，最終無法跟蹤目標(biāo)。這些智能體丟失目標(biāo)的原因有兩個：一是這些智能體在運動過程中沒有被其他智能體感知到，沒有進(jìn)入其他智能體形成的連通分支網(wǎng)絡(luò)；二是這些智能體在運動過程中進(jìn)入了其他智能體形成的連通分支網(wǎng)絡(luò)，但是由于受到不同類型智能體的共同作用，導(dǎo)致運動受到多種影響導(dǎo)致最終沒有跟蹤到目標(biāo)。

接下來對本文提出的算法進(jìn)行仿真。圖5（a）表示的是智能體的初始分布情況，其初始分布采用隨機分布。圖5（b）表示的是程序運行500步之后的智能體分布情況，圖5（c）和（d）用來表示一般智能體與領(lǐng)導(dǎo)者的速度跟隨情況，曲線的數(shù)值為智能體的在x和y方向上的分速度與速度大小的比值。從圖5（b）中可以看出所有智能體都能跟蹤到目標(biāo)，沒有出現(xiàn)智能體丟失目標(biāo)的情況，圖5（c）和（d）的速度情況也可以反映出所有智能體的速度情況都和各自追蹤的領(lǐng)導(dǎo)者的速度一致。通過圖5與圖4的比較可以看出，相比傳統(tǒng)算法，加入基于連通分支的內(nèi)聚項之后，自由智能體與信息智能體的相互作用明顯得到了加強，有利于自由智能體更好的明確跟蹤目標(biāo)，其跟蹤能力也得到了提升。

圖4 傳統(tǒng)算法運行結(jié)果

為了對本文提出算法的有效性進(jìn)行進(jìn)一步驗證，本文分別對傳統(tǒng)算法和改進(jìn)算法進(jìn)行了15次數(shù)值仿真。根據(jù)上面的理論分析可知，所有信息智能體最終肯定能夠跟蹤到目標(biāo)。由于智能體初始分布的隨機性，所以即使對于改進(jìn)算法，仍然難以保證每次所有自由智能體都能跟蹤到目標(biāo)。所以在每次仿真中，不考慮是否所有智能體都跟蹤到目標(biāo)，只記錄能夠跟蹤到領(lǐng)導(dǎo)者與無法跟蹤到領(lǐng)導(dǎo)者的智能體的數(shù)量，得到統(tǒng)計數(shù)據(jù)如圖6。通過數(shù)據(jù)可知，使用改進(jìn)算法后，能夠跟蹤到目標(biāo)的自由智能體的數(shù)目明顯上升，跟蹤效率得到了顯著提升。

圖5 改進(jìn)算法智能體分布和速度跟隨情況

為了對智能體的速度跟隨情況做進(jìn)一步分析，本文選取了程序運行300步后的速度數(shù)據(jù)做極化程度對比，如圖7，改進(jìn)算法的極化程度穩(wěn)定值H1=0.997，傳統(tǒng)算法的穩(wěn)定值H2=0.853。從圖中可以看出，改進(jìn)算法的極化程度增長速度較快，并且很快趨近于比較高的穩(wěn)定值。相比而言，傳統(tǒng)算法增長速度較慢，并且穩(wěn)定值也比較低。

圖6 15次仿真統(tǒng)計對比圖

圖7 極化程度對比圖

5 結(jié)語

針對多領(lǐng)導(dǎo)者蜂擁控制算法中不具有目標(biāo)引導(dǎo)信息的智能體在跟蹤過程中出現(xiàn)的目標(biāo)丟失的問題，本文提出了基于連通分支的多領(lǐng)導(dǎo)者蜂擁控制算法，在控制輸入中加入內(nèi)聚項提高智能體的跟蹤能力。通過理論分析證明了智能體在速度和距離上能夠保持一致，并且通過數(shù)值仿真對算法進(jìn)行了驗證，本文算法能夠使智能體明確跟蹤目標(biāo)，并且提高智能體的跟蹤能力。通過仿真驗證可知：基于連通分支的多領(lǐng)導(dǎo)者蜂擁控制算法能夠更好地實現(xiàn)多智能體系統(tǒng)的蜂擁控制和目標(biāo)跟蹤。