褚　政，郭分林,粘松雷

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

?

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

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

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

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

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

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

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

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

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

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

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

1)假定無人機不進行任務載荷更換;

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

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

4)忽略對目標偵察的持續(xù)時間;

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

6)假定基地可以同時起飛多架無人機。

2　模型建立與求解

2.1模型建立

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

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

a)對于所有的目標點必須至少偵察一次以上;

b)對于A類目標點要偵察3次,對于B類目標點至少要偵察2次;

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

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

1)建立目標函數(shù)

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

(1)

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

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

STPA01A02…A06B01…B13C01…C11

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

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

(2)

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

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

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

|M|=|V|

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

(3)

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

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

(4)

(5)

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

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

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

2.2模型求解

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

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

(6)

(7)

(8)

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

(9)

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

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

(10)

同理可以得出:

(11)

2)模型算法流程

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Step1:初始化變量:N;

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

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

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

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

2.3模型結果及分析

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

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

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

圖3　無人機偵察策略1路徑

圖4　無人機偵察策略2路徑

3　結束語

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

[1]陳濟舟.衛(wèi)星任務規(guī)劃算法綜合評價技術研究[D].長沙：國防科學技術大學,2008.

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

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

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

[5]謝濤,陳火旺,康立山.多目標優(yōu)化的演化算法[J].計算機學報,2003,26(8):997-1003.

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

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

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

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

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

[11]楊遵,雷虎民.一種多無人機協(xié)同偵察航路規(guī)劃算法仿真[J].系統(tǒng)仿真學報,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-),男,山東煙臺人,碩士,講師,研究方向為裝備管理工程。

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

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

E917;TP18

ADOI:10.3969/j.issn.1673-3819.2016.05.004