改進Quatre算法的無人機編隊快速集結(jié)方法

孫田野, 孫 偉,*, 吳建軍

(1. 西安電子科技大學(xué)空間科學(xué)與技術(shù)學(xué)院, 陜西 西安 710071;2. 西北工業(yè)大學(xué)第365研究所, 陜西 西安 710129)

0 引 言

近年來,計算機、傳感器領(lǐng)域的變化日新月異,使得科技的發(fā)展趨向于智能化、無人化[1],無人機以其價格低廉、靈活機動和便攜等特點被普遍應(yīng)用于目標跟蹤、資源遙感、電力巡線、環(huán)境監(jiān)測和城市監(jiān)控等領(lǐng)域[2],代替人工執(zhí)行未知領(lǐng)域的探索和危險環(huán)境的排查[3]。但單個無人機的能力始終有限,存在搜索范圍小、載荷小、功能單一、環(huán)境感知不明顯和作戰(zhàn)半徑小等問題。單個無人機發(fā)生故障等情況時易導(dǎo)致任務(wù)無法順利完成,因此多無人機編隊成為了無人機發(fā)展的迫切需求和趨勢,無人機編隊也成為了各個國家軍事領(lǐng)域發(fā)展的重要任務(wù)[4]。國內(nèi)外在無人機編隊控制領(lǐng)域做了大量的探索和研究,著名的包括美國的“小精靈”“拒止環(huán)境協(xié)同作戰(zhàn)”“快速量輕自主”和“集群使能攻擊戰(zhàn)術(shù)”等多個無人機集群研發(fā)項目[5-6]。

無人機編隊的研究主要包括編隊集結(jié)和編隊重構(gòu),無人機編隊集結(jié)是無人機編隊的初始條件,固定翼無人機與旋翼無人機在運動規(guī)則上有著根本性的差異,固定翼無人機從開始起飛就保持一定的飛行速度,無法像旋翼無人機懸停在半空等待其他個體[7],因此固定翼無人機的集結(jié)更難,目前無人機編隊集結(jié)算法主要包括一致性控制算法和仿生算法等[8-9]。一致性控制最開始應(yīng)用于計算機領(lǐng)域的并行計算,Vicsek等人提出了Vicsek模型,提出“對齊”規(guī)則。種群中個體勻速運動,其運動狀態(tài)由相鄰個體決定,整個大種群的動態(tài)一致性問題就簡化為多個無人機狀態(tài)矩陣的穩(wěn)定性問題[10],這樣的優(yōu)勢是將復(fù)雜的多維矩陣問題轉(zhuǎn)換成低維矩陣求解。一致性控制保證了在編隊中個體出現(xiàn)故障時也能保證整體一致性,但Hu等人指出輸入時延的存在影響系統(tǒng)的穩(wěn)定性,容易導(dǎo)致系統(tǒng)崩潰的情況。仿生算法是近年來流行的無人機編隊集結(jié)方法,模擬動物中的種群行為，被應(yīng)用于無人機編隊的集結(jié)中[11]，例如遺傳算法(genetic algorithm, GA)、蟻群算法、粒子群(particles swarm optimization, PSO)算法和蝙蝠算法[12-14]等,但這些經(jīng)典算法存在計算效率低、容易局部收斂、迭代次數(shù)多等問題,實際應(yīng)用不多。Bian等人提出一種改進差分進化(differential evolution, DE)算法,優(yōu)化了種群結(jié)構(gòu),加快了迭代速率,但是隨著編隊規(guī)模的增加,計算時間較長[15]。Meng等人提出一種Mongkey-King算法,解決了粒子群算法“走兩步退一步”的缺點,但是依然存在大規(guī)模編隊計算效率低的問題[16]。Zhang等人采用改進的約束DE算法,考慮了現(xiàn)實情況下的約束條件,但是在實際應(yīng)用中,過多的約束條件導(dǎo)致計算量偏大,算法效率低[17]。

本文針對無人機編隊在集結(jié)過程中效率低等問題,提出一種改進擬仿射類進化(improved quasi-affine transformation evolutionary, IQuatre)算法,與分布式模型預(yù)測控制(distributed model predictive control, DMPC)相結(jié)合,通過對編隊的“現(xiàn)在”和“未來”狀態(tài)的計算,保證了無人機編隊整體的穩(wěn)定性和安全性。IQuatre算法保持了DE算法迭代迅速、控制參數(shù)少的特點,實現(xiàn)了無人機編隊快速集結(jié)、編隊整體穩(wěn)定的目的。

