基于重疊聯(lián)盟博弈的無人機(jī)偵察時(shí)間資源分配優(yōu)化*

姚昌華,韓貴真,安 蕾

(南京信息工程大學(xué) 電子與信息工程學(xué)院,南京 210044)

0 引 言

隨著偵察任務(wù)的復(fù)雜化和多樣化,單架無人機(jī)執(zhí)行偵察任務(wù)時(shí)在目標(biāo)識別準(zhǔn)確率、計(jì)算能力、功耗、以及多任務(wù)點(diǎn)同時(shí)偵察等方面面臨著巨大的挑戰(zhàn)。在多無人機(jī)偵察系統(tǒng)中,其內(nèi)部的多個(gè)無人機(jī)通過協(xié)同控制高效地執(zhí)行偵察任務(wù)。多無人機(jī)偵察不僅具有較高的任務(wù)執(zhí)行效益,而且具有較強(qiáng)的緊急情況應(yīng)變能力,這些優(yōu)點(diǎn)使得多無人機(jī)更適合在復(fù)雜環(huán)境下執(zhí)行偵察任務(wù)[1-3]。

在多無人機(jī)執(zhí)行偵察任務(wù)時(shí),其中的關(guān)鍵就是對每個(gè)無人機(jī)進(jìn)行合理的任務(wù)分配。文獻(xiàn)[4]采用了一種特定的道路網(wǎng)偵察遺傳算法來解決多無人機(jī)的任務(wù)分配問題。文獻(xiàn)[5]提出了基于聚類算法的多無人機(jī)動(dòng)態(tài)任務(wù)分配方法來實(shí)現(xiàn)多無人機(jī)偵察任務(wù)的合理規(guī)劃。文獻(xiàn)[6]提出了一種余弦相似性聚類方法(模擬退火)對大型多無人機(jī)系統(tǒng)進(jìn)行任務(wù)分配。文獻(xiàn)[7]提出了一種基于廣域搜索場景的多無人機(jī)偵察任務(wù)分配模型,提高多無人機(jī)偵察任務(wù)分配效率。文獻(xiàn)[8]在任務(wù)分配過程中考慮了用戶對信息獲取的滿意度,提出了一種基于多群體合作的遺傳算法解決了多項(xiàng)式時(shí)間內(nèi)無人機(jī)的任務(wù)分配問題。文獻(xiàn)[9]針對無人機(jī)群協(xié)同實(shí)時(shí)任務(wù)分配問題提出了改進(jìn)合同網(wǎng)算法,在提高協(xié)商效率的同時(shí)也減少了通信量和通信頻率。文獻(xiàn)[10]提出一種基于改進(jìn)共識的分組算法的任務(wù)分配算法,解決了協(xié)同異構(gòu)無人機(jī)的任務(wù)分配問題。類似地,文獻(xiàn)[11-15]分別采用了不同的算法來研究多無人機(jī)協(xié)同的任務(wù)分配問題。

在多無人機(jī)協(xié)同的任務(wù)分配問題中,時(shí)間資源優(yōu)化是其中的重要部分。文獻(xiàn)[16]提出了一種改進(jìn)遺傳算法,考慮不同任務(wù)的差異化時(shí)間約束,將多任務(wù)分配問題建模為帶有時(shí)間窗約束的組合優(yōu)化問題,有效地節(jié)省無人機(jī)使用的數(shù)量并降低總能耗。文獻(xiàn)[17]在原有時(shí)間約束下模型中加入了威脅值的問題,通過一系列的約束條件來使得任務(wù)時(shí)間達(dá)到最小,以求得到最優(yōu)的任務(wù)分配方案。文獻(xiàn)[18]考慮了任務(wù)的優(yōu)先級,將無人機(jī)執(zhí)行任務(wù)所消耗的時(shí)間分解為飛行持續(xù)時(shí)間和懸停持續(xù)時(shí)間。文獻(xiàn)[19]提出了基于時(shí)間窗的多無人機(jī)聯(lián)盟組任務(wù)分配方法,以空閑時(shí)間窗為調(diào)度依據(jù)進(jìn)行高效且實(shí)時(shí)的任務(wù)分配。

