多無人機(jī)協(xié)同目標(biāo)分配與航跡規(guī)劃

許先靜，姜海燕

(福州大學(xué) 電氣工程與自動(dòng)化學(xué)院，福州 350000)

0 引言

無人機(jī)具有體積小、重量輕、成本低等諸多優(yōu)點(diǎn)，被廣泛運(yùn)用于農(nóng)業(yè)、軍事、飛行表演等多個(gè)行業(yè)。在很多實(shí)際場(chǎng)景中，單個(gè)無人機(jī)無法滿足作業(yè)需求，需要多無人機(jī)的協(xié)同作業(yè)，而協(xié)同目標(biāo)分配是多無人機(jī)協(xié)同作業(yè)的基礎(chǔ)和保障。無人機(jī)的目標(biāo)分配問題是一個(gè)約束性多且復(fù)雜的優(yōu)化問題，其解空間隨無人機(jī)和目標(biāo)總數(shù)的增加呈現(xiàn)指數(shù)級(jí)增加，求解最優(yōu)解的時(shí)間也呈指數(shù)級(jí)增加。因此，無人機(jī)的目標(biāo)分配問題是一個(gè)多參數(shù)、多約束的非線性多項(xiàng)式完全(Non-deterministic polynomial Complete，NPC)問題[1]。在進(jìn)行目標(biāo)分配時(shí)，需要考慮的因素很多，如無人機(jī)數(shù)量、任務(wù)類別、飛行環(huán)境等，同時(shí)還需要兼顧航行代價(jià)、分配算法以及各種協(xié)同約束條件等。

目前針對(duì)無人機(jī)的協(xié)同目標(biāo)分配主要有集中式和分配式。集中式系統(tǒng)可以統(tǒng)一控制，缺點(diǎn)是擴(kuò)展性差；而分布式系統(tǒng)的擴(kuò)展性強(qiáng)，但對(duì)通信系統(tǒng)要求較高[2]。目前無人機(jī)的協(xié)同目標(biāo)分配的解決方案主要有3種類型，即傳統(tǒng)的數(shù)學(xué)規(guī)劃法、市場(chǎng)機(jī)制法和智能優(yōu)化算法。傳統(tǒng)的數(shù)學(xué)規(guī)劃法應(yīng)用于集中式系統(tǒng)中，具體可分為匈牙利法[3]、分支界定法、隱枚舉法、混合整數(shù)線性規(guī)劃法、動(dòng)態(tài)規(guī)劃法等；市場(chǎng)機(jī)制法應(yīng)用于分布式系統(tǒng)，具體可分為合同網(wǎng)協(xié)議[4]、拍賣法等市場(chǎng)機(jī)制法[5]；智能優(yōu)化算法既適用于集中式也適用于分布式，具體包括人工神經(jīng)網(wǎng)絡(luò)算法、模擬退火算法[6]、遺傳算法[7-9]、差分進(jìn)化算法、和聲搜索算法[10]、蟻群算法、A_算法[11-12]、粒子群優(yōu)化算法[13-16]等，以及由若干算法組合而成的混合優(yōu)化算法[1，17]。

