沈 奧，周樹道，王 敏，彭舒齡,3，劉展華

(1.國防科技大學(xué) 氣象海洋學(xué)院，南京 211100；2.中國人民解放軍 94303部隊(duì)，山東 濰坊 2610003.中國人民解放軍 61206部隊(duì)，北京 100043)

0 引言

旋翼無人機(jī)具有結(jié)構(gòu)簡單、操作靈活、起降要求低、可懸停等特點(diǎn)，在拍照錄像、氣象監(jiān)測、物資投遞等領(lǐng)域具有難以替代的作用。而多架旋翼無人機(jī)可以通過協(xié)同配合、編隊(duì)飛行等方式完成單架無人機(jī)難以完成的任務(wù)。在多架旋翼無人機(jī)協(xié)同執(zhí)行任務(wù)時，無人機(jī)會根據(jù)需要飛至不同目的地執(zhí)行任務(wù)。這種情況下一般采用多架相同的無人機(jī)，每一架無人機(jī)都有相同的屬性和功能[1-3]。根據(jù)無人機(jī)實(shí)際應(yīng)用情況，可以大致分為兩種情況：

情況1，每架無人機(jī)分別分配一個目標(biāo)點(diǎn)，到達(dá)目標(biāo)空域點(diǎn)即可降落，比如利用無人機(jī)進(jìn)行物資運(yùn)送；

情況2，每架無人機(jī)到達(dá)各自目標(biāo)空域點(diǎn)后需要懸停，等待所有無人機(jī)就位后再開始執(zhí)行任務(wù)，比如多無人機(jī)定點(diǎn)拍照、監(jiān)控或測量。

在這類問題中，計算復(fù)雜度隨無人機(jī)數(shù)量上升，呈指數(shù)上漲，屬于多項(xiàng)式問題(Polynomial Problem，P問題)，所以無人機(jī)自主快速智能地根據(jù)任務(wù)性質(zhì)和目標(biāo)點(diǎn)位置進(jìn)行匹配，可以免除人工調(diào)度，增加無人機(jī)協(xié)同工作的自動化程度，對提升無人機(jī)集群飛行的性能有重要意義[4-5]。由于在此類應(yīng)用實(shí)際中，空間內(nèi)無人機(jī)密度相對稀疏，無人機(jī)避碰相對容易實(shí)現(xiàn)。同時，各無人機(jī)目標(biāo)空域點(diǎn)相距較遠(yuǎn)，且高度往往不同，使用時碰撞的幾率較小。所以在本文中暫不將無人機(jī)避碰作為研究的重點(diǎn)。

本文主要是針對旋翼無人機(jī)，設(shè)計了適用于無人機(jī)嵌入式系統(tǒng)的輕量級算法，完成不同情況下多無人機(jī)的目標(biāo)空域點(diǎn)匹配。第一部分介紹了旋翼無人機(jī)目標(biāo)空域點(diǎn)匹配的數(shù)學(xué)模型；第二部分針對第一種情況采用匈牙利算法進(jìn)行求解；第三部分針對第二種情況，在匈牙利算法的結(jié)構(gòu)上，針對實(shí)際問題進(jìn)行了改進(jìn)，確定了改進(jìn)后的參數(shù)，并設(shè)計了遺傳算法進(jìn)行對比；第四部分為結(jié)論。

1 旋翼無人機(jī)多目標(biāo)空域點(diǎn)匹配問題數(shù)學(xué)模型

多無人機(jī)與多目標(biāo)點(diǎn)的匹配可以看作圖論中二分圖的匹配問題[6-7]，可以簡述為：

有n架無人機(jī)A1,A2,……，An；n個目標(biāo)點(diǎn)B1,B2,……，Bn，將無人機(jī)設(shè)置為矩陣的行，目標(biāo)點(diǎn)設(shè)置為矩陣的列，則可得到匹配矩陣為X=(xij)，其中，xij表示匹配情況，取值為1表示無人機(jī)Ai與目標(biāo)點(diǎn)Bj匹配，取值0表示無人機(jī)Ai與目標(biāo)點(diǎn)Bj不匹配。同時，一架無人機(jī)必須且僅能與一個目標(biāo)點(diǎn)匹配，優(yōu)化函數(shù)可以通過實(shí)際情況進(jìn)行設(shè)置。因此，問題可以看作n2個變量2n個約束條件的最優(yōu)規(guī)劃問題：

minimizez=f(X)

(1)

服從于：

其中:

xij=0 or 1,i,j=1,2,…,n

根據(jù)實(shí)際需要，設(shè)置合適的目標(biāo)函數(shù)f(X)，在服從約束條件的情況下，優(yōu)化匹配矩陣X，即可獲得問題的優(yōu)化解。

