多無(wú)人機(jī)協(xié)同任務(wù)分群方案研究

王 毅 謝瑞煜 楊利斌 趙建軍

（海軍航空大學(xué) 煙臺(tái) 264001）

1 引言

多UAV聯(lián)合起來(lái)協(xié)同完成搜索、偵察、監(jiān)視、打擊等作戰(zhàn)任務(wù)，已經(jīng)在軍事上有初步應(yīng)用，顯示出十分良好的應(yīng)用前景，受到越來(lái)越多研究者的關(guān)注。多UAV對(duì)海及對(duì)地協(xié)同偵察是很有代表性的問(wèn)題。偵察問(wèn)題中，由多UAV同時(shí)對(duì)給定區(qū)域的多個(gè)任務(wù)點(diǎn)進(jìn)行偵察，由于偵察任務(wù)較多，需要事先進(jìn)行任務(wù)分群和任務(wù)分配，任務(wù)分群不僅可以較清楚地反映戰(zhàn)場(chǎng)態(tài)勢(shì)，而且可以減少系統(tǒng)的計(jì)算量。使UAV之間相互協(xié)作，依據(jù)具體的指標(biāo)要求提高整體的偵察效率［1］。

2 多UAV協(xié)同偵察任務(wù)分群

2.1 偵察任務(wù)分群建模

多UAV偵察任務(wù)分群?jiǎn)栴}的數(shù)學(xué)語(yǔ)言描述為，將任務(wù)集合T={T1,T2,…,TM}按一定原則劃分為一系列任務(wù)簇A={A1,A2,…,AS}，Ai中成員為{Ti1,Ti2,…,Timax} ，i=1,2,…,S ，【2】滿足：

將UAV集合V={V1,V2,…,VN}劃分為不同編隊(duì)F={F1,F2,…,Fk}，滿足：

定義“編隊(duì)-任務(wù)簇”分配矩陣：

2.2 任務(wù)分群性能優(yōu)化指標(biāo)分析

2.2.1 任務(wù)群分布指標(biāo)

2.2.2 任務(wù)數(shù)量均衡指標(biāo)

定義任務(wù)數(shù)量均衡率：

2.2.3 巡航時(shí)間均衡指標(biāo)

要達(dá)到比較均衡，應(yīng)使每架飛機(jī)的巡航時(shí)間基本相同，根據(jù)分類算法得到的子圖分別運(yùn)用禁忌搜索算法求得其最短偵察路徑ψi,i=1,2,…,S和最短偵察時(shí)間 t(ψi),i=1,2,…,S［4］。

定義任務(wù)執(zhí)行時(shí)間均衡率：

若η接近于1，則上面劃分的任務(wù)就可以接受。否則的話，根據(jù)t(ψi),i=1,2,…,S的大小用局部搜索算法調(diào)整，從而調(diào)整各分區(qū)內(nèi)點(diǎn)的個(gè)數(shù)，直至任務(wù)達(dá)到均衡。

2.2.4 總體優(yōu)化函數(shù)建模

針對(duì)任務(wù)分群性能優(yōu)化指標(biāo)［5～7］，得到任務(wù)分群的總優(yōu)化函數(shù)值計(jì)算方式：

2.3 K均值動(dòng)態(tài)聚類任務(wù)分群算法

聚類分析就是按照一定的規(guī)律和要求對(duì)事物進(jìn)行區(qū)分和分類的過(guò)程，在這一過(guò)程中沒(méi)有任何關(guān)于分類的先驗(yàn)知識(shí)，沒(méi)有教師指導(dǎo)，僅靠事物間的相似性作為類屬劃分的準(zhǔn)則。聚類屬于無(wú)監(jiān)督機(jī)器學(xué)習(xí)的范疇。K均值算法的一個(gè)特點(diǎn)是在每次迭代中都要考察每個(gè)樣本的分類是否正確。若不正確，就要調(diào)整，在全部樣本調(diào)整完后，再修改聚類中心，進(jìn)入下一次迭代。如果在一次迭代算法中所有的樣本被正確分類，則不會(huì)有調(diào)整，聚類中心不會(huì)再有變化［8］。

