彭雅蘭 段海濱 張岱峰 魏 晨

(1.北京航空航天大學(xué)自動(dòng)化科學(xué)與電氣工程學(xué)院飛行器控制一體化技術(shù)國(guó)家級(jí)重點(diǎn)實(shí)驗(yàn)室仿生自主飛行系統(tǒng)研究組,北京 100083;2.鵬城實(shí)驗(yàn)室,深圳 518000)

1 引言

近幾年隨著人工智能技術(shù)飛速發(fā)展,無(wú)人機(jī)(unmanned aerial vehicle,UAV)在軍事與民用領(lǐng)域都經(jīng)歷了革命性的發(fā)展[1].為了彌補(bǔ)單機(jī)執(zhí)行任務(wù)能力的局限性,將無(wú)人機(jī)以大規(guī)模形式聚集、互聯(lián)互通形成無(wú)人機(jī)集群,在功能上承擔(dān)單機(jī)無(wú)法實(shí)現(xiàn)的復(fù)雜任務(wù).當(dāng)多架無(wú)人機(jī)協(xié)同執(zhí)行同一項(xiàng)任務(wù)時(shí),無(wú)可避免的需要進(jìn)行合理的任務(wù)分配,以減少資源的浪費(fèi),提高單次任務(wù)的成功率與執(zhí)行任務(wù)的魯棒性[2-3].無(wú)人機(jī)集群在進(jìn)行動(dòng)態(tài)任務(wù)分配時(shí)需要考慮不同的目標(biāo)類型,針對(duì)性地指派適合類型的無(wú)人機(jī)執(zhí)行任務(wù).不僅如此,隨著任務(wù)復(fù)雜度的不斷提升,無(wú)人機(jī)集群飛行不再是單一任務(wù)序列的簡(jiǎn)單時(shí)序執(zhí)行過(guò)程,任務(wù)環(huán)境的不確定性要求無(wú)人機(jī)集群可以及時(shí)對(duì)執(zhí)行范圍內(nèi)的突發(fā)情況做出響應(yīng)[4].目標(biāo)威脅與有限載荷資源是無(wú)人機(jī)集群任務(wù)分配需要著重考慮的兩種約束[5].目標(biāo)威脅主要影響無(wú)人機(jī)類型、編隊(duì)隊(duì)形與載荷類型等的實(shí)時(shí)選擇與調(diào)整,有限載荷資源約束了無(wú)人機(jī)集群的任務(wù)效能與執(zhí)行任務(wù)的可持續(xù)性[6].因此,無(wú)人機(jī)集群的動(dòng)態(tài)任務(wù)分配是集群智能決策與自主控制中的一項(xiàng)關(guān)鍵性技術(shù).

無(wú)人機(jī)集群執(zhí)行任務(wù)的過(guò)程是一個(gè)連續(xù)的動(dòng)態(tài)過(guò)程,前期的任務(wù)執(zhí)行結(jié)果會(huì)影響到后期任務(wù)的分配與執(zhí)行情況,以前期任務(wù)執(zhí)行后的狀態(tài)作為后期任務(wù)開(kāi)始的初始狀態(tài)更符合整體任務(wù)執(zhí)行過(guò)程中的實(shí)際需求.在無(wú)人機(jī)集群動(dòng)態(tài)任務(wù)規(guī)劃研究中,既要求計(jì)劃的最優(yōu)性,同時(shí)又要保障反映的快速性,二者相互制約[7].隨著無(wú)人機(jī)集群執(zhí)行任務(wù)的復(fù)雜度增高,單純依靠提高算法速度很難滿足需求,研究在線控制機(jī)制,優(yōu)化求解時(shí)間與計(jì)劃最優(yōu)性之間的關(guān)系十分重要.

在無(wú)人機(jī)集群任務(wù)規(guī)劃研究方面,佐治亞理工大學(xué)采用可擴(kuò)展的商業(yè)開(kāi)源平臺(tái)完成了實(shí)時(shí)路徑規(guī)劃與目標(biāo)分配,可通過(guò)地面站將指令發(fā)送到每架無(wú)人機(jī)[8].中國(guó)電子科技集團(tuán)電子科學(xué)研究院等單位也實(shí)現(xiàn)了119架無(wú)人機(jī)集群的多任務(wù)目標(biāo)分組、集群行動(dòng)等任務(wù)[9].沙特哈立德國(guó)王大學(xué)的Ghamry等人將20個(gè)智能體的目標(biāo)搜索規(guī)劃問(wèn)題建模為約束時(shí)間窗口下的多維度啟發(fā)式組合優(yōu)化問(wèn)題并采用離散空間粒子群算法(discrete particle swarm optimization,DPSO)對(duì)其進(jìn)行快速精確求解[10].

