基于多Agent無人機(jī)協(xié)同偵察任務(wù)規(guī)劃模型

褚　政，郭分林,粘松雷

(1.海軍航空工程學(xué)院,山東煙臺(tái)　264001;2.南昌陸軍學(xué)院,江西南昌　330103)

?

基于多Agent無人機(jī)協(xié)同偵察任務(wù)規(guī)劃模型

褚政1，郭分林2,粘松雷1

(1.海軍航空工程學(xué)院,山東煙臺(tái)264001;2.南昌陸軍學(xué)院,江西南昌330103)

建立了多無人機(jī)協(xié)同偵察任務(wù)規(guī)劃模型,在考慮偵察時(shí)間間隔約束和目標(biāo)載荷需求基礎(chǔ)上,給出了位于不同基地的無人機(jī)優(yōu)化部署和調(diào)度策略,并提出了基于多Agent的優(yōu)化搜索仿真算法,利用Matlab實(shí)現(xiàn)了無人機(jī)優(yōu)化配置和任務(wù)規(guī)劃模型,得出了無人機(jī)優(yōu)化配置和任務(wù)規(guī)劃方案,最后分析了模型算法存在的某些不足,提出了模型改進(jìn)的方向。

無人機(jī);多Agent;協(xié)同偵察;任務(wù)規(guī)劃;優(yōu)化搜索

無人機(jī)(Unmanned Aerial Vehicle,UAV)是一種具備自主飛行和獨(dú)立執(zhí)行任務(wù)能力的新型作戰(zhàn)平臺(tái)[1]。利用多無人機(jī)進(jìn)行協(xié)同偵察,實(shí)時(shí)獲取偵察目標(biāo)的動(dòng)態(tài)信息,通過信息融合處理技術(shù),能夠及時(shí)獲得準(zhǔn)確的戰(zhàn)場態(tài)勢,為部隊(duì)實(shí)施精確打擊和戰(zhàn)場評(píng)估等提供輔助決策支持。多無人機(jī)協(xié)同偵察可以分解為偵察目標(biāo)分配、偵察路徑規(guī)劃、漸近軌跡跟蹤等多個(gè)子問題[2]。

多無人機(jī)協(xié)同路徑規(guī)劃是指通過選擇無人機(jī)的數(shù)量、配置任務(wù)載荷、確定偵察目標(biāo)、規(guī)劃航跡,使得多無人機(jī)協(xié)同偵察的整體效能最大,且代價(jià)最小。多無人機(jī)協(xié)同偵察任務(wù)規(guī)劃屬于非確定性多項(xiàng)式(Nondeter Ministic Polynomial,NP)問題,若無人機(jī)數(shù)量較多時(shí),使用窮舉法或最優(yōu)控制法求解將耗費(fèi)大量的計(jì)算代價(jià),甚至難以實(shí)現(xiàn)[3]。從近幾年該領(lǐng)域的研究情況看,求解問題的方法主要以現(xiàn)代智能算法為主,如:神經(jīng)網(wǎng)絡(luò)、遺傳算法、模擬退火、進(jìn)化算法與粒子群優(yōu)化算法等[4]。這些算法有一定的優(yōu)勢,但是需進(jìn)行大量與實(shí)際不符的情況假設(shè),因此,本文提出使用“基于多Agent搜索優(yōu)化算法”,求取一個(gè)較優(yōu)解,然后不斷應(yīng)用階梯式逐步逼近最優(yōu)解。

1　協(xié)同偵察規(guī)劃問題案構(gòu)建

