胡濱,朱亞輝,杜致澤,趙子昕,周延年

(1.西北工業(yè)大學(xué) 自動化學(xué)院,陜西 西安,710072;2.陜西學(xué)前師范學(xué)院 數(shù)學(xué)與統(tǒng)計學(xué)院,陜西 西安 710061；3.西北工業(yè)大學(xué) 機(jī)電學(xué)院,陜西 西安,710072;4.交通運(yùn)輸通信信息集團(tuán)有限公司 衛(wèi)星通信事業(yè)部,北京 100011;5.空軍工程大學(xué) 防空反導(dǎo)學(xué)院,陜西 西安 710043)

通過無人機(jī)之間的配合協(xié)作，無人機(jī)群能夠完成單體無人機(jī)難以應(yīng)付的復(fù)雜問題[1]。空中目標(biāo)圍獵是多無人機(jī)群的典型應(yīng)用場景，它源于自然界中普遍存在的捕食狩獵行為，在多年的研究發(fā)展中對圍獵形式，圍獵目的進(jìn)行了豐富的擴(kuò)展[2-3]。其中多目標(biāo)圍獵作為重要的戰(zhàn)術(shù)環(huán)節(jié)是目標(biāo)圍獵的一個熱點(diǎn)問題，可以作為抓捕敵方重要人員或在對抗中壓制敵方重要目標(biāo)的有力手段[4]。然而多目標(biāo)圍獵任務(wù)涉及智能體較多，因此也更具有挑戰(zhàn)性。

多目標(biāo)圍獵策略影響了任務(wù)整體實(shí)現(xiàn)的復(fù)雜度，合理的策略是實(shí)現(xiàn)成功圍獵的必要條件，因此對于無人機(jī)群多目標(biāo)圍獵任務(wù)需要制定高效圍獵多個目標(biāo)的策略。圍捕策略是一種特殊的編隊(duì)控制策略，根據(jù)不同目標(biāo)數(shù)目，分為單目標(biāo)圍獵和多目標(biāo)圍獵。目前，協(xié)調(diào)多架無人機(jī)執(zhí)行目標(biāo)圍獵任務(wù)的研究方法主要有基于虛擬結(jié)構(gòu)法、基于行為法、人工勢場法和圖論法。常見的單目標(biāo)圍獵策略有受自然現(xiàn)象啟發(fā)的狼群捕獵模式。Muro等[5]參考狼群的狩獵過程，提出了一種多智能體協(xié)同圍獵模型。該模型對追捕者的溝通要求較低，同時不需要構(gòu)建狼群中的等級制度來維持系統(tǒng)內(nèi)秩序。Atamurat等[6]研究了在歐氏空間中所有個體速度相同情況下的單目標(biāo)圍獵問題，對圍捕模型進(jìn)行分析得出了圍獵成功的條件。Chen等[7]研究了高速逃逸目標(biāo)的圍獵問題，給出了能夠成功圍獵的條件，包括所需執(zhí)行者的最小數(shù)量、初始分布狀態(tài)以及圍捕策略。在多目標(biāo)圍獵方面，Lopez等[8]對多智能體和多個動態(tài)目標(biāo)的圍獵博弈進(jìn)行研究，對所有博弈方設(shè)定最優(yōu)策略，采用圖論方法為智能體分配控制策略，最后對有限時間內(nèi)的圍獵效果做出分析。Amini等[9]提出了一種基于動態(tài)事件觸發(fā)機(jī)制的圍獵控制方法，利用分布式動態(tài)事件觸發(fā)結(jié)構(gòu)，在降低通信量的同時實(shí)現(xiàn)非完整智能體系統(tǒng)的多目標(biāo)圍獵任務(wù)?？梢钥闯瞿壳皩τ诙嗄繕?biāo)圍獵的研究還不成熟，往往需要依賴復(fù)雜的計算和控制策略，而且許多研究是將多個目標(biāo)考慮為一個整體進(jìn)行分析，針對多個目標(biāo)分別圍獵的研究較少。

