多目標跟蹤蜂擁控制算法研究與仿真?

張金春1王帥磊曹彪3楊蕓

多目標跟蹤蜂擁控制算法研究與仿真?

張金春1王帥磊2曹彪3楊蕓2

（1.海軍航空工程學院基礎部煙臺264001）（2.海軍航空工程學院研究生管理大隊煙臺264001）（3.海軍航空工程學院基礎實驗部煙臺264001）

針對蜂擁控制算法在多目標跟蹤問題中的應用，提出了多目標跟蹤蜂擁控制算法。假設智能體不確定具有目標信息，通過Lyapunov穩定性理論，分析了使系統穩定的條件，給出了穩定狀態的形式。并證明了如果智能體被預先指定了跟蹤的目標，則每個群體達到蜂擁，并且不發生碰撞。對不同的網絡初始連通性和兩種目標運動模式分別作了仿真，證明了算法的有效性。

多目標；跟蹤；蜂擁控制；Lyapunov穩定性；連通性；運動

Class NumberTP273

1 引言

蜂擁控制來源于對自然界生物群體的運動行為的觀察和抽象，自提出［1～2］以來，引起了許多領域的研究人員的興趣，并在多個方面做了大量研究，主要包括機器人［3～6］、移動傳感器網絡［7～8］以及控制算法［9～10］等方面。

在利用蜂擁控制算法進行多目標跟蹤的研究中，鐘午［10］針對傳統算法中不利于系統收斂的局部作用力引入了排斥勢能函數，并提出了新的多領導者蜂擁算法；羅小元［11］對跟蹤不同目標的智能體分別建立了勢場函數，實現對多目標的跟蹤；Luo［12］給每個目標設置了可接受的智能體數量，并提出一種根據智能體與目標的距離來決定如何跟隨多目標的算法，算法中包含了與距離相關的概率項；王海［13］提出以局部自適應追蹤為基礎的牽制算法，由少數信息個體帶動鄰居跟蹤多個目標；ZHANG［14］在僅具有位置信息的情況下，將動態的復雜邊界作為多個目標，利用智能體對其進行跟蹤，實現對動態邊界的實時監視。

已有研究中，對于智能體網絡的連通性有不同的假設，并且智能體對于目標的信息獲取方式有所區別，但缺乏系統的理論分析，關于目標的運動模式對智能體形成蜂擁的影響的研究也較少。本文在假設智能體預先不一定具有目標信息的基礎上，提出了多目標跟蹤蜂擁控制算法，給出了系統穩定的條件，并通過Lyapunov穩定性理論，系統地分析了算法的穩定性。針對不同的網絡連通性和不同的目標運動模式，通過仿真驗證了有效性。

2 蜂擁控制

2.1問題描述

在n維空間，考慮N個移動智能體的運動，將每個智能體視為質點。第i個智能體的位置為qi∈Rn，速度為pi∈Rn，其運動方程為

其中ui∈Rn為第i個智能體的控制輸入項。

在任意時刻t，以智能體i所在位置為中心，感知半徑r為鄰域的半徑，則鄰域內所有其他智能體為i的鄰居，記作

其中‖·‖為Euclid范數。

將智能體i視作網絡的節點，智能體i與其鄰居由無向邊連接，系統內所有節點和連邊構成的網絡用無向圖G(t)表示，對應的鄰接矩陣為A(G(t))=[aij(t)]，其中

圖G(t)的Laplacian矩陣為L(G(t))=[lij(t)]，其中

由定義可知，L(G(t))為半正定矩陣，簡記為L。

假設系統中有M個目標，所有目標的運動方程都為：

其中q∈Rn和p∈Rn分別為目標的位置向量與速度向量。

2.2控制算法

按照Reynolds［1］提出的三條規則，智能體的運動要滿足：1）分離：與鄰域內其他智能體避免碰撞；2）聚合：與其他智能體保持緊湊；3）速度匹配：與其他智能體保持速度一致。根據Olfati-Saber提出的蜂擁控制算法［2］，智能體的控制輸入為

