基于MAS的無(wú)人機(jī)新型編隊(duì)算法

王 瀟，紀(jì)志堅(jiān)

(青島大學(xué)自動(dòng)化學(xué)院，山東 青島 266071)

0 引言

1991年海灣戰(zhàn)爭(zhēng)中無(wú)人機(jī)得到成功運(yùn)用，近幾十年已有30多個(gè)國(guó)家投入巨額財(cái)力和大量人力來(lái)生產(chǎn)和研究無(wú)人機(jī)。經(jīng)過(guò)長(zhǎng)久的發(fā)展，無(wú)人機(jī)技術(shù)已相當(dāng)成熟，并在各個(gè)領(lǐng)域中發(fā)揮了重要作用。無(wú)人機(jī)群是近十幾年提出的無(wú)人機(jī)合作化發(fā)展的一個(gè)核心概念[1]。無(wú)人機(jī)群是多智能體系統(tǒng)(MAS)的典型應(yīng)用，目前無(wú)人機(jī)群已逐步擔(dān)當(dāng)起偵察、預(yù)警、監(jiān)視、指揮控制、通信、測(cè)繪、作戰(zhàn)等任務(wù)[2]。無(wú)人機(jī)群構(gòu)成了一個(gè)比單架無(wú)人機(jī)更有效的系統(tǒng)，而編隊(duì)控制是協(xié)調(diào)無(wú)人機(jī)之間協(xié)作的關(guān)鍵步驟[3]。一般而言，編隊(duì)控制的問(wèn)題是找到一種分布式協(xié)調(diào)方案，使無(wú)人機(jī)能夠到達(dá)并保持一些理想的、可能隨時(shí)間變化的編隊(duì)[4]。

在本文中，主要研究基于一致性的無(wú)人機(jī)群控制問(wèn)題，設(shè)計(jì)了一種基于MAS的無(wú)人機(jī)群新型編隊(duì)控制算法。新算法中不存在顯式領(lǐng)導(dǎo)者，即所有個(gè)體對(duì)領(lǐng)導(dǎo)者的指定一無(wú)所知，可以根據(jù)動(dòng)態(tài)需要指定領(lǐng)導(dǎo)者。盡管新算法中的某些分式與現(xiàn)有協(xié)議中的分式相似，但該算法所操縱無(wú)人機(jī)的群集行為將顯著不同。沒有明確的領(lǐng)導(dǎo)者，這表明，知情者不僅需要扮演領(lǐng)導(dǎo)者的角色，跟蹤全局軌跡，而且還必須積極、含蓄地融入到群體中。因?yàn)轭I(lǐng)導(dǎo)者可能在高風(fēng)險(xiǎn)環(huán)境下被擊落，或者需要停止當(dāng)前的任務(wù)來(lái)承擔(dān)新的任務(wù)，基于本文設(shè)計(jì)的編隊(duì)控制算法，每架無(wú)人機(jī)在有需要時(shí)可以動(dòng)態(tài)隨機(jī)地指定為領(lǐng)導(dǎo)者，所以對(duì)軍事應(yīng)用也具有非常重要的意義。

在本文第2章節(jié)，介紹了基礎(chǔ)知識(shí)和準(zhǔn)備工作。在第3章節(jié)中給出了編隊(duì)控制算法，并利用Reynolds提出的凝聚、分離和調(diào)整規(guī)則證明了該算法的可行性[17]。第4章節(jié)中給出了數(shù)值仿真來(lái)說(shuō)明算法的有效性，第5章節(jié)對(duì)本文進(jìn)行了總結(jié)。

1 基礎(chǔ)知識(shí)和準(zhǔn)備工作

1.1 基礎(chǔ)知識(shí)

設(shè)G=(V,E,A)為加權(quán)無(wú)向圖，其中頂點(diǎn)集設(shè)為V={1,2,…,N}，邊集E?{(i,j):i,j∈V}和加權(quán)鄰接矩陣A=[aij]N×N，描述了無(wú)人機(jī)之間的交互拓?fù)浣Y(jié)構(gòu)。如果i和j之間存在邊eij∈E,則表明兩個(gè)點(diǎn)可以相互接受對(duì)方信息，此時(shí)無(wú)人機(jī)j被稱為無(wú)人機(jī)i的鄰居，無(wú)人機(jī)i的鄰居集合可以被定義為Ni={j|j∈V:eij∈E}。當(dāng)且僅當(dāng)j∈Ni(j≠i)時(shí)，加權(quán)鄰接矩陣A中的元素滿足aij=aji=1，否則aij=0。將無(wú)人機(jī)個(gè)體按照是否接受外部控制輸入分為領(lǐng)導(dǎo)者與跟隨者，領(lǐng)導(dǎo)者集合表示為Vl={1,2,…,M}，M≤N；Vf=VVl表示剩下的無(wú)人機(jī)集合，即跟隨者集合。如果無(wú)向圖G是連通的，則任意一對(duì)不同的頂點(diǎn)i和j之間有一條路徑。另外，拉普拉斯矩陣L=[lij]N×N定義為

