非精確情報信息環境下跨域無人集群動態目標分配算法研究

鄭傲宇,梁曉龍*,黃 驍,陶 浩

(1.空軍工程大學空管領航學院,西安,710051;2.中國艦船研究設計中心,武漢,430064)

跨域無人集群作戰是未來作戰的發展趨勢,需要通過集成多種類型無人系統在不同領域進行協同作戰,涉及多領域的協同與合作。在當前復雜多變的戰場環境中,跨域無人集群作戰具有重要的戰術和戰略意義,通過集成各類無人系統的能力,提高作戰效率和作戰能力,可以適應現代戰爭需求,提高戰場戰術水平,提升國家安全能力。目前,諸多學者對無人機群的編隊控制[1-3]、任務分配、路徑規劃等問題展開了研究,取得了一定的成果。

目標分配是跨域無人集群協同執行任務的關鍵環節。現有的任務規劃模型缺乏對戰場約束條件的考量,對動態情況響應不足。針對這一問題,部分專家學者對此展開研究。文獻[4]提出了基于自組織特征映射神經網絡的任務分配方法,能夠快速響應無人機機群執行任務中遇到的突發情況。文獻[5]通過擴展合同網協議,設計了一種能夠均衡任務負載、減少任務執行時間的有人機-無人機任務協同方法。文獻[6]提出了考慮目標收益和代價的任務分配算法,能夠獲得至少8%的效能提升。文獻[7]提出了基于實時戰場態勢的集中式分配方法,通過協調調度層進行任務分配決策,保持分配結果的優化和效率的平衡。文獻[8]將改進的兩階段狼群搜索算法用于求解多無人機任務分配問題。文獻[9]提出了一種基于遺傳算法的無人機協同任務分配與路徑優化的集成算法。文獻[10]將無人機協同任務分配問題描述為對決策樹的搜索,可通過樹搜索算法對模型進行求解。文獻[11]設計了一個可對實際三維地形和環境信息建模的多無人機任務規劃器,提出了基于粒子群和改進蟻群算法的任務分配算法。文獻[12]設計了飛航武器的動態任務規劃模型,并提出了基于進化論和模擬退火算法的改進策略。文獻[13]提出了一種有效的基于規則的啟發式方法來解決基于資產的動態火力分配問題。文獻[14]在交互式防御作戰場景下進行了仿真,比較了傳統 WTA 方法和多階段 WTA 方法,并用蒙特卡羅方法對目標函數模型進行了驗證。

與此同時,文獻[13]還指出,在實際跨域作戰任務分配中,會面臨信息獲取不完整的現象,這類不完整、不精確的情報可能會得到以下模糊信息：

1)具有不確定性的目標位置或運動信息;

2)缺乏完整的環境場景信息,而特殊的氣象條件對火力彈藥發射會產生一定的負面影響。如文獻[15]等人研究表明大氣風對導彈的作戰效能會產生影響;

3)無法準確判斷敵方的實力。

這些模糊信息可能會導致決策錯誤,任務失敗,資源浪費等問題,因此,如何處理好這類不精確情報信息帶來的不確定跨域無人集群目標分配問題,包括其理論、方法與求解,具有重要的研究價值。

本文在上述研究的基礎上,首先給出實際跨域無人機群作戰場景,分析由于探測信息的不精確性導致的無人機位置的不確定性、火力單元的不確定性等,在此基礎上建立目標預分配模型。而后設計基于市場機制的合同網任務重分配算法,根據執行任務過程中出現的作戰環境變化進行任務重分配。

1 場景描述

本文以跨域多無人系統聯合執行對敵方目標打擊為背景,無人系統基于作戰中心指令與目標信息對敵目標實施毀傷打擊。我方在該區域部署有岸端指揮控制中心、雷達探測系統、偵察系統以及若干架可執行任務的無人作戰單元,戰場初始態勢示意圖如圖1所示。

圖1 戰場初始態勢示意圖

雷達探測系統主要用于探測作戰區域內出現的目標位置信息,偵察系統用于監測目標被毀傷的狀態,所探測到的目標信息以及無人作戰單元的位置通過信息鏈傳輸至岸端指揮控制中心,岸端指揮控制中心根據信息進行目標分配,并將目標分配結果傳輸至無人作戰單元,無人作戰單元按照所接收到的目標分配信息對目標進行打擊。作戰過程中的目標流程如圖2所示。

圖2 目標分配流程