無人機(jī)的編隊(duì)切換作為無人機(jī)的協(xié)同目標(biāo)分配問題的等效(將N個(gè)目標(biāo)分配給N個(gè)無人機(jī))，大部分可以歸納為：給定無人機(jī)的起點(diǎn)和終點(diǎn)，賦予一定的目標(biāo)任務(wù)、設(shè)定障礙或者航行代價(jià)等條件。目前許多的無人機(jī)的研究多基于二維平面，而無人機(jī)實(shí)際是在三維環(huán)境中執(zhí)行各種協(xié)同任務(wù)的，所以在三維空間中研究無人機(jī)的協(xié)同目標(biāo)分配，將會(huì)更具有理論研究意義和實(shí)際應(yīng)用價(jià)值。對(duì)于多無人機(jī)隊(duì)形變換的評(píng)價(jià)標(biāo)準(zhǔn)比較復(fù)雜，因?yàn)榭s小某一單架無人機(jī)的路徑長(zhǎng)度，必然也會(huì)增加其它無人機(jī)的飛行路徑長(zhǎng)度。在單個(gè)無人機(jī)的最大飛行路徑問題上，文獻(xiàn)[18]旋翼無人機(jī)協(xié)同任務(wù)指派問題研究與算法改進(jìn)中，通過將匈牙利算法中代價(jià)矩陣各元素值替換為各自值的m次方，有效縮小了單個(gè)無人機(jī)的最大飛行距離，但m取值不同，其得到的結(jié)果也是不同的；文獻(xiàn)[19]多旋翼無人機(jī)編隊(duì)隊(duì)形變換算法研究中，運(yùn)用粒子群算法實(shí)現(xiàn)隊(duì)形變換時(shí)間最小，縮小了單個(gè)無人機(jī)最大飛行距離，但該研究缺乏飛行距離整體性的考慮。

本文從協(xié)同目標(biāo)分配出發(fā),研究無人機(jī)編隊(duì)切換問題，發(fā)現(xiàn)標(biāo)準(zhǔn)的匈牙利算法在多無人機(jī)編隊(duì)切換應(yīng)用中，存在部分無人機(jī)分配的飛行路徑過長(zhǎng)的問題，同時(shí)由于無人飛行的能量消耗大于無人機(jī)懸停時(shí)能量消耗。從而導(dǎo)致個(gè)別無人機(jī)的電量下降迅速，因此相較于其他無人機(jī)會(huì)提前降落，而且會(huì)導(dǎo)致其他無人機(jī)在編隊(duì)切換過程中等待時(shí)間過長(zhǎng)，影響整體編隊(duì)飛行的時(shí)長(zhǎng)和編隊(duì)切換時(shí)長(zhǎng)。因此縮小單個(gè)無人機(jī)的最大飛行路徑，既可以縮短編隊(duì)切換的時(shí)間，還可以平衡無人機(jī)的耗能，延長(zhǎng)整體的編隊(duì)時(shí)長(zhǎng)。利用匈牙利算法本身的特性，求解總的飛行距離最短，將目標(biāo)函數(shù)改為求解在滿足約束條件下，單個(gè)無人機(jī)的最大飛行距離最小，對(duì)匈牙利算法進(jìn)行改進(jìn)。改進(jìn)的匈牙利算法可以使得在總的飛行距離盡量小的前提下，盡可能縮減單個(gè)無人機(jī)的飛行距離，從而有效地降低單個(gè)無人機(jī)的最大能耗，減少無人機(jī)在編隊(duì)切換時(shí)懸停等待的時(shí)間和編隊(duì)切換的時(shí)間，有效延長(zhǎng)整體編隊(duì)飛行的時(shí)間。適用于每架無人機(jī)到達(dá)各自目標(biāo)空域點(diǎn)后需要懸停，等待所有無人機(jī)就位后再開始執(zhí)行任務(wù)，比如多無人機(jī)定點(diǎn)拍照、監(jiān)控或測(cè)量、協(xié)同打擊等時(shí)間協(xié)同性強(qiáng)的應(yīng)用場(chǎng)景。而且算法簡(jiǎn)單，沒有過多的參數(shù)設(shè)置，無需占用太多的計(jì)算資源，適合無人機(jī)嵌入式系統(tǒng)的實(shí)時(shí)計(jì)算。

1 無人機(jī)編隊(duì)切換問題描述和算法改進(jìn)

1.1 隊(duì)形切換的數(shù)學(xué)模型及匈牙利算法