2 針對情況1的匈牙利算法使用

2.1 匈牙利算法

對于二分圖的最佳匹配問題，如果采用遍歷的方法，將所有匹配情況進(jìn)行比較和選取，則在問題規(guī)模較大時，會發(fā)生組合爆炸的情況。而此問題中限制條件特殊且具有明顯的數(shù)學(xué)特征，難以采用遺傳算法和模擬退火算法等隨機(jī)算法，且隨機(jī)算法在求解此問題中，丟失了問題的數(shù)學(xué)本質(zhì)，具有較大盲目性。

而匈牙利算法是基于Hall定理中充分性證明的思想，通過不斷尋找增廣路徑的方法大幅度降低時間復(fù)雜度，是解決二分圖匹配問題的主要算法[8-9]。算法步驟如下。

將優(yōu)化目標(biāo)定義為：

(2)

通過利用代價矩陣的相關(guān)定理，對矩陣進(jìn)行等價變換，算法可按圖1步驟執(zhí)行。

圖1 匈牙利算法流程圖

通過圖1中步驟計算，可得到xij的具體取值，即得到匹配矩陣X，將匹配矩陣中取值為1元素的行號對應(yīng)的無人機(jī)與列號對應(yīng)的目標(biāo)點(diǎn)進(jìn)行匹配，即為該問題的最優(yōu)匹配結(jié)果。

2.2 匈牙利算法使用

在情況1中，由于無人機(jī)到達(dá)空域點(diǎn)后即可降落，不需要等待其他無人機(jī)，所以可以將距離設(shè)置為問題中的代價值，即可求解令無人機(jī)群飛行總距離最短的匹配方式。通過衛(wèi)星定位獲取可獲取每一架無人機(jī)的當(dāng)前坐標(biāo)和空域點(diǎn)的坐標(biāo)值，計算各無人機(jī)對應(yīng)各空域點(diǎn)的距離，并將其作為代價矩陣C1中的元素,即：

C1=(c1,ij)

(3)

其中:c1,ij=distance(Ai,Bj)

對矩陣C1進(jìn)行2～6步驟運(yùn)算，即可得到匹配矩陣X1，將匹配矩陣中值為“1”的元素所在行列號進(jìn)行匹配，即為最佳匹配結(jié)果。

圖2以13架隨機(jī)初始位置的無人機(jī)對應(yīng)13個空域點(diǎn)為例，展示了匹配的幾組結(jié)果，圖中“*”代表無人機(jī)所在位置，“o”代表目標(biāo)點(diǎn)位置，連線表示無人機(jī)和目標(biāo)點(diǎn)的匹配結(jié)果。匹配結(jié)果中，無人機(jī)群總體移動距離之和最小，而從圖2中可以看出，使用匈牙利算法進(jìn)行目標(biāo)匹配，無人機(jī)徑直飛向目標(biāo)點(diǎn)時，飛行線路不會存在交叉的情況，即可不必考慮無人機(jī)避碰的問題，在安全性和節(jié)能性上都有較好的效果。

圖2 情況1中的匹配結(jié)果

3 針對情況2的匈牙利算法的改進(jìn)和對比

3.1 在情況2中存在的問題

對于情況2中時應(yīng)用背景，當(dāng)旋翼無人機(jī)到達(dá)自己空域點(diǎn)后，需要懸停飛行，等待其他無人機(jī)到達(dá)各自空域點(diǎn)，在等待的過程中，懸停飛行同樣會產(chǎn)生能量的消耗[10]。可以計算整個過程的總消耗為：

(4)

可以化簡為：

(5)

式中，a1,a2分別為飛行和懸停時，單位時間內(nèi)的能量消耗，v為旋翼無人機(jī)飛行速度，di為無人機(jī)Ai距離匹配到目標(biāo)點(diǎn)的距離，dmax為無人機(jī)到目標(biāo)點(diǎn)的距離的最大值。

與此同時，響應(yīng)速度快是無人機(jī)的優(yōu)勢，長時間懸停等待會影響旋翼無人機(jī)群整體執(zhí)行任務(wù)的效率[11]，所以整個過程所用的時間應(yīng)當(dāng)考慮在內(nèi)，計算整個過程完成的時間為：

T=dmax/v

(6)

可以看出，影響旋翼無人機(jī)群總能量消耗和完成時間取決于無人機(jī)需要移動的總距離(平均每架無人機(jī)需要移動的距離)和各無人機(jī)到各自空域點(diǎn)距離中的最大值，所以，要對無人機(jī)空域點(diǎn)進(jìn)行優(yōu)化匹配，應(yīng)當(dāng)同時優(yōu)化減小每架無人機(jī)移動的平均距離和無人機(jī)需移動距離的最大值。此外，無人機(jī)飛行的路線應(yīng)盡量減少交叉，減少相互間的避讓過程。