1 無人機編隊模型

在慣性坐標系下,不考慮其他外在環(huán)境對無人機的影響,無人機的運動可以視為其質(zhì)心的三維運動[18],使用歐拉方程對運動模型進行離散化處理,近似為

(1)

2 DMPC策略

預(yù)測控制模型分為預(yù)測模型、動態(tài)時域滾動優(yōu)化和代價值反饋校正,DMPC最早應(yīng)用在工業(yè)過程控制領(lǐng)域內(nèi)[19-20]。DMPC可以將控制系統(tǒng)轉(zhuǎn)化成條件約束問題,通過輸入控制對象的過去狀態(tài)信息,對系統(tǒng)N步之后的控制狀態(tài)進行預(yù)測,并且通過反饋校正系統(tǒng)實時對預(yù)測量進行更新和優(yōu)化[21]。

無人機編隊的集結(jié)問題可以看作僚機根據(jù)主機的位置,不斷去追擊自己期望位置的追擊過程[22]。但是在追擊的過程中,為了避免無人機發(fā)生碰撞和無人機編隊整體性變差,就需要對無人機編隊的狀態(tài)進行控制和預(yù)測,而DMPC關(guān)于未來N個狀態(tài)的計算完全可以應(yīng)用在對無人機編隊控制量的計算上,DMPC和無人機編隊相結(jié)合產(chǎn)生的分布式預(yù)測模型很好地解決了無人機編隊模型中當(dāng)前最優(yōu)解和無人機編隊安全性間的平衡問題[23]。

控制分為集中式和分布式兩種,集中式模型預(yù)測控制只采用一個控制器來求解整個控制系統(tǒng)的控制量,計算量大并且復(fù)雜,因此無人機系統(tǒng)研究中常用的是DMPC[24]。DMPC針對每一個被控對象都有一個單獨的控制器,通過關(guān)聯(lián)變量達到全局約束的目的,從而減小了每次計算的計算規(guī)模,提高求解速度。

在反饋系統(tǒng)中,將控制量和狀態(tài)量作為反饋值,整個系統(tǒng)的運動方程轉(zhuǎn)化為單個系統(tǒng)之間相互關(guān)聯(lián),離散化式(1)可以將無人機的運動方程表示為

f(x(n),u(n))=F[f1(x1(n),u1(n)),
f2(x2(n),u2(n)),…,fN(xN(n),uN(n))]

(2)

式中:x(n),u(n)分別代表無人機在n時刻的狀態(tài)量和控制量。在DMPC框架下,無人機控制系統(tǒng)的約代價可以轉(zhuǎn)換為各個子系統(tǒng)性能指標的加權(quán),式(2)可以改寫為

(3)

(4)

(5)

系統(tǒng)的收斂問題可以簡化為單無人機優(yōu)化問題:

(6)

3 IQuatre算法求解DMPC模型

Quatre算法的核心是映射函數(shù),隨機初始化種群的個體,然后再以類似數(shù)學(xué)中映射的函數(shù)關(guān)系(f:x→y),將原有的粒子投射到另一個集合中去,再通過適應(yīng)度函數(shù)進行個體優(yōu)異判斷,保留符合要求且性能優(yōu)異的個體,不斷地重復(fù)迭代,直至滿足收斂條件或最大迭代次數(shù),最后留下的個體被認為是最佳變量[25-26]。Quatre算法與其他算法相比,其優(yōu)勢在于Quatre算法在種群的變異演化過程中,僅需要一個空間矩陣M和步長c,不需要設(shè)置其他類似于DE算法的變異率等參數(shù)[27],并且Quatre算法個體間的關(guān)系更緊密,在變量空間中具有良好的搜索和尋優(yōu)能力。

(7)

式中:c是差分矩陣的系數(shù)因子(將Xr1-Xr2的結(jié)果視為差分矩陣)。選擇矩陣M是自動生成的矩陣,從Mtemp下三角矩陣一步步變換而來,具體變化如下所示:

(8)

轉(zhuǎn)換有兩個步驟,第一步是在Mtemp中隨機排列每個D維行向量的元素,第二步是隨機交換矩陣Mtemp中的行向量,即可得到交換矩陣M。