無人機(jī)的編隊(duì)切換問題，主要指的是在已知起點(diǎn)和目標(biāo)位置的情況下進(jìn)行位置移動(dòng)，形成新的隊(duì)形，主要影響編隊(duì)切換效率的因素是每個(gè)無人機(jī)目標(biāo)位置的選取。標(biāo)準(zhǔn)的匈牙利算法和其他算法大多數(shù)都只考慮無人機(jī)總飛行路徑最短，并在此基礎(chǔ)上去選取每個(gè)無人機(jī)的目標(biāo)位置。然而考慮無人機(jī)總飛行路徑最短時(shí)，就會(huì)存在部分無人機(jī)分配的飛行路徑過長(zhǎng)的問題，導(dǎo)致個(gè)別無人機(jī)電量迅速下降，提前降落且造成其他無人機(jī)等待時(shí)間過長(zhǎng)，影響整體編隊(duì)的飛行時(shí)長(zhǎng)。因此以單個(gè)無人機(jī)最大的飛行距離最小為優(yōu)化目標(biāo)，并滿足多約束條件，保證總移動(dòng)距離盡可能小的情況下，可以延長(zhǎng)整體編隊(duì)的飛行時(shí)長(zhǎng)。

為了簡(jiǎn)化問題的研究，假設(shè)每個(gè)無人機(jī)都是勻速飛行，忽略轉(zhuǎn)彎以及外界環(huán)境的影響并不考慮碰撞。記無人機(jī)編隊(duì)中各無人機(jī)的編號(hào)為i(i=1,2,3,...,n)，目標(biāo)位置編號(hào)為j(j=1,2,3,...,n)；無人機(jī)的初始位置坐標(biāo)(Xa,Ya,Za),無人機(jī)目標(biāo)的坐標(biāo)(Xs,Ys,Zs)?？梢杂?jì)算出第i架無人機(jī)飛往第j個(gè)目標(biāo)的路徑長(zhǎng)度：

(1)

匈牙利算法是基于Hall定理中充分性證明的思想，它是部圖匹配最常見的算法，該算法的核心就是尋找增廣路徑，它是一種用增廣路徑求二分圖最大匹配的算法[20-21]。匈牙利算法在多無人機(jī)編隊(duì)切換應(yīng)用中是將對(duì)于目標(biāo)位置的分配抽象成指派問題。即：

1)有n個(gè)飛機(jī)飛往n個(gè)目標(biāo)。

2)每個(gè)飛機(jī)只能飛往一個(gè)目標(biāo)，每個(gè)目標(biāo)只能有一個(gè)飛機(jī)飛往。

3)已知每個(gè)飛機(jī)飛往目標(biāo)的能耗值。

4)求如何分配使得總飛行距離最短。

將上述問題轉(zhuǎn)換成數(shù)學(xué)模型可以得到：

(1)無人機(jī)/目標(biāo)機(jī)對(duì)定義一個(gè)二值函數(shù)Xij，

(2)則總飛行距離最短的性能指標(biāo)函數(shù)為：

(i=1,2,3,...,n;j=1,2,3,...,n)

(2)

(3)需要滿足的約束條件有：

(3)

(4)

Xij=0,1

(5)

滿足上述約束條件去求性能指標(biāo)函數(shù)最優(yōu)解，庫恩(W.W.Kuhn)于1955年提出了指派問題的一種解法，他引用了匈牙利數(shù)學(xué)家康尼格(D.konig)一個(gè)關(guān)于矩陣中0元素的定理：系數(shù)矩陣中獨(dú)立0元素的最多個(gè)數(shù)等于能覆蓋所有0元素的最少直線數(shù)。這解法稱為匈牙利算法。將其運(yùn)用到多無人機(jī)編隊(duì)切換應(yīng)用中，其求解的過程是：

1)先將每個(gè)飛機(jī)飛往每個(gè)目標(biāo)的飛行距離求出并賦值為代價(jià)矩陣H(n×n)。行代表飛機(jī)編號(hào)，列代表目標(biāo)編號(hào)。

(i=1,2,3，...，n;j=1,2,3，...，n)

(6)