其中，當智能體具有目標信息時，hi=1，否則hi=0，qγi為智能體i所要跟蹤的目標的位置向量，pγi為目標的速度向量，uγi

為目標的加速度向量，下標γi表示該目標被智能體i跟蹤。

本文中，如果智能體與目標的距離小于感知半徑，則該智能體具有目標信息；如果智能體與目標的距離大于感知半徑，但與目標之間有一條連通路徑，則該智能體仍能通過其他智能體獲得目標信息。因此在運動過程中，當‖‖qij≤r時，智能體i和j之間僅存在兩種情況：1）hi=hj=0；2）hi=hj=1。因為‖‖qij≤r時，i和j之間存在通信，只要其中一個具有目標信息，不考慮通信延遲，則另一個也能夠獲取目標信息。因此，相鄰的兩個智能體只能同時具有或者同時不具有目標信息。推廣到智能體組成的連通網絡，如果其中至少存在一個直接型智能體，則整個網絡中的所有智能體都能具有目標信息，即h1=h2=…=hN=1；否則h1=h2=…=hN=0，任意一個智能體不具有目標的信息，智能體只依靠相互之間的影響形成群集運動。

系統的總能量包括智能體之間的勢能，智能體與目標之間的相對勢能和相對動能，可以寫作

因此，Q是一個正半定方程。在初始時刻t=0，假設系統能量Q(0)的值是有界的。

3算法分析

對于由智能體組成的系統以及多個目標，根據運動方程式（1）和式（5），控制輸入式（7）和系統能量函數式（8），可以得出如下結論：

1）智能體與所要跟蹤的目標的距離是有界的；

2）智能體的速度能夠收斂到所要跟蹤的目標的速度；

3）如果初始能量Q(0)＜(κ+1) e，其中e=minΨα()‖‖qij，則至多會有κ對智能體發生碰撞，當κ=0時，任何兩個智能體之間不會發生碰撞；

證明：

在時間區間[tk-1,tk)內，對系統能量求導得

其中，H=diag(h1,h2,…,hN)。由于存在多個目標，對上式作如下處理。對任意時刻t，存在正交變換矩陣K∈RN×N，使矩陣L+c2H轉換為分塊矩陣，即其中Li為跟蹤第i個目標的所有智能體組成的網絡的Laplacian矩陣，Lm+1為不跟蹤任何目標的智能體組成的網絡的Laplacian矩陣，Hi為相應的由系數hi組成的對角矩陣。又令

則有

結合式（10），可以得到

對于系統能量Q有

其中d∈(0,r)。根據人工勢函數的定義，新產生連邊的能量值是有界的，因此Qmax也是有界的。對系統來說，僅存在有限個時刻，使得mt1+mt2+…+mtk≤M，即網絡內的連邊不會無限增加。

由式（9）和（11）可知，對hi=1有并有對hi=0，當且僅當=qi時滿足集合：

是正不變緊集。根據拉薩爾不變性，所有始于Ω的解都會趨于最大不變集：當=0可知=0，即p=0，即對hi=1有 pi-pγi=0，對hi=0有pi=0。因此具有目標信息的智能體的速度會收斂到目標的速度，并且所有跟隨相同目標的智能體的速度都會收斂到相同目標的速度；穩定狀態時不具有目標信息的智能體保持靜止。結論1和2證畢。

由式（17）可知，Q()t≤Qmax。如果有κ對智能體發生碰撞，則至少有κ+1個智能體發生了碰撞。根據人工勢函數的定義，當兩個智能體將要發生碰撞時，有因此有與假設矛盾，因此至多有κ對智能體之間能夠發生碰撞。當κ=0時，任意兩個智能體不會發生碰撞。

4仿真驗證

通過證明可知，當h1=h2=…=hN=1時，所有的智能體都能夠跟蹤到目標。下面以此進行仿真驗證。

4.1參數及條件