圖2包含了目標預分配和目標實時分配的流程,二者主要區別在于數學模型的建立和求解方法的選擇。目標預分配可建立一個優化模型,求解該模型獲得最優分配方案,但是計算時間長、計算量大;在目標實時分配階段,由于其對實時性要求較高,因此通過求解優化模型的方法不再適用,此時需要通過更高效的方法得到一個較優的可行分配方案。

在某次作戰任務中,我方可攻擊敵方目標的作戰力量包含兩類無人作戰單元有,分別為無人機和無人艇,其中無人機數量為MU,無人艇數量為MW;敵方待分配的目標有3類,分別為地面目標、水面目標以及水下目標,其中地面目標數量為NG,水面目標數量為NS,水下目標數量為ND,每個敵方目標可分配給我方多個無人作戰單元。無人機主要攻擊敵方的地面目標和水面目標,無人艇主要攻擊敵方的水面目標和水下目標。同時,無人艇可以為無人機攻擊地面目標提供補充,無人機亦可為無人艇攻擊水下目標提供協助。

無人集群目標分配的初始信息記為二元組{Weapon,Target},其中Weapon為無人集群集合：

Weapon={U1,U2,…,UNU,WNU+1,

WNU+2,…,WNU+NW}

(1)

二元組中的Target為目標集合：

(2)

設岸端指揮控制中心進行目標分配時無人機/無人艇i命中目標j為事件Λij,該事件發生概率為：

P{Λij}=pij

(3)

無人機/無人艇i命中目標j后對其毀傷效能為qij,則此次目標分配所獲得的總效益為P{Λij}qijφj。

然而,在實際跨域作戰任務分配中,會面臨信息獲取不完整的現象,這類不完整、不精確的情報可能會得到部分模糊信息,下面對戰場環境中可能出現的模糊信息進行分析。

1.1 目標位置的不確定性

設目標坐標位置服從三維正態分布,且各坐標軸之間相互獨立,即：

在本任務場景中,有μj,x=xj,μj,y=yj,μj,h=hj,在該概率密度函數下,可計算得到目標落在以點(x0,y0,h0)為中心,R0為半徑的圓內的概率,該積分式沒有解析解,因此需要使用數值積分方法進行計算。即：

(5)

1.2 火力資源落點的不確定性

在跨域作戰中,對于地面火力單元,風速過大會對導彈產生較大的側向力,影響其對地面和海面目標的命中精度;對于水下火力單元,海洋內部的洋流會影響火力彈藥對海下目標的命中精度。同時,地球擾動引力等因素亦會對落點位置產生影響。

通過文獻[16]等實驗研究,可認為火力單元落點的縱橫偏差服從正態分布,并且三者具有弱相關性。設火力單元落點坐標Qi=(Xi,Yi,Zi)的概率密度函數為gi(X,Y,H),則：

式中：x=(X,Y,H)和μ=(μX,μY,μH)分別為三維隨機變量及其均值向量,正協方差矩陣Σg表示為：

設火力單元的輻射范圍為r0,火力單元落點與目標位置間的距離為d,其概率密度函數為Ω(d),則有：

其中,

則我方火力單元i對敵方目標j的命中率為：

(9)

1.3 毀傷效能的不確定性

由于難以對敵方目標的規模和實力做出準確判斷,同時導彈爆炸時的破片數量難以預測,故我方發射的火力單元對敵的毀傷效能會與預判有差異。

設我方火力單元i對敵方目標j的毀傷效能為qij,同時,火力單元對目標的毀傷效能qi,j通常與火力單元和目標之間的距離di,j有關,距離越近,毀傷效能越大,設其滿足如下函數關系：

qi,j=e-?i,jdi,j

(10)

式中：?i,j為參數,與作戰單元類型和目標的屬性相關。

大量統計數據表明,導彈毀傷效能的分布通常是右偏的,在實際研究中,對數正態分布在描述導彈毀傷效能時較為常用,能夠反映出導彈毀傷效能的多樣性和不確定性,即：

在實際作戰中,由于毀傷效能qij∈[0,1],因此,通常對基本對數正態分布進行修正,得到截斷對數正態分布：

式中：μij是對數正態分布的均值;σij是標準差;Fij為分布函數。

(13)

獲得該毀傷效能的概率為：

通過遍歷每枚火力單元的劃分區間,可以得到目標最終毀傷效能所對應的概率密度函數,進而求得其概率分布。可知當λ越大,所得到的概率密度函數越精確,當λ→∞,即δ→0時,即可得到毀傷效能的真實概率密度。