若個體bi的坐標位置為bi=[bi,1,bi,2,…,bi,D],并且種群中存在ps個個體,那么種群矩陣即為B=[b1,b2,…,bps]T,Bgbest,G表示全局最佳個體矩陣,每一個行向量的值都是bgbest向量,Bgbest,G代表種群B的第G代最佳個體,也是前G代的最佳個體。下式給出了種群矩陣和全局最佳個體矩陣的定義:

(9)

以經(jīng)典DE算法的角度來看,可以將B視為突變體Vm的矩陣。

Quatre算法相較于其他算法結(jié)構(gòu)更加簡單,更少的控制參數(shù)使得只需要在粒子演化過程中設(shè)置一個步長c[28]。將Quatre算法與PSO算法、DE算法進行對比,實驗結(jié)果表明,Quatre算法性能更好,并且在實際規(guī)模比較大的模型中尤為顯著,迭代速率快,收斂性能好。但是Quatre算法也存在DE算法的通病。迭代后期,Quatre依然容易陷入局部優(yōu)化,導(dǎo)致最后獲得的最優(yōu)解參數(shù)并非全局最優(yōu)[29-30]。

本文在Quatre算法和DMPC模型的基礎(chǔ)上,提出了IQuatre算法。DMPC模型下Bn temp的N代預(yù)測信息中包含下一時刻B(n+1)temp的最優(yōu)控制信息,即上一時刻的最優(yōu)個體bgbset包含了下一時刻b(g+1)best的部分最優(yōu)片段。在生成新種群Btemp之前,將前一時刻具有最優(yōu)方向的個體bgbest替換到新種群中,在新種群中隨機選擇bk和bk+1兩個個體,比較代價值Fi(n),并替換新種群中表現(xiàn)不佳的個體,可以提高種群迭代趨向于最優(yōu)方向的概率,提高算法的收斂速度,具體的種群優(yōu)化可表示如下:

Bctemp=[b1,b2,…,bk,bk+1,…,bn]

(10)

Bctemp=[b1,b2,…,bgbest,bk+1,…,bn]

(11)

主要流程表述如下。

步驟 1設(shè)置初始化參數(shù),包括步長c和變換矩陣M。

步驟 2生成合適大小的初始種群B1。

步驟 3根據(jù)式(7),生成包含N代預(yù)測的新種群[B1,B2,…,Bn],得到當(dāng)前種群的最優(yōu)個體bgbest和N代預(yù)測值[b2,b3,…,bn]。

步驟 4將N代預(yù)測值代入模型,得到當(dāng)前最優(yōu)個體的代價值bgbest,判斷結(jié)果是否達到最大迭代次數(shù),或判斷式(3)求得的代價值是否滿足設(shè)定的收斂條件,滿足則跳到步驟6,不滿足則進行步驟5。

步驟 5將pbest代入種群B2,隨機選取兩個個體bk和bk+1,替換代值高的個體bk,形成新的初始種群B1,跳回步驟3。

步驟 6輸出最優(yōu)控制量bgbest。

4 仿真實驗分析

為了驗證本文提出的IQuatre算法的有效性,在Matlab2020軟件環(huán)境下進行仿真驗證。在仿真實驗1中,分別采用經(jīng)典GA算法、PSO算法、DE算法、Pro-DE算法、Quatre算法和IQuatre算法對5架無人機編隊快速集結(jié)進行了對比仿真實驗;在仿真實驗2中,為了驗證本文提出的IQuatre算法對于多編隊控制的適用性,對15架無人機編隊集結(jié)進行了仿真;在仿真實驗3中,為了驗證本文提出的IQuatre算法對于編隊控制的整體性,對25架無人機編隊多種路徑下的編隊飛行進行了仿真驗證,本文所有無人機均為固定翼無人機。

4.1 仿真實驗1

5架無人機,依次間隔5 s起飛,在空中集結(jié)成一個“人”字形編隊,前后左右分別相距100 m,如圖1所示。分別采用GA、PSO算法、DE算法、Pro-DE算法、Quatre算法和IQuatre算法進行編隊的起飛集結(jié)仿真,對比不同算法的實驗結(jié)果。