雖然上述文獻(xiàn)運(yùn)用不同的方法對任務(wù)分配的問題進(jìn)行了研究,并且有的文獻(xiàn)考慮了其中的時(shí)間資源優(yōu)化問題。但是大部分文獻(xiàn)未考慮無人機(jī)自身的時(shí)間資源,未考慮兩個(gè)以上無人機(jī)同時(shí)執(zhí)行同一任務(wù)時(shí)的時(shí)間分配問題。同時(shí),大部分研究缺乏對偵察任務(wù)價(jià)值異構(gòu)性的考慮。事實(shí)上,不同偵察任務(wù)重要程度往往不同,應(yīng)當(dāng)分配的偵察時(shí)間資源也需要優(yōu)化。只有給每個(gè)偵察任務(wù)分配合理的時(shí)間資源,多無人機(jī)才能更加高效地完成偵察任務(wù)。因此,在多無人機(jī)執(zhí)行偵察任務(wù)時(shí),偵察任務(wù)的異構(gòu)性和無人機(jī)的時(shí)間資源分配問題尚需進(jìn)一步深入研究。

當(dāng)前,無人機(jī)功能的異構(gòu)性越來越明顯,有的無人機(jī)可以同時(shí)執(zhí)行多項(xiàng)任務(wù)。另外,有些重要任務(wù)的價(jià)值高、需求大,也需要多個(gè)無人機(jī)協(xié)同來提升該重要任務(wù)的執(zhí)行效果。因此,無人機(jī)在任務(wù)分配過程中的交叉組合是實(shí)際需要的?；谝陨峡紤],為了更好地解決多無人機(jī)執(zhí)行偵察任務(wù)時(shí)的時(shí)間資源分配問題,本文采用聯(lián)盟博弈的方法[20],提出一種基于重疊聯(lián)盟博弈的無人機(jī)偵察時(shí)間資源分配優(yōu)化方案,將偵察任務(wù)的價(jià)值異構(gòu)性考慮在內(nèi),研究如何將多個(gè)無人機(jī)的時(shí)間資源合理地分配給不同偵察目標(biāo)的問題。

1 系統(tǒng)模型

系統(tǒng)模型如圖1所示,有N個(gè)重要程度不同的偵察目標(biāo)和M個(gè)無人機(jī),且M>N。以偵察目標(biāo)的數(shù)量來構(gòu)建聯(lián)盟,系統(tǒng)中有N個(gè)偵察任務(wù)則聯(lián)盟數(shù)量為N。一個(gè)黑色圓圈代表一個(gè)聯(lián)盟,聯(lián)盟內(nèi)的無人機(jī)命名為忙碌無人機(jī)。黑色圓圈外的無人機(jī)命名為空閑無人機(jī),其旁邊的矩形代表該無人機(jī)3個(gè)時(shí)間比例。

圖1 系統(tǒng)模型

無人機(jī)在執(zhí)行偵察任務(wù)時(shí),首先需要考慮距離因素。距離偵察目標(biāo)最近的無人機(jī)對該目標(biāo)進(jìn)行偵察,不僅滿足偵察任務(wù)的時(shí)效性,而且節(jié)省了無人機(jī)的飛行成本。忙碌無人機(jī)距離偵察任務(wù)最近,令其對偵察目標(biāo)進(jìn)行全時(shí)段偵察?？臻e無人機(jī)將自己的時(shí)間劃分成3份進(jìn)行輔助偵察。

2 重疊聯(lián)盟博弈模型

2.1 重疊聯(lián)盟博弈的基本概念

定義1[21]:設(shè)聯(lián)盟參與者的集合為N={1,2,3,…,n},對于任意的C?N,稱C為N的一個(gè)聯(lián)盟,稱Γ={C|C?N}為聯(lián)盟集合。聯(lián)盟集合Γ中共有2n個(gè)元素,C=?和C=N為兩種特殊情況,其中C=N稱為大聯(lián)盟。

2.2 重疊聯(lián)盟博弈的效用函數(shù)

無人機(jī)偵察的識別成功率由S型函數(shù)[25]來表示:

(1)

式中:r為無人機(jī)的分辨率;T為無人機(jī)的偵察時(shí)間;a和b為S型函數(shù)的參數(shù)。當(dāng)有兩架及以上的無人機(jī)偵察時(shí),識別成功率為1減去兩架及以上的無人機(jī)偵察失敗的概率。

