魏兆恬， 趙曉林， 李俊濤， 紀(jì)良杰

(空軍工程大學(xué),a.研究生院； b.裝備管理與無人機工程學(xué)院，西安 710000)

0 引言

隨著人工智能技術(shù)快速發(fā)展，無人機(UAV)相關(guān)技術(shù)也在朝著智能化的方向發(fā)展。在現(xiàn)代戰(zhàn)場偵察、攻擊等任務(wù)中，無人機因其靈活、隱蔽等特點而被廣泛使用。單架無人機可以獨立地完成偵察、攻擊等一系列作戰(zhàn)任務(wù)。但由于其任務(wù)執(zhí)行能力差、效率低，在面對更為復(fù)雜的作戰(zhàn)任務(wù)時往往需要多架無人機協(xié)同的方式進行[1]。多無人機系統(tǒng)是由多架同構(gòu)或異構(gòu)無人機組成，相比于單架無人機具有明顯的優(yōu)勢，可以有效地提高任務(wù)的可靠性。多無人機的任務(wù)規(guī)劃問題是其進行高效協(xié)同作戰(zhàn)的關(guān)鍵。如何對任務(wù)區(qū)進行合理的最優(yōu)化分配仍是當(dāng)前研究的重點。

多無人機任務(wù)分配問題的建模方法，可歸納為旅行商問題(Travelling Salesman Problem，TSP)模型[2]、定向問題(Orientation Problem，OP)模型[3]、其他模型以及隨之衍生出的拓展模型[4]。TSP模型假設(shè)無人機會對所有目標(biāo)訪問一遍，并最終回到出發(fā)點。將多無人機拓展到TSP模型中可得到MTSP模型，該模型可用于對多無人機協(xié)同任務(wù)分配問題的研究。車輛路徑問題(Vehicle Routing Problem，VPR)模型是TSP模型的另一種拓展模型。在該模型中，無人機的燃料、載彈能力、偵察載荷等約束條件被視為車輛的運載能力，偵察、攻擊任務(wù)被視為“客戶”。VPR模型能夠在車輛運載能力的范圍內(nèi)盡量滿足客戶的需求。OP模型中，無人機可以對執(zhí)行的目標(biāo)進行選擇，使各無人機在自身的能力范圍內(nèi)找到最優(yōu)的任務(wù)分配方案。因此，OP模型更能滿足實際戰(zhàn)場環(huán)境的需要，得到了廣泛的應(yīng)用。

任務(wù)分配問題的求解方法可分為集中式、分布式、混合式等。應(yīng)用較多的群智能算法就是集中式求法中的啟發(fā)式算法。文獻[5]針對多無人機動態(tài)偵察資源分配問題提出了一種改進的人工蜂群(Artificial Bee Colony,ABC)算法?；诤贤W(wǎng)的拍賣算法[6]是應(yīng)用廣泛的一種多無人機的任務(wù)分配算法，該方法是一種分布式智能優(yōu)化算法，它通過防止沖突，對每個任務(wù)進行通信協(xié)商來解決問題。整個過程可分為“招標(biāo)-投標(biāo)-中標(biāo)-確認(rèn)”4個階段。拍賣算法的演化算法被廣泛地提出，如基于共識的捆綁算法(Consensus-Based Bundle Algorithm,CBBA)[7]，使用這種算法可以獲得無沖突的最優(yōu)解。CBBA算法被提出后，國內(nèi)外學(xué)者就算法的改進做了諸多研究。針對異構(gòu)多無人機協(xié)同偵察任務(wù)決策問題，文獻[8]提出了一種分布式的擴展CBBA算法；文獻[9]通過更改本地拍賣信息的存儲方式，提出新的沖突分配解決辦法，從而解決在軌裝配航天器的任務(wù)分配問題；文獻[10]提出了異步CBBA(ACBBA)，它通過一組新的本地消除沖突規(guī)則，不需要訪問全局信息狀態(tài)，在保持收斂特性的同時最小化通信負(fù)載和時間延遲，并且它使用相對較小的帶寬并且不需要人為的時間延遲來產(chǎn)生一致的任務(wù)分配。

本文在現(xiàn)有研究的基礎(chǔ)上，以異構(gòu)多無人機執(zhí)行帶有時間窗約束的偵察、攻擊任務(wù)為場景，以任務(wù)執(zhí)行收益為目標(biāo)，在無人機的任務(wù)執(zhí)行能力、載彈能力以及任務(wù)執(zhí)行時間的約束下，通過引入時間窗約束的CBBA算法消除了任務(wù)沖突，實現(xiàn)了合理分配。