2)把代價(jià)矩陣進(jìn)行行歸約和列歸約，即每行減去該行的最小值，再把每列減去該列的最小值。

3)進(jìn)行試指派，用盡可能少的直線去覆蓋矩陣中所有的0，如果所用的直線為n條則停止，得到最優(yōu)匹配結(jié)果A，如果少于n，則繼續(xù)下一步。

4)在第三步中得到的代價(jià)函數(shù)中找尋最小的元素X，然后將直線未覆蓋的元素都減去該元素，并在直線相交處加上該元素。再更新代價(jià)矩陣后重復(fù)第三步。

圖1為算法流程圖：

圖1 標(biāo)準(zhǔn)匈牙利算法流程圖

圖2是一個(gè)4個(gè)飛機(jī)飛往4個(gè)目標(biāo)的指派問題中匈牙利算法的過程。左1為代價(jià)矩陣，中間的圖是完成求解過程第二步和第三步后的矩陣，由于圖中只有3條直線，而n等于4，故執(zhí)行第4步，減去最小元素2，并在直線交點(diǎn)處加上2，更新矩陣，得到右1圖。然后再從該矩陣中利用匈牙利算法找出最優(yōu)匹配。

圖2 匈牙利求解過程

1.2 改進(jìn)的匈牙利算法設(shè)計(jì)

標(biāo)準(zhǔn)的匈牙利算法只解決了在滿足約束條件的情況下性能指標(biāo)函數(shù)Z的最優(yōu)解，得到的分配結(jié)果A：

A=[S1J,S2J,S3J,...,S18J]，(j=1,2,3,...,n)

(7)

注：S1J代表編號(hào)為1的無人機(jī)飛往編號(hào)為j位置。

其中A集合中最大值即單個(gè)飛機(jī)飛行的最大飛行距離。

Smax=max(A)

(8)

考慮到時(shí)間的協(xié)同性，當(dāng)無人機(jī)到達(dá)既定位置時(shí)需要等待其他無人機(jī)到達(dá)后統(tǒng)一開始執(zhí)行任務(wù)，則完成任務(wù)的總時(shí)間T為：

T=Smax/v

(9)

而無人機(jī)無論是處于懸停還是飛行都需要損耗能量，則整個(gè)過程的能量損耗為：

(10)

注：k1代表無人機(jī)飛行能耗，k2代表無人機(jī)懸停能耗。

顯然無人機(jī)的總的耗能、所有無人機(jī)飛行的總距離、單個(gè)無人機(jī)最大的飛行距離存在關(guān)聯(lián)關(guān)系。而且由于無人機(jī)的飛行耗能要大于懸停耗能，因此減小單個(gè)無人機(jī)的最大飛行距離，不僅可以減小編隊(duì)切換的時(shí)間，還可以減小總的能耗及減小單個(gè)無人機(jī)的最大能耗，延長(zhǎng)無人機(jī)整體編隊(duì)的時(shí)間。

針對(duì)標(biāo)準(zhǔn)的匈牙利算法，需要解決的問題就變成在滿足約束條件下，如何減小Smax的值，并保證性能指標(biāo)Z的值盡量小(無人機(jī)飛行的總飛行距離盡量短)。此時(shí)優(yōu)化的性能指標(biāo)變?yōu)?

f=min[max(A)]

(11)

由上述分析可知，標(biāo)準(zhǔn)匈牙利算法在多無人機(jī)編隊(duì)切換應(yīng)用中只考慮了總飛行距離最短，而沒有考慮在任務(wù)分配后單個(gè)飛機(jī)飛行的最大飛行距離。因此造成個(gè)別無人機(jī)的電量下降迅速相較于其他無人機(jī)提前降落且會(huì)造成其他無人機(jī)等待時(shí)間過長(zhǎng)，影響整體編隊(duì)飛行的時(shí)長(zhǎng)。所以在算法的改進(jìn)過程中將單個(gè)飛機(jī)飛行的最大飛行距離考慮在內(nèi)就可以解決這個(gè)問題。