對一個(gè)重疊聯(lián)盟Ci而言,識別收益等于識別成功率乘以價(jià)值函數(shù)。價(jià)值函數(shù)與偵察任務(wù)的重要程度成正比,偵察任務(wù)越重要價(jià)值函數(shù)越大。聯(lián)盟Ci的識別成功率為

(2)

一個(gè)重疊聯(lián)盟Ci的識別代價(jià)為聯(lián)盟內(nèi)所有無人機(jī)拍照偵察時(shí)的能量開銷,每架無人機(jī)能量開銷等于偵察時(shí)間乘以單位時(shí)間的能量開銷。聯(lián)盟Ci的能量消耗為

(3)

式中:Px,Py,Pk分別表示無人機(jī)x,y,k單位時(shí)間的能量消耗。

一個(gè)重疊聯(lián)盟Ci的效用等于該聯(lián)盟的收益減去該聯(lián)盟的代價(jià),效用函數(shù)為

(4)

式中:V(i)表示聯(lián)盟Ci價(jià)值函數(shù)。聯(lián)盟Ci內(nèi)的偵察任務(wù)越重要,價(jià)值函數(shù)就越大。

系統(tǒng)總的效用等于各個(gè)聯(lián)盟效用之和:

(5)

3 重疊聯(lián)盟形成算法

偵察系統(tǒng)中的無人機(jī)為博弈參與者,要求的解是使偵察系統(tǒng)收益增大的一個(gè)穩(wěn)定的聯(lián)盟結(jié)構(gòu)。首先,對所有的無人機(jī)根據(jù)距離進(jìn)行預(yù)分配,找出系統(tǒng)中的忙碌無人機(jī)和空閑無人機(jī)。然后找出空閑無人機(jī)的3個(gè)潛在輔助聯(lián)盟,得到所有可能的聯(lián)盟結(jié)構(gòu)。最后對空閑無人機(jī)的時(shí)間比例進(jìn)行優(yōu)化。

每個(gè)空閑無人機(jī)通過改變時(shí)間分配比例來提升整個(gè)系統(tǒng)效用。當(dāng)所有空閑無人機(jī)的時(shí)間分配比例都不再改變時(shí),此時(shí)便得到一個(gè)穩(wěn)定的重疊聯(lián)盟結(jié)構(gòu)。改變包括兩種情況:轉(zhuǎn)移聯(lián)盟和退出聯(lián)盟[26]。以無人機(jī)y為例來進(jìn)行轉(zhuǎn)移聯(lián)盟和退出聯(lián)盟的解釋說明。

假設(shè)無人機(jī)y的3個(gè)潛在輔助聯(lián)盟為Ci,Cj和Cm,偵察時(shí)間為Ty,時(shí)間分配比例為β=[β1,β2,β3],β1為無人機(jī)y輔助聯(lián)盟Ci的時(shí)間比例,β2為無人機(jī)y輔助聯(lián)盟Cj的時(shí)間比例,β3為無人機(jī)y輔助聯(lián)盟Cm的時(shí)間比例。無人機(jī)y為了能夠使其輔助的聯(lián)盟獲得更高的收益進(jìn)行一次時(shí)間分配比例的改變。

1)轉(zhuǎn)移聯(lián)盟:當(dāng)β=[0.2,0.35,0.45]改變?yōu)棣?[0.4,0.15,0.45]時(shí)表示無人機(jī)y將時(shí)間資源從聯(lián)盟Cj轉(zhuǎn)移到聯(lián)盟Ci,此時(shí)無人機(jī)y偵察聯(lián)盟Ci,Cj和Cm的時(shí)間分別為0.4Ty,0.15Ty和0.45Ty。轉(zhuǎn)移聯(lián)盟的條件為無人機(jī)y將時(shí)間資源從聯(lián)盟Cj轉(zhuǎn)移到聯(lián)盟Ci后,所輔助的聯(lián)盟效用之和提升,系統(tǒng)的總效用提升。

2)退出聯(lián)盟:當(dāng)β=[0.2,0.35,0.45]改變?yōu)棣?[0.2,0,0.45]時(shí)表示無人機(jī)y從聯(lián)盟Cj中退出,退出之后的時(shí)間資源用于輔助其他聯(lián)盟。退出聯(lián)盟的條件為無人機(jī)y退出聯(lián)盟Cj后,所輔助的聯(lián)盟效用之和不降低,系統(tǒng)的總效用提升。

