吳昌偉,謝紅薇
(太原理工大學(xué) 軟件學(xué)院,山西 太原 030600)
由于單獨(dú)無人機(jī)存在諸如航程有限、魯棒性不足等問題,無法處理大型復(fù)雜場景下的多并發(fā)任務(wù)。因此多架無人機(jī)進(jìn)行任務(wù)協(xié)同組成無人機(jī)集群共同執(zhí)行任務(wù)成為無人機(jī)主要的使用場景[1]。可以自主進(jìn)行任務(wù)規(guī)劃的多無人機(jī)系統(tǒng)(multi-unmanned aerial system,MUAS)以及任務(wù)規(guī)劃的相關(guān)研究也逐漸成為近年來研究的熱點(diǎn)[2,3]。
Peng等[4]基于混合粒子群算法優(yōu)化了粒子群多樣性,提高了任務(wù)規(guī)劃算法的收斂結(jié)果可靠性。吳蔚楠等[5]提出基于改進(jìn)遺傳算法集群任務(wù)規(guī)劃算法,適用于多無人機(jī)場景,并能避免規(guī)劃的“單點(diǎn)失效”問題。CAI等[6]使用小生境和粒子群算法,利用貫續(xù)化的方法尋找最優(yōu)路徑,優(yōu)化算法收斂效果。Wu等[7]通過雙抑制分割的方法,利用相關(guān)性改進(jìn)蜂群算法形成任務(wù)鏈,實現(xiàn)了任務(wù)的多維連接,優(yōu)化任務(wù)規(guī)劃結(jié)果。KIM等[8]利用社會學(xué)習(xí)粒子群優(yōu)化最大化目標(biāo)函數(shù),提高集群任務(wù)規(guī)劃的計算效率。FU等[9]基于任務(wù)序列機(jī)制和協(xié)商一致算法為無人機(jī)集群實現(xiàn)無沖突任務(wù)規(guī)劃,但規(guī)劃結(jié)果無法脫離局部最優(yōu)。Amorim等[10]基于智能群任務(wù)指派算法(swarm-GAP)算法,提出了利用3種群間隙的優(yōu)化的方式,優(yōu)化了任務(wù)規(guī)劃收斂效果。Mei等[11]基于混合遺傳算法,利用雙滿意度指標(biāo)分層迭代求解,提高任務(wù)規(guī)劃效率。
上述算法和實驗大多是基于電腦進(jìn)行數(shù)據(jù)處理和仿真實驗的,這種集中式系統(tǒng)在實際應(yīng)用中存在中心節(jié)點(diǎn),這種模式相比于分布式模型算法響應(yīng)時間長,算法模型的穩(wěn)定性強(qiáng)依賴于中心節(jié)點(diǎn)的穩(wěn)定運(yùn)行,中心節(jié)點(diǎn)故障會導(dǎo)致整個算法系統(tǒng)故障;并且中心節(jié)點(diǎn)通信壓力大,算法擴(kuò)展存在上限。同時上述算法和實驗沒有考慮真實無人機(jī)控制單元的大多是基于嵌入式操作系統(tǒng)的小型機(jī)載計算機(jī),算力無法和實驗用計算機(jī)相比,而實際的任務(wù)點(diǎn)個數(shù)也往往增加到幾百個,遠(yuǎn)復(fù)雜于實驗場景設(shè)計,并且固定翼無人機(jī)因為飛行速度快導(dǎo)致集群狀態(tài)變化快,計算時間會造成更大的影響。因此上述算法在固定翼無人機(jī)集群的實際應(yīng)用場景下存在一定的局限性。
針對以上的問題,本文設(shè)計了一種基于多智能體聚類模型和改進(jìn)化學(xué)反應(yīng)優(yōu)化算法(chemical reaction optimization,CRO)的組合優(yōu)化算法,通過多智能體獨(dú)立聚類的方式擴(kuò)大初始搜索范圍,簡化搜索流程,提高搜索效率,并基于分組模型改進(jìn)優(yōu)化了CRO算法,引入基團(tuán)概念的同時重新設(shè)計了反應(yīng)模型,依據(jù)CRO算法中的代價函數(shù)勢能最小化的思想,為固定翼無人機(jī)集群實現(xiàn)快速任務(wù)規(guī)劃。
在實際的偵察搜索等任務(wù)中,受限于充電點(diǎn)或油料補(bǔ)充點(diǎn)的位置,數(shù)據(jù)分析及無人機(jī)維護(hù)等實際需要,無人機(jī)集群通常存在一個聚集點(diǎn)H,無人機(jī)在此處出發(fā)執(zhí)行任務(wù),并在任務(wù)結(jié)束后返回聚集點(diǎn)休整。記無人機(jī)集群數(shù)量為m,任務(wù)數(shù)量為n,記R={r1,r2,…,rm} 為無人機(jī)集群,T={t1,t2,…,tn} 為待執(zhí)行任務(wù)組。無人機(jī)集群以固定速度遍歷執(zhí)行T中所有任務(wù),為了最大限度利用無人機(jī)資源,T中每個任務(wù)需要被執(zhí)行且只被執(zhí)行一次,以最短時間完成集群的所有任務(wù)作為算法優(yōu)化目標(biāo)。
對于無人機(jī)ri, 設(shè)其對應(yīng)的待執(zhí)行任務(wù)組為Ti={ti1,ti2,…tik}∈T, 則其搜索長度li為
(1)
lmax=max{l1,l2,…,lm}
(2)
無人機(jī)集群完成任務(wù)時間與最長搜索長度lmax成正比,因此算法優(yōu)化目標(biāo)等價于優(yōu)化集群中無人機(jī)執(zhí)行的最長搜索長度,使算法最長搜索長度最短,即使lmax取最小值。
在面對大規(guī)模任務(wù)時,常用的分組遺傳等算法的計算時間較長,算法復(fù)雜度往往也不支持將算法部署于機(jī)載計算機(jī)環(huán)境中。
因此為了解決實際情況下固定翼無人機(jī)集群的任務(wù)規(guī)劃問題,使用任務(wù)拆分降維的思路,將大規(guī)模的集群任務(wù),通過聚類算法拆解成獨(dú)立的子任務(wù)組,再通過CRO算法優(yōu)化任務(wù)與任務(wù)組劃分,實現(xiàn)固定翼無人機(jī)集群的快速任務(wù)規(guī)劃。算法詳細(xì)流程如下:
(1)每架無人機(jī)基于K-means++聚類算法,各自獨(dú)立的將待執(zhí)行任務(wù)組拆分為子任務(wù)組,設(shè)T(k)為無人機(jī)rk計算得到的任務(wù)分組結(jié)果,則有
(3)
(4)
K-means++聚類算法是基于K-means聚類算法的一種改進(jìn)算法,是一種基于歐氏距離的聚類算法。算法基于距離越近的兩者相似度越高的思想,通過距離權(quán)重生成概率選擇處下一個合適的聚類中心,確保初始聚類的選擇足夠離散,提供了更好的穩(wěn)定聚類結(jié)果。通過K-means++聚類算法對集群任務(wù)點(diǎn)執(zhí)行的聚類操作,可以將多執(zhí)行機(jī)構(gòu)多任務(wù)場景降維成單執(zhí)行機(jī)構(gòu)多任務(wù)場景,極大簡化了場景模型的同時減少了每個任務(wù)場景中的任務(wù)點(diǎn)數(shù)量,并且保證聚類中心分布足夠均勻,提高算法的收斂速度并保證最終規(guī)劃結(jié)果的穩(wěn)定性。
在本文的模型中,將每個聚類記為CP={cp1,cp2,…,cpm}, 對應(yīng)的聚類中心記為C={c1,c2,…,cm}, 其在分組問題中流程如下:
(1)隨機(jī)選擇一個任務(wù)點(diǎn),初始化為聚類cp1的聚類中心,其聚類中心記為c1;
(3)重復(fù)步驟(2),直到聚類中心數(shù)量為m,完成聚類初始化;
(6)重復(fù)上述(4)、(5),直到所有聚類中心點(diǎn)迭代的最大誤差變化小于期望目標(biāo)δ。算法偽代碼如算法1所示。
算法1:K-means++聚類算法偽代碼
輸入:待執(zhí)行任務(wù)組T={t1,t2,…,tn}, 無人機(jī)數(shù)據(jù)m
(1)c1←random(T),C=c1,kc=1
(2)whilekc (3) Fori=0→n且ti?Cdo (5) end for (6) fori=0→n且ti?Cdo (8) end for (9)prandom=random(0,1) (11)c(kc+1)=tn (12) end if (13)C=C+c(kc+1),CP=CP+cp(kc+1) (14) end while (15) while max{Δc1,Δc2,…,Δcm}<δdo (16) fori=0→ndo (18) end for (19) forj=0→mdo (21) Δcj=cj-c′j (22)cj=c′j (23) end for (24) end while 輸出:CP={cp1AAAAAA,cp2,…,cpm},C={c1,c2,…,cm}。 化學(xué)反應(yīng)優(yōu)化算法是Albert Y.S. Lam和Victor O.K. Li等提出的一種元啟發(fā)式算法。算法的基礎(chǔ)思想是基于模擬化學(xué)反應(yīng)來解決多目標(biāo)多任務(wù)中的群體優(yōu)化問題。算法中每一個任務(wù)狀態(tài)被描述成一個特定結(jié)構(gòu)的分子,任務(wù)狀態(tài)的衡量函數(shù)被描述為分子勢能,同時引入分子動能的概念描述任務(wù)狀態(tài)的穩(wěn)定程度。算法演進(jìn)過程中會向更穩(wěn)定的狀態(tài),即向分子勢能最低的狀態(tài)變化。最終分子勢能降至最低時,算法處于穩(wěn)定狀態(tài),此時的任務(wù)狀態(tài)即為解算的最優(yōu)解。 原始CRO算法具有較好的全局搜索能力和搜索范圍,且基于分子單元的描述與分布式模型相匹配,適用于解決分布式場景下的最優(yōu)解的問題。但在解決大規(guī)模問題的時候,存在算法結(jié)果收斂速度慢,受初始狀態(tài)影響較大的問題,并且計算代價往往比較大。 針對上述問題和使用場景中分布式分組任務(wù)規(guī)劃的場景,加快算法的收斂速度,設(shè)計了基于分組優(yōu)化的改進(jìn)CRO算法模型,引入逸散能量緩沖區(qū)和2-opt優(yōu)化算法,并重新設(shè)計了分子反應(yīng),以保留更多的有效信息用以提高CRO算法模型的收斂速度,優(yōu)化集群任務(wù)規(guī)劃效果,使算法更切合固定翼無人機(jī)集群的真實使用場景。其中單個無人機(jī)執(zhí)行的算法流程如圖1所示。 圖1 改進(jìn)CRO算法流程 任務(wù)規(guī)劃問題的每一個解方案在算法中視作一個分子,在算法初始化時生成指定規(guī)模的分子集合,并計算分配各分子的初始化參數(shù)。解方案中的子任務(wù)組視作分子的一個基團(tuán),基團(tuán)個數(shù)與集群中無人機(jī)數(shù)量相等,如上文所述,分子的總勢能由該分子中勢能最大的基團(tuán)決定。算法詳細(xì)參數(shù)見表1。 算法執(zhí)行步驟如下: (1)分子集合初始化,生成NumInit數(shù)量個分子初始化,并通過2-opt算法進(jìn)行初始優(yōu)化; (2)生成隨機(jī)數(shù)p∈[0,1], 當(dāng)p≥p1, 執(zhí)行雙分子無效碰撞;當(dāng)p2≥p>p1時,執(zhí)行合成反應(yīng),否則執(zhí)行分解反應(yīng); (3)根據(jù)反應(yīng)執(zhí)行結(jié)果,更新分子集合,更新最小分子結(jié)構(gòu)和最小分子勢能,并更新能量緩沖器內(nèi)的能量,Step=Step+1; (4)如果Step 改進(jìn)CRO算法具體流程如圖1所示。分子及基團(tuán)評價優(yōu)化,能量緩沖器優(yōu)化和改進(jìn)CRO算法各反應(yīng)設(shè)計在本文各小節(jié)介紹。 2.2.1 分子勢能的計算及基團(tuán)的評價指數(shù) 對于分子ω,其存在分子基團(tuán)為 [ψ1,ψ2,…ψm], 則分子的勢能PEω設(shè)計為 PEω=max{L(ψ1),L(ψ2),…L(ψm)} (5) 其中,函數(shù)L(x) 為基團(tuán)x的當(dāng)前路徑長度。 對于分子基團(tuán)ψi, 設(shè)計其評價指標(biāo)為 (6) 其中,ci為ψi的聚類中心,tk為屬于ψi的任務(wù)點(diǎn),mψi為ψi中任務(wù)點(diǎn)的數(shù)量。J(ψi) 越小表明基團(tuán)越符合期望預(yù)期。 2.2.2 能量緩沖器優(yōu)化 能量緩沖器(energy buffer,EB)為一個獨(dú)立的反應(yīng)能量存儲單元,每次反應(yīng)重新分配反應(yīng)分子與能量緩沖器之間的能量。反應(yīng)前后能量差為正時,能量差存入能量緩沖器;并在分解反應(yīng)、合成反應(yīng)的反應(yīng)前后能量差為負(fù)時,從能量緩沖器中支出能量為反應(yīng)提供能量支持。能量緩沖器邏輯概念等價于真實反應(yīng)中的環(huán)境溫度等外界反應(yīng)條件。 能量緩沖器主要作用是為了鼓勵擴(kuò)大反應(yīng)搜索區(qū)域,跳出局部最優(yōu)解。但原始算法中的能量緩沖器與外界無能量溝通,容易導(dǎo)致反應(yīng)搜索區(qū)域過分?jǐn)U大,算法結(jié)果收斂慢等問題。為了提高算法的局部搜索能力,并加速收斂過程,將能量緩沖器改進(jìn)為每次反應(yīng)執(zhí)行時會向外界環(huán)境逸散能量,損失量與EB中當(dāng)前能量總量有關(guān),其損失函數(shù)如下 (7) EB′=EB*(1-EBLossRate) (8) 其中,EB′為迭代后能量緩沖器內(nèi)的能量,EBLossRate為每次迭代的EB能量損失率,L∈[0,1] 為基礎(chǔ)損失率,R>0為EB能量上限。 2.2.3 2-opt算法 在任務(wù)規(guī)劃這類問題上,解空間的大小與任務(wù)數(shù)量為指數(shù)級關(guān)系。當(dāng)問題規(guī)模增大時,傳統(tǒng)的算法很難產(chǎn)生較好的效果。而局部搜索算法和啟發(fā)式算法的結(jié)合,往往能使算法在計算性能,計算結(jié)果方面獲得較好的性能[12]。 同樣的,本文引入2-opt局部搜索算法[13],在CRO算法之前對分子結(jié)構(gòu)進(jìn)行提前優(yōu)化,提前排除一些明顯錯誤,降低對錯誤分子和結(jié)構(gòu)重復(fù)計算的概率。算法效果如圖2所示。 圖2 2-opt算法優(yōu)化效果 2.2.4 雙分子間無效碰撞 雙分子之間無效碰撞模擬分子之間發(fā)生輕微碰撞,分子結(jié)構(gòu)和各基團(tuán)結(jié)構(gòu)輕微改變的過程。雙分子間無效碰撞屬于橫向搜索反應(yīng),負(fù)責(zé)在算法各基團(tuán)內(nèi)實現(xiàn)的局部搜索結(jié)果優(yōu)化。 雙分子間無效碰撞過程首先在分子集合中隨機(jī)選擇兩個分子,兩個分子同時執(zhí)行反應(yīng)改變自己分子結(jié)構(gòu)。以其中一個分子為例,對于該被選出的分子,依據(jù)各基團(tuán)的評價指標(biāo),按照輪盤賭的方式選擇出一個待反應(yīng)的基團(tuán),在被選出的基團(tuán)中隨機(jī)選擇起點(diǎn)和終點(diǎn),保留兩點(diǎn)中間的部分,基團(tuán)的剩余部分則按照另一分子中未被選中點(diǎn)的相對順序,依次置入剩余位置。 假設(shè)反應(yīng)前分子為ω1,ω2, 反應(yīng)后分子改變?yōu)棣亍?,ω′2, 如果反應(yīng)可以成功發(fā)生,則對能量的要求為 PEω1+KEω1+PEω2+KEω2≥PEω′1+PEω′2 (9) 則視作反應(yīng)成功進(jìn)行,否則持續(xù)嘗試,直到反應(yīng)成功或嘗試次數(shù)達(dá)到nc。反應(yīng)成功后,新生成分子動能為 KEω′1=(PEω1+KEω1-PEω′1)×q (10) KEω′2=(PEω2+KEω2-PEω′2)×q (11) 其中,q∈[1-KELossRate,1] 的隨機(jī)數(shù)。反應(yīng)的剩余能量則入能量緩沖器中,即 BE=BE+(PEω1+KEω1+PEω2+ (12) 雙分子間無效碰撞反應(yīng)偽代碼如算法2所示。 算法2:雙分子間無效碰撞偽代碼 輸入:被選中分子ω1,ω2 (1)ψ1=roulette(ω1),ψ2=roulette(ω2),n=0 (2)ψ′1=fc(ψ1),ψ′2=fc(ψ2) (3)ω′i=ωi-ψi+ψ′i, 其中i=1,2 (4) whilePEωi+KEωi (5)ψ′i=fc(ψi) (6)ωi=ωi-ψi+ψ′i (7) end while (8)Ed=PEω1+KEω1+PEω1+KEω2-(PEω′2+PEω′1) (9)σ4,σ5←Random(0,1) (10)KE′ω1=Ed×σ4,KE′ω1=Ed×σ5, (11)EB←EB+Ed×(1-σ4+σ5) 輸出:反應(yīng)后分子ω1,ω2,EB 2.2.5 合成反應(yīng) 合成反應(yīng)模擬兩個分子間發(fā)生碰撞后合并為一個分子的過程,這一過程分子結(jié)構(gòu)有較大變化。合成反應(yīng)屬于分子集合間的縱向搜索反應(yīng),負(fù)責(zé)分子之間的信息交換和縱向搜索,跳出基團(tuán)內(nèi)部的局部最優(yōu)解。 合成反應(yīng)過程首先在分子集合中隨機(jī)選擇兩個分子,兩個分子之間發(fā)生反應(yīng)后生成一個新分子。對于被選出的分子,首先依據(jù)分子基團(tuán)評價函數(shù),保留兩個分子中最優(yōu)的分子基團(tuán)作為合成反應(yīng)后分子的一部分。其次,計算剩余基團(tuán)中心與所有已被選中的基團(tuán)中心的距離,根據(jù)最小距離,按照輪盤賭的方式選出下一個基團(tuán)。最后,如果合成反應(yīng)后的分子基團(tuán)數(shù)量少于m,則重復(fù)上一步驟,直至被選出基團(tuán)數(shù)量等于m。剩余任務(wù)點(diǎn)根據(jù)點(diǎn)與基團(tuán)中心的距離插入最近的基團(tuán)空余位置。 假設(shè)反應(yīng)前分子結(jié)構(gòu)為ω1,ω2,反應(yīng)后生成的分子結(jié)構(gòu)為ω′,如果反應(yīng)可以成功發(fā)生,則對能量的要求為 PEω1+KEω1+PEω2+KEω2≥PEω′ (13) 新生成的ω′對應(yīng)的分子動能為 KEω′=(PEω1+KEω1)+(PEω2+KE)-PEω′ (14) 合成反應(yīng)算法偽代碼如算法3所示。 算法3:合成反應(yīng)操作偽代碼 輸入:被選中分子ω1,ω2 (1)ψ′1=min(ω1,ω2),n=0 (2)ω′=ω′+ψ′1 (3)ψ′2=roulette(ω1,ω2) (4)ω′=ω′+ψ′2 (5) whilesize(ω′) (6)ψ′i=roulette(ω1,ω2) (7)ω′=ω′+ψ′i (8) end while (9)complete(ω′) (10) ifPEω1+KEω1+PEω1+KEω2>PEω′then (11)update(PEω′) (12)KEω′=PEω1+KEω1+PEω1+KEω2-PEω′ (13)PopSize←PopSize-1 (14) end if 輸出:反應(yīng)后分子ω′ 2.2.6 分解反應(yīng) 分解反應(yīng)模擬分子碰撞之后,分解為兩個分子的過程,這一過程分子結(jié)構(gòu)有較大變化。分解反應(yīng)屬于分子內(nèi)縱向搜索反應(yīng),負(fù)責(zé)分子內(nèi)各基團(tuán)的數(shù)據(jù)交互與縱向搜索,跳出總體的局部最優(yōu)解。 合成反應(yīng)過程首先在分子集合中隨機(jī)選擇一個分子,發(fā)生反應(yīng)后生成兩個新分子。對于被選出的分子,首先依據(jù)分子基團(tuán)評價函數(shù),按照輪盤賭的方式,選擇出m-2個基團(tuán)保留。剩余任務(wù)點(diǎn)則使用K-means++聚類算法,重新生成兩個基團(tuán),與m-2個基團(tuán)保留,生成一個新分子。最后,上一步驟重復(fù)兩次,生成兩個包含原分子部分信息的新分子。 分子ω,經(jīng)過分解反應(yīng)操作后分子結(jié)構(gòu)變化為ω′1,ω′2, 如果反應(yīng)可以成功發(fā)生,則對能量的要求為 PEω+KEω+EB×σ1×σ2≥ (15) 其中,σ1,σ2∈[0,1] 且為獨(dú)立的隨機(jī)數(shù)。當(dāng)分解反應(yīng)發(fā)生后,則反應(yīng)后的總剩余能量為 Ed=(PEω+KEω+EB×σ1×σ2)- (16) 新生成的分子ω′1,ω′2對應(yīng)的分子動能為 KEω′1=Ed×σ3 (17) KEω′2=Ed×(1-σ3) (18) 其中,σ3∈[0,1] 為隨機(jī)數(shù)。分解反應(yīng)算法偽代碼如算法4所示。 算法4:分解反應(yīng)算法偽代碼 輸入:被選中分子ω (1) (ψ1,ψ2)=roulette(ω) (2) (ψ′i1,ψ′i2)=fd(ψ1,ψ2), 其中 (i=1,2) (3)ω′i=ω-(ψ1+ψ2)+(ψ′i1+ψ′i2) (4) ifPEω+KEω+σ1×σ2×BE≥(PEω1+PEω1) then (5)Ed=PEω+KEω+σ1×σ2×BE-(PEω1+PEω1) (6)KE′ω1=Ed×σ3,KE′ω1=Ed×(1-σ3) (7)BE=BE-σ1×σ2×BE (8)PopSize←PopSize+1 (9) end if 輸出:反應(yīng)后分子ω′1,ω′2,BE 數(shù)學(xué)仿真部分代碼基于C++語言編寫,使用MSVC++14.2編譯器運(yùn)行于Windows 10系統(tǒng)。硬件環(huán)境CPU為Intel Core i7-9750H @ 2.60 GHz,內(nèi)存為16 GB。算法實驗基于TSPLIB數(shù)據(jù)集中的距離對稱實例進(jìn)行數(shù)值仿真測試。為了在保證算法收斂速度的同時兼顧算法效果,算法設(shè)計兩套計算參數(shù)。初始化參數(shù)設(shè)計見表2。 表2 實驗初始參數(shù)設(shè)計 為了驗證算法的有效性,使用TSPLIB中的eil51數(shù)據(jù)集作為實驗數(shù)據(jù),分別設(shè)置無人機(jī)數(shù)量為3,5,10,集結(jié)點(diǎn)位置位于地圖中心的46號點(diǎn),則針對3個場景的兩套參數(shù),算法的執(zhí)行結(jié)果如圖3所示,算法使用兩種參數(shù)獨(dú)立計算20次,計算結(jié)果對比見表3。 表3 參數(shù)對照實驗結(jié)果 參數(shù)1相比于參數(shù)2,分子初始動能initialKE, 初始分子數(shù)量NumInit,最大反應(yīng)步長MaxStep與分子間碰撞反應(yīng)的次數(shù)nc較大,而分子的動能損失率KELossRate和緩沖區(qū)基礎(chǔ)損失率L較小,這使得使用參數(shù)1能獲得更好的收斂結(jié)果,平均最短路徑增大12%~16%,但相應(yīng)的算法收斂時間也會延長,平均延長時間為30%左右。 為了進(jìn)一步驗證算法求解效果與算法執(zhí)行性能,使用TSPLIB數(shù)據(jù)集中的ch150、pr299、pr1002作為實驗數(shù)據(jù)集。算法集結(jié)點(diǎn)位置設(shè)置為區(qū)域中心的任務(wù)點(diǎn),選取改進(jìn)遺傳算法(GAL)[14],和面向任務(wù)的蟻群算法(MOAT-ACO)作為實驗對比驗證實驗效果。改進(jìn)化學(xué)反應(yīng)優(yōu)化算法使用參數(shù)2作為執(zhí)行參數(shù),設(shè)置無人機(jī)數(shù)量的實驗組分別為3,5,10。每個算法獨(dú)立運(yùn)行20次,算法執(zhí)行結(jié)果見表4。 表4 算法對比結(jié)果 對比數(shù)據(jù)可得,改進(jìn)CRO算法的計算時間代價遠(yuǎn)小于改進(jìn)GAL算法與MOAT-ACO算法,計算時間相比于改進(jìn)GAL算法與MOAT-ACO算法分別減少了46.48%~60.14%與54.57%~63.22%,并且隨著任務(wù)點(diǎn)數(shù)量增多,算法在收斂效率的優(yōu)化效果更佳明顯。 在計算結(jié)果差異方面,本文采用單因素方差分析的方法,對3種算法的實驗結(jié)果進(jìn)行分析,改進(jìn)CRO算法在9組實驗中計算結(jié)果均優(yōu)于改進(jìn)GAL算法,在7組實驗種結(jié)果優(yōu)于MOAT-ACO算法,整體任務(wù)規(guī)劃效果最顯著。 基于pr1002數(shù)據(jù)集的3機(jī)任務(wù)規(guī)劃收斂曲線如圖4所示。其中基于分組改進(jìn)CRO算法的任務(wù)規(guī)劃收斂速度最快,全程在其余兩種啟發(fā)式算法下方;改進(jìn)GAL算法前期收斂速度較快,但容易陷入局部最優(yōu)解,而MOAT-ACO算法的收斂速度則顯著落后于改進(jìn)CRO算法。 基于上述數(shù)據(jù)可知,基于聚類后再尋優(yōu)的思路的改進(jìn)CRO算法在面對無人機(jī)集群任務(wù)規(guī)劃問題,尤其是大規(guī)模無人機(jī)集群任務(wù)規(guī)劃算法時的表現(xiàn)要優(yōu)于一般的啟發(fā)式算法。由于采用了聚類和分組思想,可以確保無人機(jī)集群任務(wù)分配時更高的效率和更低的時間代價,同時依靠合成反應(yīng)與分解反應(yīng),分別負(fù)責(zé)基團(tuán)內(nèi)的縱向搜索和基團(tuán)間的縱向搜索,跳出局部最優(yōu)解,實現(xiàn)滿足要求的無人機(jī)集群快速任務(wù)規(guī)劃,可以有效針對無人機(jī)集群的實際應(yīng)用場景。 為了模擬真實的無人機(jī)使用場景,并測試算法在機(jī)載電腦上的穩(wěn)定性和表現(xiàn),本文設(shè)計了基于PX4飛控與ROS(the robot operating system)系統(tǒng)的硬件在環(huán)仿真(hardware in the loop,HITL)實驗結(jié)構(gòu)如圖5(a)所示,單機(jī)實驗場景如圖5(b)所示。 圖5 基于PX4與ROS平臺的硬件在環(huán)仿真 算法計算機(jī)使用NVIDIA Xavier開發(fā)板,安裝基于ARM64的Ubuntu 18.04系統(tǒng),使用8核心ARM v8.2 64位CPU,內(nèi)存16 G??焖偃蝿?wù)規(guī)劃算法使用C++語言,基于ROS系統(tǒng)編寫,運(yùn)行于算法計算機(jī)上。飛控硬件使用Pixhawk FMUv2平臺,軟件使用PX4代碼固件。無人機(jī)的模型及仿真環(huán)境由X-plane軟件提供,與 Pixhawk通過串口相連接實現(xiàn)數(shù)據(jù)在環(huán)交互。 由于X-plane只支持單機(jī)的HITL仿真,因此使用3臺電腦進(jìn)行3機(jī)的固定翼無人機(jī)集群任務(wù)規(guī)劃HITL仿真實驗,通信使用NVIDIA Xavier的WIFI模塊,基于Mavlink協(xié)議,實現(xiàn)算法計算機(jī)之間的數(shù)據(jù)交互,完成集群任務(wù)規(guī)劃。 實驗選擇參數(shù)2作為執(zhí)行參數(shù),任務(wù)點(diǎn)在10000m×10000m的范圍內(nèi)隨機(jī)生成,數(shù)量為100、500、1000,集結(jié)點(diǎn)位于區(qū)域中心,每架無人機(jī)初始位于集結(jié)點(diǎn)上方盤旋等待。每架無人機(jī)基于改進(jìn)CRO算法獨(dú)立進(jìn)行集群任務(wù)規(guī)劃,任務(wù)規(guī)劃得到的每個子任務(wù)由距離子任務(wù)中心最近的無人機(jī)按照18 m/s的固定巡航速度依次執(zhí)行。每架無人機(jī)的任務(wù)規(guī)劃結(jié)果通過廣播的方式在集群中交互,選擇所有規(guī)劃結(jié)果中總體時間代價最小的規(guī)劃結(jié)果作為最終集群任務(wù)規(guī)劃結(jié)果并執(zhí)行。 任務(wù)規(guī)劃結(jié)果與改進(jìn)GAL算法、MOAT-ACO算法、貪心算法的對比見表5。 表5 NVIDIA Xavier環(huán)境下隨機(jī)任務(wù)執(zhí)行結(jié)果 基于上述實驗數(shù)據(jù)對比可知,在基于嵌入式的機(jī)載電腦上,改進(jìn)CRO算法的任務(wù)規(guī)劃時間和任務(wù)完成時間均優(yōu)于改進(jìn)GAL算法和MOAT-ACO算法。 實驗設(shè)計的任務(wù)場景下,CRO算法相比于GAL算法,平均任務(wù)規(guī)劃時間分別減小53.70%、60.73%、64.60%,平均任務(wù)完成時間代價分別減小22.96%、32.30%、35.51%;CRO算法相比于MOAT-ACO算法,平均任務(wù)規(guī)劃時間分別減小58.62%、67.80%、69.50%,平均任務(wù)完成時間代價分別減小20.32%、28.21%、29.12%。而貪心算法隨任務(wù)規(guī)劃時間代價較小,但由于無法脫離局部最優(yōu)解,總?cè)蝿?wù)平均完成時間要遠(yuǎn)大于上述3種算法?;诟倪M(jìn)CRO算法的固定翼無人機(jī)集群快速任務(wù)規(guī)劃算法,在機(jī)載計算機(jī)的真實場景下可以有效降低任務(wù)規(guī)劃時間和任務(wù)完成時間,提高任務(wù)執(zhí)行效率。 本文提出了一種基于聚類算法和改進(jìn)分組CRO模型的固定翼無人機(jī)集群任務(wù)規(guī)劃算法,用以解決真實場景下固定翼無人機(jī)集群任務(wù)規(guī)劃問題。通過數(shù)值仿真和HITL仿真可以得到如下結(jié)論:該算法相比于其它啟發(fā)式算法擁有更快的收斂速度和更穩(wěn)定的收斂結(jié)果,尤其是應(yīng)對大規(guī)模任務(wù)規(guī)劃時,隨著任務(wù)點(diǎn)數(shù)量增加算法的收斂速度和收斂效果優(yōu)化愈加明顯;同時算法更加貼近實際無人機(jī)應(yīng)用場景,根據(jù)HITL仿真結(jié)果可知,算法可以有效應(yīng)對機(jī)載計算機(jī)環(huán)境,具備實際的使用價值。2.2 基于分組優(yōu)化的改進(jìn)CRO算法
KEω2-PEω′1+PEω′2)×(1-q)
PEω′1+PEω′2
(PEω′1+PEω′2)3 實驗結(jié)果及分析
3.1 算法的數(shù)值仿真及分析
3.2 基于PX4與ROS平臺的硬件在環(huán)仿真及分析
4 結(jié)束語