處理復(fù)雜問題時，在全局中采用分布式、在局部采用集中式的方式在規(guī)模中等的任務(wù)分配中有較好的性能[10]?，F(xiàn)階段對于單目標(biāo)圍獵問題的研究比較成熟，且相對于多目標(biāo)，單目標(biāo)圍獵更容易實(shí)現(xiàn)。因此在無人機(jī)群圍獵多個獨(dú)立目標(biāo)時，考慮將復(fù)雜的多目標(biāo)圍獵問題通過聚類劃分轉(zhuǎn)換為多個簡單的單目標(biāo)圍獵問題從而降低問題難度。常見的聚類算法有基于劃分的K-means[11]及Voronoi算法[12]、基于密度的DBSCAN[13]算法以及基于圖論的譜聚類算法[14]等。Elango等[15]利用K-means算法進(jìn)行多機(jī)器人的任務(wù)分群從而最小化任務(wù)之間的距離。Bai等[16]分析了多種聚類算法，并提出將聚類策略與目標(biāo)插入度量相結(jié)合的形式，保證了訪問所有目標(biāo)位置的總旅行時間在一個合理的可計算上界內(nèi)。選擇合適的算法有利于對多個目標(biāo)進(jìn)行快速劃分，K-means聚類算法應(yīng)用廣泛，計算復(fù)雜度低，具有較好的收斂速度。因此本文使用K-means算法對多目標(biāo)圍獵問題進(jìn)行初步劃分。

圍獵的實(shí)現(xiàn)需要每個無人機(jī)個體執(zhí)行明確的任務(wù)指令，即到達(dá)確定的位置。通過任務(wù)分配可以確定每個UAV需要執(zhí)行的子任務(wù)。Wang等[17]研究了多智能體系統(tǒng)中協(xié)同控制的任務(wù)分配機(jī)制，指出通過協(xié)同分配協(xié)議可以在間歇通訊情況下得到較好的分配結(jié)果。Lee等[18]提出了一種面向資源的分散拍賣算法，該算法考慮了智能體的資源消耗問題以及有限通訊范圍問題。在分配任務(wù)時會出現(xiàn)沖突現(xiàn)象即同一個任務(wù)的最佳執(zhí)行個體不唯一，此時就需要設(shè)計分配機(jī)制。設(shè)計準(zhǔn)則可以是系統(tǒng)的資源消耗最少，任務(wù)完成的時間最短等。在實(shí)際情況中，防止目標(biāo)在圍捕之前逃逸，將目標(biāo)快速圍捕是最重要的。上述研究雖然可以實(shí)現(xiàn)最優(yōu)解，但任務(wù)完成的總時間不一定最短。Bai等[19]研究了多個分散車輛訪問一組目標(biāo)的動態(tài)任務(wù)分配問題，提出了基于事件觸發(fā)和時間觸發(fā)的2種動態(tài)任務(wù)分配算法。但該算法較為復(fù)雜。因此本文考慮無人機(jī)群中的個體在速度相同的情況下，以完成圍獵任務(wù)總時間最短為目標(biāo)，設(shè)計任務(wù)分配算法并使該算法的計算量盡可能小。

本文主要研究適用于空中無人機(jī)群多目標(biāo)圍獵任務(wù)分配策略的整體解決方案。為了得到更好的圍獵性能，采用混合式方法的思想，先利用分布式方法對系統(tǒng)進(jìn)行分層處理，之后針對每個獨(dú)立的子系統(tǒng)利用局部的集中式方法完成圍捕任務(wù)的分配。通過對任務(wù)不斷細(xì)分，實(shí)現(xiàn)復(fù)雜任務(wù)的簡單化。

本文的創(chuàng)新點(diǎn)如下：

1) 改進(jìn)了K-means法，通過該分布式算法可以將多目標(biāo)圍獵問題分解為多個相互獨(dú)立的、能夠滿足圍獵條件的單目標(biāo)圍獵系統(tǒng)。該算法計算量小、操作簡單，能夠處理大規(guī)模無人機(jī)群的任務(wù)分層。

2) 針對一個單目標(biāo)圍獵子系統(tǒng)，通過任務(wù)分解使單體無人機(jī)只需完成簡單明確的子任務(wù)即可完成單目標(biāo)的圍獵?？紤]到實(shí)際圍獵情況，以完成圍獵任務(wù)的總耗時最少為決策條件，設(shè)計了一種任務(wù)分配策略，能夠以較少的計算量得到使任務(wù)完成時間最短的分配方案。

1 圍獵問題描述

首先給出單目標(biāo)被成功圍獵的定義。當(dāng)發(fā)現(xiàn)待圍獵目標(biāo)時，目標(biāo)周圍的n個UAV逐漸靠近,將目標(biāo)限制在半徑為r的范圍內(nèi)。根據(jù)圍獵的臨界條件[20],完成圍獵需要3個智能體分布在目標(biāo)同一平面內(nèi),即為了確保目標(biāo)被成功圍獵,須滿足n≥3。此時以待圍獵目標(biāo)的位置pt為中心,在半徑r的圓上作內(nèi)接n多邊形,當(dāng)控制UAV占據(jù)多邊形的n個頂點(diǎn)形成圍獵陣型時可以認(rèn)為圍獵成功。

