網(wǎng)絡(luò)化戰(zhàn)場環(huán)境下多無人機(jī)調(diào)度問題*

馬純超，尹 棟，朱華勇

（國防科技大學(xué)機(jī)電工程與自動化學(xué)院，長沙 410073）

網(wǎng)絡(luò)化戰(zhàn)場環(huán)境下多無人機(jī)調(diào)度問題*

馬純超，尹 棟，朱華勇

（國防科技大學(xué)機(jī)電工程與自動化學(xué)院，長沙 410073）

針對網(wǎng)絡(luò)化戰(zhàn)場下無人機(jī)（UAV）跨區(qū)飛行、信息共享等特點(diǎn)擴(kuò)大了任務(wù)區(qū)域與規(guī)模而引發(fā)任務(wù)分配難題，對無人機(jī)運(yùn)動及通信特性、任務(wù)時間窗約束和初始戰(zhàn)場布局等因素建模，根據(jù)目標(biāo)屬性對其分組以降低問題復(fù)雜度，應(yīng)用優(yōu)化算法得到初始解，隨后進(jìn)行全局交換、刪除及插入等調(diào)整得到最終調(diào)度方案，由此搭建快速求解多UAV任務(wù)調(diào)度的通用算法框架。最后應(yīng)用遺傳算法驗證，仿真結(jié)果表明：該框架在解決多無人機(jī)大規(guī)模任務(wù)分配時具有較好的時效性和適應(yīng)性。

網(wǎng)絡(luò)化戰(zhàn)場，多無人機(jī)任務(wù)分配，遺傳算法

0 引言

信息化戰(zhàn)場下，數(shù)據(jù)鏈將戰(zhàn)場上的指揮中心、各級指揮所、各參戰(zhàn)部隊和武器平臺鏈接在一起，構(gòu)成陸海空天一體化數(shù)字信息網(wǎng)絡(luò)，保證各系統(tǒng)之間的數(shù)據(jù)傳輸與資源共享。在該戰(zhàn)場環(huán)境下，為優(yōu)化資源配置，各種類無人機(jī)被統(tǒng)一管理，并可跨區(qū)域執(zhí)行任務(wù)，相比傳統(tǒng)多無人機(jī)任務(wù)分配，該類問題約束與規(guī)模更復(fù)雜，且要求一定時效性，傳統(tǒng)約束滿足問題（CSP）算法難以滿足要求。

對復(fù)雜約束的多無人機(jī)多目標(biāo)任務(wù)分配問題，傳統(tǒng)的完全搜索方法難以有效或快速得到最優(yōu)解，多采用改進(jìn)的禁忌搜索［1-2］、群體進(jìn)化［3-4］、市場拍賣［5］求解，或結(jié)合多種算法優(yōu)勢得到更優(yōu)方案［2，6-7］。針對多區(qū)域和大規(guī)模無人機(jī)使用，為提高任務(wù)分配有效性和時效性，文獻(xiàn)［8］建立多基地多UAV協(xié)同規(guī)劃模型，采用“自適應(yīng)”進(jìn)化多目標(biāo)優(yōu)化算法對不同位置、不同性能的無人機(jī)進(jìn)行規(guī)劃；文獻(xiàn)［9］對目標(biāo)進(jìn)行模糊C聚類，從局部出發(fā)優(yōu)化，得到快速分配方案。文獻(xiàn)［10］基于任務(wù)依賴關(guān)系結(jié)合迭代自組織數(shù)據(jù)分析算法（ISODATA）對任務(wù)進(jìn)行分組，使用粒子群優(yōu)化算法得到任務(wù)分配方案。