改進(jìn)算法的核心在于如何縮減單機(jī)最大飛行距離，本文通過標(biāo)準(zhǔn)的匈牙利算隨后將代價(jià)矩陣中比該值大的元素都賦值一個(gè)更大的元素M。在矩陣更新后，再通過標(biāo)準(zhǔn)的匈牙利算法進(jìn)行求解。重復(fù)上述步驟，直至分配結(jié)果中出現(xiàn)元素M，接著返回上一次的分配結(jié)果，即可得出最優(yōu)解。該算法可以保證在總的飛行距離盡可能小的情況下，縮小單個(gè)飛機(jī)飛行的最大飛行距離。算法具體求解的偽代碼如下：

begin

輸入：無人機(jī)的初始位置坐標(biāo)(Xs,Ys,Zs),無人機(jī)目標(biāo)的坐標(biāo)(Xa,Ya,Zs)，

初始化：無人機(jī)數(shù)量n，矩陣H為n×n的零矩陣，最大元素M=0，矩陣A為1×n的零矩陣

For i=1 to n:

For j=1 to n:

Hij←Sij//將得到的距離值賦值到代價(jià)矩陣中

End for

End for

M←10×max(H)//M賦值為矩陣元素最大值的10倍

While Ture：

A←proceduce(Hungarian method)//進(jìn)行標(biāo)準(zhǔn)匈牙利算法，并將結(jié)果賦值給A

If (max(A)=M)： //判斷單個(gè)無人機(jī)飛行最大距離是否等于M

Break //等于則返回上一次結(jié)果，結(jié)束循環(huán)

End if

For i->1 to n:

For j->1 to n:

If (Hij≥max(A)),

Hij←M//將大于單個(gè)無人機(jī)最大飛行距離的值都賦值為M，更新代價(jià)矩陣

End if

End for

End for

a=A

End while

輸出：最優(yōu)分配結(jié)果a

End

注：M必須大于1倍max(H)，這樣才能保證第一次循環(huán)不會(huì)報(bào)錯(cuò)，若小于等于1倍的maxH，第一次循環(huán)的分配結(jié)果的maxA有可能等于M導(dǎo)致循環(huán)報(bào)錯(cuò)。

1.3 算法說明

設(shè)代價(jià)矩陣H為：

(i=1,2,3,...,n;j=1,2,3,...,n)

(12)

由匈牙利算法計(jì)算結(jié)果為：

A=[S1J,S2J,S3J,...,S18J]，(j=1,2,3,...,n)

(13)

由標(biāo)準(zhǔn)的匈牙利算法可知，最大元素Smax=max(A)出現(xiàn)在最優(yōu)解的結(jié)果中時(shí)，是因?yàn)樵诓襟E1進(jìn)行行歸約、列歸約和步驟3更新代價(jià)矩陣時(shí)該元素Sij被賦值為0。

即在步驟2進(jìn)行試指派的代價(jià)矩陣中：Sij←0將大于等于Sij的元素都賦值為M記此時(shí)代價(jià)矩陣為H′，再進(jìn)行匈牙利算法計(jì)算。

若分配結(jié)果中max(A′)=M時(shí)，說明在步驟1進(jìn)行行歸約、列歸約和步驟3更新代價(jià)矩陣時(shí)某個(gè)為M的元素被賦值為0。此時(shí)在滿足指派問題的約束條件下，必須將代價(jià)矩陣H′中等于M的元素添加到最優(yōu)解中。

又因?yàn)橐阎氐扔贛的值在原代價(jià)矩陣H中的值都是大于Sij的；所以上一次的分配結(jié)果A即為滿足指派問題約束條件下的最優(yōu)解。

2 實(shí)驗(yàn)結(jié)果與分析

2.1 實(shí)驗(yàn)背景