2 目標預分配

在作戰初期,需要根據收集到的戰場任務數據規劃一個目標預分配方案,此時通常建立一個優化模型,通過求解該模型得到預分配方案。

2.1 目標函數

在目標分配中,通常需要考慮兩個目標函數,一是無人集群摧毀目標所獲得的收益,二是我方所消耗的火力資源成本。

首先,定義目標分配的決策變量：

對于第j個敵方目標,我方無人機/無人艇對其總毀傷效能為：

目標分配的首要目標是獲得最大化收益,即：

(14)

由于目標函數中含有隨機變量,不能直接求解,因此需對其進行轉化,為了在實際作戰過程中獲得更為精準的目標分配方案,通常預先給定一個目標收益的期望值,然后最大化真實收益大于該目標收益的概率,即得到如下的目標函數：

(15)

其次,在實際作戰中,需要盡可能保留我方作戰力量,即：

(16)

由此,得到目標預分配的兩個目標函數。下面分析目標預分配的約束條件。

2.2 約束條件

首先,由于我方無人機/無人艇攜帶的火力資源有限,因此需滿足：

(17)

其次,在作戰過程中,為保證作戰效能,需要保證每個目標的毀傷程度達到一個預期值。通常當目標的毀傷程度大于ε的概率大于ζ時,即認為該目標對我方已無威脅,由此可得約束條件：

j1,j2,…,jt

(18)

由此,可得到如下的規劃模型：

xi,j=0或1

(19)

2.3 求解算法

2.3.1 算法設計

為了求解問題,本文采用粒子群算法作為優化工具。其優點是可以處理多維、非線性和離散優化問題,并且具有全局搜索、并行處理和自適應性等特點,改進粒子群算法解決該問題的步驟如下：

1)編碼和種群初始化

在粒子群算法中,種群是由一組個體組成,每個個體代表了一種解決方案。在本問題中,一個個體就是一個大小為N×M的二進制矩陣,表示每個火力單元是否攻擊了給定目標。

初始化種群時,隨機生成若干個個體,即若干個N×M的二進制矩陣,作為初始種群。

2)約束支配

定義2.1給定目標分配方案x,其約束違背程度為：

(20)

定義2.2給定目標分配方案x1和x2,若滿足以下2個條件之一,則稱x1含約束支配x2：

①c(x1)

②c(x1)=c(x2),?i∈{1,2,…,M},fi(x1)≤fi(x2),且?ik∈{1,2,…,M} 滿足fik(x1)

3)更新可行儲備集和非可行儲備集

在帶約束的多目標優化過程中,設置兩個固定容量的外部儲備集,即不可行儲備集和可行儲備集,分別存儲搜索過程中得到的不可行解和非劣解,并從這兩個儲備集中選擇個體以構建下一代種群。

本算法采用帕累托支配關系更新可行儲備集。首先將可行儲備集和新可行解集組成一個新種群,而后在新種群中根據約束支配關系選擇互不支配的粒子,將其保存在可行儲備集中,如果可行儲備集的元素大于儲備集容量Na,則選取擁擠距離最大的Na個粒子存儲到可行儲備集中。

4)粒子全局引導者的選擇

粒子需要從非可行儲備集和可行儲備集中選擇全局引導者。在算法初期,粒子應以較大的概率從非可行儲備集中選擇全局引導者,這樣有利于算法的全局搜索;在迭代后期應盡可能從可行儲備集中選擇全局引導者,這樣有利于局部探索。因此,本文以概率psl從非可行儲備集中選擇全局引導者：

式中：Tmax表示最大迭代次數。

5)粒子位置更新

在目標分配問題中,由于自變量取值為0-1變量,因此傳統的粒子群算法不再適用于本模型。Kennedy等人于1997年率先提出一種針對0-1規劃問題的二進制PSO(binary PSO)算法。在 BPSO 算法中,一個二進制的空間就表示一個超立方體空間,每個粒子用一個二進制變量來表示,可以通過該二進制變量的某些位在{0,1}之間的翻轉來實現粒子在這個超立方體空間中的移動。

為了使每次迭代后xi,j的值只取0或1,離散粒子群算法將速度vi,j轉換為相應xi,j取0、1的概率。速度vi,j的計算繼續采用傳統粒子群算法的速度計算公式,即：

vi,j=ωvi,j+c1r1(pi,j-xi,j)+c2r2(gi,j-xi,j)

(22)

式中：c1、c2為學習因子;pi,j和gi,j分別表示個體最優方案和群體最優方案。

