多無人平臺持續(xù)作業(yè)調(diào)度問題

宋志強，周獻中

（1.南京大學 工程管理學院，南京 210008；2.蘇州經(jīng)貿(mào)職業(yè)技術(shù)學院 機電與信息技術(shù)學院，浙江 蘇州 215009）

2012年，美國空軍學院開始進行一項“無人系統(tǒng)協(xié)同技術(shù)”的研究工作，進行不同類型多無人平臺協(xié)同目標跟蹤的研究，將探索融合無人平臺不同類型傳感器的數(shù)據(jù)，以提高地理定位移動目標的準確性，加強作戰(zhàn)優(yōu)勢。無人平臺（Unmanned Vechile，UV）可分為無人機（Unmanned Aerial Vehicle，UAV）、無人車（地面無人平臺）（Unmanned Ground Vehicle，UGV ） 和無人艇 （Unmanned SurfaceVehicle，USV）等。自1917年英國人研制出世界上第1架無人機，無人機經(jīng)歷了近百年的發(fā)展歷程。無人機在海灣戰(zhàn)爭、科索沃戰(zhàn)爭、阿富汗戰(zhàn)爭、伊拉克戰(zhàn)爭和利比亞戰(zhàn)爭中廣泛使用并表現(xiàn)優(yōu)異，世界各軍事強國都在積極研制本國的無人機[1]。2011年2月和4月，美國高智能化的作戰(zhàn)型無人機諾斯羅普·格魯門X-47B、“幽靈射線”無人戰(zhàn)斗機完成首飛；2014年，美國多次出動無人機空襲IS極端武裝。無人機除在軍用方面，在民用方面也具有其潛在的應(yīng)用，如災(zāi)難拯救、智能視頻監(jiān)控、海上搜救和空間探測等。地面無人平臺就是在地面上行駛的能執(zhí)行特定任務(wù)的機器人，是機械化、信息化、智能化高度融合的機動平臺。地面無人平臺技術(shù)除軍事應(yīng)用外，在民用方面也具有非常廣闊的應(yīng)用前景，如許多高溫、高寒、荒漠區(qū)域，需要地面無人平臺探測開發(fā)；另外，工業(yè)制造、農(nóng)耕作業(yè)、科學考察、搶險救災(zāi)、排爆、救援以及交通運輸?shù)阮I(lǐng)域都需要智能化的地面無人平臺。

單無人平臺由于其視線遮擋、運動限制、能量受限等因素，常常不能實現(xiàn)對目標進行連續(xù)作業(yè)，因此需要多無人平臺協(xié)作以維持對目標的持續(xù)作業(yè)，從而獲得更好的效果。多無人平臺在發(fā)現(xiàn)、跟蹤目標和搜救等方面具有重要的應(yīng)用價值，如可對目標持續(xù)監(jiān)視、跟蹤，以防止目標失聯(lián)。由于燃料或電池容量問題，無人平臺的續(xù)航時間常受到限制。在沒有后勤保障的情況下，無人平臺的持續(xù)作業(yè)能力是其應(yīng)用的瓶頸，如果無人平臺具有良好的持續(xù)作業(yè)能力，那么，無人平臺的服務(wù)能力將顯著增強。配備有能夠完成無人平臺加油、電池更換或充電等操作的自動補給站的多無人平臺系統(tǒng)使無人平臺持續(xù)作業(yè)成為可能。當一個無人平臺能量不足時，其可將任務(wù)移交給其他能量充足的無人平臺繼續(xù)執(zhí)行任務(wù)，而能量不足的無人平臺從附近的自動補給站尋求補給。本文考慮未來將多無人平臺應(yīng)用于需要持續(xù)作業(yè)的應(yīng)急救援場合，建立問題模型，通過多無人平臺和自動補給站的調(diào)度，實行多無人平臺系統(tǒng)的持續(xù)作業(yè)。