系統(tǒng)中的其他空閑無人機(jī)同樣進(jìn)行轉(zhuǎn)移聯(lián)盟和退出聯(lián)盟來提升所輔助聯(lián)盟的收益,進(jìn)而提升偵察系統(tǒng)收益。每個(gè)空閑無人機(jī)尋找自己鄰近的聯(lián)盟作為潛在的輔助對象,然后判定是否需要進(jìn)行轉(zhuǎn)移聯(lián)盟和退出聯(lián)盟的操作。在一輪決策中,每個(gè)空閑無人機(jī)都優(yōu)化一次自身的時(shí)間比例。如果在一輪決策中沒有一個(gè)空閑無人機(jī)需要進(jìn)行轉(zhuǎn)移聯(lián)盟和退出聯(lián)盟的操作,此時(shí)收斂到穩(wěn)定解。重疊聯(lián)盟博弈均衡求解流程如圖2所示。

圖2 重疊聯(lián)盟博弈均衡求解流程

4 仿真分析

考慮N=6,M=10的偵察系統(tǒng),多無人機(jī)協(xié)同偵察多目標(biāo)場景如圖3所示,共有6個(gè)聯(lián)盟。uav1～uav6分別為距離6個(gè)偵察目標(biāo)最近的無人機(jī),為忙碌無人機(jī)(全時(shí)段偵察無人機(jī))。UAV7～UAV9為系統(tǒng)中的空閑無人機(jī),即分配時(shí)間比例進(jìn)行輔助偵察的無人機(jī)。

圖3 場景預(yù)覽

偵察目標(biāo)的參數(shù)如表1所示,無人機(jī)的基本參數(shù)如表2所示,其中偵察時(shí)間已進(jìn)行歸一化處理且每架無人機(jī)的偵察時(shí)間相同。對于空閑無人機(jī)來說,首先要找到距離最近的3個(gè)聯(lián)盟作為潛在的輔助對象,然后隨機(jī)給定一個(gè)初始時(shí)刻的分配比例,開始進(jìn)行第一輪決策,每個(gè)空閑無人機(jī)依次進(jìn)行決策,所有的空閑無人機(jī)全部決策完畢即進(jìn)入下一輪決策,直到偵察系統(tǒng)的收益不再提升得到穩(wěn)定的聯(lián)盟結(jié)構(gòu)為止。初始時(shí)刻空閑無人機(jī)的分配比例如表3所示。

表1 偵察目標(biāo)參數(shù)

表2 無人機(jī)的相關(guān)參數(shù)

表3 初始時(shí)刻空閑無人機(jī)的分配比例

根據(jù)距離找出距離偵察目標(biāo)最近的3個(gè)聯(lián)盟作為空閑無人機(jī)的潛在輔助聯(lián)盟,結(jié)果如圖4所示。由圖可知,UAV7能夠?qū)β?lián)盟1,2,3進(jìn)行輔助,UAV8能夠?qū)β?lián)盟1,2,3進(jìn)行輔助,UAV9能夠?qū)β?lián)盟4,5,6進(jìn)行輔助,UAV10能夠?qū)β?lián)盟4,5,6進(jìn)行輔助。

圖4 空閑無人機(jī)潛在輔助聯(lián)盟

4.1 聯(lián)盟優(yōu)化結(jié)果

聯(lián)盟結(jié)構(gòu)達(dá)到穩(wěn)定時(shí),空閑無人機(jī)的時(shí)間分配比例如圖5所示。UAV7～UAV10在聯(lián)盟結(jié)構(gòu)穩(wěn)定時(shí)的輔助比例均不為0,表示UAV7～UAV10的潛在輔助比例即為實(shí)際輔助比例。UAV7輔助聯(lián)盟1的時(shí)間比例為0.48,輔助聯(lián)盟2的時(shí)間比例為0.01,輔助聯(lián)盟3的時(shí)間比例為0.51;UAV8輔助聯(lián)盟1的時(shí)間比例為0.2,輔助聯(lián)盟2的時(shí)間比例為0.59,輔助聯(lián)盟3的時(shí)間比例為0.21;UAV9輔助聯(lián)盟3的時(shí)間比例為0.62,輔助聯(lián)盟4的時(shí)間比例為0.01,輔助聯(lián)盟5的時(shí)間比例為0.37;UAV10輔助聯(lián)盟3的時(shí)間比例為0.01,輔助聯(lián)盟4的時(shí)間比例為0.64,輔助聯(lián)盟5的時(shí)間比例為0.35。