由于在離散粒子群算法中將速度vi,j轉化為xi,j的取值概率,因此需將其映射到{0,1}集合,本文采用sigmoid函數進行轉換,即：

由此,可定義粒子的更新公式如下：

式中：rand()是在區間[0,1]內產生的一個隨機數。

由此,可設計如下的含約束多目標粒子群算法：

Step1設置算法參數,包括粒子群數目,儲備集容量,算法迭代次數等;

Step2設置t=0,隨機初始化粒子位置,粒子的個體引導者為其自身;可行儲備集和非可行儲備集均設為空集;

Step3計算每個粒子的適應值,計算粒子約束違背程度;

Step4將粒子分為可行解和非可行解,并更新可行儲備集和非可行儲備集;

Step5判斷是否達到終止條件,若滿足,則算法終止;否則,進入下一步;

Step6對每個粒子執行以下操作：

1)以概率psl從非可行儲備集中選擇粒子的全局引導者;

2)更新粒子的個體引導者;

3) 更新粒子的位置;

Step7t←t+1,轉入Step3。

2.3.2 算法測試

本文所建立的目標預分配模型為離散多目標優化問題,通常的測試函數中針對理算多目標的優化函數較少,因此本文分別對算法處理離散問題以及多目標問題的有效性進行測試。

為分析算法處理多目標優化的性能,選取BNH和OSY[16]2個測試函數,2個測試函數的可行解占整個解空間的比為3.16%和3.25%,可行解空間較小,更能檢驗算法的可行性。

為定量分析算法處理多目標問題的性能,將其與兩種經典的多目標優化算法NSGA-II和HBGA進行對比,引入SP和GD兩個指標,分別用于評估解在空間中的分布情況以及與真實Pareto前沿之間的距離。每次測試均獨立運行20次并計算指標,結果如表1所示。

表1 算法處理多目標問題的指標對比

由表1可知,對于兩個測試函數,本節設計的BB-CMOPSO算法無論在GD指標上還是SP指標上均有較好的結果,這意味著其所獲得的有效解最接近真實的Pareto 前沿且具有較好的分布性。

為了驗證算法對于處理離散問題的適應性,本文采用一個規模為 50 的背包問題經典數據集對算法進行測試,該問題的最優解為1 063。獨立運行算法20次,得到的結果如表2所示。

表2 算法處理背包問題的結果

通過上述算法測試可知,本文所設計的引入變異算子的多目標離散粒子群優化算法能有效地處理多目標規劃和離散優化問題。

3 目標實時分配

在得到目標預分配方案后,根據預先設定的計劃執行任務。然而實際任務環境是不斷變化的,例如可能新任務出現,或者無人機執行任務時遇到緊急情況而無法按照計劃執行后續任務。這時需要進行任務分配的動態調整,修改無人機的任務序列。在實際問題中,需要進行重分配的觸發場景通常有一下3種：①出現新的任務目標;②無人機出現突發狀況無法完成任務;③目標位置等信息與預規劃時出現較大偏差。

采用合同網實現任務的重新分配,其中包括4個步驟：任務發布,競標投標,合同簽訂和任務執行。這種方法是一種分布式的自適應方法,合同簽訂過程中所有無人機的目標相同,且具有雙向選擇性。為加快對于新任務的重分配速度,本文運用一種基于市場機制的合同網算法,對多無人機在動態任務環境下執行任務過程中出現的突發狀況做出快速反應,在較短時間內完成任務的重分配,減少資源的浪費并提高任務完成的效率。

當環境出現變化,觸發重分配機制時,任務管理者向無人機發布任務信息,說明任務信息條件,無人機則根據自身能力進行投標,收到標書后任務管理者通過對比選擇最優無人機,并將此任務分配給該無人機,無人機收到合同確認信息后,根據新的任務序列開始執行任務。

針對無人機任務的重分配機制,會牽涉到合同網中競標和中標的過程。對于參與新任務競標的無人機,需要有一個可以評判標書優劣的標準。因此,必須設計一個能夠反映任務重分配收益的效能函數。而完成重分配后的方案,也需要對單個或多個無人機的任務序列進行修改。

設無人機i的目標集合Si={Tj1,Tj2,…,Tjκ},針對無人機i的任務執行過程,其效能函數為：

(25)

式中：α、β為權重系數,κ表示Si中的任務數量,Ci,jv為無人機i執行任務jv所需成本,即無人機/無人艇的彈藥消耗。無人機i執行任務序列Si不滿足約束條件(17)和(18),則定義效能函數