1 問題描述和數(shù)學(xué)模型

1.1 問題描述

在現(xiàn)代化的戰(zhàn)場環(huán)境中，多無人機在參與戰(zhàn)爭時，需要先對目標(biāo)區(qū)域進行偵察，偵察完畢后再對其進行打擊，這種作戰(zhàn)模式帶來的一個關(guān)鍵問題就是異構(gòu)多無人機多任務(wù)分配問題。針對上述問題，本文的描述如下：多無人機飛往任務(wù)區(qū)執(zhí)行偵察、攻擊任務(wù)。首先考慮無人機與目標(biāo)點的距離、到達目標(biāo)點的時間等條件的約束。在執(zhí)行攻擊任務(wù)時，一些目標(biāo)需要多枚武器才能夠摧毀，且無人機的載彈量有限，只能裝載一定數(shù)量的武器。

在完成任務(wù)之后，無人機將獲得收益。問題的關(guān)鍵在于如何在綜合各種約束條件的前提下，一方面實現(xiàn)無人機收益的最大化，另一方面實現(xiàn)最短的完成任務(wù)時間。為了簡化問題，提出如下假設(shè)：1)各無人機在執(zhí)行任務(wù)時的速度一致，即不考慮無人機之間的碰撞問題；2)無人機對于每個任務(wù)的選擇可能性相同；3)不考慮無人機飛行過程中的轉(zhuǎn)彎半徑；4)不考慮油耗代價的影響，即每架無人機的油量充足；5)作戰(zhàn)任務(wù)區(qū)域中每個攻擊任務(wù)的類型相同。

1.2 數(shù)學(xué)模型

1.2.1 目標(biāo)函數(shù)

對于每個任務(wù)設(shè)置時間窗Wj=(tj，start,tj，end,tj，last)，其中，tj，start為任務(wù)開始的時間，tj，end為任務(wù)結(jié)束的時間，tj，last為任務(wù)的持續(xù)時間。無人機Ui沿著路徑pi執(zhí)行任務(wù)k的收益為

(1)

無人機在執(zhí)行任務(wù)時存在任務(wù)風(fēng)險，任務(wù)風(fēng)險程度由無人機自身的任務(wù)執(zhí)行能力和任務(wù)威脅程度決定，任務(wù)風(fēng)險表示為

(2)

無人機在沿路徑pi執(zhí)行任務(wù)k的過程中會產(chǎn)生距離折扣，它與無人機沿路線飛行的距離有關(guān)。飛行距離越長，折扣越大。飛行距離和折扣函數(shù)可以表示為

(3)

(4)

根據(jù)式(1)、式(2)、式(4)可得到代表任務(wù)效益的函數(shù)為

(5)

本文設(shè)計的目標(biāo)是對任務(wù)進行分配，使多無人機執(zhí)行任務(wù)的收益最高，飛行距離最短。綜上可得目標(biāo)函數(shù)為

(6)

1.2.2 約束條件

每個任務(wù)需要多枚武器以確保完全摧毀目標(biāo)。此外，每架無人機有一定的載彈能力，其所使用的武器總數(shù)不超過每架無人機的載彈總數(shù)。

1) 對于偵察任務(wù)，無人機的任務(wù)執(zhí)行能力約束為

(7)

表示每架偵察無人機Ui所能執(zhí)行的偵察任務(wù)數(shù)量不超過其所能執(zhí)行的最大任務(wù)數(shù)量。

2) 對于攻擊任務(wù)，無人機的任務(wù)執(zhí)行能力約束為

(8)

3) 每個任務(wù)要求必須在任務(wù)時間窗內(nèi)完成，即

μi(pi)=max(tj，start,tj，arrive)μ(pi)

(9)

2 CBBA算法設(shè)計

CBBA算法由兩個階段構(gòu)成,即任務(wù)包構(gòu)建階段和沖突消解階段，算法在這兩個階段迭代[11-12]。在任務(wù)包構(gòu)建階段，每個代理將任務(wù)插入到自己的路徑中，并進行排序，直到所有任務(wù)均被分配完畢或代理的載荷資源被耗盡為止。在沖突消解階段，消除代理之間的任務(wù)沖突，使利益最大化。算法流程如圖1所示。