為了使得問題研究更具有針對(duì)性,本文首先以一個(gè)具體的實(shí)例為例,歸納總結(jié)成一個(gè)一般性問題?，F(xiàn)設(shè)定一個(gè)具體問題:某部隊(duì)現(xiàn)有3個(gè)可供無人機(jī)起降的停靠基地,分別為基地S、基地T、基地P,每個(gè)基地均配備有一定數(shù)量的無人機(jī),每架無人機(jī)可攜帶一種任務(wù)載荷去執(zhí)行偵察任務(wù)。已知基地S配有載荷Ⅰ和Ⅱ,基地T配有載荷Ⅲ和Ⅳ,基地P配有載荷Ⅰ、Ⅱ和Ⅲ。該部隊(duì)承擔(dān)著某區(qū)域內(nèi)30個(gè)點(diǎn)目標(biāo)的偵察任務(wù),其中包括6個(gè)A類目標(biāo)、13個(gè)B類目標(biāo)、11個(gè)C類目標(biāo)。根據(jù)偵察目標(biāo)的特點(diǎn)和實(shí)際需要,要求對(duì)A類目標(biāo)每天用不同的載荷偵察三次,并且間隔時(shí)間4至8小時(shí)。對(duì)B類目標(biāo)每天至少用不同的載荷偵察兩次,間隔時(shí)間至少6小時(shí)。對(duì)C類目標(biāo)每天至少用某種載荷偵察一次。該型無人機(jī)平均航速200km/h,最大續(xù)航時(shí)間為10小時(shí)。無人機(jī)根據(jù)續(xù)航能力可以選擇最近的基地降落進(jìn)行能量補(bǔ)充和必要的維護(hù)保養(yǎng)(每次需要時(shí)間5小時(shí)),之后可以連續(xù)執(zhí)行偵察任務(wù),但在24小時(shí)內(nèi)執(zhí)行完最后一次任務(wù)要返回原?？炕?。

通過分析,該問題是一個(gè)復(fù)雜的多目標(biāo)規(guī)劃,目標(biāo)函數(shù)的維度較高,未知變量較多,用一般的數(shù)學(xué)方法較難得到最優(yōu)解。如果加上對(duì)問題的約束條件以后,問題可轉(zhuǎn)化為多目標(biāo)優(yōu)化的決策問題。

此問題要解決的是,在24小時(shí)內(nèi)使用最少的無人機(jī)數(shù)量完成指定的偵察任務(wù),并給出無人機(jī)最優(yōu)調(diào)度策略。通過分析,應(yīng)該建立兩個(gè)目標(biāo)函數(shù):第一級(jí)目標(biāo)為無人機(jī)數(shù)量最少,第二級(jí)目標(biāo)為總路徑最短。另外,在本次模型當(dāng)中,可以不考慮敵情、天候、故障等影響因素。由于有多個(gè)因素影響目標(biāo)函數(shù)的最優(yōu),因此,在求解過程中,可以考慮首先搜索出一個(gè)可行解,然后對(duì)這個(gè)可行解進(jìn)行調(diào)整,使其逐步逼近最優(yōu)解。通過問題分析,現(xiàn)做以下假設(shè):

1)假定無人機(jī)不進(jìn)行任務(wù)載荷更換;

2)假定無人機(jī)從源基地出發(fā),經(jīng)過多個(gè)目標(biāo)點(diǎn)(包括到其他基地補(bǔ)給)為飛行一個(gè)架次;

3)假定無人機(jī)飛行過程中不考慮敵情、故障、天候、地形等影響因素;

4)忽略對(duì)目標(biāo)偵察的持續(xù)時(shí)間;

5)忽略無人機(jī)的轉(zhuǎn)角問題,無人機(jī)以平均速度飛行;

6)假定基地可以同時(shí)起飛多架無人機(jī)。

2　模型建立與求解

2.1模型建立

定義1:設(shè)Xτ,Yτ均為記錄元素出現(xiàn)的時(shí)間序列集合,則兩集合的“代數(shù)和”,記為Sτ=Xτ?Yτ,且|Sτ|=|Xτ|+|Yτ|。

從問題分析的情況看,所得到的模型解必須滿足以下幾個(gè)條件:

a)對(duì)于所有的目標(biāo)點(diǎn)必須至少偵察一次以上;

b)對(duì)于A類目標(biāo)點(diǎn)要偵察3次,對(duì)于B類目標(biāo)點(diǎn)至少要偵察2次;

c)對(duì)于A類目標(biāo)點(diǎn)連續(xù)偵察的間隔時(shí)間在4小時(shí)至8小時(shí)之內(nèi),對(duì)于B類目標(biāo)點(diǎn)連續(xù)偵察的間隔時(shí)間在6小時(shí)以上;

d)所有的偵察任務(wù)必須在24小時(shí)之內(nèi)完成。

1)建立目標(biāo)函數(shù)

根據(jù)問題分析來看,本問題是一個(gè)多目標(biāo)規(guī)劃問題,在保證任務(wù)完成的情況下,第一級(jí)目標(biāo)函數(shù)為使用的無人機(jī)數(shù)量最少[5],即要滿足條件a),則:

(1)

其中,Nij為第i類基地的第j種任務(wù)載荷的無人機(jī)序號(hào)集合,i∈J,J={1,2,3},j∈Pi,Pi?P,P={1,2,3,4};J中,1表示基地S,2為基地T,3為基地P;P中,1表示任務(wù)載荷為Ⅰ型,2為Ⅲ型,3為Ⅳ型,4為Ⅱ型[2]。

根據(jù)實(shí)際情況和給定條件分析,一架無人機(jī)從基地i1直接飛到基地i2(i1≠i2),此次任務(wù)為無效,即兩基地間的距離為∞,距離矩陣D具體值為[6]

STPA01A02…A06B01…B13C01…C11

其中,di,i=0,dij=dji。

從條件b),可知第二級(jí)目標(biāo)為一天內(nèi)所有無人機(jī)飛行的總路程最短,即

(2)

其中,i∈J,j∈Pi,l∈Nij。

2)目標(biāo)函數(shù)的約束條件

①對(duì)于條件a),可作如下約束:

|M|=|V|

②對(duì)于條件b),有以下約束:

(3)

通過問題分析,可知C類偵察目標(biāo)只須偵察一次即可,可以由式(3)滿足,可不用計(jì)算。

③根據(jù)條件c),有如下約束:

(4)

(5)

④根據(jù)條件d),如下約束:

問題當(dāng)中,有一個(gè)要滿足條件c),要求24小時(shí)之內(nèi)完成偵察任務(wù),則必須滿足下式條件,即

綜上可見,問題比較復(fù)雜,很難用一個(gè)具體的方法去求解,因此,必須使用降維的方式進(jìn)行簡化。

2.2模型求解

通過模型的建立和分析,可以看出這是一個(gè)復(fù)雜的多目標(biāo)規(guī)劃問題,為了對(duì)這類復(fù)雜問題的求解,主要利用于階梯式反推方式進(jìn)行求解[7],首先仿真求出一組無人機(jī)飛行策略,利用這個(gè)飛行策略(初始可行解)推理出目標(biāo)函數(shù)模型所需的計(jì)算支撐數(shù)據(jù)(如:時(shí)間間隔數(shù)據(jù)、經(jīng)過偵察目標(biāo)的不同任務(wù)載荷的種類數(shù)量等),再從模型目標(biāo)出發(fā),在不影響任務(wù)完成與滿足模型約束條件下,利用優(yōu)化搜索仿真算法不斷逼近最優(yōu)解[8]。

1)推算目標(biāo)函數(shù)模型所需的計(jì)算支撐數(shù)據(jù)

(6)

(7)

(8)

根據(jù)定義1可以得出[10]:

(9)

其中,?VτA為記錄時(shí)間t的所有無人機(jī)一天內(nèi)經(jīng)過A類偵察目標(biāo)點(diǎn)的集合;?VτB為記錄時(shí)間t的所有無人機(jī)一天內(nèi)經(jīng)過B類偵察目標(biāo)點(diǎn)的集合;?VτC為記錄時(shí)間t的所有無人機(jī)一天內(nèi)經(jīng)過C類偵察目標(biāo)點(diǎn)的集合。