文獻(xiàn)［8］中UAV被限制在所屬基地控制下，UAV的使用被限制；文獻(xiàn)［3-4，10］將任務(wù)執(zhí)行時間作為代價考慮，而未考慮時間窗約束；文獻(xiàn)［2，7，9］中對目標(biāo)自身特性如其優(yōu)先級等的不同未加考慮。且除文獻(xiàn)［5，8］外，其他文獻(xiàn)實(shí)驗中目標(biāo)可全部被UAV分配，對UAV不能全部完成任務(wù)時如何取舍考慮稍欠缺。除文獻(xiàn)［8］外以上研究均在單基地下考慮。本文基于以上研究，結(jié)合問題特性，分析UAV平臺特性、任務(wù)約束、戰(zhàn)場初始布局等因素對多UAV任務(wù)分配的影響。針對問題規(guī)模較大的情況，對目標(biāo)分組處理降維，得到局部初始解，隨后全局調(diào)整得到最優(yōu)解。

1 通用戰(zhàn)術(shù)網(wǎng)下多UAV資源調(diào)度問題

通用戰(zhàn)術(shù)網(wǎng)由通用數(shù)據(jù)鏈路和通用控制鏈路組成，使得戰(zhàn)場中的平臺、系統(tǒng)連接成有機(jī)整體。通用控制鏈路使得UAV活動擺脫了傳統(tǒng)視距鏈約束，可由分布于戰(zhàn)場的任一具有相應(yīng)操控能力的地面站（GCS）控制飛行。通用數(shù)據(jù)鏈聯(lián)網(wǎng)使得分布于戰(zhàn)場任意位置的UAV可將得到的信息進(jìn)行全局共享，使整個戰(zhàn)場的各級作戰(zhàn)單元共享高度的感知信息，實(shí)現(xiàn)作戰(zhàn)同步化。

在此背景下，UAV、地面站及通信鏈路等均被作為資源由指揮中心進(jìn)行統(tǒng)一管理和調(diào)度，根據(jù)任務(wù)約束及要求，合理選派資源，由地面站控制UAV執(zhí)行任務(wù)。

1.1 問題描述

如圖1，假設(shè)通用戰(zhàn)術(shù)網(wǎng)絡(luò)已建立，在［0，S］*［0，S］戰(zhàn)場區(qū)域內(nèi)分布有Ng個不同能力的地面控制站{GCS1，GCS2…GCSNg}和隨機(jī)分布的Nv個不同類型的UAV{V1，V2…VNv}，及Nt個目標(biāo) {T1，T2…TNt}。UAV由任務(wù)管理中心進(jìn)行統(tǒng)一管理。任務(wù)管理中心從戰(zhàn)場全局出發(fā)，綜合考慮UAV平臺特性、目標(biāo)特點(diǎn)和GCS等戰(zhàn)場環(huán)境進(jìn)行多UAV對多目標(biāo)進(jìn)行偵察的任務(wù)規(guī)劃。

UAV平臺特性主要考慮其巡航速度、搭載傳感器不同等方面，目標(biāo)考慮其優(yōu)先級和時間窗特性等，GCS能力的不同則體現(xiàn)在其可操控的UAV數(shù)量和通信覆蓋范圍等。表1用多元數(shù)組對各因素進(jìn)行了形式化描述。

1.2 通用求解框架

針對網(wǎng)絡(luò)化戰(zhàn)場下大規(guī)模UAV任務(wù)分配難以快速找到最優(yōu)解，提出的解決方案是首先將任務(wù)目標(biāo)按照一定原則分類，分為有一定共同特性的子集合。根據(jù)任務(wù)子集需要的UAV能力選取執(zhí)行任務(wù)的UAV集合，對目標(biāo)子集合分別按時間窗、優(yōu)先級等排序后，依次采用優(yōu)化算法求得最優(yōu)初始解，最后進(jìn)行全局調(diào)整，得到優(yōu)化分配方案。

1.2.1 算法設(shè)計及步驟

算法框架主要分為任務(wù)目標(biāo)預(yù)處理、求解初始解和初始解改進(jìn)3部分。下頁圖2給出了算法設(shè)計流程。

具體實(shí)施過程如下：

