針對固定翼無人機集群的快速任務規(guī)劃算法

吳昌偉，謝紅薇

(太原理工大學 軟件學院，山西 太原 030600)

0 引 言

由于單獨無人機存在諸如航程有限、魯棒性不足等問題，無法處理大型復雜場景下的多并發(fā)任務。因此多架無人機進行任務協(xié)同組成無人機集群共同執(zhí)行任務成為無人機主要的使用場景[1]?？梢宰灾鬟M行任務規(guī)劃的多無人機系統(tǒng)(multi-unmanned aerial system，MUAS)以及任務規(guī)劃的相關研究也逐漸成為近年來研究的熱點[2，3]。

Peng等[4]基于混合粒子群算法優(yōu)化了粒子群多樣性，提高了任務規(guī)劃算法的收斂結果可靠性。吳蔚楠等[5]提出基于改進遺傳算法集群任務規(guī)劃算法，適用于多無人機場景，并能避免規(guī)劃的“單點失效”問題。CAI等[6]使用小生境和粒子群算法，利用貫續(xù)化的方法尋找最優(yōu)路徑，優(yōu)化算法收斂效果。Wu等[7]通過雙抑制分割的方法，利用相關性改進蜂群算法形成任務鏈，實現(xiàn)了任務的多維連接，優(yōu)化任務規(guī)劃結果。KIM等[8]利用社會學習粒子群優(yōu)化最大化目標函數(shù)，提高集群任務規(guī)劃的計算效率。FU等[9]基于任務序列機制和協(xié)商一致算法為無人機集群實現(xiàn)無沖突任務規(guī)劃，但規(guī)劃結果無法脫離局部最優(yōu)。Amorim等[10]基于智能群任務指派算法(swarm-GAP)算法，提出了利用3種群間隙的優(yōu)化的方式，優(yōu)化了任務規(guī)劃收斂效果。Mei等[11]基于混合遺傳算法，利用雙滿意度指標分層迭代求解，提高任務規(guī)劃效率。

上述算法和實驗大多是基于電腦進行數(shù)據(jù)處理和仿真實驗的，這種集中式系統(tǒng)在實際應用中存在中心節(jié)點，這種模式相比于分布式模型算法響應時間長，算法模型的穩(wěn)定性強依賴于中心節(jié)點的穩(wěn)定運行，中心節(jié)點故障會導致整個算法系統(tǒng)故障；并且中心節(jié)點通信壓力大，算法擴展存在上限。同時上述算法和實驗沒有考慮真實無人機控制單元的大多是基于嵌入式操作系統(tǒng)的小型機載計算機，算力無法和實驗用計算機相比，而實際的任務點個數(shù)也往往增加到幾百個，遠復雜于實驗場景設計，并且固定翼無人機因為飛行速度快導致集群狀態(tài)變化快，計算時間會造成更大的影響。因此上述算法在固定翼無人機集群的實際應用場景下存在一定的局限性。

針對以上的問題，本文設計了一種基于多智能體聚類模型和改進化學反應優(yōu)化算法(chemical reaction optimization，CRO)的組合優(yōu)化算法，通過多智能體獨立聚類的方式擴大初始搜索范圍，簡化搜索流程，提高搜索效率，并基于分組模型改進優(yōu)化了CRO算法，引入基團概念的同時重新設計了反應模型，依據(jù)CRO算法中的代價函數(shù)勢能最小化的思想，為固定翼無人機集群實現(xiàn)快速任務規(guī)劃。

1 固定翼無人機集群任務規(guī)劃問題建模

在實際的偵察搜索等任務中，受限于充電點或油料補充點的位置，數(shù)據(jù)分析及無人機維護等實際需要，無人機集群通常存在一個聚集點H，無人機在此處出發(fā)執(zhí)行任務，并在任務結束后返回聚集點休整。記無人機集群數(shù)量為m，任務數(shù)量為n，記R={r1，r2，…，rm} 為無人機集群，T={t1，t2，…，tn} 為待執(zhí)行任務組。無人機集群以固定速度遍歷執(zhí)行T中所有任務，為了最大限度利用無人機資源，T中每個任務需要被執(zhí)行且只被執(zhí)行一次，以最短時間完成集群的所有任務作為算法優(yōu)化目標。