(1)

由以上定義可知，在無(wú)向圖G中，矩陣L的對(duì)角線元素為其所在行剩余元素之和的相反數(shù)，即矩陣L的每行元素之和為零。當(dāng)且僅當(dāng)無(wú)向圖G連通時(shí)，易證明矩陣L存在零特征值，而所有其它特征值都為正值，因此矩陣L是半正定的。此外，拉普拉斯矩陣滿足如式(2)的平方和性質(zhì)[18]：

(2)

其中，M=[M1,…,MN]∈RNn，Mi∈Rn，i=1,…,N。

1.2 準(zhǔn)備工作

假設(shè)一個(gè)無(wú)人機(jī)群由N個(gè)個(gè)體組成，用1,…,N表示，從編隊(duì)控制的角度來(lái)分析，這些無(wú)人機(jī)中的每個(gè)個(gè)體都可以看作點(diǎn)質(zhì)量。無(wú)人機(jī)群的編隊(duì)控制可以分解為水平和垂直方向編隊(duì)問(wèn)題，實(shí)踐表明，水平軌跡控制器比垂直軌跡控制器具有更大的時(shí)間常數(shù)，本文僅考慮水平運(yùn)動(dòng)一致性。如果所有無(wú)人機(jī)都具有相同的有限的環(huán)境感測(cè)范圍，只能在自己的感測(cè)范圍內(nèi)發(fā)現(xiàn)群體同伴，則無(wú)人機(jī)i的鄰居集可描述為

Ni={j:‖pij‖

(3)

其中,pij=pi-pj是無(wú)人機(jī)i到無(wú)人機(jī)j的位置矢量，R是感測(cè)范圍。在實(shí)際應(yīng)用中，無(wú)人機(jī)群的系統(tǒng)輸入是預(yù)先定義好的。對(duì)于每一個(gè)領(lǐng)導(dǎo)者i∈Vl，其系統(tǒng)動(dòng)力學(xué)方程為

(4)

如果i∈Vf，無(wú)人機(jī)i為跟隨者；基于實(shí)現(xiàn)坐標(biāo)轉(zhuǎn)換且軌跡二階連續(xù)可微，系統(tǒng)動(dòng)力學(xué)常表現(xiàn)為

(5)

其中,p、v、u分別為位置、速度和加速度輸入矢量。

領(lǐng)導(dǎo)者的fl(pl,vl)是無(wú)人機(jī)群跟蹤控制器設(shè)計(jì)最關(guān)鍵的一步。考慮到跟隨者的輸入，本文構(gòu)造了一個(gè)廣泛使用的分布式控制器協(xié)議，以此來(lái)引導(dǎo)某些數(shù)量的跟隨者組成群體，并以適當(dāng)?shù)南鄬?duì)距離和方向跟蹤領(lǐng)導(dǎo)者，該協(xié)議表達(dá)式為

(6)

(7)

符號(hào)Vij(‖pij‖)代表無(wú)人機(jī)i與無(wú)人機(jī)j之間相對(duì)距離可微、非負(fù)的人工勢(shì)能函數(shù)。它用來(lái)調(diào)節(jié)群體中的分離和聚集運(yùn)動(dòng)，滿足如下條件:

1)為避免與太近的無(wú)人機(jī)個(gè)體發(fā)生碰撞，當(dāng)‖pij‖→0時(shí)，Vij(‖pij‖)達(dá)到最大值V0(V0→+∞)。

2)當(dāng)無(wú)人機(jī)i和j位于期望距離時(shí)，Vij(‖pij‖)達(dá)到其獨(dú)特的最低值Vd(Vd=0)。

3)如果無(wú)人機(jī)i與無(wú)人機(jī)j相對(duì)距離超過(guò)有效感測(cè)范圍時(shí)，Vij(‖pij‖)保持一個(gè)常量VR。