（1）目標(biāo)預(yù)處理。主要進(jìn)行目標(biāo)分組，降低問題規(guī)模。目標(biāo)分組目的是對一組目標(biāo)點(diǎn)盡可能使用同樣的UAV資源執(zhí)行，通常的分類原則有：①目標(biāo)偵察情報類型要求（圖像、視頻及其分辨率等）。②目標(biāo)緊急程度。③目標(biāo)位置（聚集在同一區(qū)域或在某無人機(jī)活動半徑內(nèi)）。④對時間跨度較長的目標(biāo)，將處在同一時間段內(nèi)的目標(biāo)分為一組。⑤同一通信覆蓋區(qū)域內(nèi)的目標(biāo)歸為一組等等。針對分組并排序后的目標(biāo)集合，選取具有執(zhí)行該組目標(biāo)能力的UAV集合進(jìn)行調(diào)度。

（2）求解初始解。對得到的目標(biāo)與無人機(jī)集合，依照其不同分組原則等，選取如遺傳算法、粒子群算法等合適的最優(yōu)化算法求取子問題初始解。

（3）初始解改進(jìn)。按照步驟2得到的初始解，只是問題的局部較優(yōu)解，需要從全局進(jìn)一步改進(jìn)。對于不同的解序列，根據(jù)其時間窗的共同覆蓋程度，可以對解序列進(jìn)行一系列插入、刪除、交換、重新排序等調(diào)整，從而獲得全局最優(yōu)或較優(yōu)解。

如圖3所示全局調(diào)整優(yōu)化方案實(shí)例，對UAV1、UAV2的任務(wù)序列，任務(wù)j在UAV1的空閑時間窗內(nèi)，若j目標(biāo)位置滿足UAV1從i目標(biāo)飛行至i+1目標(biāo)的時間段內(nèi)執(zhí)行，則可將j目標(biāo)插入UAV1的任務(wù)序列中。同樣，若i+2與j+2目標(biāo)交換后使全局優(yōu)化值更高，則可以進(jìn)行交換。

1.2.2 問題數(shù)學(xué)建模

對某含有N個目標(biāo)的任務(wù)子集合T={1，2，3，…，i，j，…，N}，其對應(yīng)含M架無人機(jī)集合UAV= {1，2，3，…，k，…，M}，決策變量xijk表示無人機(jī)k從執(zhí)行完任務(wù)i后繼續(xù)執(zhí)行任務(wù)j。UAV分配任務(wù)的3個優(yōu)化指標(biāo)主要為任務(wù)完成的收益最大、代價最小和分配的目標(biāo)盡量多。

任務(wù)收益優(yōu)化目標(biāo)：

rijk表示從i出發(fā)去執(zhí)行j時獲得的收益，收益由目標(biāo)的優(yōu)先級確定，rijk=xijk*L（j），保證盡量執(zhí)行優(yōu)先級高的目標(biāo)。

任務(wù)代價優(yōu)化目標(biāo)：

cijk表示從i出發(fā)去執(zhí)行j時的代價，包括路徑代價和通信代價。通信代價與目標(biāo)位置距離GCS距離相關(guān)，dis為目標(biāo)間距離。結(jié)合通信信號在自由空間衰減公式

可以將無人機(jī)從i目標(biāo)出發(fā)執(zhí)行j目標(biāo)的代價表示為式（4）。式（5）中Lbf：自由空間損耗，F(xiàn)：信號頻率，D:傳輸距離。路徑代價即各個目標(biāo)點(diǎn)之間距離之和。

任務(wù)分配個數(shù)優(yōu)化指標(biāo)，表示分配的目標(biāo)個數(shù)盡可能多：

式（7）約束每個目標(biāo)只被某一UAV單獨(dú)執(zhí)行。式（8）為航程約束，式（9）、式（10）為時間窗約束：

［ai，bi］代表任務(wù)i的任務(wù)時間窗，tstarti/tstartj：實(shí)際開始偵察目標(biāo)i/j的時間，tleavei/tleavej：實(shí)際離開目標(biāo)i/j的時間，twaitj：開始偵察目標(biāo)j時的等待時間，tworkj：目標(biāo)j的實(shí)際偵察持續(xù)時間。

