考慮時(shí)間窗約束的多無人機(jī)任務(wù)分配

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

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

0 引言

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

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

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

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

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

1.1 問題描述

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

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

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

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

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

(1)

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

(2)

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

(3)

(4)

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

(5)

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

(6)

1.2.2 約束條件

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

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

(7)

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

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

(8)

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

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

(9)

2 CBBA算法設(shè)計(jì)

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

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

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

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

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

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

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

每架無人機(jī)構(gòu)建一個(gè)任務(wù)包，根據(jù)自己的載彈能力將能使自己的收益達(dá)到最大的任務(wù)依次加入到任務(wù)包中，按照無人機(jī)計(jì)劃完成任務(wù)的順序進(jìn)行排序。用Bi表示添加到無人機(jī)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)建完成之后，無人機(jī)之間需進(jìn)行通信來交流競拍得到的任務(wù)信息。無人機(jī)需要考慮自己對(duì)所選任務(wù)的出價(jià)是否高于最高出價(jià)，以及每個(gè)任務(wù)可以被分配的無人機(jī),這就需要一定的規(guī)則來消解沖突。沖突消解的目的就是確保每個(gè)任務(wù)只能分配給一架無人機(jī)。

2.3 沖突消解

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

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

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

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

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

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

3 仿真驗(yàn)證

3.1 任務(wù)場景

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

表2 無人機(jī)屬性

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

圖3 每架無人機(jī)具體分配時(shí)間圖Fig.3 Specific time allocation of each UAV

3.2 結(jié)果分析

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

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

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

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

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

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

4 結(jié)論

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