考慮到實(shí)際情況,允許UAV的位置pu與多邊形頂點(diǎn)之間存在Δr的偏差。即

r-Δr≤‖pu-pt‖≤r+Δr

(1)

式中：pu為UAV的位置;pt為待圍獵目標(biāo)位置。圍獵效果如圖1所示。

圖1 圍獵成功示意圖

2 任務(wù)分層與任務(wù)分配問題描述

通過任務(wù)分層可以將無人機(jī)群多目標(biāo)圍獵問題分解成與待圍獵目標(biāo)一一對應(yīng)的多個單目標(biāo)圍獵子系統(tǒng)。子系統(tǒng)結(jié)構(gòu)更簡單且相互獨(dú)立,從而可以降低無人機(jī)群多目標(biāo)圍獵系統(tǒng)的耦合性。子系統(tǒng)內(nèi)部繼續(xù)對圍獵任務(wù)進(jìn)行分解,將單目標(biāo)圍獵任務(wù)分解成多個簡單的子任務(wù)并分配給具體的UAV個體。任務(wù)分層與任務(wù)分配問題如圖2所示。

圖2 任務(wù)分層與任務(wù)分配示意圖

考慮在無人機(jī)群多目標(biāo)圍獵系統(tǒng)中有M個待圍獵目標(biāo),定義待圍獵目標(biāo)個體的集合T為

T={ti|1≤i≤M}

(2)

同時空間中存在N個UAV,定義UAV個體的集合U為

U={uj|1≤j≤N}

(3)

為了保證所有的目標(biāo)都能被成功圍獵,需要滿足N≥3M。

任務(wù)分層目標(biāo):分層結(jié)果需要保證每個待圍獵目標(biāo)ti對應(yīng)一個子系統(tǒng)Si,并且每個子系統(tǒng)中包含的UAV數(shù)量q需要滿足q≥3。子系統(tǒng)Si表示為

Si={uij|1≤i≤M,1≤j≤q}

(4)

子任務(wù)的集合表示為

S={Si|1≤i≤M}

(5)

任務(wù)分配是指:在圍獵子系統(tǒng)Si中,若存在q個UAV,則會對應(yīng)q個子任務(wù)。子系統(tǒng)i中待分配的子任務(wù)tik的集合表示為

Ti={tik|1≤i≤M,1≤k≤q}

(6)

子系統(tǒng)i中的UAV個體uij可以對tik做出評價,評價的效用值用bijk表示。對于可以執(zhí)行的任務(wù)bijk≥0,若不能執(zhí)行tik,則bijk=0。把完成任務(wù)所需的時間作為評價指標(biāo)時,uij完成tik的時間越短,則bijk的值越大。

任務(wù)分配問題可以描述為

(7)

且需滿足

(8)

通過(8)式可以保證子系統(tǒng)中的每個UAV都有需要待執(zhí)行的子任務(wù),同時每個待執(zhí)行的子任務(wù)都必須由一個UAV去完成。

3 改進(jìn)K-means算法的任務(wù)分層方法

傳統(tǒng)的K-means算法能夠?qū)Υ罅繑?shù)據(jù)進(jìn)行劃分,從而形成所需數(shù)目的數(shù)據(jù)簇,同一個簇中數(shù)據(jù)元素之間的相近度較高,經(jīng)過該算法的劃分,每個數(shù)據(jù)只能隸屬于一個數(shù)據(jù)簇。該算法的劃分依據(jù)是最小誤差函數(shù),該誤差函數(shù)可以描述各個數(shù)據(jù)與聚類中心的偏差情況。一般選用數(shù)據(jù)和中心的歐式距離作為誤差函數(shù)。

根據(jù)任務(wù)分層的要求,將K-means算進(jìn)行改進(jìn)。改進(jìn)后的算法主要有以下特點(diǎn):

1) 將N個待圍獵目標(biāo)的坐標(biāo)設(shè)置為聚類中心,并且該聚類中心不隨著算法的迭代而發(fā)生變化。

2) 劃分完成后分別判斷每個子系統(tǒng)內(nèi)的UAV個數(shù)是否滿足要求,如果存在數(shù)量不滿足的子系統(tǒng),則重新劃分。

改進(jìn)的K-means算法步驟如下:

步驟1 設(shè)在空間R內(nèi)存在由n個UAV組成的無人機(jī)群,以UAV位置坐標(biāo)為元素的數(shù)據(jù)集記為p={p1,…,pn},同時存在m個待圍捕目標(biāo),將目標(biāo)的位置坐標(biāo)設(shè)置為初始的m個聚類中心,表示為pti,i∈{1,…,m}。用(9)式計算pj相對于pti的距離dij。

(9)

根據(jù)計算結(jié)果,pj會被規(guī)劃到距離最近的數(shù)據(jù)中心i所代表的數(shù)據(jù)簇Ci內(nèi)。

Ci={pj|‖pj-pti‖≤‖pj-ptq‖,1≤q≤m}

(10)

步驟2 通過步驟1，初步形成m個子系統(tǒng)。之后判斷每個子系統(tǒng)內(nèi)的UAV數(shù)量是否滿足要求。

步驟3 對于數(shù)量不滿足的子系統(tǒng)Se,計算不包含在子系統(tǒng)Se內(nèi)的元素與屬于Se的聚類中心pte的距離,將距離該中心最近的元素劃分至Se。在調(diào)整子系統(tǒng)內(nèi)元素數(shù)量時,可能出現(xiàn)子系統(tǒng)內(nèi)的元素被抽離后,該子系統(tǒng)元素個數(shù)不滿足要求的情況,需要重新補(bǔ)充。為了防止同個元素被來回調(diào)動所造成的算法循環(huán)，需要限制被調(diào)動的元素不再考慮補(bǔ)充到原來的子系統(tǒng)中。

（19）分期出杳入宴，恍惚經(jīng)緯萬方。（《太上說玄天大聖真武本傳神呪妙經(jīng)註》卷二，《中華道藏》30/549）

步驟4 重復(fù)步驟2～3直至所有子系統(tǒng)內(nèi)的元素滿足要求。

改進(jìn)K-means算法的流程圖如圖3所示。

圖3 改進(jìn)K-means算法流程圖

4 基于總時最短機(jī)制的任務(wù)分配策略

系統(tǒng)分層后,每個子系統(tǒng)需要根據(jù)UAV的數(shù)量規(guī)劃子任務(wù)并給出子任務(wù)的分配結(jié)果。通過設(shè)計任務(wù)分配機(jī)制,可以使整個系統(tǒng)得到能夠?qū)崿F(xiàn)需要的較為優(yōu)化的解。

本文的任務(wù)分配機(jī)制是優(yōu)先考慮任務(wù)完成的總時間最短。子系統(tǒng)內(nèi)UAV完成圍獵任務(wù)的總時間取決于完成子任務(wù)時間最長的UAV。假設(shè)同一子系統(tǒng)內(nèi)的UAV同時執(zhí)行任務(wù)且速度相同。這意味著UAV完成子任務(wù)需移動的距離d越短則完成子任務(wù)的用時t越少,即t∝d?；谏鲜鲈O(shè)定,總時最短的分配機(jī)制可轉(zhuǎn)化為分配結(jié)果使UAV完成子任務(wù)移動的距離最大值是眾多分配方案中最小的。

對于一個包含q個UAV的子系統(tǒng)Si,任務(wù)分配算法步驟如下:

步驟1 選取距離待圍獵目標(biāo)最近的UAV作為任務(wù)分配中心記為ui1,計算該UAV到半徑為r的圍獵圓上的最近點(diǎn),并將該點(diǎn)設(shè)為圍獵圓的內(nèi)接正q邊形的一個頂點(diǎn)z1。同時將該頂點(diǎn)位置作為子任務(wù)分配給ui1。

(11)

步驟2 任務(wù)分配中心計算得出其余q-1個頂點(diǎn)的位置。將q-1個頂點(diǎn)位置作為子任務(wù)集向其他UAV發(fā)布。UAV個體uij,j∈{2,…,q}到頂點(diǎn)zk,k∈{2,…,q}的距離記為dijk。每個UAV分別計算與q-1個頂點(diǎn)的距離,得到該UAV的距離數(shù)據(jù)集dij,任務(wù)分配中心對每個數(shù)據(jù)集進(jìn)行匯總得到矩陣Ai,此時Ai∈R(q-1)×(q-1)。

(12)

步驟3 若uij執(zhí)行子任務(wù)tik,則從矩陣Ai中刪除uij對應(yīng)的列向量dij和子任務(wù)tik對應(yīng)的行向量,此時Ai的階數(shù)減1。