圖5 聯(lián)盟穩(wěn)定解

穩(wěn)定時(shí)的聯(lián)盟結(jié)構(gòu)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}。

4.2 各聯(lián)盟識別成功率分析

圖6給出了各聯(lián)盟輔助前后識別成功率對比結(jié)果。在沒有空閑無人機(jī)輔助偵察時(shí),6個(gè)聯(lián)盟的識別成功率均小于0.85,偵察的準(zhǔn)確性難以得到有效保障。在空閑無人機(jī)加入聯(lián)盟進(jìn)行輔助偵察并且達(dá)到穩(wěn)定的聯(lián)盟結(jié)構(gòu)時(shí),6個(gè)聯(lián)盟的識別成功率均大于0.99,有效保證了無人機(jī)偵察的準(zhǔn)確性。

圖6 各聯(lián)盟輔助前后識別成功率對比

4.3 聯(lián)盟總效用分析

多無人機(jī)偵察系統(tǒng)總效用(聯(lián)盟總效用)與迭代次數(shù)的關(guān)系如圖7所示,可見隨著迭代次數(shù)的增加,聯(lián)盟的總收益在不斷提升。在迭代到第36次時(shí)聯(lián)盟總收益達(dá)到收斂狀態(tài),繼續(xù)迭代聯(lián)盟總收益將不會繼續(xù)增加。達(dá)到收斂狀態(tài)時(shí),聯(lián)盟總的效用得到了有效提升。

圖7 多無人機(jī)偵察系統(tǒng)總效用

優(yōu)化時(shí)間比例后的多無人機(jī)偵察系統(tǒng)的總效用與未優(yōu)化時(shí)間比例的多無人機(jī)偵察系統(tǒng)的總效用對比如圖8所示。

(a)優(yōu)化時(shí)間資源比例

在圖8(a)中,優(yōu)化時(shí)間資源比例方法為本文所提方法,隨機(jī)時(shí)間比例方法為每次迭代的時(shí)候都隨機(jī)給定時(shí)間資源分配比例。在圖8(b)中,固定時(shí)間資源比例0為初始時(shí)刻空閑無人機(jī)的分配比例,固定時(shí)間資源比例1,2,3為除初始比例外的3個(gè)時(shí)間分配比例。UAV7,UAV8,UAV9,UAV10的時(shí)間分配比例為β7,β8,β9,β10。固定時(shí)間資源比例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];固定時(shí)間資源比例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];固定時(shí)間資源比例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)化時(shí)間資源比例的方法要優(yōu)于隨機(jī)時(shí)間資源比例方法。由圖10可知,與固定時(shí)間資源比例相比,優(yōu)化時(shí)間資源比例更能夠提高聯(lián)盟的總效用。 綜上所述,基于重疊聯(lián)盟博弈的無人機(jī)偵察時(shí)間資源分配優(yōu)化方法不僅能夠提高偵察系統(tǒng)的總效用,而且無人機(jī)的時(shí)間資源得到了高效的利用。

5 結(jié) 論

本文考慮利用多無人機(jī)對價(jià)值異構(gòu)的多目標(biāo)進(jìn)行協(xié)同偵察時(shí)的時(shí)間資源分配問題。首先,根據(jù)距離找出偵察系統(tǒng)中的忙碌無人機(jī)和空閑無人機(jī)。然后通過構(gòu)建重疊聯(lián)盟博弈模型,優(yōu)化偵察系統(tǒng)中空閑無人機(jī)的時(shí)間資源分配比例。在重疊聯(lián)盟博弈模型達(dá)到穩(wěn)定狀態(tài)時(shí),得到了所有無人機(jī)的時(shí)間資源分配方案。最后,對整個(gè)偵察系統(tǒng)收益進(jìn)行了仿真驗(yàn)證。仿真結(jié)果表明,所提出的多無人機(jī)的時(shí)間資源分配方案使得整個(gè)系統(tǒng)的偵察收益得到了有效提升。