基于改進(jìn)K-means算法和總時(shí)最短機(jī)制的無人機(jī)群多目標(biāo)分配圍獵策略

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

(1.西北工業(yè)大學(xué) 自動(dòng)化學(xué)院,陜西 西安,710072;2.陜西學(xué)前師范學(xué)院 數(shù)學(xué)與統(tǒng)計(jì)學(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)用場(chǎng)景，它源于自然界中普遍存在的捕食狩獵行為，在多年的研究發(fā)展中對(duì)圍獵形式，圍獵目的進(jìn)行了豐富的擴(kuò)展[2-3]。其中多目標(biāo)圍獵作為重要的戰(zhàn)術(shù)環(huán)節(jié)是目標(biāo)圍獵的一個(gè)熱點(diǎn)問題，可以作為抓捕敵方重要人員或在對(duì)抗中壓制敵方重要目標(biāo)的有力手段[4]。然而多目標(biāo)圍獵任務(wù)涉及智能體較多，因此也更具有挑戰(zhàn)性。

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

處理復(fù)雜問題時(shí)，在全局中采用分布式、在局部采用集中式的方式在規(guī)模中等的任務(wù)分配中有較好的性能[10]。現(xiàn)階段對(duì)于單目標(biāo)圍獵問題的研究比較成熟，且相對(duì)于多目標(biāo)，單目標(biāo)圍獵更容易實(shí)現(xiàn)。因此在無人機(jī)群圍獵多個(gè)獨(dú)立目標(biāo)時(shí)，考慮將復(fù)雜的多目標(biāo)圍獵問題通過聚類劃分轉(zhuǎn)換為多個(gè)簡(jiǎ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)位置的總旅行時(shí)間在一個(gè)合理的可計(jì)算上界內(nèi)。選擇合適的算法有利于對(duì)多個(gè)目標(biāo)進(jìn)行快速劃分，K-means聚類算法應(yīng)用廣泛，計(jì)算復(fù)雜度低，具有較好的收斂速度。因此本文使用K-means算法對(duì)多目標(biāo)圍獵問題進(jìn)行初步劃分。

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

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

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

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

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

1 圍獵問題描述

首先給出單目標(biāo)被成功圍獵的定義。當(dāng)發(fā)現(xiàn)待圍獵目標(biāo)時(shí)，目標(biāo)周圍的n個(gè)UAV逐漸靠近,將目標(biāo)限制在半徑為r的范圍內(nèi)。根據(jù)圍獵的臨界條件[20],完成圍獵需要3個(gè)智能體分布在目標(biāo)同一平面內(nèi),即為了確保目標(biāo)被成功圍獵,須滿足n≥3。此時(shí)以待圍獵目標(biāo)的位置pt為中心,在半徑r的圓上作內(nèi)接n多邊形,當(dāng)控制UAV占據(jù)多邊形的n個(gè)頂點(diǎn)形成圍獵陣型時(shí)可以認(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)一一對(duì)應(yīng)的多個(gè)單目標(biāo)圍獵子系統(tǒng)。子系統(tǒng)結(jié)構(gòu)更簡(jiǎn)單且相互獨(dú)立,從而可以降低無人機(jī)群多目標(biāo)圍獵系統(tǒng)的耦合性。子系統(tǒng)內(nèi)部繼續(xù)對(duì)圍獵任務(wù)進(jìn)行分解,將單目標(biāo)圍獵任務(wù)分解成多個(gè)簡(jiǎn)單的子任務(wù)并分配給具體的UAV個(gè)體。任務(wù)分層與任務(wù)分配問題如圖2所示。

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

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

T={ti|1≤i≤M}

(2)

同時(shí)空間中存在N個(gè)UAV,定義UAV個(gè)體的集合U為

U={uj|1≤j≤N}

(3)

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

任務(wù)分層目標(biāo):分層結(jié)果需要保證每個(gè)待圍獵目標(biāo)ti對(duì)應(yīng)一個(gè)子系統(tǒng)Si,并且每個(gè)子系統(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個(gè)UAV,則會(huì)對(duì)應(yīng)q個(gè)子任務(wù)。子系統(tǒng)i中待分配的子任務(wù)tik的集合表示為

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

(6)

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

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

(7)

且需滿足

(8)

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

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

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

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

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

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

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

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

(9)

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

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

(10)

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

步驟3 對(duì)于數(shù)量不滿足的子系統(tǒng)Se,計(jì)算不包含在子系統(tǒng)Se內(nèi)的元素與屬于Se的聚類中心pte的距離,將距離該中心最近的元素劃分至Se。在調(diào)整子系統(tǒng)內(nèi)元素?cái)?shù)量時(shí),可能出現(xiàn)子系統(tǒng)內(nèi)的元素被抽離后,該子系統(tǒng)元素個(gè)數(shù)不滿足要求的情況,需要重新補(bǔ)充。為了防止同個(gè)元素被來回調(diào)動(dòng)所造成的算法循環(huán)，需要限制被調(diào)動(dòng)的元素不再考慮補(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 基于總時(shí)最短機(jī)制的任務(wù)分配策略

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

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

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

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

(11)

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

(12)

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

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

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

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

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

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

為了驗(yàn)證本文提出的多目標(biāo)圍獵策略的有效性,設(shè)計(jì)了一個(gè)仿真實(shí)驗(yàn)，指派9個(gè)UAV分別圍獵3個(gè)目標(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算法對(duì)系統(tǒng)進(jìn)行分層,分層效果如圖6所示?？梢钥闯?分層算法能夠生成與待圍獵目標(biāo)數(shù)量相同的子系統(tǒng),并且能夠?qū)?shù)目不滿足的子系統(tǒng)進(jìn)行補(bǔ)全。由圖6b)～6c)可以看出,被調(diào)動(dòng)過的UAV不會(huì)被重復(fù)調(diào)動(dòng),最終使得每個(gè)子系統(tǒng)都滿足成功圍獵的要求。

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

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

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

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

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

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

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

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

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

6 結(jié) 論

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