無人平臺中的無人機是目前主要的研究對象，多無人機協(xié)同問題研究是當今研究熱點，主要涉及協(xié)同偵察、協(xié)同搜索、協(xié)同探測與感知、協(xié)同任務(wù)規(guī)劃、協(xié)同跟蹤、協(xié)同路徑跟隨與編隊控制等問題。文獻[2]中研究多無人機協(xié)同偵察問題，文獻[3-5]中研究多無人機協(xié)同搜索問題，文獻[6-7]中研究協(xié)同多無人機探測與感知問題。對于協(xié)同跟蹤問題，目前研究最多的一類協(xié)同跟蹤為協(xié)同對峙跟蹤[8-9]。文獻[10]中介紹了空中和地面機器人協(xié)同工作以完成火災(zāi)監(jiān)測和滅火任務(wù)，并描述了系統(tǒng)架構(gòu)。文獻[11]中研究在動態(tài)不確定環(huán)境下多無人機實時任務(wù)

分配問題。文獻[12]中將多無人機任務(wù)規(guī)劃問題建模為標準車輛路由問題。文獻[13]中研究了任務(wù)同步情形下的無人機資源調(diào)度問題。上述文獻均未考慮無人機的能量約束問題。文獻[14]中開發(fā)了為無人機補給的自動服務(wù)站，使多無人機持續(xù)作業(yè)成為可能。文獻[15-17]中研究了多無人機持續(xù)作業(yè)問題，但系統(tǒng)考慮僅存在一個具有多端口的服務(wù)站情形，即沒有考慮存在地理上分散的多個服務(wù)站的問題。文獻[18]中研究了具有地理上分散的自動補給站支持的多無人機持續(xù)作業(yè)問題，僅將多無人機的總飛行距離作為目標函數(shù)，沒有考慮各無人機的出行成本。

文獻[18]中提出的模型目標函數(shù)僅是最小化總距離，即只考慮同構(gòu)平臺，而由于異構(gòu)無人平臺構(gòu)成的系統(tǒng)更具普遍意義。因此，本文考慮由于無人平臺型號、功能等的不同，引起的無人平臺出動成本的不同，將其也納入目標函數(shù)；同時，考慮無人機的飛行距離與出行成本，更符合實際情況。

1 情景想定

鑒于已有電池更換系統(tǒng)[19]應(yīng)用于無人機，在此假想未來多無人機系統(tǒng)在執(zhí)行應(yīng)急任務(wù)時，具有地理位置分散的自動補給站作為后勤保障，無人平臺在自動補給站可完成加油或電池更換等能量補充，也可在自動補給站裝配應(yīng)急物資等，以便多無人平臺能夠持續(xù)、不間斷地完成任務(wù)。圖1為具有3個補給站、4架無人機和3個目標的示例系統(tǒng)。

圖1 具有3個補給站、4架無人機和3個任務(wù)的示例系統(tǒng)

為了解決無人平臺能量有限的問題，本文提出多無人平臺共享地理上分散的自動補給站的思想，設(shè)計調(diào)度算法來協(xié)調(diào)任務(wù)。假定無人平臺要完成的任務(wù)的時空軌跡是確定的，至少有一個無人平臺執(zhí)行任務(wù)。如圖1所示，多無人機系統(tǒng)任務(wù)是為時空軌跡確定的3個目標提供不間斷的服務(wù)，其中目標1和目標2是靜止的，均為待無人機服務(wù)的應(yīng)急需求點。3個候選自動補給站分布于任務(wù)空間，它們可被任一無人機使用。其中的一個可行方案為UAV1從自動補給站1出發(fā)，先向目標2提供服務(wù)；然后飛至自動補給站2補充能源和資源，之后飛至目標2提供服務(wù)；最后，返回自動補給站2。無人機的另一任務(wù)是對運動目標3進行護航或跟蹤，由于運動目標3的路徑持續(xù)時間大于無人機的最大飛行時間，則首先由UAV4提供服務(wù)，在UAV4出現(xiàn)能量預(yù)警時，將其任務(wù)移交給UAV3，由UAV3完成剩余的服務(wù)，而UAV4 飛至自動補給站2 進行補給。在該方案中，UAV2不參與任務(wù)的執(zhí)行。整個系統(tǒng)的協(xié)同可使得任務(wù)不中斷的執(zhí)行。