2 遺傳算法求解算例

為驗證算法框架合理性，根據(jù)分析的問題特點(diǎn)，對傳統(tǒng)遺傳算法進(jìn)行改進(jìn)并驗證。

2.1 編碼

本文將任務(wù)序列集合作為一條染色體，每個基因表示一個任務(wù)目標(biāo)，基因取值為無人機(jī)的編號。圖4表示大小為n的目標(biāo)集合編碼。編號為2的無人機(jī)執(zhí)行第1、3、7…等個目標(biāo)，0為該目標(biāo)未被任何UAV執(zhí)行。采用對基因位隨機(jī)賦值UAV編號的形式進(jìn)行群體初始化，并用時間窗約束式（9）、式（10）判斷生成的群體是否可行。

2.2 適應(yīng)度函數(shù)

該問題是復(fù)雜的多目標(biāo)優(yōu)化問題，為便于求解，將多個目標(biāo)函數(shù)設(shè)置不同權(quán)值融合在一個目標(biāo)函數(shù)中。由此定義適應(yīng)度函數(shù)：

其中Reward為染色體對應(yīng)解得到的總收益，Cost為其總代價，Percent為目標(biāo)完成度（完成目標(biāo)數(shù)與總目標(biāo)數(shù)的比值）。權(quán)值設(shè)定一般根據(jù)決策者的偏好或經(jīng)驗確定。由于目標(biāo)函數(shù)的量綱不同，為保證優(yōu)化結(jié)果的合理性，需將它們統(tǒng)一到同一數(shù)量級上。如本問題未調(diào)整時Reward的數(shù)量級在102而1/Cost數(shù)量級在10-1，則代價的變化對適應(yīng)值的影響將被收益指標(biāo)所“淹沒”，導(dǎo)致優(yōu)化結(jié)果不合理。

2.3 遺傳算子

根據(jù)本問題自身特殊性，遺傳算子中除選擇算子仍采用傳統(tǒng)輪盤賭法，對交叉算子和變異算子均做如下改進(jìn)。

2.3.1 交叉算子

對隨機(jī)兩兩配對的每對父代個體，生成0-1內(nèi)的隨機(jī)數(shù)與交叉概率Pc比較，小于Pc的配對按照設(shè)置的交叉點(diǎn)進(jìn)行交叉。交叉算子如圖5，長度為n的染色體存在n-1個交叉點(diǎn)，設(shè)置交叉點(diǎn)時首先隨機(jī)生成n-1個［1，n-1］范圍內(nèi)的不重復(fù)隨機(jī)數(shù)，依次按照生成的隨機(jī)數(shù)設(shè)置交叉點(diǎn)，直到交叉后個體仍為可行個體，將其遺傳到子代種群。若全部交叉點(diǎn)設(shè)置完仍無可行個體，則不進(jìn)行交叉，直接遺傳到下一代。

2.3.2 變異算子

變異算子的處理是對每個長度為n的染色體生成［0，1］內(nèi)的n個隨機(jī)數(shù)，與變異概率Pm比較，小于變異概率值的進(jìn)行變異。在該問題中，如圖6，當(dāng)個體需要變異時，優(yōu)先變異基因值為0的位置，置換為其他無人機(jī)編號，判斷變異后個體是否為可行解，若均不可行，則變異隨機(jī)數(shù)小于Pm的位置，置換為不同于該位置的無人機(jī)編號，判斷是否可行。若均不可行則不進(jìn)行變異。規(guī)定同一染色體只有一處基因值發(fā)生變異。

3 仿真結(jié)果與分析

3.1 結(jié)果分析

假設(shè)在800 km*800 km的戰(zhàn)區(qū)內(nèi)存在3個地面控制站，8架偵察UAV對隨機(jī)分布在戰(zhàn)區(qū)不同位置的40個目標(biāo)進(jìn)行偵察。下頁表2、表3給出了UAV和目標(biāo)的仿真數(shù)據(jù)。

