亚洲免费av电影一区二区三区,日韩爱爱视频,51精品视频一区二区三区,91视频爱爱,日韩欧美在线播放视频,中文字幕少妇AV,亚洲电影中文字幕,久久久久亚洲av成人网址,久久综合视频网站,国产在线不卡免费播放

        ?

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

        2023-11-03 11:52:14吳昌偉謝紅薇
        計算機(jī)工程與設(shè)計 2023年10期
        關(guān)鍵詞:基團(tuán)集群聚類

        吳昌偉,謝紅薇

        (太原理工大學(xué) 軟件學(xué)院,山西 太原 030600)

        0 引 言

        由于單獨(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ī)劃。

        1 固定翼無人機(jī)集群任務(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取最小值。

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

        在面對大規(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)

        2.1 K-means++聚類算法

        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}。

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

        化學(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+
        KEω2-PEω′1+PEω′2)×(1-q)

        (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≥
        PEω′1+PEω′2

        (15)

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

        Ed=(PEω+KEω+EB×σ1×σ2)-
        (PEω′1+PEω′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

        3 實驗結(jié)果及分析

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

        數(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)用場景。

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

        為了模擬真實的無人機(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í)行效率。

        4 結(jié)束語

        本文提出了一種基于聚類算法和改進(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)境,具備實際的使用價值。

        猜你喜歡
        基團(tuán)集群聚類
        海上小型無人機(jī)集群的反制裝備需求與應(yīng)對之策研究
        一種無人機(jī)集群發(fā)射回收裝置的控制系統(tǒng)設(shè)計
        電子制作(2018年11期)2018-08-04 03:25:40
        R基團(tuán)篩選技術(shù)用于HDACIs的分子設(shè)計
        基于DBSACN聚類算法的XML文檔聚類
        電子測試(2017年15期)2017-12-18 07:19:27
        Python與Spark集群在收費(fèi)數(shù)據(jù)分析中的應(yīng)用
        勤快又呆萌的集群機(jī)器人
        芳烴ArCOR的構(gòu)象分析和基團(tuán)對親電取代反應(yīng)的定位作用
        基于改進(jìn)的遺傳算法的模糊聚類算法
        內(nèi)含雙二氯均三嗪基團(tuán)的真絲織物抗皺劑的合成
        一種層次初始的聚類個數(shù)自適應(yīng)的聚類方法研究
        国产精品农村妇女一区二区三区 | 一区二区三区亚洲视频| 风韵少妇性饥渴推油按摩视频| 欧洲一卡2卡三卡4卡免费网站| 久久半精品国产99精品国产| 国语对白三级在线观看| 国产在线观看91一区二区三区| 国产乱码精品一区二区三区四川人| 99爱这里只有精品| 中文字幕成人精品久久不卡| 亚洲视频在线免费不卡| 69一区二三区好的精华| 国内精品一区视频在线播放| 一区二区三区熟妇人妻18| 中文字幕本久久精品一区| 国产免费av片在线观看| 国产福利片无码区在线观看| 亚洲国产综合精品中文| 欧美性猛交aaaa片黑人| 摸进她的内裤里疯狂揉她动视频 | 免费在线亚洲视频| 女同久久精品国产99国产精| 午夜被窝精品国产亚洲av香蕉| 边啃奶头边躁狠狠躁| a级福利毛片| 网红尤物泛滥白浆正在播放| 韩国三级在线观看久| 欲妇荡岳丰满少妇岳| 国产成人精品一区二免费网站| 在线播放草猛免费视频| 国产精品成人久久电影| 亚洲AⅤ无码片一区二区三区| 亚洲一区二区av免费观看| 丰满大爆乳波霸奶| 最新四色米奇影视777在线看| 日本一区二区三区专区| 午夜国产视频一区二区三区| 奇米影视777撸吧| 日本加勒比东京热日韩| 久久夜色精品国产噜噜噜亚洲av| 欧美人与禽zozzo性伦交|