有了以上的條件,可以通過下式來判斷第j種任務(wù)載荷是否有無人機(jī)經(jīng)過第i序號(hào)的A類偵察目標(biāo):

(10)

同理可以得出:

(11)

2)模型算法流程

針對(duì)這一問題,本文采用基于多Agent優(yōu)化算法[4,11]進(jìn)行仿真求解。首先構(gòu)造初始可行方案,通過逐步逼近最優(yōu)解的方式得出最終方案。

算法主要思路可以分為以下兩過程:

◆Process1:根據(jù)約束條件,利用無人機(jī)Agent遍歷目標(biāo)點(diǎn)的方法,通過逐步增加無人機(jī)Agent數(shù)量,判斷是否完成任務(wù),得出目標(biāo)函數(shù)的初始可行解,其中目標(biāo)點(diǎn)分為偵察目標(biāo)點(diǎn)和基地目標(biāo)點(diǎn)兩類,通過首先遍歷偵察目標(biāo)點(diǎn)、其次遍歷基地目標(biāo)點(diǎn)的方法,優(yōu)化搜索算法。具體流程(流程圖如圖1)如下:

Step3:選擇目標(biāo)點(diǎn),判斷本基地出發(fā)的無人機(jī)能否到達(dá)目標(biāo)Ti,若成立,轉(zhuǎn)入步驟Step4,否則不偵察此目標(biāo)點(diǎn),繼續(xù)執(zhí)行Step3;

Step4:判別目標(biāo)的類型,若屬于A類目標(biāo),轉(zhuǎn)入步驟Step5,否則轉(zhuǎn)入步驟Step8;

Step5:針對(duì)A類目標(biāo),判斷偵察目標(biāo)i的不同載荷無人機(jī)數(shù)量,若li<3,轉(zhuǎn)入Step6,否則轉(zhuǎn)入Step3;

Step6:判定是否有同種載荷的無人機(jī)偵察目標(biāo)點(diǎn),若是,轉(zhuǎn)入Step7,否則轉(zhuǎn)入Step2;

Step7:判定是否符合前后兩次不同載荷的無人機(jī)經(jīng)過目標(biāo)i的時(shí)間間隔,若4≤Vtj≤8,轉(zhuǎn)入Step11,否則轉(zhuǎn)入Step3;

Step8:判別是否屬于B類目標(biāo),如果是,轉(zhuǎn)入Step9,否則轉(zhuǎn)入Step11;

Step9:判定是否有相同類型載荷的無人機(jī)偵察目標(biāo)i,若是,轉(zhuǎn)入Step10,否則記錄無人機(jī)偵察目標(biāo)i的時(shí)刻;

Step10:判定前后不同載荷的無人機(jī)到達(dá)目標(biāo)i的時(shí)間間隔,若Vtj≤6時(shí),記錄無人機(jī)載荷種類數(shù)量,li=li+1,記錄到達(dá)目標(biāo)i的時(shí)刻,否則轉(zhuǎn)入Step3;

Step11:偵察目標(biāo)點(diǎn)Mi,記錄經(jīng)過目標(biāo)點(diǎn)i的無人機(jī)載荷種類數(shù)量li=li+1,記錄到達(dá)目標(biāo)i的時(shí)刻;

Step12:判定無人機(jī)能否繼續(xù)飛行,若能夠繼續(xù)飛行,轉(zhuǎn)入Step3,否則飛往基地目標(biāo)點(diǎn),記錄無人機(jī)降落的時(shí)刻和起飛的時(shí)刻tij=tij+5,hij=tij,同時(shí)記錄無人機(jī)維護(hù)的次數(shù)nj=nj+1;