本次仿真模擬18架無人機(jī)的編隊(duì)切換，每架無人機(jī)到達(dá)各自目標(biāo)空域點(diǎn)后需要懸停，等待所有無人機(jī)就位后再開始執(zhí)行任務(wù)，比如多無人機(jī)定點(diǎn)拍照、監(jiān)控或測(cè)量、協(xié)同打擊等。本文提出的方法是在已知無人機(jī)自身的位置和周圍環(huán)境信息下的目標(biāo)分配與航跡規(guī)劃方法。無人機(jī)的初始位置坐標(biāo)由自身攜帶的定位系統(tǒng)確定，目標(biāo)位置坐標(biāo)由無人機(jī)控制系統(tǒng)給定。

假定無人機(jī)初始位置坐標(biāo)：

A_x=[100,140,180,220,260,300,100,140,180,140,260,260,260,140,140,140,180,220]

A_y=[400,400,400,400,400,400,100,100,100,350,300,250,200,150,200,300,250,250]

A_z=[500,500,500,500,500,500,200,200,200,450,400,350,300,250,300,400,350,350]

將上述對(duì)應(yīng)初始位置的無人機(jī)進(jìn)行編號(hào)為1-18。

無人機(jī)目標(biāo)點(diǎn)位置坐標(biāo)：

B_x=[100,140,180,220,260,300,100,140,180,100,260,260,260,220,120,160,200,240]

B_y=[400,400,400,400,400,400,100,100,100,350,350,150,100,100,150,190,260,315]

B_z=[500,500,500,500,500,500,200,200,200,450,450,250,200,200,250,290,360,415]

將上述對(duì)應(yīng)目標(biāo)點(diǎn)位置編號(hào)為任務(wù)1～18。

編隊(duì)飛行實(shí)驗(yàn)從隊(duì)形F到隊(duì)形Z，如圖3～4所示。

圖3 編隊(duì)F 圖4 編隊(duì)Z

為了驗(yàn)證算法的性能，針對(duì)上述問題設(shè)計(jì)了粒子群算法并且分別用標(biāo)準(zhǔn)的匈牙利算法、m次方的匈牙利算法[18]、和本文中改進(jìn)的匈牙利算法進(jìn)行目標(biāo)位置的分配，無人機(jī)編隊(duì)切換航線由各算法的目標(biāo)分配結(jié)果確定，以二維空間的下匈牙利算法為例，其坐標(biāo)值為上述坐標(biāo)中去除z軸坐標(biāo)，將初始位置坐標(biāo)和目標(biāo)點(diǎn)坐標(biāo)賦予匈牙利算法，得到目標(biāo)分配結(jié)果。算法輸出結(jié)果如下：任務(wù)1～18依次分配的無人機(jī)編號(hào)為：

[1,2,3,4,5,6,7,8,9,10,11,13,12,15,16,18,17,14]。根據(jù)算法分配結(jié)果的飛行路線如圖5所示，圖中圓表示無人機(jī)的初始位置，*號(hào)表示無人機(jī)的目標(biāo)位置。對(duì)應(yīng)的飛行距離為：

[0,0,0,0,0,0,0,0,0,40,50,150,50,20,22,101,22,150]

圖5 無人機(jī)編隊(duì)切換示例

2.2 粒子群算法

粒子群算法的思想是模擬鳥群捕食的行為演化而來，捕食的鳥群都是通過各自的搜索與群體的合作最終發(fā)現(xiàn)食物所在的位置。通過一種無質(zhì)量的粒子來模擬鳥群中的鳥，每個(gè)粒子含有兩種屬性，速度和位置，速度表示移動(dòng)的快慢，位置表示移動(dòng)的方向。算法中將無人機(jī)當(dāng)作粒子，首先，每個(gè)無人機(jī)在空間中搜索當(dāng)前個(gè)體極值，每個(gè)個(gè)體極值通過比較，以此找到當(dāng)前最優(yōu)的個(gè)體極值作為當(dāng)前全局最優(yōu)解，根據(jù)當(dāng)前全局最優(yōu)，粒子來調(diào)整自己的速度和位置，往最優(yōu)化方向靠近來求得最優(yōu)解。