對于無人機ri， 設其對應的待執(zhí)行任務組為Ti={ti1，ti2，…tik}∈T， 則其搜索長度li為

(1)

lmax=max{l1，l2，…，lm}

(2)

無人機集群完成任務時間與最長搜索長度lmax成正比，因此算法優(yōu)化目標等價于優(yōu)化集群中無人機執(zhí)行的最長搜索長度，使算法最長搜索長度最短，即使lmax取最小值。

2 固定翼無人機集群任務規(guī)劃優(yōu)化算法

在面對大規(guī)模任務時，常用的分組遺傳等算法的計算時間較長，算法復雜度往往也不支持將算法部署于機載計算機環(huán)境中。

因此為了解決實際情況下固定翼無人機集群的任務規(guī)劃問題，使用任務拆分降維的思路，將大規(guī)模的集群任務，通過聚類算法拆解成獨立的子任務組，再通過CRO算法優(yōu)化任務與任務組劃分，實現(xiàn)固定翼無人機集群的快速任務規(guī)劃。算法詳細流程如下：

(1)每架無人機基于K-means++聚類算法，各自獨立的將待執(zhí)行任務組拆分為子任務組，設T(k)為無人機rk計算得到的任務分組結果，則有

(3)

(4)

2.1 K-means++聚類算法

K-means++聚類算法是基于K-means聚類算法的一種改進算法，是一種基于歐氏距離的聚類算法。算法基于距離越近的兩者相似度越高的思想，通過距離權重生成概率選擇處下一個合適的聚類中心，確保初始聚類的選擇足夠離散，提供了更好的穩(wěn)定聚類結果。通過K-means++聚類算法對集群任務點執(zhí)行的聚類操作，可以將多執(zhí)行機構多任務場景降維成單執(zhí)行機構多任務場景，極大簡化了場景模型的同時減少了每個任務場景中的任務點數(shù)量，并且保證聚類中心分布足夠均勻，提高算法的收斂速度并保證最終規(guī)劃結果的穩(wěn)定性。

在本文的模型中，將每個聚類記為CP={cp1，cp2，…，cpm}， 對應的聚類中心記為C={c1，c2，…，cm}， 其在分組問題中流程如下：

(1)隨機選擇一個任務點，初始化為聚類cp1的聚類中心，其聚類中心記為c1；

(3)重復步驟(2)，直到聚類中心數(shù)量為m，完成聚類初始化；

(6)重復上述(4)、(5)，直到所有聚類中心點迭代的最大誤差變化小于期望目標δ。算法偽代碼如算法1所示。

算法1：K-means++聚類算法偽代碼

輸入：待執(zhí)行任務組T={t1，t2，…，tn}， 無人機數(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}。

2.2 基于分組優(yōu)化的改進CRO算法

化學反應優(yōu)化算法是Albert Y.S. Lam和Victor O.K. Li等提出的一種元啟發(fā)式算法。算法的基礎思想是基于模擬化學反應來解決多目標多任務中的群體優(yōu)化問題。算法中每一個任務狀態(tài)被描述成一個特定結構的分子，任務狀態(tài)的衡量函數(shù)被描述為分子勢能，同時引入分子動能的概念描述任務狀態(tài)的穩(wěn)定程度。算法演進過程中會向更穩(wěn)定的狀態(tài)，即向分子勢能最低的狀態(tài)變化。最終分子勢能降至最低時，算法處于穩(wěn)定狀態(tài)，此時的任務狀態(tài)即為解算的最優(yōu)解。

原始CRO算法具有較好的全局搜索能力和搜索范圍，且基于分子單元的描述與分布式模型相匹配，適用于解決分布式場景下的最優(yōu)解的問題。但在解決大規(guī)模問題的時候，存在算法結果收斂速度慢，受初始狀態(tài)影響較大的問題，并且計算代價往往比較大。

針對上述問題和使用場景中分布式分組任務規(guī)劃的場景，加快算法的收斂速度，設計了基于分組優(yōu)化的改進CRO算法模型，引入逸散能量緩沖區(qū)和2-opt優(yōu)化算法，并重新設計了分子反應，以保留更多的有效信息用以提高CRO算法模型的收斂速度，優(yōu)化集群任務規(guī)劃效果，使算法更切合固定翼無人機集群的真實使用場景。其中單個無人機執(zhí)行的算法流程如圖1所示。