Kim 等[18]提出通過無人機和服務(wù)站的合理調(diào)度，可使無人機持續(xù)跟蹤給定時空軌跡的思想。借鑒其思想，本文將具有確定性時空軌跡的任務(wù)分為多個子任務(wù)。由于油量或電池容量有限，單個無人平臺可能不能執(zhí)行整個完整的任務(wù)，故有必要將一個任務(wù)分為若干個子任務(wù)。如圖2所示，根據(jù)運動目標的軌跡將任務(wù)分為若干子任務(wù)，每個子任務(wù)可由一個無人平臺提供服務(wù)。由于假定目標的運動軌跡是確定的，故可獲得每個子任務(wù)的開始和結(jié)束坐標，子任務(wù)i的起始和結(jié)束坐標分別為（x is，y is）、（x ie，y ie）。子任務(wù)的數(shù)量及其位置和時間可預(yù)先確定。用Dij表示子任務(wù)i的終點或自動補給站i至子任務(wù)j的起點或自動補給站j的歐式距離。

圖2 將運動目標時空軌跡分為子任務(wù)

2 符號定義

各符號含義：

i，j——任務(wù)索引，i，j∈ΩJ=｛1，2，…，N J｝

s——自動補給站索引

k——無人平臺索引，k∈K=｛1，2，…，NUV｝

l——無人平臺第l次出行索引，l∈L=｛1，2，…，N L｝

W t——無人平臺單位距離行進成本

P k——無人平臺出動成本

N J——系統(tǒng)中子任務(wù)數(shù)量

NUV——系統(tǒng)中無人平臺數(shù)量

NSTA——系統(tǒng)中自動補給站數(shù)量

NL——無人平臺出行最大次數(shù)

M——大正數(shù)

Dij——子任務(wù)i的終點或自動補給站i至子任務(wù)j的起點或自動補給站j的距離。注意，由于起點和終點的變化，故Dij不一定等于D ji

Si——子任務(wù)i的開始時間

Ei——子任務(wù)i的結(jié)束時間

H i——子任務(wù)i的處理時間（Ei-Si）

T——無人平臺在自動補給站的補給時間

Qk——無人平臺k的最大續(xù)航時間

Sok——無人平臺k的初始位置

MSk——無人平臺k的最大速度

ΩJ——子任務(wù)集，ΩJ=｛1，2，…，N J｝

ΩSS——無人平臺任務(wù)起始站集，

ΩSS=｛N J+1，N J+3，…，N J+2NSTA-1｝

ΩSE——無人平臺任務(wù)結(jié)束站集，

ΩSE=｛N J+2，N J+4，…，N J+2NSTA｝

ΩA——所有任務(wù)和自動補給站集，ΩA=ΩJ∪ΩSS∪ΩSE

X ijkl——二進制決策變量，若無人平臺k在第l次出行期間，在處理完子任務(wù)i或在站i完成補給后，處理子任務(wù)j或在站j補給，則為1，否則為0

Cikl——決策變量，若無人平臺k在第l次出行期間，執(zhí)行子任務(wù)i開始時間或無人平臺k在站i補給開始時間，否則為0

3 建 模

在此，除考慮無人平臺最大速度約束外，不考慮如無人平臺的其他飛行動力學約束。本文將多無人平臺的持續(xù)作業(yè)調(diào)度問題描述為混合整數(shù)線性規(guī)劃（MILP），目標函數(shù)為最小化無人平臺出行和出動總成本為：

