部分具有引導信息的多領導者蜂擁控制算法?

叢 凱 張金春 盧 翰

（海軍航空大學 煙臺 264001）

1 引言

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

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

針對現有工作的不足，總結上述問題的原因，本文在不改變勢能函數的條件下，提出了一種改進的部分具有引導信息的多領導者蜂擁控制算法，并且通過理論分析證明了算法的穩定性，最后通過仿真實驗驗證了算法的有效性。

2 問題描述

2.1 預備知識

在n維平面上，假設存在N個智能體，全部視為質點。將具有領導者信息的智能體稱為信息智能體，將不具有領導者信息的智能體稱為自由智能體。第i個智能體的運動方程為

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

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

圖G(t)的Laplacian矩陣為

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

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

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

當系統內所有的智能體的速度均勻的指向不同的方向，H=0；H越大，表明速度情況越相同；當所有智能體的速度方向相同時，H=1。

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

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

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

控制輸入ui的具體形式為

這里，hi可以用來描述智能體i是否擁有領導者的引導信息。當hi=1時，智能體i為信息智能體，當hi=0時，智能體為自由智能體。

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

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

圖1 人工勢函數

所有智能體總能量分為兩部分，一是所有智能體間的總勢能，包括智能體間的勢能和智能體與領導者間的勢能，二是智能體與領導者間的相對動能，具體形式為

2.3 少數信息智能體的蜂擁控制模型

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

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

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

圖2 智能體相互作用關系圖

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

圖3 連通分支圖

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

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

其中，c3，c4為系數。

3 理論證明

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

1）從t=0開始，任意一個信息智能體與領導者的距離小于

2）所有信息智能體的速度都會趨近于自身所追蹤的領導者的速度

這兩條結論就可以保證Rerynolds提出的分離、聚合和速度匹配三條規則。下面對結論進行證明：

首先證明結論（1），它是關于分離和聚合規則的結論。記信息智能體i與它所追蹤的領導者的位置和速度差值為 Δqi=qi-qγi和 Δpi=pi-pγi，則

所以

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

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

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

其余兩項對時間t的導數為

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

i數Q(q，p)得：

4 仿真結果與分析

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

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

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

圖4 傳統算法運行結果

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

圖5 改進算法智能體分布和速度跟隨情況

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

圖6 15次仿真統計對比圖

圖7 極化程度對比圖

5 結語

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