根據(jù)如上要求，本文設(shè)計(jì)的勢(shì)能函數(shù)如下:

(8)

圖1 d=5,R=15時(shí)的勢(shì)場(chǎng)函數(shù)YFig.1 Potential field function Y at d=5, R=15

特別注意的是，大多數(shù)現(xiàn)有的編隊(duì)控制方法都是為移動(dòng)機(jī)器人設(shè)計(jì)的，它們的約束比無(wú)人機(jī)的約束要容易得多。對(duì)于在水平方向上飛行的無(wú)人機(jī)，其運(yùn)動(dòng)方向一般可分為切向跟橫向，分別用上標(biāo)t和n表示，為確保無(wú)人機(jī)在飛行范圍內(nèi)飛行，單個(gè)無(wú)人機(jī)的實(shí)際約束，包括速度、加速度和角速度，可以描述如下：

(9)

2 編隊(duì)控制算法

2.1 算法描述

假設(shè)無(wú)人機(jī)群中只存在一部分領(lǐng)導(dǎo)者，剩余個(gè)體為跟隨者，則集成協(xié)議(4)、(5)和(6)，控制器協(xié)議可以改寫為(10)：

(10)

系數(shù)αi是一個(gè)事件觸發(fā)變量，當(dāng)無(wú)人機(jī)i接收全局軌跡信息是領(lǐng)導(dǎo)者時(shí)，αi=1；如果無(wú)人機(jī)i是跟隨者時(shí)，αi=0?；谑?10)，無(wú)人機(jī)i分布式控制協(xié)議設(shè)計(jì)為

(11)

f(uid,vid,pid)=uid-b2(pi-pid)-b3(vi-vid)

本文只考慮水平運(yùn)動(dòng)一致性，可得u1d=…=uNd=ud，v1d=…=vNd=vd，p1d=…=pNd=pd，則控制協(xié)議可以改寫為(12)：

(12)

f(ud,vd,pd)=ud-b2(pi-pd)-b3(vi-vd)

2.2 主要結(jié)果

在本節(jié)中，利用定理一給出了無(wú)人機(jī)群運(yùn)動(dòng)一致性和編隊(duì)控制協(xié)議的主要結(jié)論?；诙ɡ硪恢械膬?nèi)容，對(duì)新型分散控制協(xié)議進(jìn)行了理論分析和證明。

定理1假設(shè)一組N架無(wú)人機(jī)，動(dòng)力學(xué)描述為(10)并且由控制輸入函數(shù)(12)控制，初始相互作用圖G0(t=0)是無(wú)向連通的，Q(0)表示初始時(shí)刻無(wú)人機(jī)群總?cè)斯?shì)能和相對(duì)動(dòng)能之和，則得到以下結(jié)論：

1)在新型控制協(xié)議下，無(wú)人機(jī)群通訊消耗減少，系統(tǒng)更具有可伸縮性。

2)在Q(0)0時(shí)無(wú)人機(jī)群的交互圖G總是連通的。

3)在Q(0)

4)所有無(wú)人機(jī)的速度逐漸收斂于期望值。

證明：首先證明定理1的第1)部分，其次證明定理1的第2)、3)、4)部分。

圖2 信息流程圖Fig.2 Information flow chart

現(xiàn)存的控制協(xié)議體系結(jié)構(gòu)中的信息傳遞圖由圖2a表示，本文設(shè)計(jì)的控制器協(xié)議(12)中的信息傳遞圖由圖2b表示。從圖2中可以直觀地看出，在無(wú)人機(jī)個(gè)數(shù)相同的情況下，圖2b邊數(shù)較少，也就是說(shuō)，在多個(gè)領(lǐng)導(dǎo)者的無(wú)人機(jī)編隊(duì)中，通信消耗會(huì)減少，領(lǐng)導(dǎo)者越多編隊(duì)隊(duì)形越大，兩種協(xié)議的消耗差距也會(huì)更大，若再添加一個(gè)新的無(wú)人機(jī)，圖2b需要添加更加少的邊，說(shuō)明新型控制協(xié)議比現(xiàn)存控制協(xié)議更具可伸縮性，即證明了定理1的第1)部分。

在不失一般性的情況下，假設(shè)前M輛無(wú)人機(jī)被指定為領(lǐng)導(dǎo)者，且1≤M≤N，系統(tǒng)運(yùn)動(dòng)誤差定義為

