旋翼無(wú)人機(jī)協(xié)同任務(wù)指派問(wèn)題研究與算法改進(jìn)

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

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

0 引言

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

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

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

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

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

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

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

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

minimizez=f(X)

(1)

服從于：

其中:

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

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

2 針對(duì)情況1的匈牙利算法使用

2.1 匈牙利算法

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

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

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

(2)

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

圖1 匈牙利算法流程圖

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

2.2 匈牙利算法使用

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

C1=(c1,ij)

(3)

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

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

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

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

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

3.1 在情況2中存在的問(wèn)題

對(duì)于情況2中時(shí)應(yīng)用背景，當(dāng)旋翼無(wú)人機(jī)到達(dá)自己空域點(diǎn)后，需要懸停飛行，等待其他無(wú)人機(jī)到達(dá)各自空域點(diǎn)，在等待的過(guò)程中，懸停飛行同樣會(huì)產(chǎn)生能量的消耗[10]?？梢杂?jì)算整個(gè)過(guò)程的總消耗為：

(4)

可以化簡(jiǎn)為：

(5)

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

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

T=dmax/v

(6)

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

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

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

3.2 算法改進(jìn)

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

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

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

C2=(c2,ij)

(7)

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

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

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

3.3 遺傳算法對(duì)此問(wèn)題的求解

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

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

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

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

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

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

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

3.4 實(shí)例對(duì)比

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語(yǔ)

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