圖1 CBBA算法流程圖Fig.1 Flow chart of CBBA algorithm

2.1 信息結(jié)構(gòu)

在CBBA算法中，不同無人機的任務(wù)分配和通信中介是獨立的。每架無人機都有一定的信息,如下所述。

1)Bi為任務(wù)包集，包括無人機Ui在任務(wù)空間上已知的所有任務(wù)。Bi表示無人機Ui通過競拍獲得的依次排列的任務(wù)序列，若無人機Ui尚未競拍到任務(wù)，則Bi=?。

2)pi為路徑集，代表無人機Ui分配到的所有任務(wù)，按照執(zhí)行的先后順序排列。

2.2 任務(wù)包構(gòu)建

每架無人機構(gòu)建一個任務(wù)包，根據(jù)自己的載彈能力將能使自己的收益達到最大的任務(wù)依次加入到任務(wù)包中，按照無人機計劃完成任務(wù)的順序進行排序。用Bi表示添加到無人機Ui的一組任務(wù)，pi表示任務(wù)包中任務(wù)的分配順序。當(dāng)向任務(wù)包中插入任務(wù)Tj導(dǎo)致得分增加，則可以表示為

(10)

(11)

(12)

(13)

(14)

pi=pi⊕ni,j*{j*}。

(15)

在任務(wù)包構(gòu)建完成之后，無人機之間需進行通信來交流競拍得到的任務(wù)信息。無人機需要考慮自己對所選任務(wù)的出價是否高于最高出價，以及每個任務(wù)可以被分配的無人機,這就需要一定的規(guī)則來消解沖突。沖突消解的目的就是確保每個任務(wù)只能分配給一架無人機。

2.3 沖突消解

在CBBA算法中，無人機根據(jù)其當(dāng)前分配的任務(wù)集將任務(wù)添加到其任務(wù)包中。因此，如果一架無人機對某一個任務(wù)的出價高于其他無人機，它也應(yīng)該釋放在它之后添加到包中的任務(wù)，因為它們可能不再是最佳選擇。通過允許無人機出價高于較早選擇的任務(wù)，該算法能夠完成比以前的迭代方法更有價值的任務(wù)。但這也導(dǎo)致了算法更加復(fù)雜，為了避免多架無人機分配到相同的任務(wù)，需要一定的沖突消解規(guī)則來解決這一問題。

在沖突消解階段，每架相鄰的無人機之間通過交互通信共享以下3個信息：1) 中標(biāo)任務(wù)集合Yi；2) 中標(biāo)無人機集合Zi；3) 其他每架無人機最后一次更新消息的時間Si。

在接收到信息之后，無人機Ui會通過比較來確定自己能否中標(biāo)。如果Ui的出價更高，則它將通過競爭得到任務(wù)Tj，那么其他在任務(wù)集中含有任務(wù)Tj的無人機將會釋放任務(wù)Tj，路徑集中任務(wù)Tj之后的所有任務(wù)也會隨之被刪除，在下一次的迭代中進行重新分配。

表1 接收者Ui對于發(fā)送者Uk信息所采取的方案

收到信息后，無人機會根據(jù)表1中方法驗證哪些信息狀態(tài)是正確的，并采取相應(yīng)的行動。在表中，Zi有4種不同的考慮情況：1) 認(rèn)為發(fā)送者Uk中標(biāo)；2) 認(rèn)為接收者Ui中標(biāo)；3) 認(rèn)為其他無人機Um中標(biāo)，發(fā)送者Uk認(rèn)為Zi是Um時，在接收者中會增加考慮不是Ui,Uk,Um的情況，即Un；4) 不知道誰贏得投標(biāo)，即?。

如果出價列表在第2階段被更改，且更改的任務(wù)在其任務(wù)包中，則釋放此任務(wù)以及在它后面添加到任務(wù)包中的所有任務(wù)。相應(yīng)的Yi,Zi重置，即：Yi，bin=0,Zi，bin=?,bin=?。通過這種方式解決在分配過程中的任務(wù)沖突，然后算法會重新返回第1階段繼續(xù)添加任務(wù)。算法會一直迭代這兩個階段直到相應(yīng)的Yi，Zi不再發(fā)生變化，表明所有的沖突被消解完畢，證明各無人機已完成對各攻擊目標(biāo)的分配方案。

3 仿真驗證

3.1 任務(wù)場景