對40個目標(biāo)根據(jù)位置進(jìn)行分類，按照時間窗和優(yōu)先級進(jìn)行排序，并選取相應(yīng)UAV集合，最終得到3組目標(biāo)集合及對應(yīng)UAV的編號集合，如下頁表4。

根據(jù)上述算法描述，優(yōu)先對T1、T3進(jìn)行分配，對T1、T3中未進(jìn)行分配的目標(biāo)選取優(yōu)先級較高的加入T2，初始群體設(shè)置為100個，交叉概率Pc=0.75，變異概率Pm=0.01，遺傳1 000代，權(quán)重值w1=0.5，w2=0. 3，w3=0.2。每組目標(biāo)序列執(zhí)行10次算法，由于遺傳算法的初始解是隨機(jī)生成的，且進(jìn)化方向不定，因此會產(chǎn)生適應(yīng)度收斂到一定值的幾個不同結(jié)果，挑選適應(yīng)值最大的4組，得到圖7分配結(jié)果，T2序列中被標(biāo)記出的為其他兩個序列未分配且優(yōu)先級較高而加入的目標(biāo)。

程序平均規(guī)劃時間72 s，40個目標(biāo)點(diǎn)中10個目標(biāo)未分配，成功率為75%。仿真實(shí)驗中目標(biāo)點(diǎn)與UAV位置及任務(wù)時間窗均是隨機(jī)得到的，目標(biāo)特性與UAV能力導(dǎo)致目標(biāo)并不一定被分配。圖8和圖9給出了仿真實(shí)驗結(jié)果中不同UAV執(zhí)行任務(wù)的順序和時間窗，綜合兩圖及目標(biāo)參數(shù)可以看出：①未被分配的目標(biāo)其優(yōu)先級一般較小。②未分配目標(biāo)其位置和時間窗相互約束，即盡管其時間窗在其他UAV空閑時間范圍內(nèi)，但地理位置相差較遠(yuǎn)導(dǎo)致不可能完成該目標(biāo)，同樣在UAV執(zhí)行路徑附近的其他目標(biāo)因時間窗不符合同樣不能被分配。根據(jù)時間窗進(jìn)行全局調(diào)整已經(jīng)找不到更優(yōu)解，且規(guī)劃時間較短，可判定該方案是最優(yōu)的。

3.2 算法比較

為判斷算法的適應(yīng)性，分別進(jìn)行4架UAV對20個目標(biāo)，8架UAV對40個目標(biāo)，15架UAV對80個目標(biāo)，用傳統(tǒng)遺傳算法和本文先分組求初始解并全局調(diào)整的改進(jìn)算法進(jìn)行分配，得到結(jié)果數(shù)據(jù)如下：

從實(shí)驗可以看出，在問題規(guī)模較小時，本文提出的分組遺傳算法由于需要進(jìn)行多次求解并全局調(diào)整，傳統(tǒng)遺傳算法更具優(yōu)勢，但當(dāng)問題規(guī)模擴(kuò)大，需要搜索的解空間規(guī)模呈指數(shù)級增長，分組遺傳算法的規(guī)劃時間遠(yuǎn)低于傳統(tǒng)遺傳算法，在15架UAV，80個目標(biāo)時，傳統(tǒng)算法在執(zhí)行1 h后仍未找到可行解，分組遺傳算法則在較短時間內(nèi)可以給出合理的分配方案。

4 結(jié)束語

本文研究了基于戰(zhàn)術(shù)通用數(shù)據(jù)鏈在戰(zhàn)場全局調(diào)度下無人機(jī)的多目標(biāo)分配問題，對問題規(guī)模較大難以求解的難題，提出對目標(biāo)分組降低問題緯度，求得一系列初始解并進(jìn)一步進(jìn)行全局調(diào)整，得到最終解決方案的思路方法。通過仿真實(shí)驗可以看出本文設(shè)計的目標(biāo)分組求解并在全局調(diào)整尋找最優(yōu)解的算法，對較大規(guī)模的無人機(jī)目標(biāo)分配問題具有較好的合理性、時效性和適應(yīng)性。同時可以根據(jù)決策者的不同偏好設(shè)置適應(yīng)度權(quán)重系數(shù)以滿足決策需要，具有較大的實(shí)際應(yīng)用性。下一步工作將對約束因素更加實(shí)際化考慮，如將路徑代價替換為油耗模型，偵察得到的不同情報類型的回傳方式對分配的影響，調(diào)度過程中的安全問題及動態(tài)任務(wù)的調(diào)整，使算法更具實(shí)際性。