在二維平面上，考慮由50個智能體和3個目標組成的系統，指定10個智能體跟蹤目標1，20個智能體跟蹤目標2以及20個智能體跟蹤目標3。初始狀態下，智能體和目標的位置隨機分布在[0,70]×[0,70]的區域內，智能體的速度隨機分布在[-1,1]×[-1,1]的區間內隨機選定，目標的速度在[-5,5]×[-5,5]的區間內隨機選定。智能體的感知半徑為r=6，智能體之間的期望距離為d= 5。σ范數中參數ε=0.1；定義ρh(z)中h=0.9；?(z)中a=1，b=2；參數c1=0.1，c2=0.2。對智能體網絡初始連通和非連通的情況都進行了仿真，并在兩種情況下分別比較了目標作勻速運動和變速運動的情況。

4.2智能體網絡初始連通

在初始時刻，智能體組成了連通的網絡，3個目標的位置隨機選定。圖1中箭頭的方向和長度表示速度的方向和大小。

目標在運動方程的作用下分別作勻速運動和變速運動時，智能體都能準確跟蹤上相應的目標，形成一致的運動軌跡，最終分成了3個群體。按照預設的數量，10個智能體跟蹤上了目標1，20個智能體跟蹤上了目標2，20個智能體跟蹤上了目標3，達到了預期目的。

圖1智能體網絡初始連通

圖2目標與智能體的運動軌跡

圖3（a）和（b）為目標勻速運動時，智能體速度在X和Y方向上的收斂情況。圖3（c）和（d）為智能體變速運動時，智能體速度在X和Y方向上的收斂情況?？梢钥闯觯涍^一段時間的變化，每個智能體的速度都收斂到了相應目標的速度，并最終與目標速度保持一致。

4.3智能體網絡初始非連通

在非連通條件下，智能體網絡在初始狀態的連通性較差，僅有少數智能體之間存在連接。

目標在運動方程的作用下分別作勻速運動和變速運動。盡管智能體網絡在初始時刻的連通性較差，但智能體仍然能準確跟蹤上相應的目標，形成一致的運動軌跡，并最終分成3個群體。按照預設的數量，10個智能體跟蹤上了目標1，20個智能體跟蹤上了目標2，20個智能體跟蹤上了目標3，達到了預期目的。

圖3 智能體速度收斂情況

圖4 智能體網絡初始非連通

圖5目標與智能體的運動軌跡

圖6 （a）和（b）圖為目標作勻速運動時，智能體速度在X和Y方向上的收斂情況。圖6（c）和（d）圖為目標作變速運動時，智能體速度在X和Y方向上的收斂情況?？梢钥闯?，智能體的速度仍然能夠收斂到目標的速度，并最終與目標保持一致。

5 結語

本文提出了多目標跟蹤蜂擁控制算法，理論上證明了該算法能夠保證智能體準確跟蹤上預設目標，跟蹤相同目標的智能體速度能夠達到一致，并形成穩定的群體運動。在網絡初始連通和非連通條件下，分別比較了目標作勻速運動和變速運動的情況，仿真結果驗證了算法的有效性。

圖6 智能體速度收斂情況

［1］Reynolds C W.Flocks，Herds and Schools：A Distributed Behavioral Model［C］//ACM SIGGRAPH computer graph?ics.ACM，1987，21（4）：25-34.

［2］Olfati-Saber R.Flocking for Multi-Agent Dynamic Sys?tems：Algorithms and Theory［J］.Automatic Control IEEE Transactions on，2006，51（3）：401-420.

［3］Jia Y，Wang L.Experimental Implementation of Distribut?ed Flocking Algorithm for Multiple Robotic Fish［J］.Con?trol Engineering Practice，2014，30：1-11.

［4］Vásárhelyi G，Virágh C，Somorjai G，et al.Outdoor Flock?ing and Formation Flight with Autonomous Aerial Robots［C］//2014 IEEE/RSJ International Conference on Intelli?gent Robots and Systems.IEEE，2014：3866-3873.

［5］陳世明，聶森，謝競，等.非完整移動機器人群體的優化蜂擁控制［J］.控制與決策，2012，27（12）：1839-1843.

CHEN Shiming，NIE Sen，XIE Jing，et al.Optimal Flock?ing Control of Nonholonomic Mobile Robot Swarm［J］. Control and Decision，2012，27（12）：1839-1843.