Step13:判斷在基地的無人機(jī)是否繼續(xù)飛往目標(biāo)點(diǎn),若成立,轉(zhuǎn)入Step3,否則此架無人機(jī)不再飛行,同時(shí)判斷是否完成任務(wù),若成立,不再增加無人機(jī),得出模型一個(gè)初始可行解,否則,轉(zhuǎn)入Step2,繼續(xù)增加一架無人機(jī)。

◆Process2:在初始可行解的基礎(chǔ),通過逐步減少無人機(jī)數(shù)量,同樣利用無人機(jī)Agent遍歷目標(biāo)點(diǎn)方法得出目標(biāo)函數(shù)的一個(gè)較優(yōu)解。同時(shí)通過依次調(diào)整每架無人機(jī)的飛行路徑上的每個(gè)節(jié)點(diǎn),達(dá)到重新規(guī)劃所有無人機(jī)路徑的目的,從而在較優(yōu)解基礎(chǔ)上逐步逼近最優(yōu)解,得出的這個(gè)結(jié)果就可以認(rèn)為是較好的結(jié)果。算法流程(如流程圖2)具體如下:

圖1　多Agent優(yōu)化算法流程1

Step1:初始化變量:N;

Step2:從初始可行解中,返回基地時(shí)間最晚的第N架無人機(jī)開始,減去第N架無人機(jī),N=N-1,判斷N>0?如果是,轉(zhuǎn)入Step3,否則轉(zhuǎn)入Step4;

Step3:以最早執(zhí)行完任務(wù)返回基地時(shí)間最早的無人機(jī)為第一架無人機(jī),根據(jù)Process1流程,根據(jù)約束條件,遍歷搜索所有偵察目標(biāo)點(diǎn),判斷能否完成任務(wù),如若能,得出一個(gè)無人機(jī)數(shù)量N′和調(diào)度策略,同時(shí)將N′作為初始可行解,N=N′,繼續(xù)執(zhí)行Step2,否則,直接轉(zhuǎn)入Step4;

Step4:加入調(diào)整策略,本文的調(diào)整策略是依次限制每架無人機(jī)上一次飛行路徑上的點(diǎn)序列,根據(jù)Process1流程,重新遍歷搜索偵察目標(biāo)點(diǎn),判斷能否完成任務(wù),能完成,得出一個(gè)無人機(jī)數(shù)量N′調(diào)度策略,同時(shí)將N′作為初始可行解,N=N′,繼續(xù)執(zhí)行Step2,否則,跳出循環(huán),結(jié)束算法,此時(shí),最后一次完成任務(wù)得到的無人機(jī)數(shù)量N和調(diào)度策略,就是一個(gè)比較優(yōu)的解。

圖2　多Agent優(yōu)化算法流程2

2.3模型結(jié)果及分析

通過仿真計(jì)算,得出了多個(gè)方案,這里僅選取了其中兩個(gè)方案。方案表明最少需要6架無人機(jī)可以完成偵察任務(wù),具體結(jié)果如表1、表2所示,每架飛機(jī)的路徑如圖3、圖4所示。通過兩個(gè)方案的對(duì)比,最少無人機(jī)數(shù)量都是6架,但是方案一總飛行時(shí)間小于方案二,表明其飛行路徑最短,所以方案一的無人機(jī)調(diào)度策略優(yōu)于方案二。

表1　飛行調(diào)度策略1

表2　飛行調(diào)度策略2

圖3　無人機(jī)偵察策略1路徑

圖4　無人機(jī)偵察策略2路徑

3　結(jié)束語