圖1 改進CRO算法流程

任務規(guī)劃問題的每一個解方案在算法中視作一個分子，在算法初始化時生成指定規(guī)模的分子集合，并計算分配各分子的初始化參數(shù)。解方案中的子任務組視作分子的一個基團，基團個數(shù)與集群中無人機數(shù)量相等，如上文所述，分子的總勢能由該分子中勢能最大的基團決定。算法詳細參數(shù)見表1。

算法執(zhí)行步驟如下：

(1)分子集合初始化，生成NumInit數(shù)量個分子初始化，并通過2-opt算法進行初始優(yōu)化；

(2)生成隨機數(shù)p∈[0，1]， 當p≥p1， 執(zhí)行雙分子無效碰撞；當p2≥p>p1時，執(zhí)行合成反應，否則執(zhí)行分解反應；

(3)根據(jù)反應執(zhí)行結果，更新分子集合，更新最小分子結構和最小分子勢能，并更新能量緩沖器內(nèi)的能量，Step=Step+1；

(4)如果Step

改進CRO算法具體流程如圖1所示。分子及基團評價優(yōu)化，能量緩沖器優(yōu)化和改進CRO算法各反應設計在本文各小節(jié)介紹。

2.2.1 分子勢能的計算及基團的評價指數(shù)

對于分子ω，其存在分子基團為 [ψ1，ψ2，…ψm]， 則分子的勢能PEω設計為

PEω=max{L(ψ1)，L(ψ2)，…L(ψm)}

(5)

其中，函數(shù)L(x) 為基團x的當前路徑長度。

對于分子基團ψi， 設計其評價指標為

(6)

其中，ci為ψi的聚類中心，tk為屬于ψi的任務點，mψi為ψi中任務點的數(shù)量。J(ψi) 越小表明基團越符合期望預期。

2.2.2 能量緩沖器優(yōu)化

能量緩沖器(energy buffer，EB)為一個獨立的反應能量存儲單元，每次反應重新分配反應分子與能量緩沖器之間的能量。反應前后能量差為正時，能量差存入能量緩沖器；并在分解反應、合成反應的反應前后能量差為負時，從能量緩沖器中支出能量為反應提供能量支持。能量緩沖器邏輯概念等價于真實反應中的環(huán)境溫度等外界反應條件。

能量緩沖器主要作用是為了鼓勵擴大反應搜索區(qū)域，跳出局部最優(yōu)解。但原始算法中的能量緩沖器與外界無能量溝通，容易導致反應搜索區(qū)域過分擴大，算法結果收斂慢等問題。為了提高算法的局部搜索能力，并加速收斂過程，將能量緩沖器改進為每次反應執(zhí)行時會向外界環(huán)境逸散能量，損失量與EB中當前能量總量有關，其損失函數(shù)如下

(7)

EB′=EB*(1-EBLossRate)

(8)

其中，EB′為迭代后能量緩沖器內(nèi)的能量，EBLossRate為每次迭代的EB能量損失率，L∈[0，1] 為基礎損失率，R>0為EB能量上限。

2.2.3 2-opt算法

在任務規(guī)劃這類問題上，解空間的大小與任務數(shù)量為指數(shù)級關系。當問題規(guī)模增大時，傳統(tǒng)的算法很難產(chǎn)生較好的效果。而局部搜索算法和啟發(fā)式算法的結合，往往能使算法在計算性能，計算結果方面獲得較好的性能[12]。

同樣的，本文引入2-opt局部搜索算法[13]，在CRO算法之前對分子結構進行提前優(yōu)化，提前排除一些明顯錯誤，降低對錯誤分子和結構重復計算的概率。算法效果如圖2所示。

圖2 2-opt算法優(yōu)化效果

2.2.4 雙分子間無效碰撞

雙分子之間無效碰撞模擬分子之間發(fā)生輕微碰撞，分子結構和各基團結構輕微改變的過程。雙分子間無效碰撞屬于橫向搜索反應，負責在算法各基團內(nèi)實現(xiàn)的局部搜索結果優(yōu)化。