表1為無人機約束參數(shù)取值范圍,考慮到無人機存在失速和失控的風(fēng)險,無人機的最低速度設(shè)定在30 m/s,最高速度不超過50 m/s,無人機的俯仰角不低于45°,不高于135°,無人機航向角速度和俯仰角速度均不超過15°。

表1 無人機約束參數(shù)Table 1 Unmanned aerial vehicle constraint parameters

各個算法的初始參數(shù)設(shè)置取自參考文獻,具體參數(shù)如表2所示。圖2為不同算法的5架無人機編隊集結(jié)軌跡圖。從圖2可以看出,采用IQuatre算法的無人機編隊集結(jié),減少了2號和5號無人機出現(xiàn)的上下波動情況,較其他傳統(tǒng)DE算法、GA算法、PSO算法提升更加明顯;通過對比無人機編隊集結(jié)后的軌跡圖可以看出,采用IQuatre算法的模型,集結(jié)完成后的穩(wěn)定性更好,較原始Quatre算法無人機最大位置誤差減少了0.42 m。表3為不同算法5架次、15架次、25架次無人機編隊集結(jié)計算時間。由表3可以看出,IQuatre算法較Quatre算法至少有約3.4%的提升,較傳統(tǒng)的DE算法、GA算法和PSO算法提升明顯。從表4可以看出,無人機編隊集結(jié)完成后,IQuatre算法的最大位置誤差最小為1.62 m,較原Quatre算法提升了0.45 m,較5號無人機位置誤差表現(xiàn)最優(yōu)的PSO算法提升了0.33 m,無人機編隊的穩(wěn)定性更高。圖3為不同算法的平均迭代次數(shù),從圖3可以看出IQuatre算法較其他算法迭代速度更快,大約有5.2%的提升。從圖4第5架無人機位置誤差圖可以看出,IQuatre算法收斂速度與其他算法相當(dāng),但IQuatre算法誤差更小、更穩(wěn)定。

表2 各算法基礎(chǔ)參數(shù)設(shè)置Table 2 Basic parameters setting of each algorithm

表3 不同算法的多無人機編隊集結(jié)計算時間Table 3 Calculation time of multi-unmanned aerial vehicle formations with different algorithms s

表4 不同算法5號無人機最大位置誤差Table 4 Maximum position error of unmanned aerial vehicle 5 with different algorithms m

通過對不同算法無人機編隊各實驗數(shù)據(jù)對比可知,IQuatre算法提高了無人機編隊集結(jié)過程的穩(wěn)定性,在保證無人機編隊內(nèi)機間安全距離的前提下,提高了模型迭代速度,極大地減少了計算量和計算時間。

4.2 仿真實驗2

為了驗證本文提出的IQuatre算法對于多編隊無人機集結(jié)的適用性,增加無人機個數(shù)。15架無人機分成3個編隊,依次間隔5 s起飛,前后左右相距100 m,各個小編隊在空中集結(jié)呈“人”字形,3個小編隊組成一個大的“人”字形,編隊隊形如圖5所示,對無人機編隊的起飛集結(jié)進行仿真,分析多編隊情況下IQuatre算法的適用性。

圖6為不同算法15架無人機編隊集結(jié)軌跡圖,從圖6可以看到,采用6種算法的編隊集結(jié)模型基本完成了編隊集結(jié),但從圖6(a)可以看到,采用IQuatre算法的編隊集結(jié)穩(wěn)定性更好,有效地減少了其他算法中出現(xiàn)的無人機小幅度上下波動的情況,這與仿真實驗1中5架無人機編隊集結(jié)的情況一致。采用IQuatre算法的集結(jié)模型,在編隊集結(jié)成形后,無人機最大期望位置誤差減少到1.7 m,較其他算法提升明顯。圖7為編隊1與編隊3距離,從圖7可以看出,編隊1和編隊3保持穩(wěn)定的距離,符合期望目標。圖8為15號無人機期望位置誤差圖,在300 s處,無人機期望位置誤差基本收斂至0,并一直保持在期望位置。

表5為不同算法無人機編隊集結(jié)成型后最大位置誤差表,從表中可以看到,采用IQuatre算法的15架無人機編隊集結(jié)后最大期望位置誤差為1.7 m,遠小于其他算法,證明了本文提出的IQuatre算法提高了多無人機編隊集結(jié)的穩(wěn)定性。