K均值算法能夠使得聚類域中所有樣品到聚類中心距離的平方和最小，其原理為算法首先隨機(jī)從數(shù)據(jù)集中選取k個(gè)點(diǎn)作為初始聚類中心，然后計(jì)算各個(gè)樣本到這k個(gè)聚類中心的距離，把樣本歸到離它最近的那個(gè)聚類中心所在的類。計(jì)算新形成的每一個(gè)聚類的數(shù)據(jù)對(duì)象的平均值來(lái)得到新的聚類中心，直到新的聚類中心與上一次的中心沒(méi)有任何變化，則樣本調(diào)整結(jié)束［9］。數(shù)學(xué)模型描述如下：

假設(shè)任務(wù)集合T={T1,T2,…,TM}，按一定原則劃分為一系列任務(wù)簇A={A1,A2,…,AS}，且滿足：

K均值動(dòng)態(tài)聚類法實(shí)現(xiàn)步驟如下：

Step1：選擇k個(gè)初始凝聚點(diǎn)，作為類中心的估計(jì)；

Step2：對(duì)每一個(gè)樣本，按照最短距離原則劃歸某個(gè)類中；

Step3：重新計(jì)算各類的重心；

Step4：跳轉(zhuǎn)到Step2直到各類重心穩(wěn)定。

2.4 K均值聚類算法優(yōu)化

基本的K均值算法目的是找到使目標(biāo)函數(shù)值最小的K個(gè)劃分，算法思想簡(jiǎn)單，易實(shí)現(xiàn)，而且收斂速度較快。如果各個(gè)簇之間區(qū)分明顯，且數(shù)據(jù)分布稠密，則該算法比較有效，但如果各個(gè)簇的形狀和大小差別不大，則可能出現(xiàn)較大的簇分割現(xiàn)象，此外，在K均值算法聚類時(shí)，最佳聚類結(jié)果通常對(duì)應(yīng)于目標(biāo)函數(shù)的極值點(diǎn)，由于目標(biāo)函數(shù)可能存在很多的局部極小值點(diǎn)，這就會(huì)導(dǎo)致算法在局部極小值點(diǎn)收斂，因此初始聚類中心的隨機(jī)選取可能會(huì)使解陷入局部最優(yōu)解，難以獲得全局最優(yōu)解［10］。

基于模擬退火思想對(duì)K均值聚類算法進(jìn)行優(yōu)化，模擬退火算法是一種啟發(fā)式隨機(jī)搜索算法，具有并行性和漸近收斂性。理論上證明它以概率1收斂于全局最優(yōu)，因此，用模擬退火算法對(duì)K均值聚類算法進(jìn)行優(yōu)化，可以改進(jìn)K均值聚類算法的局限性，提高算法性能?；谀M退火思想，將內(nèi)能E模擬為目標(biāo)函數(shù)值，將基本K均值聚類算法的聚類結(jié)果作為初始解，初始目標(biāo)函數(shù)值作為初始溫度T0，對(duì)當(dāng)前解重復(fù)“產(chǎn)生新解→計(jì)算目標(biāo)函數(shù)差→接受或舍棄新解”的迭代過(guò)程，并逐步降低溫度，算法終止時(shí)當(dāng)前解為近似最優(yōu)解，該算法開(kāi)始時(shí)以較快的速度找到相對(duì)較優(yōu)的區(qū)域，然后進(jìn)行更精確的搜索，最終找到全局最優(yōu)解［11～12］。

2.5 基于模擬退火思想的改進(jìn)K均值聚類算法

算法實(shí)現(xiàn)步驟如下：

Step1：對(duì)樣本進(jìn)行K均值聚類，將聚類劃分結(jié)果作為初始解A，根據(jù)當(dāng)前聚類劃分的總類間離散度指標(biāo)，計(jì)算目標(biāo)函數(shù)值；

Step2：初始化溫度T0，令T0=JA。初始化退火速度a和最大退火次數(shù)；

Step3：對(duì)于某一溫度t，隨機(jī)擾動(dòng)產(chǎn)生新的聚類劃分A'，即隨機(jī)改變一個(gè)聚類樣品的當(dāng)前所屬類別，計(jì)算新的目標(biāo)函數(shù)值JA'；

Step4：算新的目標(biāo)函數(shù)值與當(dāng)前目標(biāo)函數(shù)值的差ΔJ=JA'

