徐勝紅,曹文靜
(海軍航空工程學(xué)院 控制工程系,山東 煙臺(tái) 264001)
?
多無人機(jī)協(xié)同工作流建模與分析
徐勝紅,曹文靜
(海軍航空工程學(xué)院 控制工程系,山東 煙臺(tái)264001)
摘要:多無人機(jī)協(xié)同執(zhí)行任務(wù)能夠提升無人機(jī)的作戰(zhàn)效能和生存性,而協(xié)同方法是協(xié)同的基礎(chǔ);描述了基于工作流的多無人機(jī)協(xié)同方法;通過分析單個(gè)無人機(jī)工作流執(zhí)行過程,建立單個(gè)無人機(jī)工作流,研究了協(xié)同工作過程;引入Petri網(wǎng)理論,使用基本Petri網(wǎng)形式化描述協(xié)同工作流,構(gòu)建了多無人機(jī)協(xié)同工作流Petri網(wǎng)模型;針對(duì)所建立的協(xié)同工作流Petri網(wǎng)模型,通過構(gòu)建和分析相應(yīng)的可達(dá)圖,驗(yàn)證了多無人機(jī)協(xié)同工作流的有效性;結(jié)果表明:所建立的多無人機(jī)協(xié)同工作流是有效的,基于工作流的協(xié)同方法是可行的。
關(guān)鍵詞:協(xié)同;無人機(jī);工作流;Petri網(wǎng);可達(dá)圖
本文引用格式:徐勝紅,曹文靜.多無人機(jī)協(xié)同工作流建模與分析[J].兵器裝備工程學(xué)報(bào),2016(1):109-112.
Citation format:XU Sheng-hong,CAO Wen-jing.Modeling and Analysis for Multi-UAV Cooperation Workflow[J].Journal of Ordnance Equipment Engineering,2016(1):109-112.
在復(fù)雜多變的信息化戰(zhàn)場(chǎng)環(huán)境下,單個(gè)無人機(jī)執(zhí)行偵察或攻擊等任務(wù)時(shí)面臨偵察角度和范圍、殺傷半徑和摧毀能力等諸方面的限制,制約了作戰(zhàn)效能的發(fā)揮。多無人機(jī)協(xié)同作戰(zhàn)是根據(jù)作戰(zhàn)目的,組織多無人機(jī)協(xié)同實(shí)施作戰(zhàn)行動(dòng),對(duì)敵目標(biāo)進(jìn)行協(xié)同搜索、跟蹤、攻擊和防御。目前,多無人機(jī)協(xié)同執(zhí)行任務(wù)過程中所采用的協(xié)同方法主要有:基于地面控制站的協(xié)同方法[1-2]、基于中心節(jié)點(diǎn)的協(xié)同方法[3]、基于多無人機(jī)間協(xié)商的協(xié)同方法[4-8],以及我們提出的基于工作流的多無人機(jī)協(xié)同方法[9-10]。
1基于工作流的多無人機(jī)協(xié)同方法
在基于工作流的多無人機(jī)協(xié)同方法中,所有參與協(xié)同的無人機(jī)對(duì)任務(wù)的執(zhí)行都要遵循同樣的工作流進(jìn)行。
設(shè)所有參與協(xié)同的無人機(jī)集合記為U,協(xié)同執(zhí)行的任務(wù)集合記為T,對(duì)于?t∈T,都對(duì)應(yīng)一個(gè)工作流w,與T相應(yīng)的工作流集合記為W,w中的活動(dòng)包括兩類:協(xié)同決策活動(dòng):協(xié)同決策活動(dòng)包括戰(zhàn)場(chǎng)態(tài)勢(shì)同步和決策兩個(gè)步驟,整個(gè)過程中沒有新的戰(zhàn)場(chǎng)態(tài)勢(shì)產(chǎn)生;單機(jī)任務(wù)規(guī)劃和執(zhí)行活動(dòng):無人機(jī)根據(jù)決策的結(jié)果,規(guī)劃和控制本無人機(jī)的相關(guān)設(shè)備完成任務(wù),任務(wù)執(zhí)行完畢,修改在執(zhí)行任務(wù)中改變了的本無人機(jī)相關(guān)戰(zhàn)場(chǎng)態(tài)勢(shì)。
戰(zhàn)場(chǎng)態(tài)勢(shì)通常包括如下信息:所有參與協(xié)同的無人機(jī)的編號(hào)、飛行狀態(tài)、作戰(zhàn)能力狀態(tài)、當(dāng)前活動(dòng)狀態(tài)、以及相應(yīng)狀態(tài)產(chǎn)生的時(shí)刻;所有敵方目標(biāo)的狀態(tài)、以及檢測(cè)到該狀態(tài)的時(shí)刻和無人機(jī)編號(hào)。
設(shè)無人機(jī)集合U中的所有無人機(jī)要協(xié)同執(zhí)行一項(xiàng)任務(wù)tm∈T,tm對(duì)應(yīng)的工作流記作wn,wn中的所有決策集合記為D,?d∈D,d的決策方法記為f,決策方法集合記為F,初始戰(zhàn)場(chǎng)態(tài)勢(shì)為x0,則對(duì)于?u∈U,其協(xié)同執(zhí)行任務(wù)的方法如下:
開始協(xié)同后,u的工作流管理設(shè)備執(zhí)行wn活動(dòng)的遷移,并判斷當(dāng)前活動(dòng)的類型;
如果當(dāng)前活動(dòng)是協(xié)同決策類型,則與其它無人機(jī)進(jìn)行戰(zhàn)場(chǎng)態(tài)勢(shì)同步,直至u存儲(chǔ)的戰(zhàn)場(chǎng)態(tài)勢(shì)與其他無人機(jī)存儲(chǔ)的戰(zhàn)場(chǎng)態(tài)勢(shì)一致,然后依據(jù)u存儲(chǔ)的戰(zhàn)場(chǎng)態(tài)勢(shì)xj進(jìn)行決策,決策過程可以描述為
其中,fi∈F是與di∈D相對(duì)應(yīng)的決策方法,xj為戰(zhàn)場(chǎng)態(tài)勢(shì),yj為決策結(jié)果。由于對(duì)于?u∈U,此刻決策活動(dòng)di相同,對(duì)應(yīng)的決策方法fi相同,存儲(chǔ)的戰(zhàn)場(chǎng)態(tài)勢(shì)xj相同,因此,對(duì)于所有參與協(xié)同的無人機(jī)而言,決策產(chǎn)生的決策結(jié)果yj是相同的;決策完畢,繼續(xù)活動(dòng)遷移;如果當(dāng)前活動(dòng)是單機(jī)任務(wù)規(guī)劃和執(zhí)行活動(dòng),則依據(jù)決策結(jié)果和u存儲(chǔ)的戰(zhàn)場(chǎng)態(tài)勢(shì)對(duì)u的任務(wù)進(jìn)行規(guī)劃,并控制u相關(guān)設(shè)備執(zhí)行任務(wù),任務(wù)執(zhí)行完畢,修改和維護(hù)u存儲(chǔ)的戰(zhàn)場(chǎng)態(tài)勢(shì)中由于執(zhí)行任務(wù)而相應(yīng)變化的狀態(tài),繼續(xù)活動(dòng)遷移。
任意無人機(jī)u的工作流執(zhí)行過程如圖1所示。
圖1 單個(gè)無人機(jī)工作流執(zhí)行過程
在協(xié)同執(zhí)行任務(wù)的過程中,往往在執(zhí)行單機(jī)任務(wù)規(guī)劃和執(zhí)行活動(dòng)的過程中,需要根據(jù)當(dāng)前出現(xiàn)的新情況進(jìn)行重新協(xié)同決策,相應(yīng)的工作流設(shè)計(jì)如圖2(a)所示,圖2(b)是對(duì)圖2(a)活動(dòng)的進(jìn)一步分解。
圖2 考慮重新協(xié)同決策時(shí)單個(gè)無人機(jī)工作流
圖2(a)中,“協(xié)同決策”是協(xié)同決策活動(dòng),而“單機(jī)任務(wù)規(guī)劃和執(zhí)行”是單機(jī)任務(wù)規(guī)劃和執(zhí)行活動(dòng)。協(xié)同決策活動(dòng)的執(zhí)行內(nèi)容包括:無人機(jī)首先同步戰(zhàn)場(chǎng)態(tài)勢(shì),當(dāng)所有無人機(jī)所存儲(chǔ)的戰(zhàn)場(chǎng)態(tài)勢(shì)一致后,進(jìn)入決策,由于戰(zhàn)場(chǎng)態(tài)勢(shì)一致,決策方法一致,因此,決策結(jié)果也是一致的。各無人機(jī)根據(jù)決策結(jié)果執(zhí)行單機(jī)任務(wù)規(guī)劃和執(zhí)行活動(dòng)。單機(jī)任務(wù)規(guī)劃和執(zhí)行活動(dòng)包括:規(guī)劃和執(zhí)行任務(wù),當(dāng)在任務(wù)執(zhí)行過程中檢測(cè)到新態(tài)勢(shì)且需要重新協(xié)同決策,則發(fā)出重新協(xié)同決策請(qǐng)求,并修改自身戰(zhàn)場(chǎng)態(tài)勢(shì),重新進(jìn)入?yún)f(xié)同決策活動(dòng);當(dāng)在任務(wù)執(zhí)行過程中接收到其他無人機(jī)發(fā)送過來的重新協(xié)同決策請(qǐng)求,則重新進(jìn)入?yún)f(xié)同決策活動(dòng);當(dāng)在執(zhí)行過程中檢測(cè)到已完成任務(wù),則結(jié)束任務(wù)。
2基于Petri網(wǎng)的多無人機(jī)協(xié)同工作流建模
為了驗(yàn)證多無人機(jī)協(xié)同工作流的有效性和基于工作流的多無人機(jī)協(xié)同方法的可行性,應(yīng)用Petri網(wǎng)對(duì)多無人機(jī)協(xié)同工作流進(jìn)行形式化建模。
定義1Petri網(wǎng).五元式PN(P,T,F,W,M0)稱為一個(gè)Petri網(wǎng),其中:P={p1,p2,…,pm}是有限位置集,用圓圈來標(biāo)識(shí),用于描述可能的系統(tǒng)局部狀態(tài);T={t1,t2,…,tn}是有限變遷集,使用矩形標(biāo)識(shí),用于描述修改系統(tǒng)狀態(tài)的事件;F?(P×T)∪(T×P)是有向弧集,它代表節(jié)點(diǎn)流關(guān)系,表示使事件發(fā)生的局部狀態(tài)(因)或事件發(fā)生所引起的局部狀態(tài)的變化(果),并且:P∩T=Φ,P∪T≠Φ;W:F→{1,2,3,…}是弧的權(quán)函數(shù);M0:P→{0,1,2,…}是初始標(biāo)識(shí)。
在Petri網(wǎng)中,系統(tǒng)的動(dòng)態(tài)特性用令牌(token)標(biāo)識(shí),令牌表示為包含在位置節(jié)點(diǎn)中的圓點(diǎn),它反映了位置節(jié)點(diǎn)代表的狀態(tài)實(shí)現(xiàn)的動(dòng)態(tài)情況。若某位置節(jié)點(diǎn)中包含一個(gè)令牌,則表示位置節(jié)點(diǎn)代表的狀態(tài)的一次實(shí)現(xiàn)(條件或結(jié)果為真);若位置節(jié)點(diǎn)中無令牌,則表示位置節(jié)點(diǎn)代表的狀態(tài)尚未實(shí)現(xiàn)(條件或結(jié)果為假)。
定義2前置集.稱?x={y|y∈P∪T∧(y,x)∈F}為前置集。
定義3后置集.稱x?={y|y∈P∪T∧(x,y)∈F}為后置集。
定義4點(diǎn)火規(guī)則.對(duì)p∈P,若M(p)=k,表示位置p中有k個(gè)標(biāo)記(Token):
1)t∈T稱為在標(biāo)識(shí)M下是使能的(Enable),記為M[t>,當(dāng)且僅當(dāng)?p∈?t:M(p)≥w(p,t),其中w(p,t)是從p到t的有向弧上的權(quán);
2) 若t∈T在標(biāo)識(shí)M下是使能的,則t可以點(diǎn)火(fire),從M點(diǎn)火變遷后,演變到新的標(biāo)識(shí)M′,記為:M[t>M′:
定義5死標(biāo)識(shí).一個(gè)標(biāo)識(shí)M∈M0[>稱為死標(biāo)識(shí),當(dāng)?t∈T:M[t≯。即,在此標(biāo)識(shí)下任何一個(gè)變遷都不能點(diǎn)火。
若所有位置節(jié)點(diǎn)容量和弧的權(quán)都為1,這樣的Petri網(wǎng)就是基本Petri網(wǎng)?;诙酂o人機(jī)協(xié)同工作流,構(gòu)造了多無人機(jī)協(xié)同工作流的基本Petri網(wǎng)模型,如圖3所示。
圖3 多無人機(jī)協(xié)同工作流Petri網(wǎng)模型
在圖3中,phk(k∈N,0 3Petri網(wǎng)模型分析 下面基于多無人機(jī)協(xié)同工作流Petri網(wǎng)模型,構(gòu)建相應(yīng)的可達(dá)圖,研究多無人機(jī)協(xié)同工作流的有效性。對(duì)可達(dá)圖的分析主要包括:Petri網(wǎng)中所有的事件是否都能點(diǎn)火;可達(dá)圖中是否有死標(biāo)識(shí),即端點(diǎn),并判斷該死標(biāo)識(shí)是否是死鎖。 可達(dá)標(biāo)識(shí)是Petri網(wǎng)所能進(jìn)入的狀態(tài)。對(duì)于以上多無人機(jī)協(xié)同Petri網(wǎng)模型,狀態(tài)節(jié)點(diǎn)多,描述Petri網(wǎng)狀態(tài)的標(biāo)識(shí)太長(zhǎng),為了方便描述,我們使用如下形式來描述圖3的可達(dá)標(biāo)識(shí): 其中,〈P1x〉,〈P2y〉,…,〈Pnz〉分別描述了無人機(jī)1,2,…,n的令牌當(dāng)前所處的位置,則初始標(biāo)識(shí)M0=(〈p11〉,〈p21〉,…,〈pi1〉,…,〈pj1〉,…〈pn1〉)。 M0[>表示從初始標(biāo)識(shí)M0開始的所有可達(dá)標(biāo)識(shí)的集合。為了減少可達(dá)圖中的可達(dá)標(biāo)識(shí),同時(shí)還能檢測(cè)出事件發(fā)生和死鎖的情況,需要簡(jiǎn)化構(gòu)造的可達(dá)圖,不能對(duì)每一個(gè)事件所產(chǎn)生的標(biāo)識(shí)都描述出來。為此,引入下面的兩個(gè)定義。 定義6順序事件序列.設(shè)對(duì)于多無人機(jī)協(xié)同Petri網(wǎng)模型中的無人機(jī)i,其事件集合記為Ti,i的事件序列〈til1,til2,…,tilm〉稱為順序事件序列,當(dāng)且僅當(dāng)對(duì)于?tilx∈Ti,1≤x≤m-1,tilx + 1∈tilx??,且tilx??是唯一的。 定義7可并行執(zhí)行的順序事件序列.對(duì)于無人機(jī)i和j,設(shè)i的一個(gè)順序事件序列記為ti=〈til1,til2,…,tilm〉,j的一個(gè)順序事件序列記為tj=〈tjk1,tjk2,…,tjkn〉,如果?tilx∈ti,?tjky∈tj,和tjky不存在執(zhí)行順序關(guān)系,則ti和tj可以并行執(zhí)行,稱為可并行執(zhí)行的順序事件序列,記為〈til1,til2,…,tilm〉,〈tjk1,tjk2,…,tjkn〉。 以順序事件序列并行執(zhí)行的結(jié)果作為可達(dá)圖的一個(gè)標(biāo)識(shí),對(duì)圖3構(gòu)造出的可達(dá)圖如圖4所示。由圖4可見,該可達(dá)圖的狀態(tài)空間大大縮簡(jiǎn),且不影響對(duì)事件觸發(fā)情況和死鎖情況的分析。 圖4 多無人機(jī)協(xié)同Petri網(wǎng)模型可達(dá)圖 從圖4可知: (1)多無人機(jī)協(xié)同Petri網(wǎng)中,由于各無人機(jī)戰(zhàn)場(chǎng)態(tài)勢(shì)往往需要多次通信才能達(dá)到一致,因此,th3一般都會(huì)發(fā)生,在圖4中,只描述了th3的后繼必經(jīng)事件th4。 (2)圖4中有一個(gè)死標(biāo)識(shí),即(〈p17〉,〈p27〉,…,〈pi7〉,…,〈pj7〉,…,〈pn7〉),該標(biāo)識(shí)代表了所有參與協(xié)同的無人機(jī)都進(jìn)入結(jié)束任務(wù)狀態(tài)。由于1≤x≤n,px7都沒有遷出事件,因此,此標(biāo)識(shí)并不是真正的死鎖標(biāo)識(shí),而是工作流結(jié)束標(biāo)識(shí)。 以上可達(dá)圖表明,本文建立的多無人機(jī)協(xié)同工作流中,所有事件都能被觸發(fā),不存在死鎖情況,因此,所建立的多無人機(jī)協(xié)同工作流是有效的,基于工作流的多無人機(jī)協(xié)同方法是可行的。 4結(jié)束語(yǔ) 多無人機(jī)協(xié)同執(zhí)行作戰(zhàn)任務(wù)能夠提升無人機(jī)的作戰(zhàn)效能和生存能力。本文依據(jù)基于工作流的多無人機(jī)協(xié)同方法,研究了協(xié)同工作過程,建立了協(xié)同工作流Petri網(wǎng)模型,通過構(gòu)建和分析相應(yīng)可達(dá)圖,驗(yàn)證了多無人機(jī)協(xié)同工作流的有效性。然而,以上的可達(dá)圖是通過靜態(tài)遍歷Petri網(wǎng)得到的,因此,其判斷工作流有效性的能力有限。 在多無人機(jī)協(xié)同執(zhí)行一項(xiàng)具體任務(wù)時(shí),需要在多無人機(jī)協(xié)同工作流的基礎(chǔ)上,結(jié)合具體協(xié)同任務(wù)和所采取的決策方法,構(gòu)建具體的工作流,并采用動(dòng)態(tài)執(zhí)行的方式,準(zhǔn)確地構(gòu)造可達(dá)圖,以驗(yàn)證所建立的協(xié)同工作流的有效性,并指導(dǎo)建立有效的協(xié)同工作流。 參考文獻(xiàn): [1]曹菊紅,高曉光.多架無人機(jī)協(xié)同作戰(zhàn)智能指揮控制系統(tǒng)[J].火力與指揮控制,2003,28(5):22-24. [2]李建,符小衛(wèi),高曉光.通信約束下的多無人機(jī)協(xié)同航路規(guī)劃[J].電光與控制,2013,20(6):29-33. [3]郭銘,閻昊,韋有平.移動(dòng)自組網(wǎng)絡(luò)在無人機(jī)通信中的應(yīng)用研究[J].艦船電子工程,2008,28(6):59-62. [4]應(yīng)賁.分布式多Agent 系統(tǒng)的通信與協(xié)商策略研究[D].南京:南京郵電大學(xué),2010. [5]韓健.基于多Agent的無人機(jī)協(xié)作控制[D].哈爾濱:哈爾濱工業(yè)大學(xué),2012. [6]歐建軍,鐘麟.基于多智能體的編隊(duì)協(xié)同空戰(zhàn)戰(zhàn)術(shù)規(guī)劃[J].電光與控制,2010,17(2):35-38. [7]MERINO L,CABALLERO F,MARTíNEZ-DE DIOS J R,et al.A cooperative perception system for multiple UAVs:application to automatic detection for forest fires[J].Journal of Field Robotics,2006,23(3/4):165-184. [8]MAZS I,KONDAK K,BERNARD M,et al.Multi-UAV cooperation and control for load transportation and deployment[C].the 2nd International Symposium on UAVs,Reno,Nevada,U.S.A:2010:417-449. [9]曹文靜,徐勝紅,張毅,基于工作流的多無人飛行器協(xié)同方法及系統(tǒng)[P].中國(guó)專利:201410154104.8,2014. [10]徐勝紅,曹文靜,李文強(qiáng).一種多無人機(jī)協(xié)同方法及其性能分析[J].四川兵工學(xué)報(bào),2015,36(8):100-103. (責(zé)任編輯楊繼森) 【信息科學(xué)與控制工程】 Modeling and Analysis for Multi-UAV Cooperation Workflow XU Sheng-hong,CAO Wen-jing (Department of Control Engineering, Naval Aeronautical and Astronautical University, Yantai 264001, China) Abstract:Cooperation of multi-UAV could improve the combat effectiveness and survivability. Cooperation method is critical to cooperation. Workflow-based multi-UAV cooperation method was described. With the execution process of one UAV’s work flow, we established one UAV’s work flow, and the cooperation process was studied. With the introduce of Petri network, basic Petri net was used to formalize cooperation work flow, and the Petri net model of multi-UAV cooperation work flow was established. For the Petri net model of multi-UAV cooperation work flow, the corresponding reachability graph was established and analyzed to validate the cooperation workflow. Results show that the established cooperation work flow is effective and the workflow-based cooperation method is feasible. Key words:cooperation; unmanned aerial vehicle(UAV); work flow; Petri network; reachability graph 文章編號(hào):1006-0707(2016)01-0109-04 中圖分類號(hào):TP393.4 文獻(xiàn)標(biāo)識(shí)碼:A doi:10.11809/scbgxb2016.01.026 作者簡(jiǎn)介:徐勝紅(1974—),男,副教授,博士,主要從事無人飛行器組網(wǎng)技術(shù)研究。 基金項(xiàng)目:國(guó)家自然科學(xué)基金(61203168);中國(guó)博士后科學(xué)基金(2011M500156;2013T60922) 收稿日期:2015-06-21;修回日期:2015-07-10