仿灰狼合作捕食行為的無人機集群動態(tài)任務(wù)分配

彭雅蘭 段海濱 張岱峰 魏 晨

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

1 引言

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

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

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

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

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

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

2 灰狼合作捕食行為模型

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

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

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

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

2.2 灰狼合作捕食行為模型

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

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

3 無人機集群動態(tài)任務(wù)分配

3.1 無人機模型

假定無人機配置有速度、航跡角與航向角3個回路的自駕儀,則無人機模型[17]可簡化為

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

考慮到無人機自身的飛行條件限制

其中:Vmin,Vmax,γmin與γmax為無人機航速與航跡角限制;ωmax為無人機最大航向角速度的絕對值.

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

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

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

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

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

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

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

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

4 仿真結(jié)果

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

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

文獻[18]介紹了一種基于拍賣機制的分布式任務(wù)分配方法,該方法以個體打擊概率、資源量、航程和目標威脅度作為任務(wù)分配的指標,且邏輯結(jié)構(gòu)與本文所提仿灰狼算法類似.選取該拍賣算法作為本方法的對比算法.選取3個算例進行對比驗證,分別為10架、15架、20架無人機對15個任務(wù)目標進行合作打擊動態(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分別給出了仿灰狼合作捕食行為的無人機集群動態(tài)任務(wù)分配算法與拍賣機制任務(wù)分配算法的三維仿真結(jié)果,圖中標號代表無人機與目標編號.

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

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

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

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

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

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

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

5 結(jié)論

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