(13)

(14)

Q(t)表示所有無(wú)人機(jī)之間的總?cè)斯?shì)能和總相對(duì)動(dòng)能之和，然后表達(dá)式為

(15)

由系統(tǒng)運(yùn)動(dòng)誤差定義可將式(15)改寫為

(16)

(17)

(18)

因此，有

(19)

然后，取Q(t)對(duì)時(shí)間的導(dǎo)數(shù)得到：

(20)

假定αi=1代表領(lǐng)導(dǎo)者，αi=0代表跟隨者，通過(guò)將式(14)代入(20)，有：

(21)

方程(21)可以簡(jiǎn)化并以矩陣形式表示為

(22)

(23)

(24)

因?yàn)榧僭O(shè)前M輛無(wú)人機(jī)被指定為領(lǐng)導(dǎo)者，對(duì)于領(lǐng)導(dǎo)者αi=1，對(duì)于追隨者αi=0，式(23)就意味著所有領(lǐng)導(dǎo)者的速度誤差漸近收斂為零，所以：

(25)

通過(guò)式(2)中描述的平方和性質(zhì)，我們從式(24)可以得到式(26)：

(26)

由式(25)和(26)可知，所有無(wú)人機(jī)的速度誤差收斂到零，即，這就意味著所有無(wú)人機(jī)的速度漸近收斂于期望值。從而證明了定理的第4)部分。

從而完成了定理1的證明。

在實(shí)際應(yīng)用中，加速度和角速度受到有效橫向負(fù)載的限制。因此，無(wú)人機(jī)之間的初始距離及其相互作用距離必須足夠遠(yuǎn)，初始速度也應(yīng)較小，以滿足Q(0)

3 仿真研究與分析

在本節(jié)中，將進(jìn)行數(shù)值仿真模擬，進(jìn)一步說(shuō)明理論結(jié)果，并驗(yàn)證新型編隊(duì)控制協(xié)議的有效性。在二維空間中，用協(xié)議(14)引導(dǎo)8架無(wú)人機(jī)進(jìn)行運(yùn)動(dòng)，仿真過(guò)程分為兩個(gè)階段。在第一階段，隨機(jī)分布的8架無(wú)人機(jī)被引導(dǎo)進(jìn)行直線編隊(duì)飛行，以此來(lái)驗(yàn)證協(xié)議的速度跟蹤、軌跡跟蹤以及動(dòng)態(tài)領(lǐng)導(dǎo)者重新分配能力；第二階段，模擬高空避障，編隊(duì)被引導(dǎo)進(jìn)行V型曲線飛行，驗(yàn)證該協(xié)議在軌跡劇烈變化下的速度與軌跡跟蹤能力。只有領(lǐng)導(dǎo)者有關(guān)于全局軌跡的信息，相對(duì)于全局軌跡的平均位置誤差定義如下：

其中，El和Ea分別為領(lǐng)導(dǎo)者和整個(gè)編隊(duì)的平均軌跡誤差，M為領(lǐng)導(dǎo)者的數(shù)量，N為整個(gè)隊(duì)形中的無(wú)人機(jī)數(shù)量(領(lǐng)導(dǎo)者和追隨者)。

感測(cè)距離R=200 m，期望距離d=80 m，最大加速度umax=6 m/s2，有效橫向負(fù)載ng=6，其它參數(shù)設(shè)為b1=0.8，b2=0.5，b3=1，在整個(gè)仿真模擬過(guò)程中，上述所有參數(shù)都保持不變。

3.1 第一階段