雙分子間無效碰撞過程首先在分子集合中隨機選擇兩個分子，兩個分子同時執(zhí)行反應改變自己分子結構。以其中一個分子為例，對于該被選出的分子，依據(jù)各基團的評價指標，按照輪盤賭的方式選擇出一個待反應的基團，在被選出的基團中隨機選擇起點和終點，保留兩點中間的部分，基團的剩余部分則按照另一分子中未被選中點的相對順序，依次置入剩余位置。

假設反應前分子為ω1，ω2， 反應后分子改變?yōu)棣亍?，ω′2， 如果反應可以成功發(fā)生，則對能量的要求為

PEω1+KEω1+PEω2+KEω2≥PEω′1+PEω′2

(9)

則視作反應成功進行，否則持續(xù)嘗試，直到反應成功或嘗試次數(shù)達到nc。反應成功后，新生成分子動能為

KEω′1=(PEω1+KEω1-PEω′1)×q

(10)

KEω′2=(PEω2+KEω2-PEω′2)×q

(11)

其中，q∈[1-KELossRate，1] 的隨機數(shù)。反應的剩余能量則入能量緩沖器中，即

BE=BE+(PEω1+KEω1+PEω2+
KEω2-PEω′1+PEω′2)×(1-q)

(12)

雙分子間無效碰撞反應偽代碼如算法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)

輸出：反應后分子ω1，ω2，EB

2.2.5 合成反應

合成反應模擬兩個分子間發(fā)生碰撞后合并為一個分子的過程，這一過程分子結構有較大變化。合成反應屬于分子集合間的縱向搜索反應，負責分子之間的信息交換和縱向搜索，跳出基團內(nèi)部的局部最優(yōu)解。

合成反應過程首先在分子集合中隨機選擇兩個分子，兩個分子之間發(fā)生反應后生成一個新分子。對于被選出的分子，首先依據(jù)分子基團評價函數(shù)，保留兩個分子中最優(yōu)的分子基團作為合成反應后分子的一部分。其次，計算剩余基團中心與所有已被選中的基團中心的距離，根據(jù)最小距離，按照輪盤賭的方式選出下一個基團。最后，如果合成反應后的分子基團數(shù)量少于m，則重復上一步驟，直至被選出基團數(shù)量等于m。剩余任務點根據(jù)點與基團中心的距離插入最近的基團空余位置。

假設反應前分子結構為ω1，ω2，反應后生成的分子結構為ω′，如果反應可以成功發(fā)生，則對能量的要求為

PEω1+KEω1+PEω2+KEω2≥PEω′

(13)

新生成的ω′對應的分子動能為

KEω′=(PEω1+KEω1)+(PEω2+KE)-PEω′

(14)

合成反應算法偽代碼如算法3所示。

算法3：合成反應操作偽代碼

輸入：被選中分子ω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

輸出：反應后分子ω′

2.2.6 分解反應

分解反應模擬分子碰撞之后，分解為兩個分子的過程，這一過程分子結構有較大變化。分解反應屬于分子內(nèi)縱向搜索反應，負責分子內(nèi)各基團的數(shù)據(jù)交互與縱向搜索，跳出總體的局部最優(yōu)解。

合成反應過程首先在分子集合中隨機選擇一個分子，發(fā)生反應后生成兩個新分子。對于被選出的分子，首先依據(jù)分子基團評價函數(shù)，按照輪盤賭的方式，選擇出m-2個基團保留。剩余任務點則使用K-means++聚類算法，重新生成兩個基團，與m-2個基團保留，生成一個新分子。最后，上一步驟重復兩次，生成兩個包含原分子部分信息的新分子。

分子ω，經(jīng)過分解反應操作后分子結構變化為ω′1，ω′2， 如果反應可以成功發(fā)生，則對能量的要求為

PEω+KEω+EB×σ1×σ2≥
PEω′1+PEω′2

(15)

其中，σ1，σ2∈[0，1] 且為獨立的隨機數(shù)。當分解反應發(fā)生后，則反應后的總剩余能量為

Ed=(PEω+KEω+EB×σ1×σ2)-
(PEω′1+PEω′2)

(16)

新生成的分子ω′1，ω′2對應的分子動能為