-JA，判斷ΔJ是否小于0；Step5：若ΔJ＜0，則接受新解，保存聚類劃分A'為最優(yōu)聚類劃分，JA'為最優(yōu)目標(biāo)函數(shù)值，將新解作為當(dāng)前解；

Step6：若 ΔJ≥0，根據(jù)Metropolis準(zhǔn)則，以概率p=eΔJ/Kt接受新解，K為常數(shù)；

Step7：判斷是否達(dá)到最大退火次數(shù)，是則結(jié)束算法，輸出最優(yōu)聚類劃分，否則根據(jù)退火公式對(duì)溫程序設(shè)計(jì)流程圖如圖1所示。

圖1 基于模擬退火思想的改進(jìn)K均值聚類算法流程

3 仿真分析

假設(shè)敵方100個(gè)任務(wù)點(diǎn)的GPS經(jīng)緯度坐標(biāo)如表1所示。

100個(gè)任務(wù)從左到右按列排序，由于給定的是地理坐標(biāo)（經(jīng)度和緯度），我們必須求兩點(diǎn)間的實(shí)際距離。設(shè)A,B兩點(diǎn)的地理坐標(biāo)分別為(x1,y1)，(x2,y2)，過(guò)A,B兩點(diǎn)的大圓的劣弧長(zhǎng)即為兩點(diǎn)的實(shí)際距離。以地心為坐標(biāo)原點(diǎn)O，以赤道平面為XOY平面，以0°經(jīng)線圈所在的平面為XOZ平面建立三維直角坐標(biāo)系。如圖2所示。

表1 100個(gè)任務(wù)點(diǎn)的GPS經(jīng)緯度坐標(biāo)

圖2 GPS經(jīng)緯度坐標(biāo)轉(zhuǎn)三維直角坐標(biāo)示意圖

則A,B兩點(diǎn)的直角坐標(biāo)分別為

其中地球半徑R=6370km。

A,B兩點(diǎn)的實(shí)際距離：

我方有三個(gè)基地，經(jīng)度和緯度分別為(10,60)，(30,60)，(50,60)。假設(shè)我方所有無(wú)人偵察機(jī)的速度都為1000 km/h。三個(gè)基地各派出一架飛機(jī)偵察敵方任務(wù)

首先用K均值聚類法通過(guò)聚類分析得到初始分群結(jié)果，再采用基于模擬退火思想的改進(jìn)K均值聚類法得到優(yōu)化分群結(jié)果，如表2所示。

規(guī)劃出無(wú)威脅情況下算法改進(jìn)前后的最短航路，為了顯示的直觀方便，選用經(jīng)緯度坐標(biāo)。

這樣劃分任務(wù)方案，使得巡航時(shí)間最短，目標(biāo)群分布群內(nèi)比較集中，群間比較分散，且各UAV任務(wù)分配比較均衡。

表2 算法改進(jìn)前后最優(yōu)任務(wù)分群方案表

其中，1代表該任務(wù)分配給UAV1，在圖中以○表示；2代表該任務(wù)分配給UAV2，在圖中以△表示；3代表該任務(wù)分配給UAV3，在圖中以☆表示；（）內(nèi)代表優(yōu)化后的分群方案。

圖3 算法改進(jìn)前后任務(wù)分群與任務(wù)規(guī)劃方案

表3 任務(wù)分群與各無(wú)人機(jī)巡航時(shí)間表

4 結(jié)語(yǔ)

文中針對(duì)多UAV協(xié)同偵察任務(wù)分群?jiǎn)栴}，建立了偵察任務(wù)分群模型，提出了評(píng)價(jià)任務(wù)分群性能好壞的3個(gè)優(yōu)化指標(biāo)，這些指標(biāo)代表群內(nèi)聚集，群間分散，以及任務(wù)數(shù)量均衡和巡航時(shí)間均衡等性能。采用基于模擬退火思想的改進(jìn)K均值聚類算法進(jìn)行任務(wù)分群和尋找最短路徑。仿真結(jié)果表明，基于模擬退火思想的改進(jìn)K均值聚類算法能夠有效解決任務(wù)分群?jiǎn)栴}，符合部隊(duì)的實(shí)際情況。