而本次任務(wù)要求分配方案要滿足無人機(jī)飛行路徑相近，因此，在粒子搜索最優(yōu)解(即路徑和最小)的過程中加入第一優(yōu)先級(jí)：滿足相近條件。在相近的條件下，再來找到路徑和最小。PSO算法流程圖，如圖6所示。

圖6 PSO算法流程圖

2.3 實(shí)驗(yàn)結(jié)果

將無人機(jī)的初始位置和目標(biāo)位置分別賦予給匈牙利算法、m次方的匈牙利算法、粒子群算法和本文中改進(jìn)的匈牙利算法，通過各算法給出的目標(biāo)分配結(jié)果指定無人機(jī)的航線并計(jì)算無人機(jī)的飛行距離。文獻(xiàn)[18]中比較了當(dāng)m分別等于2、3、4情況下算法的匹配結(jié)果，當(dāng)m越大時(shí)，其結(jié)果變化趨勢(shì)與之前相同，綜合考慮優(yōu)化參數(shù)和實(shí)際中對(duì)路線的要求，最終將m的值設(shè)定為2。本次實(shí)驗(yàn)中引入該算法，并且分別比較當(dāng)m等于2和3兩種情況下的匹配結(jié)果。如表1所示為上述各算法的目標(biāo)分配結(jié)果，可見各算法的匹配結(jié)果不見相同。

由圖7可知，無人機(jī)按照各算法的匹配結(jié)果飛至指點(diǎn)目標(biāo)位置的飛行距離中，匈牙利算法的單個(gè)無人機(jī)的飛行距離最長(zhǎng)為212.13 m，其次是粒子群算法為156.84 m，m次方的匈牙利算法和本文提出的改進(jìn)的匈牙利算法均為141.42 m。單個(gè)無人機(jī)的飛行距離影響著無人機(jī)的編隊(duì)切換時(shí)長(zhǎng)和懸停等待能耗，同時(shí)也可以降低各無人的能耗差，延長(zhǎng)無人機(jī)的整體編隊(duì)飛行時(shí)長(zhǎng)，m次方的匈牙利算法和本文提出的改進(jìn)的匈牙利算法在這方面均表現(xiàn)良好。

圖7 根據(jù)各算法匹配結(jié)果無人機(jī)飛至指定目標(biāo)的距離

無人機(jī)的編隊(duì)切換時(shí)間取決于最大飛行距離，并且無

表1 各算法的任務(wù)匹配結(jié)果

人機(jī)的能耗取決于懸停等待時(shí)間和飛行的距離。由表2可知，粒子群算法相比于匈牙利算法，其最大飛行距離雖然縮短了，但粒子群算法不僅有著大量的參數(shù)設(shè)置，并且其結(jié)果不如其他的改進(jìn)算法，計(jì)算結(jié)果和效率明顯欠缺。相對(duì)于其他算法，改進(jìn)的匈牙利算法得到的最大飛行距離最小，且總距離只比匈牙利算法多了11 m；m次方匈牙利算法的匈牙利算法的最大距離雖然和改進(jìn)的匈牙利算法一致，但其總的飛行距離比較大，影響無人機(jī)編隊(duì)切換的總體能耗。改進(jìn)的匈牙利算法不僅縮減了無人機(jī)的等待和編隊(duì)切換時(shí)間，還降低了無人機(jī)懸停等待能耗和各無人機(jī)之間的能耗差，同時(shí)其總的飛行距離和平均距離較小，無人機(jī)的飛行能耗也較小，降低了整體編隊(duì)的耗能，延長(zhǎng)了整體編隊(duì)飛行時(shí)間。

表2 算法結(jié)果對(duì)比