［1］陳英武，方炎申，李菊芳，等.衛(wèi)星任務(wù)調(diào)度問題的約束規(guī)劃模型［J］.國防科技大學(xué)學(xué)報，2006，28（5）:126-132.

［2］Yan P，Tan B.Evolutionary Group Theoretic Tabu Search Approach to Task Allocation of Autonomous Unmanned Aerial Vehicles［C］//Control and Automation（ICCA），2013 10th IEEE InternationalConference on.IEEE，2013: 687-692.

［3］施展，陳慶偉.基于改進(jìn)的多目標(biāo)量子行為粒子群優(yōu)化算法的多無人機(jī)協(xié)同任務(wù)分配［J］.南京理工大學(xué)學(xué)報，2012，36（6）:945-951.

［4］王婷，符小衛(wèi)，高曉光.基于改進(jìn)遺傳算法的異構(gòu)多無人機(jī)任務(wù)分配［J］.火力與指揮控制，2013，38（5）:37-41.

［5］Lin L，Sun Q B，Wang S G，et al.Research on PSO Based Multiple UAVs Real-Time Task Assignment［C］//2013 25th Chinese Control and Decision Conference（CCDC），2013: 1530-1536.

［6］龍國慶，祝小平，周洲.多無人機(jī)系統(tǒng)協(xié)同多任務(wù)分配模型與仿真［J］.飛行力學(xué)，2011，29（4）:68-71.

［7］Liu Z，Quan L，Ding W，et al.A Task Assignment Algorithm for Multiple AerialVehicles to Attack Targets With Dynamic Values［C］//IEEE Transactions on Intelligent Transportation Systems，2013，14（1）:236-248.

［8］田菁.多無人機(jī)協(xié)同偵察任務(wù)規(guī)劃問題建模與優(yōu)化技術(shù)研究［D］.長沙：國防科學(xué)技術(shù)大學(xué)，2007.

［9］龍國慶，祝小平，董世友.基于聚類算法的多無人機(jī)系統(tǒng)任務(wù)分配［J］.火力與指揮控制，2011，36（12）:54-59.

［10］譚和順，曹雷，彭輝，等.一種多無人機(jī)層次化任務(wù)分配方法［J］.解放軍理工大學(xué)學(xué)報（自然科學(xué)版），2014，15（1）:18-24.

A Study on Multi-UAVs Scheduling in Networked Battlefield

MA Chun-chao，YIN Dong，ZHU Hua-yong
（College of Mechatronic Engineering and Automation，National University of Defense Technology，Changsha 410073，China）

In networked battlefield，UAVs can fly cross regions and share information to others，which expand the area and scale of tasks.In order to address the difficulties of mission allocation caused by that，this paper will first model UAVs motion and communication features，task time window，initial battlefield layout，etc.，group the targets by their characteristics in order to reduce the complexity，then apply optimization algorithm to obtain initial solution and adjust them through exchange，deletion or insert so as to obtain the final plan，and build a common algorithm framework for fast solution.Genetic algorithm will be employed for verification.The simulation results indicate that the framework may achieve higher timeliness and adaptability in large-scale multi-UAV mission allocation.

networked battlefield，multi-UAVs mission allocation，genetic algorithm

V279

A

1002-0640（2015）10-0031-06

2014-09-05

2014-10-17

國家自然科學(xué)基金青年科學(xué)基金資助項目（71303252）

馬純超（1990- ），男，河北衡水人，碩士研究生。研究方向：無人機(jī)系統(tǒng)技術(shù)。