通過對(duì)上述問題的分析、建模和求解,本文建立了多無人機(jī)協(xié)同偵察的優(yōu)化配置和任務(wù)規(guī)劃模型,通過對(duì)多Agent優(yōu)化搜索仿真算法得到的數(shù)據(jù)分析,可以看出建立的無人機(jī)優(yōu)化配置和任務(wù)規(guī)劃方案,能夠滿足問題研究的要求,并且具有一定的實(shí)用性和推廣性。該模型可擴(kuò)展性強(qiáng),可以滿足多基地多目標(biāo)多任務(wù)的復(fù)雜多目標(biāo)規(guī)劃問題的數(shù)學(xué)描述,基于啟發(fā)式搜索算法的模型求解與人的思維類似,便于理解實(shí)現(xiàn)。

[1]陳濟(jì)舟.衛(wèi)星任務(wù)規(guī)劃算法綜合評(píng)價(jià)技術(shù)研究[D].長沙：國防科學(xué)技術(shù)大學(xué),2008.

[2]袁利平,夏潔,陳宗基.多無人機(jī)協(xié)同路徑規(guī)劃研究綜述[J].飛行力學(xué),2009,27(5):1-5.

[3]孫小雷,齊乃明,董程,等.無人機(jī)任務(wù)分配與航跡規(guī)劃協(xié)同控制方法[J].系統(tǒng)工程與電子技術(shù),2015,27(12):2772-2776.

[4]田菁.多無人機(jī)協(xié)同偵察任務(wù)規(guī)劃問題建模與優(yōu)化技術(shù)研究[D].長沙:國防科學(xué)技術(shù)大學(xué),2007:163.

[5]謝濤,陳火旺,康立山.多目標(biāo)優(yōu)化的演化算法[J].計(jì)算機(jī)學(xué)報(bào),2003,26(8):997-1003.

[6]安偉剛.多目標(biāo)優(yōu)化方法研究及其工程應(yīng)用[D].西安:西北工業(yè)大學(xué),2005:52.

[7]周昊,覃征,邢劍寬.基于多Agent的多無人機(jī)協(xié)同決策算法仿真平臺(tái)設(shè)計(jì)[J].系統(tǒng)仿真學(xué)報(bào),2012,24(3):587-593.

[8]夏爽.C4ISR系統(tǒng)下的無人機(jī)情報(bào)分發(fā)策略研究[J].中國科學(xué)信息,2012(11):104-106.

[9]柳長安.無人機(jī)航路規(guī)劃方法研究[D].西安:西北工業(yè)大學(xué),2003:67.

[10]趙先章,常紅星,曾雋芳,等.一種基于粒子群算法的移動(dòng)機(jī)器人路徑規(guī)劃方法[J].計(jì)算機(jī)應(yīng)用研究,2007,24 (3):181-186.

[11]楊遵,雷虎民.一種多無人機(jī)協(xié)同偵察航路規(guī)劃算法仿真[J].系統(tǒng)仿真學(xué)報(bào),2007,19(2):433-436.

Programming Model of UAV Cooperative Reconnaissance Mission Based on Multi-Agent

CHU Zheng1， GUO Fen-lin2， NIAN Song-lei1

(1.Naval Aeronautical Engineering Institue,Yantai 264001；2.China Nanchang Military College,Nanchang 330103， China)

This paper views programming model of UAV cooperative reconnaissance mission.In the conside of reconnaissance time interval and target load requirement,the paper decipts optimization deployment and attemper tactic of the different base’s UAV,and decipts multi-agent based simulation arithmetic of optimization search.The paper realizes deployment and mission programming model of UAV,and figures out the model’s outcome.The paper analyses some shortages of the model and arithmetic,and puts forward the betterment’s directions of the model lastly.

UAV； Multi-Agent； cooperative reconnaissance； mission programming； optimization search

1673-3819(2016)05-0021-07

2016-06-21

2016-08-01

褚政(1978-),男,山東煙臺(tái)人,碩士,講師,研究方向?yàn)檠b備管理工程。

郭分林(1979-),男,碩士,副教授。

粘松雷(1982-),男,博士,講師。

E917;TP18

ADOI:10.3969/j.issn.1673-3819.2016.05.004