步驟4 任務(wù)分配中心找到矩陣Ai中的最大值,該值對應(yīng)的UAV完成子任務(wù)的時間最長。若最大值不唯一,則找出所有最大值對應(yīng)的列向量中的最小值,最小值表示該值對應(yīng)的UAV完成子任務(wù)用時最短。最小值對應(yīng)的UAV和子任務(wù)相互匹配,同時進(jìn)行一次步驟3。若最大值唯一,則找出最大值所在列向量中的最小值。若最小值不唯一,則先將該列向量排除,并重復(fù)步驟4,直到該列向量中的最小值唯一,最小值對應(yīng)的UAV和子任務(wù)相匹配。

步驟5 循環(huán)步驟3～4,直到所有子任務(wù)分配完成。

任務(wù)分配的流程圖如圖4所示。

圖4 任務(wù)分配流程圖

5 實(shí)驗(yàn)仿真

為了驗(yàn)證本文提出的多目標(biāo)圍獵策略的有效性,設(shè)計了一個仿真實(shí)驗(yàn)，指派9個UAV分別圍獵3個目標(biāo)。該系統(tǒng)的初始狀態(tài)如圖5所示。

圖5 多無人機(jī)圍獵系統(tǒng)初始狀態(tài)

UAV的位置是隨機(jī)確定的,表1～2給出了仿真中各UAV和待圍獵目標(biāo)位置。

表1 仿真中各UAV位置

表2 仿真中待圍獵目標(biāo)位置

根據(jù)第2節(jié)所述任務(wù)分層與任務(wù)分配策略,首先使用改進(jìn)的K-means算法對系統(tǒng)進(jìn)行分層,分層效果如圖6所示。可以看出,分層算法能夠生成與待圍獵目標(biāo)數(shù)量相同的子系統(tǒng),并且能夠?qū)?shù)目不滿足的子系統(tǒng)進(jìn)行補(bǔ)全。由圖6b)～6c)可以看出,被調(diào)動過的UAV不會被重復(fù)調(diào)動,最終使得每個子系統(tǒng)都滿足成功圍獵的要求。

系統(tǒng)分層后每個子系統(tǒng)進(jìn)行子任務(wù)的生成與分配,為了比較本文提出總時分配機(jī)制的性能,同時使用匈牙利算法對子任務(wù)進(jìn)行分配。基于總時最短機(jī)制的分配結(jié)果如圖7所示?；谛傺览惴ǖ姆峙浣Y(jié)果如圖8所示。

圖6 任務(wù)分層效果

圖7 各子系統(tǒng)基于總時最短機(jī)制的任務(wù)分解結(jié)果

圖8 各子系統(tǒng)基于匈牙利算法的任務(wù)分解結(jié)果

各子系統(tǒng)內(nèi)子任務(wù)對應(yīng)的坐標(biāo)如表3所示,任務(wù)分配中心對應(yīng)子任務(wù)為1號子任務(wù),其他子任務(wù)按照順時針進(jìn)行編號。

表3 各子系統(tǒng)中各子任務(wù)位置及對應(yīng)關(guān)系

為了分析2種算法的效果,比較了2種分配結(jié)果對應(yīng)的完成圍獵任務(wù)的總時間,為了方便計算,設(shè)智能體的速度都為1,結(jié)果保留2位小數(shù),如表4所示。結(jié)果表明本文提出的分配算法能夠滿足總時最短的要求。

表4 2種算法的完成任務(wù)用時對比

根據(jù)仿真結(jié)果可以看出本文提出的任務(wù)分配策略會選擇總時最短的分配方案,例如圖7b)所示子系統(tǒng)2的分配情況,子任務(wù)2.2對于5號UAV和6號UAV都是距離最近的子任務(wù)。因此會出現(xiàn)分配沖突,此時通過計算,6號UAV完成子任務(wù)2.3的時間比5號UAV完成子任務(wù)2.3的時間更長,因此為了使完成任務(wù)的時間最短,將子任務(wù)2.2分配給6號UAV。

6 結(jié) 論

本文提出的多目標(biāo)任務(wù)分配策略將復(fù)雜的系統(tǒng)逐步分解為多個簡單子任務(wù),將計算任務(wù)分散在單體UAV上,提高了系統(tǒng)的靈活性。該策略首先通過改進(jìn)K-means算法使系統(tǒng)分層形成多個子系統(tǒng),實(shí)現(xiàn)系統(tǒng)的解耦。之后每個子系統(tǒng)作為單獨(dú)的任務(wù)單元將任務(wù)細(xì)分并以完成任務(wù)的總時間為主要考慮因素對子任務(wù)進(jìn)行分配,使UAV在最短時間內(nèi)完成目標(biāo)的圍獵任務(wù)。通過仿真實(shí)驗(yàn)可以證明該策略易行且有效。