初始自動補給站約束式（2）確保每個無人平臺從其初始自動補給站開始第一次作業(yè)。自動補給站約束式（3）確保每次作業(yè)無人平臺k僅從一個自動補給站出發(fā)至子任務(wù)。式（4）確保無人平臺k每次作業(yè)必須且僅在一個結(jié)束補給站完成。式（5）確保無人平臺k第l次出行結(jié)束站和其l+1次作業(yè)起始站相同。式（6）表明，在同一自動補給站無人平臺第l次出行完成時間與其第l+1次出行開始時間的關(guān)系。子任務(wù)分配約束式（7）確保在ΩJ集中的每個子任務(wù)都能由一個無人平臺處理。式（8）確保無人平臺不能在子任務(wù)上結(jié)束工作。式（9）確保無人平臺不能在起始站（s∈ΩSS）完成作業(yè)，此約束來自于每個站有兩個索引。開始時間約束式（10）給出了無人平臺k第l次出行期間子任務(wù)i或站i的補給開始時間與無人平臺下一步動作的關(guān)系。式（11）隱含信息為若子任務(wù)i未分配給第l次出行的無人平臺k，則決策變量Cikl為0。式（12）保證在ΩJ集中的每個子任務(wù)均能在預(yù)先確定的開始時間被執(zhí)行。能量約束式（13）表明，無人平臺k的包括旅途時間和子任務(wù)處理時間在內(nèi)的總出行時間不超過無人平臺k的最大續(xù)航時間。被選中無人平臺約束式（14）確保僅選中的無人平臺去執(zhí)行子任務(wù)。決策變量非負和整數(shù)約束式（15）、（16）限定的決策變量的取值范圍。

由于式（5）、（6）的約束，該數(shù)學模型要求NL＞1。NL只是無人平臺出行最大次數(shù)，并不限制模型能力。文獻[18]中使用決策變量Y ikl表示UAVk在第l次出行時，子任務(wù)i分配給UAVk，但該信息其實已經(jīng)隱含在決策變量Cikl中，故可刪除。本文所設(shè)計模型比文獻[18]中的模型決策變量要少，從而減少了計算復(fù)雜度。若無人平臺最大出行次數(shù)NL=1，則式（5）、（6）可刪除。

4 算例求解

仿真試驗在PC 機上運行，PC 機配置為Intel（R）Core（TM）2 Duo CPU E7200，2.52 GHz，2 GB內(nèi)存，仿真軟件采用MATLAB 2014a，利用該版本提供的Intlinprog 函數(shù)可較方便地求解MILP問題。

算例1假設(shè)有3 個任務(wù)需要無人平臺來完成，其中任務(wù)1和任務(wù)2需要無人平臺運送應(yīng)急物資至指定位置處，任務(wù)1的坐標在（100，450）處，任務(wù)2的坐標在（150，100）處，任務(wù)3為無人平臺跟隨目標3運動軌跡，任務(wù)3起始坐標為（590，590），終止坐標為（590，11）。有3個候選自動補給站（Station），Station1 坐標為（50，200），初始有UV1和UV2，Station2的坐標為（500，600），初始有UV3和UV4，Station3 的坐標為（450，300），初始有UV5。系統(tǒng)初始部署圖如圖3所示。

圖3 系統(tǒng)初始部署圖

將3個任務(wù)分為6個子任務(wù)，假設(shè)每個子任務(wù)的處理時間均為2 min，子任務(wù)信息如表1所示，將任務(wù)3分解為子任務(wù)1、2、3、4。任務(wù)1、2即子任務(wù)5、6。

表1 算例1的3個任務(wù)分成6個子任務(wù)的信息

仿真參數(shù)表如表2所示。

表2 仿真參數(shù)表

