凌文通，倪建軍，陳 顏，唐廣翼

(河海大學(xué)物聯(lián)網(wǎng)工程學(xué)院，江蘇 常州 213022)

0 引 言

隨著計(jì)算機(jī)、傳感器、控制等各方面技術(shù)的發(fā)展，無人機(jī)技術(shù)在各個方面的應(yīng)用也越來越廣泛。因?yàn)闊o人機(jī)的速度、機(jī)動性的優(yōu)勢[1]，無人機(jī)所發(fā)揮的作用也會越來越大。相比較于單無人機(jī)，多無人機(jī)執(zhí)行任務(wù)能力更強(qiáng)，效率更高[2-3]。而多無人機(jī)對目標(biāo)進(jìn)行圍捕是其中重要且典型的任務(wù)之一。

為了解決這個任務(wù)，已經(jīng)有許多學(xué)者做了廣泛的研究。文獻(xiàn)[4]提出了一種多層環(huán)狀攻擊圍捕模型，并依據(jù)能量均衡原則，對系統(tǒng)能量進(jìn)行消耗平衡。文獻(xiàn)[5]提出了一種基于博弈論及Q學(xué)習(xí)的多Agent協(xié)作追捕算法。文獻(xiàn)[6]通過優(yōu)化機(jī)器人的速度和方向以達(dá)到快速圍捕任務(wù)。Dutta[7]介紹了Kamimura和Ohira以及Angelani的多目標(biāo)離散化圍捕模型,但初始化時隨機(jī)分布、無障礙物、無對抗、路徑特殊，不需要形成一定的隊(duì)形。文獻(xiàn)[8]針對有障礙的復(fù)雜環(huán)境下圍捕問題，改進(jìn)了粒子群算法，使得圍捕者能夠在規(guī)避障礙物的情況下實(shí)現(xiàn)對目標(biāo)的圍捕。文獻(xiàn)[9]通過改進(jìn)傳統(tǒng)的人工勢場方法，解決了“目標(biāo)不可到達(dá)”和“死鎖”問題從而完成任務(wù)。文獻(xiàn)[10]把動物學(xué)行為引入無人機(jī)群，使用基于勢點(diǎn)的策略完成任務(wù)。

在實(shí)時圍捕任務(wù)中，仍有一些問題需要解決，如人工勢場、粒子群算法搜索效率慢等。大部分的算法直接使用路徑規(guī)劃[11-13]方法圍捕目標(biāo)，而使用預(yù)測的方法能夠?qū)崿F(xiàn)攔截式圍捕，具有先驗(yàn)性，減小航行距離，能夠更快地完成圍捕任務(wù)。針對上述問題，本文將改進(jìn)的鯨魚優(yōu)化算法用于無人機(jī)圍捕任務(wù)，提出一種基于動態(tài)預(yù)測圍捕點(diǎn)的多無人機(jī)圍捕算法。

1 問題描述

在本文任務(wù)中，將所有的無人機(jī)視為質(zhì)點(diǎn)，忽略大小、形狀及通訊問題，UAV被標(biāo)記為Ui，i=1,2,…,N,其中N是無人機(jī)的數(shù)量；T表示移動目標(biāo)，目標(biāo)運(yùn)動軌跡未知。

圍捕過程描述如下：無人機(jī)探測范圍大于目標(biāo)，并且可以實(shí)時感知目標(biāo)的位置信息，無人機(jī)相互之間信息共享，若無人機(jī)在目標(biāo)周圍均勻分布且到目標(biāo)的距離小于規(guī)定距離時，即可以認(rèn)定圍捕成功。

2 動態(tài)圍捕點(diǎn)預(yù)測和分配

2.1 動態(tài)圍捕點(diǎn)

因?yàn)楸疚募僭O(shè)目標(biāo)軌跡是未知的，沒有大量數(shù)據(jù)進(jìn)行模擬預(yù)測[14-15]，可以認(rèn)為目標(biāo)未來短期時間內(nèi)的運(yùn)動軌跡與其之前一段時間內(nèi)的運(yùn)動狀態(tài)有關(guān)，而與更久遠(yuǎn)之前的運(yùn)動狀態(tài)無關(guān)。通過采樣當(dāng)前位置及之前k個位置信息，通過多項(xiàng)式擬合法擬合出目標(biāo)運(yùn)動軌跡方程，在較短時間內(nèi)可以認(rèn)為目標(biāo)會沿著擬合運(yùn)動軌跡運(yùn)動。根據(jù)所需求預(yù)測的步數(shù)在軌跡上確定目標(biāo)點(diǎn)，然后發(fā)送給無人機(jī)。預(yù)測步數(shù)越大，圍捕效果越好；預(yù)測步數(shù)越小，準(zhǔn)確度越高，同時因?yàn)楸疚牡貓D是連續(xù)的，所以本文將預(yù)測步數(shù)設(shè)置如下：