而匈牙利算法主要是針對單一變量進(jìn)行優(yōu)化，當(dāng)存在多個獨(dú)立變量時，需要按照變量影響程度加權(quán)計算出代價矩陣。但在此問題中，優(yōu)化目標(biāo)為無人機(jī)平均移動距離和無人機(jī)的最大移動距離是一對相互耦合的變量，只有當(dāng)一種匹配完成后，才能進(jìn)行二次匹配，得到這種匹配下的最大移動距離[12]。

針對于此，許多二次分配問題線性化方法已被提出，如：Kaufman和Broeckx線性化模型[13]，Lawler線性化模型[14]等，此外Peter Hahn還提出一種基于匈牙利算法的對偶上升求解方法[15]，但這些方法需要大量的矩陣運(yùn)算，占用大量計算資源和時間，不適用于無人機(jī)嵌入式系統(tǒng)實(shí)時計算[16]。

3.2 算法改進(jìn)

使用標(biāo)準(zhǔn)的匈牙利算法，得到結(jié)果可以使平均移動距離最小，但卻無法優(yōu)化無人機(jī)中的最大移動距離，經(jīng)過多次實(shí)例計算發(fā)現(xiàn)，當(dāng)兩架以上無人機(jī)全部位于空域點(diǎn)一側(cè)時，如圖3所示，由于線段AB與線段CD的和小于線段AD與BC的和，所以無人機(jī)B與目標(biāo)A匹配，無人機(jī)D與目標(biāo)C匹配，但實(shí)際中，A與D匹配，B與C匹配更符合應(yīng)用要求，在平均距離相差不大的情況下，均衡無人機(jī)的最大移動距離，同時，避免了前方無人機(jī)到達(dá)目標(biāo)后阻擋了后方無人機(jī)路線的情況。同樣的情況還存在于無人機(jī)F、H與目標(biāo)點(diǎn)G、H。

圖3 匹配結(jié)果分析

針對這一問題，為了避免較大距離的移動，在不增加額外矩陣計算的情況下，可以將代價矩陣中的元素由距離的一次函數(shù)改為距離的m次函數(shù)，增大遠(yuǎn)距離匹配的代價，具體改進(jìn)如下：

C2=(c2,ij)

(7)

其中:c2,ij=[distance(Ai,Bj)]m,m∈Z+,m≥2

對矩陣C1進(jìn)行2～6步驟運(yùn)算，即可得到匹配矩陣X2，匹配矩陣中所有值為“1”的元素所在行號無人機(jī)與所在列號目標(biāo)進(jìn)行匹配，可視為此情況下的優(yōu)化匹配。

經(jīng)過改進(jìn)，由于指數(shù)函數(shù)的單調(diào)性，每一架無人機(jī)匹配各自目標(biāo)點(diǎn)的代價值大小排序仍與無人機(jī)與目標(biāo)點(diǎn)距離遠(yuǎn)近的排序一致。但此時與距離較大的目標(biāo)進(jìn)行匹配的代價值將會明顯增大，限制了匹配中對較遠(yuǎn)距離目標(biāo)點(diǎn)的匹配，在匈牙利算法的框架中，在不增加變量的情況下，通過無人機(jī)-目標(biāo)點(diǎn)匹配的特點(diǎn)均衡優(yōu)化了平均移動距離和最大移動距離兩個參數(shù)。同時，優(yōu)化后的匹配結(jié)果不具有隨機(jī)性，對同一矩陣多次的匹配結(jié)果相同，可以在分布式系統(tǒng)中使用[17]。

3.3 遺傳算法對此問題的求解

為了更好的驗(yàn)證算法性能，針對此問題設(shè)計了遺傳算法進(jìn)行求解：

1)產(chǎn)生r條父輩染色體，染色體為1×n維矩陣，每個基因取值范圍為[1,n]，其中n為無人機(jī)數(shù)量，父輩中染色體為隨機(jī)生成的n的排列，第i個基因取值為N1代表無人機(jī)i與目標(biāo)N1匹配；

2)由于匹配模型限制較多，采用只變異不交叉的方式，從父輩染色體中隨機(jī)選擇兩個基因變異，為了保證目標(biāo)的逐一匹配，變異方式為此兩段基因進(jìn)行交換；

3)將父輩中r條染色體與產(chǎn)生的條子代染色體進(jìn)行評價，淘汰評價低的r條，保留評價高的r條染色體；

4)將保留的染色體作為父輩重復(fù)迭代。

