姚昌華,韓貴真,安 蕾
(南京信息工程大學 電子與信息工程學院,南京 210044)
隨著偵察任務的復雜化和多樣化,單架無人機執(zhí)行偵察任務時在目標識別準確率、計算能力、功耗、以及多任務點同時偵察等方面面臨著巨大的挑戰(zhàn)。在多無人機偵察系統(tǒng)中,其內部的多個無人機通過協(xié)同控制高效地執(zhí)行偵察任務。多無人機偵察不僅具有較高的任務執(zhí)行效益,而且具有較強的緊急情況應變能力,這些優(yōu)點使得多無人機更適合在復雜環(huán)境下執(zhí)行偵察任務[1-3]。
在多無人機執(zhí)行偵察任務時,其中的關鍵就是對每個無人機進行合理的任務分配。文獻[4]采用了一種特定的道路網(wǎng)偵察遺傳算法來解決多無人機的任務分配問題。文獻[5]提出了基于聚類算法的多無人機動態(tài)任務分配方法來實現(xiàn)多無人機偵察任務的合理規(guī)劃。文獻[6]提出了一種余弦相似性聚類方法(模擬退火)對大型多無人機系統(tǒng)進行任務分配。文獻[7]提出了一種基于廣域搜索場景的多無人機偵察任務分配模型,提高多無人機偵察任務分配效率。文獻[8]在任務分配過程中考慮了用戶對信息獲取的滿意度,提出了一種基于多群體合作的遺傳算法解決了多項式時間內無人機的任務分配問題。文獻[9]針對無人機群協(xié)同實時任務分配問題提出了改進合同網(wǎng)算法,在提高協(xié)商效率的同時也減少了通信量和通信頻率。文獻[10]提出一種基于改進共識的分組算法的任務分配算法,解決了協(xié)同異構無人機的任務分配問題。類似地,文獻[11-15]分別采用了不同的算法來研究多無人機協(xié)同的任務分配問題。
在多無人機協(xié)同的任務分配問題中,時間資源優(yōu)化是其中的重要部分。文獻[16]提出了一種改進遺傳算法,考慮不同任務的差異化時間約束,將多任務分配問題建模為帶有時間窗約束的組合優(yōu)化問題,有效地節(jié)省無人機使用的數(shù)量并降低總能耗。文獻[17]在原有時間約束下模型中加入了威脅值的問題,通過一系列的約束條件來使得任務時間達到最小,以求得到最優(yōu)的任務分配方案。文獻[18]考慮了任務的優(yōu)先級,將無人機執(zhí)行任務所消耗的時間分解為飛行持續(xù)時間和懸停持續(xù)時間。文獻[19]提出了基于時間窗的多無人機聯(lián)盟組任務分配方法,以空閑時間窗為調度依據(jù)進行高效且實時的任務分配。
雖然上述文獻運用不同的方法對任務分配的問題進行了研究,并且有的文獻考慮了其中的時間資源優(yōu)化問題。但是大部分文獻未考慮無人機自身的時間資源,未考慮兩個以上無人機同時執(zhí)行同一任務時的時間分配問題。同時,大部分研究缺乏對偵察任務價值異構性的考慮。事實上,不同偵察任務重要程度往往不同,應當分配的偵察時間資源也需要優(yōu)化。只有給每個偵察任務分配合理的時間資源,多無人機才能更加高效地完成偵察任務。因此,在多無人機執(zhí)行偵察任務時,偵察任務的異構性和無人機的時間資源分配問題尚需進一步深入研究。
當前,無人機功能的異構性越來越明顯,有的無人機可以同時執(zhí)行多項任務。另外,有些重要任務的價值高、需求大,也需要多個無人機協(xié)同來提升該重要任務的執(zhí)行效果。因此,無人機在任務分配過程中的交叉組合是實際需要的?;谝陨峡紤],為了更好地解決多無人機執(zhí)行偵察任務時的時間資源分配問題,本文采用聯(lián)盟博弈的方法[20],提出一種基于重疊聯(lián)盟博弈的無人機偵察時間資源分配優(yōu)化方案,將偵察任務的價值異構性考慮在內,研究如何將多個無人機的時間資源合理地分配給不同偵察目標的問題。
系統(tǒng)模型如圖1所示,有N個重要程度不同的偵察目標和M個無人機,且M>N。以偵察目標的數(shù)量來構建聯(lián)盟,系統(tǒng)中有N個偵察任務則聯(lián)盟數(shù)量為N。一個黑色圓圈代表一個聯(lián)盟,聯(lián)盟內的無人機命名為忙碌無人機。黑色圓圈外的無人機命名為空閑無人機,其旁邊的矩形代表該無人機3個時間比例。
圖1 系統(tǒng)模型
無人機在執(zhí)行偵察任務時,首先需要考慮距離因素。距離偵察目標最近的無人機對該目標進行偵察,不僅滿足偵察任務的時效性,而且節(jié)省了無人機的飛行成本。忙碌無人機距離偵察任務最近,令其對偵察目標進行全時段偵察??臻e無人機將自己的時間劃分成3份進行輔助偵察。
定義1[21]:設聯(lián)盟參與者的集合為N={1,2,3,…,n},對于任意的C?N,稱C為N的一個聯(lián)盟,稱Γ={C|C?N}為聯(lián)盟集合。聯(lián)盟集合Γ中共有2n個元素,C=?和C=N為兩種特殊情況,其中C=N稱為大聯(lián)盟。
無人機偵察的識別成功率由S型函數(shù)[25]來表示:
(1)
式中:r為無人機的分辨率;T為無人機的偵察時間;a和b為S型函數(shù)的參數(shù)。當有兩架及以上的無人機偵察時,識別成功率為1減去兩架及以上的無人機偵察失敗的概率。
對一個重疊聯(lián)盟Ci而言,識別收益等于識別成功率乘以價值函數(shù)。價值函數(shù)與偵察任務的重要程度成正比,偵察任務越重要價值函數(shù)越大。聯(lián)盟Ci的識別成功率為
(2)
一個重疊聯(lián)盟Ci的識別代價為聯(lián)盟內所有無人機拍照偵察時的能量開銷,每架無人機能量開銷等于偵察時間乘以單位時間的能量開銷。聯(lián)盟Ci的能量消耗為
(3)
式中:Px,Py,Pk分別表示無人機x,y,k單位時間的能量消耗。
一個重疊聯(lián)盟Ci的效用等于該聯(lián)盟的收益減去該聯(lián)盟的代價,效用函數(shù)為
(4)
式中:V(i)表示聯(lián)盟Ci價值函數(shù)。聯(lián)盟Ci內的偵察任務越重要,價值函數(shù)就越大。
系統(tǒng)總的效用等于各個聯(lián)盟效用之和:
(5)
偵察系統(tǒng)中的無人機為博弈參與者,要求的解是使偵察系統(tǒng)收益增大的一個穩(wěn)定的聯(lián)盟結構。首先,對所有的無人機根據(jù)距離進行預分配,找出系統(tǒng)中的忙碌無人機和空閑無人機。然后找出空閑無人機的3個潛在輔助聯(lián)盟,得到所有可能的聯(lián)盟結構。最后對空閑無人機的時間比例進行優(yōu)化。
每個空閑無人機通過改變時間分配比例來提升整個系統(tǒng)效用。當所有空閑無人機的時間分配比例都不再改變時,此時便得到一個穩(wěn)定的重疊聯(lián)盟結構。改變包括兩種情況:轉移聯(lián)盟和退出聯(lián)盟[26]。以無人機y為例來進行轉移聯(lián)盟和退出聯(lián)盟的解釋說明。
假設無人機y的3個潛在輔助聯(lián)盟為Ci,Cj和Cm,偵察時間為Ty,時間分配比例為β=[β1,β2,β3],β1為無人機y輔助聯(lián)盟Ci的時間比例,β2為無人機y輔助聯(lián)盟Cj的時間比例,β3為無人機y輔助聯(lián)盟Cm的時間比例。無人機y為了能夠使其輔助的聯(lián)盟獲得更高的收益進行一次時間分配比例的改變。
1)轉移聯(lián)盟:當β=[0.2,0.35,0.45]改變?yōu)棣?[0.4,0.15,0.45]時表示無人機y將時間資源從聯(lián)盟Cj轉移到聯(lián)盟Ci,此時無人機y偵察聯(lián)盟Ci,Cj和Cm的時間分別為0.4Ty,0.15Ty和0.45Ty。轉移聯(lián)盟的條件為無人機y將時間資源從聯(lián)盟Cj轉移到聯(lián)盟Ci后,所輔助的聯(lián)盟效用之和提升,系統(tǒng)的總效用提升。
2)退出聯(lián)盟:當β=[0.2,0.35,0.45]改變?yōu)棣?[0.2,0,0.45]時表示無人機y從聯(lián)盟Cj中退出,退出之后的時間資源用于輔助其他聯(lián)盟。退出聯(lián)盟的條件為無人機y退出聯(lián)盟Cj后,所輔助的聯(lián)盟效用之和不降低,系統(tǒng)的總效用提升。
系統(tǒng)中的其他空閑無人機同樣進行轉移聯(lián)盟和退出聯(lián)盟來提升所輔助聯(lián)盟的收益,進而提升偵察系統(tǒng)收益。每個空閑無人機尋找自己鄰近的聯(lián)盟作為潛在的輔助對象,然后判定是否需要進行轉移聯(lián)盟和退出聯(lián)盟的操作。在一輪決策中,每個空閑無人機都優(yōu)化一次自身的時間比例。如果在一輪決策中沒有一個空閑無人機需要進行轉移聯(lián)盟和退出聯(lián)盟的操作,此時收斂到穩(wěn)定解。重疊聯(lián)盟博弈均衡求解流程如圖2所示。
圖2 重疊聯(lián)盟博弈均衡求解流程
考慮N=6,M=10的偵察系統(tǒng),多無人機協(xié)同偵察多目標場景如圖3所示,共有6個聯(lián)盟。uav1~uav6分別為距離6個偵察目標最近的無人機,為忙碌無人機(全時段偵察無人機)。UAV7~UAV9為系統(tǒng)中的空閑無人機,即分配時間比例進行輔助偵察的無人機。
圖3 場景預覽
偵察目標的參數(shù)如表1所示,無人機的基本參數(shù)如表2所示,其中偵察時間已進行歸一化處理且每架無人機的偵察時間相同。對于空閑無人機來說,首先要找到距離最近的3個聯(lián)盟作為潛在的輔助對象,然后隨機給定一個初始時刻的分配比例,開始進行第一輪決策,每個空閑無人機依次進行決策,所有的空閑無人機全部決策完畢即進入下一輪決策,直到偵察系統(tǒng)的收益不再提升得到穩(wěn)定的聯(lián)盟結構為止。初始時刻空閑無人機的分配比例如表3所示。
表1 偵察目標參數(shù)
表2 無人機的相關參數(shù)
表3 初始時刻空閑無人機的分配比例
根據(jù)距離找出距離偵察目標最近的3個聯(lián)盟作為空閑無人機的潛在輔助聯(lián)盟,結果如圖4所示。由圖可知,UAV7能夠對聯(lián)盟1,2,3進行輔助,UAV8能夠對聯(lián)盟1,2,3進行輔助,UAV9能夠對聯(lián)盟4,5,6進行輔助,UAV10能夠對聯(lián)盟4,5,6進行輔助。
圖4 空閑無人機潛在輔助聯(lián)盟
聯(lián)盟結構達到穩(wěn)定時,空閑無人機的時間分配比例如圖5所示。UAV7~UAV10在聯(lián)盟結構穩(wěn)定時的輔助比例均不為0,表示UAV7~UAV10的潛在輔助比例即為實際輔助比例。UAV7輔助聯(lián)盟1的時間比例為0.48,輔助聯(lián)盟2的時間比例為0.01,輔助聯(lián)盟3的時間比例為0.51;UAV8輔助聯(lián)盟1的時間比例為0.2,輔助聯(lián)盟2的時間比例為0.59,輔助聯(lián)盟3的時間比例為0.21;UAV9輔助聯(lián)盟3的時間比例為0.62,輔助聯(lián)盟4的時間比例為0.01,輔助聯(lián)盟5的時間比例為0.37;UAV10輔助聯(lián)盟3的時間比例為0.01,輔助聯(lián)盟4的時間比例為0.64,輔助聯(lián)盟5的時間比例為0.35。
圖5 聯(lián)盟穩(wěn)定解
穩(wěn)定時的聯(lián)盟結構CS*為C1={uav1,UAV7,UAV8},C2={uav2,UAV7,UAV8},C3={uav3,UAV7,UAV8},C4={uav4,UAV9,UAV10},C5={uav5,UAV9,UAV10},C6={uav6,UAV9,UAV10}。
圖6給出了各聯(lián)盟輔助前后識別成功率對比結果。在沒有空閑無人機輔助偵察時,6個聯(lián)盟的識別成功率均小于0.85,偵察的準確性難以得到有效保障。在空閑無人機加入聯(lián)盟進行輔助偵察并且達到穩(wěn)定的聯(lián)盟結構時,6個聯(lián)盟的識別成功率均大于0.99,有效保證了無人機偵察的準確性。
圖6 各聯(lián)盟輔助前后識別成功率對比
多無人機偵察系統(tǒng)總效用(聯(lián)盟總效用)與迭代次數(shù)的關系如圖7所示,可見隨著迭代次數(shù)的增加,聯(lián)盟的總收益在不斷提升。在迭代到第36次時聯(lián)盟總收益達到收斂狀態(tài),繼續(xù)迭代聯(lián)盟總收益將不會繼續(xù)增加。達到收斂狀態(tài)時,聯(lián)盟總的效用得到了有效提升。
圖7 多無人機偵察系統(tǒng)總效用
優(yōu)化時間比例后的多無人機偵察系統(tǒng)的總效用與未優(yōu)化時間比例的多無人機偵察系統(tǒng)的總效用對比如圖8所示。
(a)優(yōu)化時間資源比例
在圖8(a)中,優(yōu)化時間資源比例方法為本文所提方法,隨機時間比例方法為每次迭代的時候都隨機給定時間資源分配比例。在圖8(b)中,固定時間資源比例0為初始時刻空閑無人機的分配比例,固定時間資源比例1,2,3為除初始比例外的3個時間分配比例。UAV7,UAV8,UAV9,UAV10的時間分配比例為β7,β8,β9,β10。固定時間資源比例1為β7=[0.6,0.2,0.2],β8=[0.2,0.5,0.3],β9=[0.3,0.3,0.4],β10=[0.7,0.15,0.15];固定時間資源比例2為β7=[0.4,0.3,0.3],β8=[0.3,0.2,0.5],β9=[0.33,0.33,0.34],β10=[0.25,0.35,0.4];固定時間資源比例3為β7=[0.3,0.4,0.3],β8=[0.33,0.33,0.34],β9=[0.4,0.3,0.3],β10=[0.33,0.34,0.33]。
由圖9可知,本文所采用的優(yōu)化時間資源比例的方法要優(yōu)于隨機時間資源比例方法。由圖10可知,與固定時間資源比例相比,優(yōu)化時間資源比例更能夠提高聯(lián)盟的總效用。 綜上所述,基于重疊聯(lián)盟博弈的無人機偵察時間資源分配優(yōu)化方法不僅能夠提高偵察系統(tǒng)的總效用,而且無人機的時間資源得到了高效的利用。
本文考慮利用多無人機對價值異構的多目標進行協(xié)同偵察時的時間資源分配問題。首先,根據(jù)距離找出偵察系統(tǒng)中的忙碌無人機和空閑無人機。然后通過構建重疊聯(lián)盟博弈模型,優(yōu)化偵察系統(tǒng)中空閑無人機的時間資源分配比例。在重疊聯(lián)盟博弈模型達到穩(wěn)定狀態(tài)時,得到了所有無人機的時間資源分配方案。最后,對整個偵察系統(tǒng)收益進行了仿真驗證。仿真結果表明,所提出的多無人機的時間資源分配方案使得整個系統(tǒng)的偵察收益得到了有效提升。