灰狼作為自然界中自組織行為顯著的生物集群,其社會(huì)組織結(jié)構(gòu)與層次十分明確,在捕食狩獵中采用機(jī)會(huì)主義策略,通過(guò)獵物選擇提高整體捕食成功率以維持整個(gè)灰狼的生存與繁衍.灰狼在復(fù)雜、嚴(yán)峻的野外環(huán)境中進(jìn)化出自發(fā)的集群捕食策略[11-12].

倫敦大學(xué)的Hubel將土狼、野狗等犬科動(dòng)物的捕食過(guò)程與獵豹進(jìn)行了1119次對(duì)比,雖然犬科動(dòng)物的運(yùn)動(dòng)能力較獵豹較弱,但善于通過(guò)集體狩獵和食物分享來(lái)維持群體中每個(gè)個(gè)體的能量收支平衡[13-14].灰狼通過(guò)采用這種多次追逐的機(jī)會(huì)主義捕食策略來(lái)彌補(bǔ)個(gè)體捕食效率不足,平衡灰狼中的個(gè)體差異、獵物類型、環(huán)境等影響因素.灰狼捕食過(guò)程這一多因素交互迭代過(guò)程中演化出的行為機(jī)制符合無(wú)人機(jī)集群在執(zhí)行任務(wù)過(guò)程中的動(dòng)態(tài)任務(wù)規(guī)劃所需的性質(zhì).佐治亞理工學(xué)院的Madden將灰狼捕食麋鹿的過(guò)程分解為搜索、逼近、群組攻擊、個(gè)體攻擊和捕食5個(gè)階段,通過(guò)對(duì)場(chǎng)景與對(duì)象的模擬,較好的還原了真實(shí)的交互過(guò)程[15].

本文借鑒灰狼合作捕食行為,根據(jù)灰狼在捕食過(guò)程中表現(xiàn)的合作狩獵行為,建立交互行為動(dòng)力學(xué)模型與合作捕食行為模型,設(shè)計(jì)無(wú)人機(jī)集群的動(dòng)態(tài)任務(wù)分配方法,具有一定的技術(shù)優(yōu)勢(shì).

2 灰狼合作捕食行為模型

2.1 灰狼交互行為動(dòng)力學(xué)模型

灰狼群體中的因個(gè)體間的性別、年齡、體型等差異,在種群競(jìng)爭(zhēng)關(guān)系中逐步形成社會(huì)地位差異,組成一定的社會(huì)層級(jí)結(jié)構(gòu).灰狼的社會(huì)層級(jí)結(jié)構(gòu)是一種類似分叉屬性的領(lǐng)導(dǎo)層級(jí)結(jié)構(gòu),頭狼作為頂層節(jié)點(diǎn),后代形成子樹(shù),并按照性別分開(kāi),生存能力最弱的個(gè)體作為最底層[16].

狼群中一般由年齡最長(zhǎng)的個(gè)體作為頭狼,從頭狼到幼崽,按照指揮關(guān)系,存在一條信息流,為整個(gè)狼群提供交互行為的信息交流途徑.為了方便通過(guò)數(shù)學(xué)表達(dá)式表征灰狼內(nèi)部的交互關(guān)系,將每只灰狼當(dāng)做一個(gè)節(jié)點(diǎn),該節(jié)點(diǎn)具有的所有屬性由下列數(shù)據(jù)結(jié)構(gòu)體表示:

其中:R(i)表示當(dāng)前第i個(gè)個(gè)體的領(lǐng)導(dǎo)者個(gè)體;Z(i)表示當(dāng)前個(gè)體的性別屬性;C(i)與Q(i)分別為當(dāng)前個(gè)體支配的左子個(gè)體和右子個(gè)體;N(i)表示當(dāng)前個(gè)體是否為幼崽.由此數(shù)據(jù)結(jié)構(gòu)體表示形式可以得到第i只灰狼個(gè)體的鄰居集合,可由式(2)表示:

2.2 灰狼合作捕食行為模型

其中:COT為捕食階段個(gè)體在單位路徑上的能量損耗(cost of transportation),D為捕食階段個(gè)體的移動(dòng)路徑長(zhǎng)度,COTlow與Dlow對(duì)應(yīng)低速捕食階段,COThigh與Dhigh對(duì)應(yīng)高速捕食階段;ξthreaten為獵物的威脅度,其取值范圍為0～1;E為捕食成功后獵物提供的總能量;Cost為捕食獵物中灰狼的能量支出百分比;N為狼群中個(gè)體數(shù)量;Krate為灰狼個(gè)體殺傷率;Ecost為灰狼捕食過(guò)程中的能量支出.由上述灰狼合作捕食過(guò)程分析可知,灰狼個(gè)體殺傷率與獵物的威脅度負(fù)相關(guān),灰狼捕食過(guò)程中的能量支出與獵物的威脅度正相關(guān).設(shè)Krate,Ecost與ξthreaten的關(guān)系滿足式(4):

其中:α為相應(yīng)獵物威脅度下的個(gè)體最高殺傷率;β為獵物威脅度對(duì)個(gè)體殺傷率的影響系數(shù),β≤0;θ為相應(yīng)獵物威脅度下最低能量支出;γ為獵物威脅度對(duì)灰狼捕食能量支出的影響系數(shù),γ≤0.

3 無(wú)人機(jī)集群動(dòng)態(tài)任務(wù)分配

3.1 無(wú)人機(jī)模型

假定無(wú)人機(jī)配置有速度、航跡角與航向角3個(gè)回路的自駕儀,則無(wú)人機(jī)模型[17]可簡(jiǎn)化為

其中:Vc,γc與χc分別為速度、航跡角與航向角控制輸入量;(x,y,z,V,γ,χ)為無(wú)人機(jī)的6個(gè)狀態(tài)量,分別為無(wú)人機(jī)x,y與z軸坐標(biāo)、飛行速度、航跡角與航向角;τV,τγ與τχ分別為速度、航跡角與航向角自動(dòng)駕駛儀控制參數(shù).

考慮到無(wú)人機(jī)自身的飛行條件限制

其中:Vmin,Vmax,γmin與γmax為無(wú)人機(jī)航速與航跡角限制;ωmax為無(wú)人機(jī)最大航向角速度的絕對(duì)值.

3.2 基于灰狼合作捕食行為模型的無(wú)人機(jī)集群動(dòng)態(tài)任務(wù)分配

根據(jù)第2.1節(jié)中灰狼社會(huì)層級(jí)結(jié)構(gòu)與表示個(gè)體屬性的數(shù)據(jù)結(jié)構(gòu)體構(gòu)建無(wú)人機(jī)集群交互通訊結(jié)構(gòu),類似于狼群個(gè)體屬性數(shù)據(jù)結(jié)構(gòu)體,定義無(wú)人機(jī)屬性結(jié)構(gòu)體:

其中:R(i)表示當(dāng)前第i架無(wú)人機(jī)的領(lǐng)導(dǎo)者編號(hào);Z(i)表示當(dāng)前無(wú)人機(jī)的狀態(tài),可參與任務(wù)為1,無(wú)法參與任務(wù)為?1;C(i)與Q(i)分別為當(dāng)前無(wú)人機(jī)支配的左子個(gè)體與右子個(gè)體;N(i)表示當(dāng)前無(wú)人機(jī)是否為信息傳遞路徑的末端個(gè)體.

灰狼捕食過(guò)程中,發(fā)現(xiàn)獵物的個(gè)體會(huì)通過(guò)嚎叫的方式召喚周圍愿意參與捕獵的同伴共同展開(kāi)獵殺,參與捕食的個(gè)體合作攻擊并在成功抓住獵物后平均分配.借鑒灰狼的群體合作捕食行為策略,設(shè)計(jì)了無(wú)人機(jī)集群動(dòng)態(tài)任務(wù)分配策略,算法流程圖如圖1所示.

圖1 基于灰狼捕食行為機(jī)制的無(wú)人機(jī)集群任務(wù)分配算法流程圖Fig.1 Algorithm flowchart of UAV swarm dynamic mission planning inspired by cooperative predation of wolf-pack