5)經(jīng)過迭代，選擇最終染色體中評價最高的作為匹配結(jié)果。

在此例中，將r設(shè)置為100，迭代次數(shù)設(shè)置為1 000，對問題進(jìn)行解算。

3.4 實(shí)例對比

以13架隨機(jī)位置的無人機(jī)對應(yīng)13個已知空域點(diǎn)進(jìn)行計算，表1和圖4展示了m不同取值時匹配結(jié)果的對比，并與遺傳算法結(jié)果進(jìn)行比較?？梢钥闯?，匈牙利算法在解決此問題時，計算時間相差不大，將代價矩陣由距離的函數(shù)改為m次函數(shù)會使平均移動距離增大，但差別幾乎可以忽略，而最大移動距離會得到很大的改善，減小無人機(jī)群整體的等待時間。而遺傳算法由于在選擇上具有隨機(jī)性，計算效果和效率明顯欠缺，并且每次計算結(jié)果會不同，不利于無人機(jī)自主分布式計算。

表1 算法參數(shù)對比(無人機(jī)在空域點(diǎn)四周)

圖4 算法性能對比柱形圖(無人機(jī)在空域點(diǎn)四周)

改變無人機(jī)群與空域點(diǎn)的相對位置，使無人機(jī)群位于空域點(diǎn)的不同方向，表2、圖5展示了無人機(jī)群位于空域點(diǎn)一側(cè)時的匹配結(jié)果對比?？梢钥闯觯?dāng)無人機(jī)群位于目標(biāo)點(diǎn)一側(cè)時，當(dāng)m值變大時，結(jié)果變化趨勢與之前相似，而遺傳算法的效果有了很大提升，但計算時間仍然遠(yuǎn)遠(yuǎn)超過匈牙利算法。經(jīng)過多次實(shí)驗(yàn)，改變無人機(jī)和目標(biāo)點(diǎn)的相對位置，也會得到類似的結(jié)果。

表2 算法參數(shù)對比(無人機(jī)在空域點(diǎn)一側(cè))

圖5 算法性能對比柱形圖(無人機(jī)在空域點(diǎn)一側(cè))

此外，圖6～9和圖10～13展示了幾組m不同取值下，無人機(jī)與目標(biāo)點(diǎn)的匹配結(jié)果圖。通過多次試驗(yàn)可以看出，當(dāng)m=1時，由于匹配結(jié)果為總距離最短的最優(yōu)匹配，不存在路線的交叉，各無人機(jī)與其匹配的目標(biāo)點(diǎn)之間路線相離度較大；而m=2時，匹配結(jié)果會為了減小最大移動距離而做出一定修改，有時會發(fā)生路線交叉的情況；m=3或4時，由于代價矩陣元素變化較大，匹配時會發(fā)生過度避免較遠(yuǎn)目標(biāo)的情況，導(dǎo)致匹配結(jié)果中交叉較多，實(shí)際應(yīng)用中，不僅提升很小，并且會帶來飛行安全隱患。所以，將算法中m的值設(shè)置為2，可以兼顧優(yōu)化參數(shù)和實(shí)際中對路線的要求。

圖6 當(dāng)m=1時匹配結(jié)果(無人機(jī)在空域點(diǎn)四周)

圖7 當(dāng)m=2時匹配結(jié)果(無人機(jī)在空域點(diǎn)四周)

圖8 當(dāng)m=3時匹配結(jié)果(無人機(jī)在空域點(diǎn)四周)

圖9 當(dāng)m=4時匹配結(jié)果(無人機(jī)在空域點(diǎn)四周)

圖10 當(dāng)m=1時匹配結(jié)果(無人機(jī)在空域點(diǎn)一側(cè))

圖12 當(dāng)m=3時匹配結(jié)果(無人機(jī)在空域點(diǎn)一側(cè))

圖13 當(dāng)m=4時匹配結(jié)果(無人機(jī)在空域點(diǎn)一側(cè))

4 結(jié)束語

通過實(shí)例可以發(fā)現(xiàn)，匈牙利算法對于解決無人機(jī)群的空域點(diǎn)匹配有很好的效果。對于到達(dá)空域點(diǎn)即可降落的情況，使用標(biāo)準(zhǔn)匈牙利算法可以得到最優(yōu)解；而對于到達(dá)空域點(diǎn)后需要等待的情況，可以修改匈牙利算法中的代價矩陣，將其中元素改為各自值的平方，可以在平均移動距離和計算時間變化不大的情況下，將無人機(jī)中最大移動距離減小，通過與遺傳算法的比較和多次結(jié)果的對比，驗(yàn)證了算法在此問題中的優(yōu)越性。