(1)

其中，s為預(yù)測步數(shù)，s1為常數(shù)，t為迭代次數(shù)，tmax為最大迭代次數(shù)。預(yù)測目標(biāo)點(diǎn)確立之后，在其周圍產(chǎn)生動態(tài)圍捕點(diǎn)。隨著目標(biāo)的不斷移動，預(yù)測信息不斷進(jìn)行更新，動態(tài)圍捕點(diǎn)也不斷更新，實(shí)現(xiàn)動態(tài)預(yù)測。

無人機(jī)沿著動態(tài)圍捕點(diǎn)向著目標(biāo)進(jìn)行圍捕，因?yàn)殡x目標(biāo)的距離不同，為避免有無人機(jī)提前進(jìn)入目標(biāo)勘測范圍，導(dǎo)致目標(biāo)逃逸增加任務(wù)難度，所以設(shè)立安全域的范圍[16]，當(dāng)所有無人機(jī)未到達(dá)期望圍捕點(diǎn)之前，安全域禁止進(jìn)入，其定義為：

(2)

其中，Dsafe(E)為安全域，(x,y)為安全域中任一點(diǎn)，(xm,ym)為目標(biāo)點(diǎn)位置，f為目標(biāo)探測距離。

期望圍捕點(diǎn)在安全域邊界產(chǎn)生，以目標(biāo)運(yùn)動反方向與安全域交點(diǎn)為起點(diǎn)，均勻產(chǎn)生n個點(diǎn)作為圍捕點(diǎn)，n的個數(shù)等同于圍捕無人機(jī)的個數(shù)。如圖1所示。

圖1 圍捕點(diǎn)的分配

圖1中V為目標(biāo)運(yùn)動方向，因此圍捕點(diǎn)的坐標(biāo)表示為：

(3)

(4)

2.2 圍捕點(diǎn)分配

圍捕點(diǎn)確定之后，需要將圍捕點(diǎn)分配給各個無人機(jī)[17-19]。最常用的方法是貪婪算法，但是該方法容易出現(xiàn)死鎖問題，本文采取的是基于距離的雙向協(xié)商法。該方法首先利用基于距離最近原則的貪婪算法，通過計(jì)算機(jī)器人與圍捕點(diǎn)的距離，對圍捕點(diǎn)進(jìn)行預(yù)分配，然后雙向協(xié)商進(jìn)行再分配。這種雙向協(xié)商方法計(jì)算簡單，效率很高，算法具體過程如下：

1)初始化無人機(jī)和期望圍捕點(diǎn)位置，設(shè)U為無人機(jī)的集合，U={U1,U2,…,Un}，M為期望圍捕點(diǎn)的集合，M={m1,m2,…,mn}。

2)計(jì)算無人機(jī)Ui到各個圍捕點(diǎn)mj的距離Dij；其中：

3)對于無人機(jī)Ui,i=1,2,…,n，計(jì)算Dij,j=1,2,…,n的最小值，將對應(yīng)距離最小的圍捕點(diǎn)mj分配給無人機(jī)Ui，令mj=mj+1。

4)mj的值有3種情況：

①mj=0，則該點(diǎn)未進(jìn)行分配。

②mj=1，則該點(diǎn)匹配成功，記錄下匹配成功的圍捕點(diǎn)mj和無人機(jī)Ui，并將其分別從集合U和集合M中移除，令n=n-1。

③mj>1，則將圍捕點(diǎn)mj分配給距離最遠(yuǎn)的無人機(jī)Ui，并將其分別從集合U和集合M中移除，令n=n-1。

5)若n=0，則表明所有的圍捕點(diǎn)都分配成功，否則跳往步驟1繼續(xù)。

3 鯨魚優(yōu)化算法及改進(jìn)

3.1 鯨魚優(yōu)化算法