本階段的目的是用該協(xié)議引導(dǎo)無(wú)人機(jī)編隊(duì)進(jìn)行直線飛行，以此來(lái)驗(yàn)證速度跟蹤、軌跡跟蹤和動(dòng)態(tài)領(lǐng)導(dǎo)者重新分配能力。如圖3所示，從[0 m,200 m]和[0 m,150 m]中隨機(jī)選8架無(wú)人機(jī)的位置，并且它們的速度和方向分別隨機(jī)設(shè)定在區(qū)間[40 m/s,90 m/s]和[-π/2,π/2]中。在模擬開始時(shí)，1、2號(hào)無(wú)人機(jī)被指定為領(lǐng)導(dǎo)者，模擬持續(xù)300 s(從0 s到300 s)，步進(jìn)0.1 s。當(dāng)t=110 s時(shí)，預(yù)計(jì)無(wú)人機(jī)群將以0.5 m/s的速度開始加速，直到速度達(dá)到75 m/s。在圖4、5中分別給出了速度以及速度與期望速度的誤差。從圖4中可以看出，期望速度被領(lǐng)導(dǎo)者與跟隨者很好地追蹤；圖5表示無(wú)人機(jī)的速度誤差，從而驗(yàn)證了速度跟蹤能力。圖6顯示了無(wú)人機(jī)的軌跡，注意x軸和y軸的比例不同；圖7表示軌跡跟蹤誤差，從中可以看出，領(lǐng)導(dǎo)者的平均誤差較小，而整個(gè)編隊(duì)的平均誤差相對(duì)較大，由于領(lǐng)導(dǎo)者受跟隨者的影響，參考的軌跡不可能完全匹配，考慮到編隊(duì)規(guī)模時(shí)，則在可接受的范圍內(nèi)，因此驗(yàn)證了該算法的軌跡跟蹤能力。值得注意的是，T=230 s時(shí)，圖4、5、6、7發(fā)生的波動(dòng)是因?yàn)榫幪?hào)1、2號(hào)的無(wú)人機(jī)變?yōu)楦S者，編號(hào)3、4號(hào)的無(wú)人機(jī)重新被指定為領(lǐng)導(dǎo)者，這驗(yàn)證了無(wú)人機(jī)編隊(duì)領(lǐng)導(dǎo)者重新分配能力。

圖3 編隊(duì)初始狀態(tài)Fig.3 Initial status of formation

圖5 0～300 s速度誤差Fig.5 Speed error during 0～300 s

圖6 無(wú)人機(jī)軌跡Fig.6 UAV trajectory

圖7 0～300 s軌跡誤差Fig.7 Trajectory error during 0～300 s

圖8 350 s時(shí)編隊(duì)狀態(tài)Fig.8 Formation status at 350 s

3.2 第二階段

這一階段的目的是證明該協(xié)議在模擬障礙物和高風(fēng)險(xiǎn)空域避讓時(shí)的軌跡跟蹤能力、速度跟蹤能力。第一階段的最終狀態(tài)被視為該階段的輸入，引導(dǎo)編隊(duì)以75 m/s等速進(jìn)行V型曲線飛行。模擬持續(xù)150 s(從300 s到450 s)，步進(jìn)0.1 s，圖8顯示350 s時(shí)的編隊(duì)狀態(tài)，圖9為該階段無(wú)人機(jī)的軌跡。圖10為領(lǐng)導(dǎo)者和無(wú)人機(jī)編隊(duì)的平均軌跡誤差，表明該階段無(wú)人機(jī)的軌跡跟蹤是可以接受的。該階段的速度誤差如圖11表示，表明在整個(gè)軌跡跟蹤過(guò)程中，領(lǐng)導(dǎo)者和追隨者都能很好地跟蹤參考速度。整個(gè)仿真過(guò)程中無(wú)人機(jī)與其最近鄰居之間的距離如圖12所示，從圖12可以看出，無(wú)人機(jī)之間的最小距離均大于零，說(shuō)明無(wú)人機(jī)之間的避碰是成功的。仿真結(jié)果表明，該算法能夠?qū)崿F(xiàn)軌跡與速度的漸近跟蹤，即使軌跡在運(yùn)動(dòng)過(guò)程中發(fā)生劇烈變化，該算法仍然有效。

圖9 V軌跡Fig.9 V trajectory

圖10 300～450 s軌跡誤差Fig.10 During 300～450 s trajectory error

圖11 300～450 s速度誤差Fig.11 Speed error during 300～450 s

圖12 無(wú)人機(jī)之間最小距離Fig.12 Minimum distance between UAVs

4 結(jié)論

本文對(duì)無(wú)人機(jī)群的運(yùn)動(dòng)一致性和編隊(duì)控制進(jìn)行了研究，提出了一種新型的無(wú)人機(jī)群編隊(duì)控制算法，并對(duì)系統(tǒng)的穩(wěn)定性進(jìn)行了證明。結(jié)果表明，初始交互圖是連通的情況下，無(wú)人機(jī)編隊(duì)可以很好地完成軌跡與速度的漸近追蹤并且不會(huì)發(fā)生碰撞。通過(guò)數(shù)值模擬驗(yàn)證了速度與軌跡跟蹤能力，即便軌跡變化劇烈，也能以期望的速度跟蹤預(yù)定的軌跡。