設(shè)計采用偵察、攻擊無人機分別執(zhí)行偵察和攻擊的任務(wù)。偵察任務(wù)的時間窗口為5 min，攻擊任務(wù)的時間窗口為15 min。假設(shè)執(zhí)行攻擊任務(wù)的無人機和執(zhí)行偵察任務(wù)的無人機的飛行速度相同，并且有充足的油量維持飛行。為了驗證算法的可靠性，選取6架偵察無人機，4架攻擊無人機，11個偵察任務(wù)，9個攻擊任務(wù)。多無人機的位置坐標(biāo)及類型如表2所示。在引入時間窗的情況下，仿真結(jié)果如圖2所示。每架無人機具體執(zhí)行任務(wù)的時間表如圖3所示。

表2 無人機屬性

圖2 帶有任務(wù)窗的任務(wù)分配細(xì)節(jié)圖Fig.2 Task allocation details with task window

圖3 每架無人機具體分配時間圖Fig.3 Specific time allocation of each UAV

3.2 結(jié)果分析

圖2顯示了X,Y軸隨時間的位置變化。從圖中可以看出，多無人機已經(jīng)完成了所有子任務(wù)，且每架無人機之間在執(zhí)行任務(wù)時不存在任務(wù)沖突。

圖3顯示了每架無人機的具體任務(wù)分配時間表。用矩形的長短表示時間窗的不同。從圖3可以看出，由于每架無人機的能力不同，在任務(wù)分配中有些無人機可能執(zhí)行多個任務(wù)。此外，在偵察和攻擊任務(wù)時間窗不同的情況下，該算法可以成功地解決帶有復(fù)雜時間約束的多任務(wù)分配問題。

綜合圖2、圖3可以得出，實驗所得到的任務(wù)分配結(jié)果合理并且達到了預(yù)期的效果。在相同的情況下，將引入時間窗的CBBA算法(即本文算法)與未引入時間窗的CBBA算法進行對比，如表3所示。

表3 兩種算法任務(wù)分配結(jié)果對比

通過兩種算法的對比可以看出，引入時間窗后的任務(wù)收益明顯提高,這是由于無人機對目標(biāo)進行偵察、攻擊時，如果停留的時間過長，容易被目標(biāo)發(fā)現(xiàn)并被摧毀，使無人機的任務(wù)執(zhí)行效率降低。引入時間窗之后，多無人機在執(zhí)行任務(wù)過程中被發(fā)現(xiàn)的概率會降低，提高了任務(wù)的完成效率，能夠得到更高的任務(wù)收益。圖4所示為每個任務(wù)下無人機的毀傷概率，從中可以看出，使用引入時間窗的CBBA算法的無人機在執(zhí)行任務(wù)時，毀傷概率大大降低。由此可知，本文算法明顯優(yōu)于未引入時間窗的CBBA算法。

圖4 每個任務(wù)下無人機的毀傷概率Fig.4 Damage probability of UAV in each task

4 結(jié)論

本文研究了異構(gòu)多無人機的多任務(wù)分配問題。在進行任務(wù)分配的過程中考慮了以下限制：無人機的載彈能力、任務(wù)的時間窗，引入了基于無人機飛行距離的折扣函數(shù)進一步優(yōu)化任務(wù)分配方案，通過對發(fā)送者與接收者無人機對于任務(wù)競價分?jǐn)?shù)的各種情況的分析，成功地消除了在任務(wù)分配階段產(chǎn)生的沖突。利用CBBA算法對偵察、攻擊兩種任務(wù)進行分配，并進行了仿真實驗與分析。實驗證明，算法能夠在任務(wù)不同時間窗的情況下對任務(wù)進行合理的分配，執(zhí)行任務(wù)的收益明顯高于未引入時間窗的CBBA算法。綜上所述，根據(jù)本文提出的異構(gòu)多無人機多任務(wù)分配算法可以得出在任務(wù)分配過程中的無沖突的方案，能夠保證多任務(wù)的成功分配。但在實際的戰(zhàn)場環(huán)境中，無人機在執(zhí)行作戰(zhàn)任務(wù)時可能遇到雷達、障礙物等威脅，可能存在執(zhí)行任務(wù)區(qū)的數(shù)量發(fā)生驟降的情況，無人機本身也會出現(xiàn)突發(fā)故障等情況。因此，多任務(wù)區(qū)任務(wù)分配方案的實時性問題將是接下來研究的重點內(nèi)容。