借鑒灰狼捕食過(guò)程召喚周圍同伴共同行動(dòng)的行為,當(dāng)指揮權(quán)限高的無(wú)人機(jī)接收到任務(wù)指令后,將任務(wù)信息發(fā)送給周圍存在交互關(guān)系的無(wú)人機(jī).當(dāng)?shù)趇架無(wú)人機(jī)接受到指揮者傳遞的任務(wù)指令后,判斷其資源量是否足夠完成該任務(wù),即Ri≥Rmin.若第i架無(wú)人機(jī)資源量足夠完成該任務(wù),則按照一定的激勵(lì)概率選擇是否參與執(zhí)行任務(wù),其激勵(lì)概率函數(shù)為

若第i架無(wú)人機(jī)依據(jù)激勵(lì)概率函數(shù)Pik(t)判斷為執(zhí)行任務(wù),則向其指揮者無(wú)人機(jī)反饋當(dāng)前資源量Qi.由上式可知,合作機(jī)制可以提高集群的任務(wù)完成率.

對(duì)于?k中的第n個(gè)子集??nk按式(17)計(jì)算其完成目標(biāo)任務(wù)k的總體能量收益.

4 仿真結(jié)果

為驗(yàn)證該仿灰狼合作捕食行為的無(wú)人機(jī)集群動(dòng)態(tài)任務(wù)規(guī)劃方法的可行性和有效性,設(shè)計(jì)仿真實(shí)驗(yàn)為無(wú)人機(jī)集群在規(guī)定的任務(wù)區(qū)域內(nèi),對(duì)若干個(gè)運(yùn)動(dòng)的任務(wù)目標(biāo)點(diǎn)進(jìn)行追擊.選取任務(wù)區(qū)域?yàn)?0 km×20 km×20 km的矩形空間,無(wú)人機(jī)性能配置參數(shù)如下:

無(wú)人機(jī)和任務(wù)目標(biāo)的初始位置均隨機(jī)分布于任務(wù)區(qū)域內(nèi),且均滿足式(5)的運(yùn)動(dòng)約束條件.無(wú)人機(jī)的初始空速為80 km/h,初始航跡角為0,初始航向角在[0,2π]范圍內(nèi)隨機(jī)分布,任務(wù)目標(biāo)的速度、任務(wù)方向與俯仰角都是隨機(jī)調(diào)節(jié)的.每個(gè)任務(wù)目標(biāo)的初始收益均為100,衰減因子φ=0.01.仿灰狼合作捕食行為動(dòng)態(tài)任務(wù)分配方法的參數(shù)設(shè)置如下:a=0.01,b1=b2=333,Pmin=0.7.

文獻(xiàn)[18]介紹了一種基于拍賣(mài)機(jī)制的分布式任務(wù)分配方法,該方法以個(gè)體打擊概率、資源量、航程和目標(biāo)威脅度作為任務(wù)分配的指標(biāo),且邏輯結(jié)構(gòu)與本文所提仿灰狼算法類似.選取該拍賣(mài)算法作為本方法的對(duì)比算法.選取3個(gè)算例進(jìn)行對(duì)比驗(yàn)證,分別為10架、15架、20架無(wú)人機(jī)對(duì)15個(gè)任務(wù)目標(biāo)進(jìn)行合作打擊動(dòng)態(tài)任務(wù)分配.得到仿真結(jié)果如圖2-3所示.

圖2 仿灰狼合作捕食行為任務(wù)分配三維仿真結(jié)果Fig.2 Simulation result of UAV swarm dynamic mission planning inspired by cooperative predation of wolf-pack in three dimensions

圖2與圖3分別給出了仿灰狼合作捕食行為的無(wú)人機(jī)集群動(dòng)態(tài)任務(wù)分配算法與拍賣(mài)機(jī)制任務(wù)分配算法的三維仿真結(jié)果,圖中標(biāo)號(hào)代表無(wú)人機(jī)與目標(biāo)編號(hào).

圖3 拍賣(mài)機(jī)制任務(wù)分配三維仿真結(jié)果Fig.3 Simulation result of UAV swarm dynamic mission planning inspired by auction mechanism in three dimensions

圖4顯示的分別是仿灰狼機(jī)制與拍賣(mài)機(jī)制在任務(wù)收益與資源分配平衡度方面的對(duì)比曲線,資源分配平衡度指標(biāo)如式(22)所示:

圖4 仿灰狼機(jī)制與拍賣(mài)機(jī)制任務(wù)收益與資源均衡度Fig.4 Task income and resource equilibrium of the wolfpack mechanism and auction mechanism

其中:Ji(t)為t時(shí)刻無(wú)人機(jī)的剩余資源量,Tmax為最大仿真時(shí)間, ˉJi(t)為t時(shí)刻無(wú)人機(jī)集群的平均剩余資源量.

根據(jù)仿真結(jié)果可知,拍賣(mài)機(jī)制每次只分配一架打擊概率最高的無(wú)人機(jī)對(duì)相應(yīng)目標(biāo)執(zhí)行打擊任務(wù),不存在編隊(duì)協(xié)同打擊行為.這種機(jī)制的問(wèn)題在于沒(méi)有考慮打擊編隊(duì)與資源均衡兩個(gè)因素,致使打擊資源在任務(wù)執(zhí)行前期消耗極不均勻.有的無(wú)人機(jī)因頻繁遇到目標(biāo)而提前消耗完攜帶的資源,導(dǎo)致任務(wù)執(zhí)行后期會(huì)出現(xiàn)找不到合適打擊者的問(wèn)題.與之相反,仿灰狼合作捕食行為任務(wù)分配算法通過(guò)資源的均分機(jī)制,保留了大量持有有效打擊資源的無(wú)人機(jī)個(gè)體.通過(guò)編隊(duì)打擊,不僅均衡了整個(gè)集群的打擊資源,同時(shí)也為多機(jī)協(xié)同執(zhí)行打擊任務(wù)提供了更多的可選方案,提高了打擊成功概率,體現(xiàn)了仿灰狼合作捕食機(jī)制的時(shí)效性與持久性等特點(diǎn).

表1給出了兩種算法任務(wù)分配主要指標(biāo)的對(duì)比結(jié)果,表中數(shù)據(jù)為每種算例分別獨(dú)立運(yùn)行15次后取得的平均值.統(tǒng)計(jì)結(jié)果同樣反映了兩種任務(wù)分配算法的差異性,在擊毀目標(biāo)數(shù)量相近的情況下,仿灰狼合作捕食機(jī)制的累計(jì)收益明顯高于拍賣(mài)機(jī)制,且在資源均衡度方面明顯優(yōu)于拍賣(mài)機(jī)制.資源的均衡在任務(wù)執(zhí)行后期尤為重要,拍賣(mài)機(jī)制在后期出現(xiàn)了較為明顯的資源分化,個(gè)別無(wú)人機(jī)出現(xiàn)資源匱乏的情況,導(dǎo)致可用無(wú)人機(jī)數(shù)量減少.通過(guò)表1也可以看出,無(wú)人機(jī)集群規(guī)模的增加并不一定能夠提升拍賣(mài)算法的分配效果,而仿灰狼合作捕食機(jī)制的執(zhí)行效能則大致與無(wú)人機(jī)集群規(guī)模成正比.

表1 仿灰狼機(jī)制與拍賣(mài)機(jī)制的任務(wù)分配指標(biāo)統(tǒng)計(jì)結(jié)果Table 1 Task planning metric statistics of wolfpack mechanism and auction mechanism

5 結(jié)論

針對(duì)無(wú)人機(jī)集群任務(wù)分配問(wèn)題中,優(yōu)化計(jì)劃最優(yōu)性與響應(yīng)快速性二者之間的關(guān)系,借鑒灰狼合作捕食行為,提出了一種無(wú)人機(jī)集群動(dòng)態(tài)任務(wù)分配策略.首先,通過(guò)分析灰狼狩獵過(guò)程中表現(xiàn)出的社會(huì)層級(jí)結(jié)構(gòu)與合作捕食行為,建立了一種灰狼交互行為模型與合作捕食行為模型.其次,建立了仿灰狼合作捕食行為機(jī)制與無(wú)人機(jī)集群動(dòng)態(tài)任務(wù)分配之間的映射關(guān)系,建立了無(wú)人機(jī)集群動(dòng)態(tài)任務(wù)分配流程框架.仿真結(jié)果表明,在有限時(shí)間內(nèi),本文所提方法在資源分配平衡度與任務(wù)收益度方面有具有較好優(yōu)勢(shì),驗(yàn)證了該方法的有效性.