I(Si)=-∞

(26)

從上述建模過程可知,目標預分配和目標實施分配均需要計算任務分配方案所能獲得的價值,同時要滿足彈藥消耗、對目標的毀傷程度等約束條件。目標實時重分配模型本質上是從目標預分配模型轉化而來,綜合考慮目標預分配模型中的總收益及總彈藥消耗這2個目標函數以及式(17)～(18)中2個約束條件,將其轉化為各個無人機/無人艇的效能函數,體現了每個作戰單元被分配相應的目標集合中的目標后所能獲得的效益,效能函數越大,說明作戰單元執行該任務集合更有優勢,若效能函數較小,說明作戰單元不適宜執行該目標集合。

本文通過基于市場機制的合同網求解算法求解任務重分配問題。算法流程如圖3所示。

圖3 基于市場機制合同網的任務重分配示意圖

在指揮中心發布招標信息后,若無人機Ui滿足新任務的執行要求,則根據得到的任務信息制定標書ΔIi,其體現了增加新任務后Ui的效能函數值的變化,即

指揮中心在收到所有無人機發送的標書后,對標書值進行排序,達到最大標書ΔImax,而后將該任務分配給ΔImax所對應的無人機,收到任務執行計劃后無人機按照新的任務分配方案執行任務。

4 實驗仿真

4.1 實驗參數設置

本場景設置環境大小為100 km×100 km×8 km,我方共10個火力單元,其中無人機5架,無人艇5架。初始時刻探測到目標數量30個。

火力單元和初始時刻探測到的目標位置坐標相關參數分別如表3和表4所示。

表3 我方火力單元坐標

表4 敵方目標位置坐標

由于我方探測系統的不精確性,所獲取的目標位置具有不確定性,目標坐標位置服從三維正態分布,且各坐標軸之間相互獨立。設坐標軸三個維度上的方差

火力單元落點在三個維度上的方差及各維度之間的相關系數分別設置的如下：

ρXY=0.12,ρYZ=0.15,ρXZ=0.11

4.2 實驗仿真與結果分析

本文采用MATLAB進行仿真實驗,設置α=380,得到初始Pareto有效目標分配方案見表5。

表5 初始Pareto有效目標分配方案

從表中數據可知,如果采用有效目標分配方案1,所消耗的彈藥量為65枚,所獲得的總價值大于380的概率為96.81%;如果采用有效任務分配方案2,則所消耗的彈藥量為64枚,所獲得的總價值大于380的概率為95.19%。

表6 目標重分配方案

從表中數據可知,新探測的目標被分配給火力單元8執行。該方案所消耗的火力單元總數量為66,獲得的總價值大于380的概率為97.12%。與預分配方案相比,通過基于市場機制合同網的任務重分配方法得到的重分配方案提高了我方所能獲得的總效益,同時所消耗的火力單元數量僅增加1枚。

為驗證任務重分配算法的有效性,在實驗過程當出發重分配條件時,進一步采用預分配的優化模型進行求解,得到若干Pareto有效解,祈禱所對應的目標函數值見表7。

表7 優化模型求解重分配問題的Pareto有效解

通過表中數據可知,通過優化模型得到的有效解中,當彈藥消耗量為66時,所獲得的總價值大于380的概率為97.28%,雖然該結果相較基于市場機制的合同網算法所得方案更優,但是該算法耗時較長,復雜度大,而基于市場機制的合同網算法耗時短,且所得結果僅略次于最優解,能夠在取得較優解的同時滿足實時性要求。

5 結語

本研究旨在探討跨域無人集群在不精確情報信息環境下的動態目標分配問題,并提出相應的解決方案。首先,本文描述了一個具體的跨域無人機集群作戰場景,并分析了信息不確定性對無人機位置和火力單位的影響。基于此,構建了一個概率模型來進行目標預分配。其次,本文采用市場機制和合同網絡任務重新分配算法來應對作戰環境的動態變化。最后通過實驗模擬驗證了所提算法的有效性。實驗結果表明,本文給出的算法能夠在不精確情報信息的條件下實現動態目標分配,從而提高無人集群作戰的效果和效率。本研究為解決跨域無人集群動態目標分配問題提供了一種可行的解決方案,對于優化作戰任務分配和指導無人集群作戰具有重要意義。未來研究可以進一步探索該算法在實際作戰情境中的應用,并對算法進行進一步改進和優化。