鯨魚優(yōu)化算法[20](Whale Optimization Algorithm， WOA)是澳大利亞學(xué)者M(jìn)irjalili等根據(jù)座頭鯨的狩獵方式提出的一種新的群智能優(yōu)化算法。鯨魚在大海中隨機(jī)游走尋找獵物，使用一種泡網(wǎng)覓食法的狩獵方式，先深入水底收縮包圍獵物，而后螺旋上升在靠近海面的地方捕食獵物。鯨魚優(yōu)化算法數(shù)學(xué)模型主要包括3個部分：游走搜索獵物、收縮包圍獵物和螺旋捕食獵物。

1)搜索階段。

WOA在尋優(yōu)過程中，通過參數(shù)A的改變來控制搜索策略。當(dāng)|A|>1時，WOA進(jìn)行全局尋優(yōu)，隨機(jī)選擇一個作為參考個體，新個體然后按以下公式進(jìn)行更新：

D=|C·Xrand-X|

(5)

X(t+1)=Xrand-A·D

(6)

其中，X表示當(dāng)前鯨魚位置，D表示包圍步長，Xrand為種群中隨機(jī)選取鯨魚的位置，t為當(dāng)前計(jì)算次數(shù)，A表示生成個體離參考個體遠(yuǎn)近程度，A和C的定義如式(8)和式(9)所示：

a=2-2t/tmax

(7)

A=2·a·r-a

(8)

C=2·r

(9)

其中，r是在[0,1]范圍內(nèi)的隨機(jī)數(shù)。

2)包圍階段。

包圍階段時，鯨魚個體不再隨機(jī)更新位置，選擇當(dāng)前最優(yōu)位置作為目標(biāo)，從而使種群獲得最優(yōu)解。收縮包圍獵物的位置更新公式為：

Dbest=|C·X(t)best-X(t)|

(10)

X(t+1)=X(t)best-A·Dbest

(11)

3)捕食階段。

鯨魚通過一種螺旋式游走的方式形成氣泡網(wǎng)進(jìn)行捕食，其具體更新為：

X(t+1)=Dbest·ebt·cos(2πl(wèi))+X(t)best

(12)

其中，b為控制螺旋線形狀的常數(shù)，l為[0,1]的隨機(jī)變量。鯨魚的捕獵行為和螺旋收縮是同時進(jìn)行的，假設(shè)兩者概率均為50%，具體數(shù)學(xué)模型為：

(13)

3.2 改進(jìn)的鯨魚優(yōu)化算法

WOA相比其它算法，具有結(jié)構(gòu)簡單、自身參數(shù)少以及尋優(yōu)能力強(qiáng)的特點(diǎn)，在許多工程領(lǐng)域已經(jīng)得到應(yīng)用，但與其它智能優(yōu)化算法類似，容易陷入局部最優(yōu)，導(dǎo)致早熟。因此需要提升算法的全局搜索能力[21-23]，本文提出一種自適應(yīng)權(quán)重方法。在算法包圍階段，迭代完成之后，保留最優(yōu)的3個個體X1(t),X2(t),X3(t)，最優(yōu)個體按照式(14)進(jìn)行計(jì)算：

(14)

因?yàn)檫m應(yīng)度值是反應(yīng)個體優(yōu)劣的重要指標(biāo)，所以將適應(yīng)度值作為求取權(quán)重的判斷依據(jù)，w1的計(jì)算方法為：

(15)

其中，J1、J2、J3分別代表X1、X2、X3的適應(yīng)度值，w2,w3由同樣計(jì)算方式所得。通過保留多個最優(yōu)個體從而提升全局搜索能力，克服算法容易陷入局部最優(yōu)的缺點(diǎn)。

在捕食階段，鯨魚以螺旋式方式對自身位置進(jìn)行更新，其中公式(13)的b為控制螺旋形狀的參數(shù)，一般設(shè)為常數(shù)，這種前進(jìn)方式比較單一。為了使鯨魚能夠以更多的方式捕獲目標(biāo)，將參數(shù)b設(shè)計(jì)為隨迭代次數(shù)而不斷進(jìn)行改變的變量，參數(shù)b的具體設(shè)置為：

(16)

b隨著迭代的次數(shù)不斷增加而改變，螺旋線形狀由大到小也在發(fā)生改變，在算法初期，能夠擴(kuò)大搜索空間；在算法的后期，能夠提高局部尋優(yōu)精度，加快搜索速率，改善算法性能。改進(jìn)后整個算法步驟如下：

步驟1 初始化無人機(jī)以及目標(biāo)位置。

步驟2 根據(jù)目標(biāo)信息，動態(tài)預(yù)測目標(biāo)將要出現(xiàn)的位置，以此位置建立目標(biāo)安全域和期望圍捕點(diǎn)。