經(jīng)過實(shí)驗(yàn)對(duì)比，本文提出的算法在面對(duì)每架無人機(jī)到達(dá)各自目標(biāo)空域點(diǎn)后需要懸停，等待所有無人機(jī)就位后再開始執(zhí)行任務(wù)這類場(chǎng)景下的目標(biāo)分配表現(xiàn)良好。不僅可以縮短無人機(jī)的編隊(duì)切換時(shí)間，還可以降低無人機(jī)的總體能耗和各無人機(jī)的能耗差，延長(zhǎng)無人機(jī)的整體編隊(duì)飛行時(shí)間。并且該算法簡(jiǎn)單，無需占用太多的計(jì)算資源，相比于計(jì)算智能領(lǐng)域的各種算法如粒子群算法、蟻群算法等，沒有過多的參數(shù)設(shè)置并且其分配結(jié)果不會(huì)因?yàn)閰?shù)的改變而變化，適用于無人機(jī)嵌入式系統(tǒng)實(shí)時(shí)計(jì)算。能夠適應(yīng)時(shí)間協(xié)同性強(qiáng)的目標(biāo)分配系統(tǒng)；如無人機(jī)編隊(duì)表演時(shí)能延長(zhǎng)整體編隊(duì)飛行時(shí)長(zhǎng)，縮短編隊(duì)切換時(shí)間；對(duì)敵方目標(biāo)進(jìn)行協(xié)同打擊時(shí)能縮短無人機(jī)的集結(jié)時(shí)間，快速完成打擊任務(wù)等。

3 結(jié)束語

標(biāo)準(zhǔn)匈牙利算法在無人機(jī)編隊(duì)切換中存在問題，即單個(gè)無人機(jī)飛行距離過長(zhǎng)，造成其他無人機(jī)懸停等待過長(zhǎng)，影響編隊(duì)切換的時(shí)長(zhǎng)又以及因?yàn)楦鱾€(gè)無人機(jī)能耗差別導(dǎo)致個(gè)別無人機(jī)的電量下降迅速而提前降落，影響整體編隊(duì)飛行時(shí)間。單個(gè)無人機(jī)的飛行距離可通過粒子群等智能優(yōu)化算法有效縮短飛行距離，但存在參數(shù)的選取等問題，在一部分系統(tǒng)中不能很好的得到最優(yōu)解，且只考慮了單個(gè)無人機(jī)的飛行距離，未將總的飛行距離考慮在內(nèi)。通過仿真實(shí)例，利用匈牙利算法特性，將目標(biāo)函數(shù)改為求解滿足約束條件下單個(gè)無人機(jī)的最大飛行距離最小。經(jīng)過改進(jìn)的匈牙利算法對(duì)無人機(jī)編隊(duì)切換有著很好的表現(xiàn)，雖然標(biāo)準(zhǔn)的匈牙利算法可以得到飛行總距離最小的最優(yōu)解，但使用改進(jìn)的匈牙利可以在總距離變化不大的情況下，最大化的減小單個(gè)無人機(jī)的飛行距離。可以有效的降低單個(gè)無人機(jī)的最大能耗，減少無人機(jī)在編隊(duì)切換時(shí)懸停等待和編隊(duì)切換的時(shí)間，有效延長(zhǎng)整個(gè)編隊(duì)飛行的時(shí)間。本文提出的方法相較于匈牙利算法、粒子群算法及m次方的匈牙利算法更適用于無人機(jī)飛行時(shí)的編隊(duì)切換，能夠縮短無人編隊(duì)切換的時(shí)間，提升整體飛行的時(shí)長(zhǎng)；同時(shí)適用于具有時(shí)間協(xié)同性的目標(biāo)分配系統(tǒng)及性能指標(biāo)為最小化單個(gè)個(gè)體指標(biāo)的協(xié)同目標(biāo)分配系統(tǒng)，算法簡(jiǎn)單具有良好的適用性。