［6］王祥科，李迅，鄭志強.多智能體系統編隊控制相關問題研究綜述［J］.控制與決策，2013，28（11）：1601-1613.

WANG Xiangke，LI Xun，ZHENG Zhiqiang.Survey of De?velopments on Multi-agent Formation Control Related Problems［J］.Control and Decision，2013，28（11）：1601-1613.

［7］La H M，Sheng W.Adaptive flocking control for dynamic target tracking in mobile sensor networks［C］//2009 IEEE/ RSJ International Conference on Intelligent Robots and Systems.IEEE，2009：4843-4848.

［8］婁柯，崔寶同，李紋.基于蜂擁控制的移動傳感器網絡目標跟蹤算法［J］.控制與決策，2013，28（11）：1637-1642，1649.

LOU Ke，CUI Baotong，LI Wen.Target Tracking Algo?rithm of Mobile Sensor Networks Based on Flocking Con?trol［J］.Control and Decision，2013，28（11）：1637-1642，1649.

［9］Gazi V，Passino K M.A class of attractions/repulsion func?tions for stable swarm aggregations［J］.International Jour?nal of Control，2004，77（18）：1567-1579.

［10］鐘午，張偉，康懷褀，等.一種改進的多領導者蜂擁算法及其性能分析［J］.小型微型計算機系統，2014，35（9）：2116-2121.

ZHONG Wu，ZHANG Wei，KANG Huaiqi，et al.An Im?proved Flocking Algorithm with Multiple Leaders and Its Performance Analysis［J］.Journal of Chinese Computer Systems，2014，35（9）：2116-2121.

［11］羅小元，李紹寶，關新平.多智能體多目標跟蹤算法研究［J］.控制工程，2008，15（4）：420-422.

LUO Xiaoyuan，LI Shaobao，GUAN Xinping.Multi-tar?get Tracking Algorithm for Multi-agent［J］.Control Engi?neering of China，2008，15（4）：420-422.

［12］Luo X，Li S，Guan X.Flocking algorithm with multi-tar?get tracking for multi-agent systems［J］.Pattern Recogni?tion Letters，2010，31（9）：800-805.

［13］王海，羅琦，徐騰飛.融合局部自適應追蹤的多目標牽制蜂擁算法［J］.計算機應用，2014，34（12）：3428-3432.

WANG Hai，LUO Qi，XU Tengfei.Multi-target Pinning FlockingAlgorithmCombinedwithLocalAdaptive Tracking［J］.Journal of Computer Applications，2014，34（12）：3428-3432.

［14］Zhang G，Fricke G K，Garg D P.Spill detection and pe?rimeter surveillance via distributed swarming agents［J］. IEEE/ASME Transactions on Mechatronics，2013，18（1）：121-129.

Research and Simulation on Multi-target Tracking Flocking Control Algorithm

ZHANG Jinchun1WANG Shuailei2CAO Biao3YANG Yun2
（1.Company of Basic Sciences，Naval Aeronautical and Astronautical University，Yantai264001）（2.Gradugate Administrative Group，Naval Aeronautical and Astronautical University，Yantai264001）（3.Basic Experiment Department，Naval Aeronautical and Astronautical University，Yantai264001）

For implementation of flocking control algorithm in multi-target tracking，this paper proposes a multi-target track?ing flocking control algorithm.It is assumed that each agent uncertainly have the information of a target.By Lyapuvov stability theo?ry，the paper analyzes the condition to make the system stable，and gives the stable state.It also demonstrates that if an agent has a presupposed target，then each group can form a flock，and no agents collide.The simulation verifies the effectiveness of it by differ?ent initial connectivity of the network and two kinds of movement patterns of the targets.

multi-target，tracking，flocking control，Lyapunov stability，connectivity，movement

TP273

10.3969/j.issn.1672-9722.2017.05.015

2016年11月17日，

2016年12月21日

張金春，男，碩士，教授，研究方向：復雜系統。王帥磊，男，碩士研究生，研究方向：軍事系統的優化與控制。曹彪，男，碩士，講師，研究方向：航空裝備保障。楊蕓，男，碩士研究生，研究方向：離散動態系統。