KEω′1=Ed×σ3

(17)

KEω′2=Ed×(1-σ3)

(18)

其中，σ3∈[0，1] 為隨機數(shù)。分解反應算法偽代碼如算法4所示。

算法4：分解反應算法偽代碼

輸入：被選中分子ω

(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

輸出：反應后分子ω′1，ω′2，BE

3 實驗結果及分析

3.1 算法的數(shù)值仿真及分析

數(shù)學仿真部分代碼基于C++語言編寫，使用MSVC++14.2編譯器運行于Windows 10系統(tǒng)。硬件環(huán)境CPU為Intel Core i7-9750H @ 2.60 GHz，內(nèi)存為16 GB。算法實驗基于TSPLIB數(shù)據(jù)集中的距離對稱實例進行數(shù)值仿真測試。為了在保證算法收斂速度的同時兼顧算法效果，算法設計兩套計算參數(shù)。初始化參數(shù)設計見表2。

表2 實驗初始參數(shù)設計

為了驗證算法的有效性，使用TSPLIB中的eil51數(shù)據(jù)集作為實驗數(shù)據(jù)，分別設置無人機數(shù)量為3，5，10，集結點位置位于地圖中心的46號點，則針對3個場景的兩套參數(shù)，算法的執(zhí)行結果如圖3所示，算法使用兩種參數(shù)獨立計算20次，計算結果對比見表3。

表3 參數(shù)對照實驗結果

參數(shù)1相比于參數(shù)2，分子初始動能initialKE， 初始分子數(shù)量NumInit，最大反應步長MaxStep與分子間碰撞反應的次數(shù)nc較大，而分子的動能損失率KELossRate和緩沖區(qū)基礎損失率L較小，這使得使用參數(shù)1能獲得更好的收斂結果，平均最短路徑增大12%～16%，但相應的算法收斂時間也會延長，平均延長時間為30%左右。

為了進一步驗證算法求解效果與算法執(zhí)行性能，使用TSPLIB數(shù)據(jù)集中的ch150、pr299、pr1002作為實驗數(shù)據(jù)集。算法集結點位置設置為區(qū)域中心的任務點，選取改進遺傳算法(GAL)[14]，和面向任務的蟻群算法(MOAT-ACO)作為實驗對比驗證實驗效果。改進化學反應優(yōu)化算法使用參數(shù)2作為執(zhí)行參數(shù)，設置無人機數(shù)量的實驗組分別為3，5，10。每個算法獨立運行20次，算法執(zhí)行結果見表4。

表4 算法對比結果

對比數(shù)據(jù)可得，改進CRO算法的計算時間代價遠小于改進GAL算法與MOAT-ACO算法，計算時間相比于改進GAL算法與MOAT-ACO算法分別減少了46.48%～60.14%與54.57%～63.22%，并且隨著任務點數(shù)量增多，算法在收斂效率的優(yōu)化效果更佳明顯。

在計算結果差異方面，本文采用單因素方差分析的方法，對3種算法的實驗結果進行分析，改進CRO算法在9組實驗中計算結果均優(yōu)于改進GAL算法，在7組實驗種結果優(yōu)于MOAT-ACO算法，整體任務規(guī)劃效果最顯著。

基于pr1002數(shù)據(jù)集的3機任務規(guī)劃收斂曲線如圖4所示。其中基于分組改進CRO算法的任務規(guī)劃收斂速度最快，全程在其余兩種啟發(fā)式算法下方；改進GAL算法前期收斂速度較快，但容易陷入局部最優(yōu)解，而MOAT-ACO算法的收斂速度則顯著落后于改進CRO算法。

基于上述數(shù)據(jù)可知，基于聚類后再尋優(yōu)的思路的改進CRO算法在面對無人機集群任務規(guī)劃問題，尤其是大規(guī)模無人機集群任務規(guī)劃算法時的表現(xiàn)要優(yōu)于一般的啟發(fā)式算法。由于采用了聚類和分組思想，可以確保無人機集群任務分配時更高的效率和更低的時間代價，同時依靠合成反應與分解反應，分別負責基團內(nèi)的縱向搜索和基團間的縱向搜索，跳出局部最優(yōu)解，實現(xiàn)滿足要求的無人機集群快速任務規(guī)劃，可以有效針對無人機集群的實際應用場景。

3.2 基于PX4與ROS平臺的硬件在環(huán)仿真及分析

為了模擬真實的無人機使用場景，并測試算法在機載電腦上的穩(wěn)定性和表現(xiàn)，本文設計了基于PX4飛控與ROS(the robot operating system)系統(tǒng)的硬件在環(huán)仿真(hardware in the loop，HITL)實驗結構如圖5(a)所示，單機實驗場景如圖5(b)所示。

圖5 基于PX4與ROS平臺的硬件在環(huán)仿真

算法計算機使用NVIDIA Xavier開發(fā)板，安裝基于ARM64的Ubuntu 18.04系統(tǒng)，使用8核心ARM v8.2 64位CPU，內(nèi)存16 G?？焖偃蝿找?guī)劃算法使用C++語言，基于ROS系統(tǒng)編寫，運行于算法計算機上。飛控硬件使用Pixhawk FMUv2平臺，軟件使用PX4代碼固件。無人機的模型及仿真環(huán)境由X-plane軟件提供，與 Pixhawk通過串口相連接實現(xiàn)數(shù)據(jù)在環(huán)交互。