將上述MILP問題在Matlab 2014a中求解，當無人平臺的最大續(xù)航時間Qk=16 min時，UV1從自動補給站1出發(fā)，先執(zhí)行子任務(wù)5（即任務(wù)1），接著執(zhí)行子任務(wù)6（即任務(wù)2），然后返回自動補給站1；UV3從自動補給2站出發(fā)，依次執(zhí)行子任務(wù)1、2、3、4，然后至自動補給站3。整個過程總費用為13 337.5元，期間UV2、UV4、UV5 不參與任務(wù)執(zhí)行。由于Qk=16 min，UV3從自動補給2站出發(fā)，依次執(zhí)行子任務(wù)1、2、3、4，返回自動補給站3，不違反式（13）的約束條件，故由UV3完成任務(wù)1。

當無人平臺的最大續(xù)航時間Qk=8 min時，受式（10）約束，UV1從自動補給站1出發(fā)，執(zhí)行子任務(wù)5（即任務(wù)1），然后返回自動補給站1；UV2從自動補給站1出發(fā)，執(zhí)行子任務(wù)6（即任務(wù)2），然后返回自動補給站1。受式（13）約束，UV3從自動補給2站出發(fā)，執(zhí)行子任務(wù)1、2后，然后至自動補給站3補給；UV5從自動補給3 站出發(fā)，執(zhí)行子任務(wù)3、4后，返回自動補給站3。由于最大續(xù)航時間的約束，由子任務(wù)1、2、3、4組成的任務(wù)1由UV3、UV5協(xié)作完成，對于任務(wù)1而言，由于多無人平臺的“接力”，彌補了單一無人平臺由于能量有限而無法完成整個任務(wù)的缺點，實現(xiàn)了多無人平臺持續(xù)不間斷地作業(yè)。整個過程總費用為￥16 453，期間UV4不參與任務(wù)執(zhí)行。

算例2假設(shè)由無人平臺進行邊境巡邏，自動補給站1 位于（300，600），自動補站2 位于（600，300）處，開始時UV1、UV2分別位于站1、站2，有4條巡邏路徑需無人機遵循，各路徑的起點、終點如圖4所示。

圖4 無人平臺邊境巡邏部署圖

路徑1、2、3、4需分別于6、18、6、18 min開始，無人平臺的最大速度為150 m/min，如表3所示，將整個巡邏任務(wù)分為8個子任務(wù)，各無人平臺的最大續(xù)航時間Qk=15 min。

表3 算例2的8個子任務(wù)信息

W t=8 元/m，UV1 的P1=400 元，UV2 的P2=700元，用Matlab 2014a可求得最優(yōu)解：UV1從站1出發(fā)，完成子任務(wù)1、2、3、4，然后進入站2補給。UV2從站2出發(fā)，完成子任務(wù)5、6、7、8后進入站1補給，整個過程總費用為27 088元。

5 結(jié)語

無人平臺由于電池壽命或燃料量的限制，其應(yīng)用受到制約，單一無人平臺不能進行持續(xù)作業(yè)。具備地理上分散的自動補給站支持的多無人平臺系統(tǒng)可完成持續(xù)時間長的任務(wù)。對于確定性任務(wù)而言，無人平臺在作業(yè)時若能量即將耗盡，則可至附近自動補給站獲得補給，而后再次作業(yè)或在自動補給站待命。同時，其他無人平臺接替該無人平臺的工作，繼續(xù)任務(wù)的執(zhí)行。通過自動補給站，任務(wù)可被多個無人平臺以“接力”的形式不間斷地執(zhí)行。本文將多無人平臺任務(wù)調(diào)度問題建模為混合整數(shù)線性規(guī)劃（MILP）問題，并用Matatb 2014a求解實例。結(jié)果表明，多無人平臺持續(xù)作業(yè)調(diào)度可提高系統(tǒng)的自主性和實用性。用啟發(fā)式或智能算法來解決MILP問題[20]是今后該領(lǐng)域的努力方向。