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

叢 凱 張金春 盧 翰

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

1 引言

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

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

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

2 問題描述

2.1 預(yù)備知識(shí)

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

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

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

圖G(t)的Laplacian矩陣為

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

拉薩爾不變性原理［22］：對(duì)于一個(gè)動(dòng)態(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→∞ 時(shí)，x(t)→M。

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

當(dāng)系統(tǒng)內(nèi)所有的智能體的速度均勻的指向不同的方向，H=0；H越大，表明速度情況越相同；當(dāng)所有智能體的速度方向相同時(shí)，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時(shí)，智能體i為信息智能體，當(dāng)hi=0時(shí)，智能體為自由智能體。

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

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

圖1 人工勢(shì)函數(shù)

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

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

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

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

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

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

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

圖3 連通分支圖

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

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

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

3 理論證明

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

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

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

這兩條結(jié)論就可以保證Rerynolds提出的分離、聚合和速度匹配三條規(guī)則。下面對(duì)結(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ì)能函數(shù)V(q)和能量函數(shù)Q(q，p)都可以改寫為

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

其余兩項(xiàng)對(duì)時(shí)間t的導(dǎo)數(shù)為

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

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

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

本文模仿了15個(gè)智能體在二維平面中的運(yùn)動(dòng)情況。其中，10個(gè)智能體為信息智能體，分成5個(gè)一組分別跟蹤兩個(gè)領(lǐng)導(dǎo)者，其余5個(gè)為自由智能體。參數(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，程序運(yùn)行步數(shù)loop=500。

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

接下來對(duì)本文提出的算法進(jìn)行仿真。圖5（a）表示的是智能體的初始分布情況，其初始分布采用隨機(jī)分布。圖5（b）表示的是程序運(yùn)行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)聚項(xiàng)之后，自由智能體與信息智能體的相互作用明顯得到了加強(qiáng)，有利于自由智能體更好的明確跟蹤目標(biāo)，其跟蹤能力也得到了提升。

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

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

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

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

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

圖7 極化程度對(duì)比圖

5 結(jié)語

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