由于X-plane只支持單機的HITL仿真，因此使用3臺電腦進行3機的固定翼無人機集群任務規(guī)劃HITL仿真實驗，通信使用NVIDIA Xavier的WIFI模塊，基于Mavlink協(xié)議，實現(xiàn)算法計算機之間的數(shù)據(jù)交互，完成集群任務規(guī)劃。

實驗選擇參數(shù)2作為執(zhí)行參數(shù)，任務點在10000m×10000m的范圍內(nèi)隨機生成，數(shù)量為100、500、1000，集結點位于區(qū)域中心，每架無人機初始位于集結點上方盤旋等待。每架無人機基于改進CRO算法獨立進行集群任務規(guī)劃，任務規(guī)劃得到的每個子任務由距離子任務中心最近的無人機按照18 m/s的固定巡航速度依次執(zhí)行。每架無人機的任務規(guī)劃結果通過廣播的方式在集群中交互，選擇所有規(guī)劃結果中總體時間代價最小的規(guī)劃結果作為最終集群任務規(guī)劃結果并執(zhí)行。

任務規(guī)劃結果與改進GAL算法、MOAT-ACO算法、貪心算法的對比見表5。

表5 NVIDIA Xavier環(huán)境下隨機任務執(zhí)行結果

基于上述實驗數(shù)據(jù)對比可知，在基于嵌入式的機載電腦上，改進CRO算法的任務規(guī)劃時間和任務完成時間均優(yōu)于改進GAL算法和MOAT-ACO算法。

實驗設計的任務場景下，CRO算法相比于GAL算法，平均任務規(guī)劃時間分別減小53.70%、60.73%、64.60%，平均任務完成時間代價分別減小22.96%、32.30%、35.51%；CRO算法相比于MOAT-ACO算法，平均任務規(guī)劃時間分別減小58.62%、67.80%、69.50%，平均任務完成時間代價分別減小20.32%、28.21%、29.12%。而貪心算法隨任務規(guī)劃時間代價較小，但由于無法脫離局部最優(yōu)解，總任務平均完成時間要遠大于上述3種算法?；诟倪MCRO算法的固定翼無人機集群快速任務規(guī)劃算法，在機載計算機的真實場景下可以有效降低任務規(guī)劃時間和任務完成時間，提高任務執(zhí)行效率。

4 結束語

本文提出了一種基于聚類算法和改進分組CRO模型的固定翼無人機集群任務規(guī)劃算法，用以解決真實場景下固定翼無人機集群任務規(guī)劃問題。通過數(shù)值仿真和HITL仿真可以得到如下結論：該算法相比于其它啟發(fā)式算法擁有更快的收斂速度和更穩(wěn)定的收斂結果，尤其是應對大規(guī)模任務規(guī)劃時，隨著任務點數(shù)量增加算法的收斂速度和收斂效果優(yōu)化愈加明顯；同時算法更加貼近實際無人機應用場景，根據(jù)HITL仿真結果可知，算法可以有效應對機載計算機環(huán)境，具備實際的使用價值。