馬純超,尹 棟,朱華勇
(國防科技大學機電工程與自動化學院,長沙 410073)
網絡化戰(zhàn)場環(huán)境下多無人機調度問題*
馬純超,尹 棟,朱華勇
(國防科技大學機電工程與自動化學院,長沙 410073)
針對網絡化戰(zhàn)場下無人機(UAV)跨區(qū)飛行、信息共享等特點擴大了任務區(qū)域與規(guī)模而引發(fā)任務分配難題,對無人機運動及通信特性、任務時間窗約束和初始戰(zhàn)場布局等因素建模,根據目標屬性對其分組以降低問題復雜度,應用優(yōu)化算法得到初始解,隨后進行全局交換、刪除及插入等調整得到最終調度方案,由此搭建快速求解多UAV任務調度的通用算法框架。最后應用遺傳算法驗證,仿真結果表明:該框架在解決多無人機大規(guī)模任務分配時具有較好的時效性和適應性。
網絡化戰(zhàn)場,多無人機任務分配,遺傳算法
信息化戰(zhàn)場下,數據鏈將戰(zhàn)場上的指揮中心、各級指揮所、各參戰(zhàn)部隊和武器平臺鏈接在一起,構成陸??仗煲惑w化數字信息網絡,保證各系統(tǒng)之間的數據傳輸與資源共享。在該戰(zhàn)場環(huán)境下,為優(yōu)化資源配置,各種類無人機被統(tǒng)一管理,并可跨區(qū)域執(zhí)行任務,相比傳統(tǒng)多無人機任務分配,該類問題約束與規(guī)模更復雜,且要求一定時效性,傳統(tǒng)約束滿足問題(CSP)算法難以滿足要求。
對復雜約束的多無人機多目標任務分配問題,傳統(tǒng)的完全搜索方法難以有效或快速得到最優(yōu)解,多采用改進的禁忌搜索[1-2]、群體進化[3-4]、市場拍賣[5]求解,或結合多種算法優(yōu)勢得到更優(yōu)方案[2,6-7]。針對多區(qū)域和大規(guī)模無人機使用,為提高任務分配有效性和時效性,文獻[8]建立多基地多UAV協同規(guī)劃模型,采用“自適應”進化多目標優(yōu)化算法對不同位置、不同性能的無人機進行規(guī)劃;文獻[9]對目標進行模糊C聚類,從局部出發(fā)優(yōu)化,得到快速分配方案。文獻[10]基于任務依賴關系結合迭代自組織數據分析算法(ISODATA)對任務進行分組,使用粒子群優(yōu)化算法得到任務分配方案。
文獻[8]中UAV被限制在所屬基地控制下,UAV的使用被限制;文獻[3-4,10]將任務執(zhí)行時間作為代價考慮,而未考慮時間窗約束;文獻[2,7,9]中對目標自身特性如其優(yōu)先級等的不同未加考慮。且除文獻[5,8]外,其他文獻實驗中目標可全部被UAV分配,對UAV不能全部完成任務時如何取舍考慮稍欠缺。除文獻[8]外以上研究均在單基地下考慮。本文基于以上研究,結合問題特性,分析UAV平臺特性、任務約束、戰(zhàn)場初始布局等因素對多UAV任務分配的影響。針對問題規(guī)模較大的情況,對目標分組處理降維,得到局部初始解,隨后全局調整得到最優(yōu)解。
通用戰(zhàn)術網由通用數據鏈路和通用控制鏈路組成,使得戰(zhàn)場中的平臺、系統(tǒng)連接成有機整體。通用控制鏈路使得UAV活動擺脫了傳統(tǒng)視距鏈約束,可由分布于戰(zhàn)場的任一具有相應操控能力的地面站(GCS)控制飛行。通用數據鏈聯網使得分布于戰(zhàn)場任意位置的UAV可將得到的信息進行全局共享,使整個戰(zhàn)場的各級作戰(zhàn)單元共享高度的感知信息,實現作戰(zhàn)同步化。
在此背景下,UAV、地面站及通信鏈路等均被作為資源由指揮中心進行統(tǒng)一管理和調度,根據任務約束及要求,合理選派資源,由地面站控制UAV執(zhí)行任務。
1.1 問題描述
如圖1,假設通用戰(zhàn)術網絡已建立,在[0,S]*[0,S]戰(zhàn)場區(qū)域內分布有Ng個不同能力的地面控制站{GCS1,GCS2…GCSNg}和隨機分布的Nv個不同類型的UAV{V1,V2…VNv},及Nt個目標 {T1,T2…TNt}。UAV由任務管理中心進行統(tǒng)一管理。任務管理中心從戰(zhàn)場全局出發(fā),綜合考慮UAV平臺特性、目標特點和GCS等戰(zhàn)場環(huán)境進行多UAV對多目標進行偵察的任務規(guī)劃。
UAV平臺特性主要考慮其巡航速度、搭載傳感器不同等方面,目標考慮其優(yōu)先級和時間窗特性等,GCS能力的不同則體現在其可操控的UAV數量和通信覆蓋范圍等。表1用多元數組對各因素進行了形式化描述。
1.2 通用求解框架
針對網絡化戰(zhàn)場下大規(guī)模UAV任務分配難以快速找到最優(yōu)解,提出的解決方案是首先將任務目標按照一定原則分類,分為有一定共同特性的子集合。根據任務子集需要的UAV能力選取執(zhí)行任務的UAV集合,對目標子集合分別按時間窗、優(yōu)先級等排序后,依次采用優(yōu)化算法求得最優(yōu)初始解,最后進行全局調整,得到優(yōu)化分配方案。
1.2.1 算法設計及步驟
算法框架主要分為任務目標預處理、求解初始解和初始解改進3部分。下頁圖2給出了算法設計流程。
具體實施過程如下:
(1)目標預處理。主要進行目標分組,降低問題規(guī)模。目標分組目的是對一組目標點盡可能使用同樣的UAV資源執(zhí)行,通常的分類原則有:①目標偵察情報類型要求(圖像、視頻及其分辨率等)。②目標緊急程度。③目標位置(聚集在同一區(qū)域或在某無人機活動半徑內)。④對時間跨度較長的目標,將處在同一時間段內的目標分為一組。⑤同一通信覆蓋區(qū)域內的目標歸為一組等等。針對分組并排序后的目標集合,選取具有執(zhí)行該組目標能力的UAV集合進行調度。
(2)求解初始解。對得到的目標與無人機集合,依照其不同分組原則等,選取如遺傳算法、粒子群算法等合適的最優(yōu)化算法求取子問題初始解。
(3)初始解改進。按照步驟2得到的初始解,只是問題的局部較優(yōu)解,需要從全局進一步改進。對于不同的解序列,根據其時間窗的共同覆蓋程度,可以對解序列進行一系列插入、刪除、交換、重新排序等調整,從而獲得全局最優(yōu)或較優(yōu)解。
如圖3所示全局調整優(yōu)化方案實例,對UAV1、UAV2的任務序列,任務j在UAV1的空閑時間窗內,若j目標位置滿足UAV1從i目標飛行至i+1目標的時間段內執(zhí)行,則可將j目標插入UAV1的任務序列中。同樣,若i+2與j+2目標交換后使全局優(yōu)化值更高,則可以進行交換。
1.2.2 問題數學建模
對某含有N個目標的任務子集合T={1,2,3,…,i,j,…,N},其對應含M架無人機集合UAV= {1,2,3,…,k,…,M},決策變量xijk表示無人機k從執(zhí)行完任務i后繼續(xù)執(zhí)行任務j。UAV分配任務的3個優(yōu)化指標主要為任務完成的收益最大、代價最小和分配的目標盡量多。
任務收益優(yōu)化目標:
rijk表示從i出發(fā)去執(zhí)行j時獲得的收益,收益由目標的優(yōu)先級確定,rijk=xijk*L(j),保證盡量執(zhí)行優(yōu)先級高的目標。
任務代價優(yōu)化目標:
cijk表示從i出發(fā)去執(zhí)行j時的代價,包括路徑代價和通信代價。通信代價與目標位置距離GCS距離相關,dis為目標間距離。結合通信信號在自由空間衰減公式
可以將無人機從i目標出發(fā)執(zhí)行j目標的代價表示為式(4)。式(5)中Lbf:自由空間損耗,F:信號頻率,D:傳輸距離。路徑代價即各個目標點之間距離之和。
任務分配個數優(yōu)化指標,表示分配的目標個數盡可能多:
式(7)約束每個目標只被某一UAV單獨執(zhí)行。式(8)為航程約束,式(9)、式(10)為時間窗約束:
[ai,bi]代表任務i的任務時間窗,tstarti/tstartj:實際開始偵察目標i/j的時間,tleavei/tleavej:實際離開目標i/j的時間,twaitj:開始偵察目標j時的等待時間,tworkj:目標j的實際偵察持續(xù)時間。
為驗證算法框架合理性,根據分析的問題特點,對傳統(tǒng)遺傳算法進行改進并驗證。
2.1 編碼
本文將任務序列集合作為一條染色體,每個基因表示一個任務目標,基因取值為無人機的編號。圖4表示大小為n的目標集合編碼。編號為2的無人機執(zhí)行第1、3、7…等個目標,0為該目標未被任何UAV執(zhí)行。采用對基因位隨機賦值UAV編號的形式進行群體初始化,并用時間窗約束式(9)、式(10)判斷生成的群體是否可行。
2.2 適應度函數
該問題是復雜的多目標優(yōu)化問題,為便于求解,將多個目標函數設置不同權值融合在一個目標函數中。由此定義適應度函數:
其中Reward為染色體對應解得到的總收益,Cost為其總代價,Percent為目標完成度(完成目標數與總目標數的比值)。權值設定一般根據決策者的偏好或經驗確定。由于目標函數的量綱不同,為保證優(yōu)化結果的合理性,需將它們統(tǒng)一到同一數量級上。如本問題未調整時Reward的數量級在102而1/Cost數量級在10-1,則代價的變化對適應值的影響將被收益指標所“淹沒”,導致優(yōu)化結果不合理。
2.3 遺傳算子
根據本問題自身特殊性,遺傳算子中除選擇算子仍采用傳統(tǒng)輪盤賭法,對交叉算子和變異算子均做如下改進。
2.3.1 交叉算子
對隨機兩兩配對的每對父代個體,生成0-1內的隨機數與交叉概率Pc比較,小于Pc的配對按照設置的交叉點進行交叉。交叉算子如圖5,長度為n的染色體存在n-1個交叉點,設置交叉點時首先隨機生成n-1個[1,n-1]范圍內的不重復隨機數,依次按照生成的隨機數設置交叉點,直到交叉后個體仍為可行個體,將其遺傳到子代種群。若全部交叉點設置完仍無可行個體,則不進行交叉,直接遺傳到下一代。
2.3.2 變異算子
變異算子的處理是對每個長度為n的染色體生成[0,1]內的n個隨機數,與變異概率Pm比較,小于變異概率值的進行變異。在該問題中,如圖6,當個體需要變異時,優(yōu)先變異基因值為0的位置,置換為其他無人機編號,判斷變異后個體是否為可行解,若均不可行,則變異隨機數小于Pm的位置,置換為不同于該位置的無人機編號,判斷是否可行。若均不可行則不進行變異。規(guī)定同一染色體只有一處基因值發(fā)生變異。
3.1 結果分析
假設在800 km*800 km的戰(zhàn)區(qū)內存在3個地面控制站,8架偵察UAV對隨機分布在戰(zhàn)區(qū)不同位置的40個目標進行偵察。下頁表2、表3給出了UAV和目標的仿真數據。
對40個目標根據位置進行分類,按照時間窗和優(yōu)先級進行排序,并選取相應UAV集合,最終得到3組目標集合及對應UAV的編號集合,如下頁表4。
根據上述算法描述,優(yōu)先對T1、T3進行分配,對T1、T3中未進行分配的目標選取優(yōu)先級較高的加入T2,初始群體設置為100個,交叉概率Pc=0.75,變異概率Pm=0.01,遺傳1 000代,權重值w1=0.5,w2=0. 3,w3=0.2。每組目標序列執(zhí)行10次算法,由于遺傳算法的初始解是隨機生成的,且進化方向不定,因此會產生適應度收斂到一定值的幾個不同結果,挑選適應值最大的4組,得到圖7分配結果,T2序列中被標記出的為其他兩個序列未分配且優(yōu)先級較高而加入的目標。
程序平均規(guī)劃時間72 s,40個目標點中10個目標未分配,成功率為75%。仿真實驗中目標點與UAV位置及任務時間窗均是隨機得到的,目標特性與UAV能力導致目標并不一定被分配。圖8和圖9給出了仿真實驗結果中不同UAV執(zhí)行任務的順序和時間窗,綜合兩圖及目標參數可以看出:①未被分配的目標其優(yōu)先級一般較小。②未分配目標其位置和時間窗相互約束,即盡管其時間窗在其他UAV空閑時間范圍內,但地理位置相差較遠導致不可能完成該目標,同樣在UAV執(zhí)行路徑附近的其他目標因時間窗不符合同樣不能被分配。根據時間窗進行全局調整已經找不到更優(yōu)解,且規(guī)劃時間較短,可判定該方案是最優(yōu)的。
3.2 算法比較
為判斷算法的適應性,分別進行4架UAV對20個目標,8架UAV對40個目標,15架UAV對80個目標,用傳統(tǒng)遺傳算法和本文先分組求初始解并全局調整的改進算法進行分配,得到結果數據如下:
從實驗可以看出,在問題規(guī)模較小時,本文提出的分組遺傳算法由于需要進行多次求解并全局調整,傳統(tǒng)遺傳算法更具優(yōu)勢,但當問題規(guī)模擴大,需要搜索的解空間規(guī)模呈指數級增長,分組遺傳算法的規(guī)劃時間遠低于傳統(tǒng)遺傳算法,在15架UAV,80個目標時,傳統(tǒng)算法在執(zhí)行1 h后仍未找到可行解,分組遺傳算法則在較短時間內可以給出合理的分配方案。
本文研究了基于戰(zhàn)術通用數據鏈在戰(zhàn)場全局調度下無人機的多目標分配問題,對問題規(guī)模較大難以求解的難題,提出對目標分組降低問題緯度,求得一系列初始解并進一步進行全局調整,得到最終解決方案的思路方法。通過仿真實驗可以看出本文設計的目標分組求解并在全局調整尋找最優(yōu)解的算法,對較大規(guī)模的無人機目標分配問題具有較好的合理性、時效性和適應性。同時可以根據決策者的不同偏好設置適應度權重系數以滿足決策需要,具有較大的實際應用性。下一步工作將對約束因素更加實際化考慮,如將路徑代價替換為油耗模型,偵察得到的不同情報類型的回傳方式對分配的影響,調度過程中的安全問題及動態(tài)任務的調整,使算法更具實際性。
[1]陳英武,方炎申,李菊芳,等.衛(wèi)星任務調度問題的約束規(guī)劃模型[J].國防科技大學學報,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]施展,陳慶偉.基于改進的多目標量子行為粒子群優(yōu)化算法的多無人機協同任務分配[J].南京理工大學學報,2012,36(6):945-951.
[4]王婷,符小衛(wèi),高曉光.基于改進遺傳算法的異構多無人機任務分配[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]龍國慶,祝小平,周洲.多無人機系統(tǒng)協同多任務分配模型與仿真[J].飛行力學,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]田菁.多無人機協同偵察任務規(guī)劃問題建模與優(yōu)化技術研究[D].長沙:國防科學技術大學,2007.
[9]龍國慶,祝小平,董世友.基于聚類算法的多無人機系統(tǒng)任務分配[J].火力與指揮控制,2011,36(12):54-59.
[10]譚和順,曹雷,彭輝,等.一種多無人機層次化任務分配方法[J].解放軍理工大學學報(自然科學版),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
國家自然科學基金青年科學基金資助項目(71303252)
馬純超(1990- ),男,河北衡水人,碩士研究生。研究方向:無人機系統(tǒng)技術。