表5 不同算法無人機編隊集結(jié)成型后最大位置誤差表Table 5 Maximum position error of unmanned aerial vehicle after formation assembly with different algorithms m

在仿真實驗1的基礎(chǔ)上,通過對比不同算法15架無人機編隊集結(jié)的軌跡圖和位置誤差等實驗數(shù)據(jù)可知,IQuatre算法提高了無人機編隊集結(jié)過程的穩(wěn)定性,在多編隊的情況下依然適用。

4.3 仿真實驗3

為了驗證本文提出的IQuatre算法在復(fù)雜路徑中的可行性,改變編隊的飛行路徑,25架無人機分成5個編隊,依次間隔5 s起飛,前后左右相距100 m,各個編隊在空中集結(jié)呈“人”字形,5個小編隊組成一個大的“人”字形,具體編隊隊形如圖9所示。25架無人機集結(jié)完成后,整個編隊按照1號無人機半徑326 m的“s” 形和1號無人機半徑3 100 m的圓形路徑飛行,通過無人機編隊在復(fù)雜路徑上的航跡和誤差對比,分析IQuatre算法的優(yōu)劣。

圖10為25架無人機從編隊集結(jié)到編隊做“s”形和圓形變軌的所有軌跡圖,從圖10可以看出,25架無人機飛行軌跡基本與主機的運動軌跡吻合,整體飛行軌跡符合預(yù)設(shè)編隊隊形,不存在無人機交叉碰撞的情況。圖11為去除軌跡后部分時間節(jié)點圖,從圖11可以看出,編隊隊形集結(jié)完畢后,無論是直線運動還是曲線運動,無人機編隊整體隊形沒有打亂,始終保持預(yù)設(shè)的“人”字形編隊。圖12為編隊3和編隊5之間最外圍無人機間的距離圖。從圖12可以看到,整個大編隊內(nèi)部的兩個小編隊間距離保持穩(wěn)定,沒有碰撞發(fā)生,始終保持固定的編隊隊形。圖13是25號無人機的期望位置誤差圖,從圖13可以看到,最外圍的25號無人機在250 s左右時完全追上整個編隊,在追上1號主機后基本保持在期望位置,無人機偏離預(yù)期位置的最大誤差不超過8 m。

在仿真實驗1和仿真實驗2的基礎(chǔ)上,通過25架無人機編隊多種路徑的仿真實驗,驗證了本文提出的IQuatre算法確實能夠完成無人機編隊的快速集結(jié),性能較其他算法更加優(yōu)異,編隊更加穩(wěn)定,在保證編隊安全的前提下,保持了編隊的整體性。

5 結(jié) 論

本文針對無人機編隊集結(jié)的穩(wěn)定性問題進行了研究分析,基于DMPC和IQuatre算法建立了無人機的運動模型,利用滾動優(yōu)化的數(shù)學(xué)模型提高了無人機編隊的穩(wěn)定性和安全性。首先通過5架無人機編隊的集結(jié)實驗,對比IQuatre算法與其他5種算法的無人機集結(jié)情況,驗證了本文提出的IQuatre算法的有效性。相比其他算法最外層無人機的位置誤差,IQuatre算法能夠提高無人機編隊集結(jié)的穩(wěn)定性;然后增加無人機編隊數(shù)量,驗證了本文提出的DMPC和IQuatre算法在多編隊情況下依然能夠保持編隊穩(wěn)定;最后通過25架無人機復(fù)雜路徑下的編隊集結(jié)與跟隨仿真實驗,驗證了本文IQuatre算法在復(fù)雜路徑下能夠?qū)崿F(xiàn)編隊的穩(wěn)定集結(jié)。

IQuatre算法與Quatre算法、Pro-DE算法、GA算法、DE算法和PSO算法對比實驗的數(shù)據(jù)表明,IQuatre算法較原Quatre算法減少了5.2%的平均迭代次數(shù),減少了計算量,在計算時間方面節(jié)約了4.6%,較原Quatre算法最外層無人機位置誤差提升了最少0.45 m,與其他算法對比最少提升了0.33 m。實驗數(shù)據(jù)表明,基于DMPC與IQuatre算法的無人機編隊集結(jié)方法提高了編隊集結(jié)的穩(wěn)定性,為無人機編隊集結(jié)提供了新的方法。