步驟3 根據(jù)雙向協(xié)商法將期望圍捕點(diǎn)分配給各個無人機(jī)。

步驟4 無人機(jī)使用改進(jìn)后的鯨魚群算法朝著期望圍捕點(diǎn)前進(jìn)。

步驟5 當(dāng)無人機(jī)都達(dá)到任務(wù)點(diǎn)后停止，否則返回步驟2繼續(xù)。

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

4.1 簡單環(huán)境實(shí)驗(yàn)

在實(shí)驗(yàn)過程中，為驗(yàn)證所提出算法的有效性，首先在二維環(huán)境中進(jìn)行了無障礙和有障礙的實(shí)驗(yàn)。實(shí)驗(yàn)過程中，目標(biāo)進(jìn)行不規(guī)則的平滑曲線運(yùn)動。實(shí)驗(yàn)結(jié)果如圖2所示。

在這部分實(shí)驗(yàn)中，無人機(jī)初始位置分別為(0,0)，(90,10)，(10,50)，其中圖2(a)和圖2(c)是原始算法結(jié)果，圖2(b)和圖2(d)為改進(jìn)后算法所得到結(jié)果，從2幅對比圖中可以明顯看出改進(jìn)后的算法優(yōu)于原始算法，行進(jìn)路線更為平滑，減小了無人機(jī)轉(zhuǎn)彎損耗。在面對障礙物時，也能更好地躲避障礙物，圍捕效果明顯優(yōu)于原始算法。

(a) 原始算法

(b) 改進(jìn)算法

(c) 原始算法

(d) 改進(jìn)算法

4.2 中等環(huán)境實(shí)驗(yàn)

無人機(jī)實(shí)際工作環(huán)境為三維環(huán)境，為了使實(shí)驗(yàn)更加接近真實(shí)環(huán)境，并測試所提出算法的性能，設(shè)計(jì)了如下實(shí)驗(yàn)，建立了三維環(huán)境模型。如圖3所示，將無人機(jī)數(shù)量設(shè)為5，其初始位置分別為(10,10,8)，(30,40,65)，(80,35,40)，(15,85,60)，(80,95,50)，目標(biāo)點(diǎn)位置為(50,50,10)。目標(biāo)是運(yùn)動的，三維空間中存在障礙物。通過多幅圖來展現(xiàn)無人機(jī)目標(biāo)圍捕過程，圖3(a)為初始位置，圖3(b)和圖3(c)是無人機(jī)進(jìn)行圍捕的路徑過程，從圖中可以看出無人機(jī)在三維環(huán)境中也可以成功完成目標(biāo)圍捕任務(wù)。

(a) 初始位置

(b) 圍捕過程1

(c) 圍捕過程2

(d) 最終結(jié)果

4.3 復(fù)雜環(huán)境實(shí)驗(yàn)

針對實(shí)際環(huán)境中可能出現(xiàn)更加復(fù)雜的情況，比如出現(xiàn)動態(tài)障礙物等，設(shè)計(jì)了如下實(shí)驗(yàn)。在這次實(shí)驗(yàn)中，存在著空中移動障礙物。圖4顯示整個團(tuán)隊(duì)圍捕過程，即使在復(fù)雜的實(shí)驗(yàn)環(huán)境下，無人機(jī)仍可以安全完成圍捕任務(wù)。

(a) 初始位置

(b) 圍捕過程1

(c) 圍捕過程2

(d) 最終結(jié)果

為了驗(yàn)證算法的有效性，以中等環(huán)境為實(shí)驗(yàn)背景，將蟻群算法和原始算法以及改進(jìn)后的算法進(jìn)行了比較，實(shí)驗(yàn)結(jié)果如表1所示。

表1 實(shí)驗(yàn)對比結(jié)果

5 結(jié)束語

本文研究了未知運(yùn)動目標(biāo)軌跡下的無人機(jī)圍捕問題，通過預(yù)測目標(biāo)短期內(nèi)可能出現(xiàn)的位置，采用雙向協(xié)商法對預(yù)測圍捕點(diǎn)進(jìn)行分配，最后通過改進(jìn)的鯨魚優(yōu)化算法，實(shí)現(xiàn)了目標(biāo)圍捕任務(wù)。為了驗(yàn)證本文算法的有效性，分別在二維以及三維環(huán)境下進(jìn)行了多次實(shí)驗(yàn)，驗(yàn)證了算法的優(yōu)越性。在下一步工作中，將尋找更好的預(yù)測與更簡潔的分配方法，提升算法的性能。