持續(xù)監(jiān)視問(wèn)題多無(wú)人機(jī)協(xié)同搜索策略*

王嘉博，劉 莉，王 祝，許 萌

(北京理工大學(xué)宇航學(xué)院，北京 100081)

0 引言

無(wú)人機(jī)對(duì)目標(biāo)空間執(zhí)行持續(xù)監(jiān)視任務(wù)[1]廣泛應(yīng)用于氣象監(jiān)測(cè)、地形測(cè)繪、戰(zhàn)術(shù)偵察和地外探索等領(lǐng)域[2]，典型的偵察無(wú)人機(jī)包括“全球鷹(Global Hawk)”、“捕食者(Predator)”和“折疊式掃描鷹(ScanEagle Compressed Carriage，SECC)”等。然而，在現(xiàn)實(shí)任務(wù)環(huán)境中，由于持續(xù)監(jiān)視任務(wù)的復(fù)雜性和多樣性，單架無(wú)人機(jī)獨(dú)自完成持續(xù)監(jiān)視任務(wù)變得十分艱難，因此多無(wú)人機(jī)協(xié)同搜索成為一種有效的解決方案[3－4]。多無(wú)人機(jī)協(xié)同搜索策略研究正逐漸成為研究熱點(diǎn)。

本研究從持續(xù)監(jiān)視問(wèn)題的基本概念入手，針對(duì)貪婪搜索策略和分布式協(xié)議搜索策略兩種基準(zhǔn)策略[5]在執(zhí)行持續(xù)監(jiān)視任務(wù)時(shí)因重復(fù)搜索和頻繁轉(zhuǎn)場(chǎng)導(dǎo)致搜索代價(jià)無(wú)功消耗的不足，將模糊聚類(lèi)方法引入?yún)f(xié)同搜索策略，提出了基于模糊c均值聚類(lèi)的多無(wú)人機(jī)協(xié)同搜索策略(FCM搜索策略)。仿真結(jié)果表明，F(xiàn)CM搜索策略具有搜索效率高與穩(wěn)定性強(qiáng)的優(yōu)點(diǎn)。

1 持續(xù)監(jiān)視問(wèn)題描述

持續(xù)監(jiān)視問(wèn)題可描述為對(duì)某一群體或地點(diǎn)保持密切觀察。對(duì)敵軍進(jìn)行頻繁照相是持續(xù)監(jiān)視問(wèn)題的經(jīng)典應(yīng)用。持續(xù)監(jiān)視問(wèn)題要求對(duì)目標(biāo)空間長(zhǎng)時(shí)間頻繁甚至連續(xù)不斷的進(jìn)行觀察覆蓋，使得對(duì)目標(biāo)空間內(nèi)不同區(qū)域進(jìn)行兩次搜索的時(shí)間間隔最短。持續(xù)監(jiān)視問(wèn)題相對(duì)于其它搜索問(wèn)題，是一種更為復(fù)雜的搜索問(wèn)題。其特點(diǎn)是目標(biāo)在搜索空間出現(xiàn)的位置與時(shí)間均未知且不確定，要求對(duì)所有單元格持續(xù)均勻的進(jìn)行搜索。為研究搜索策略方便，將持續(xù)監(jiān)視問(wèn)題作如下簡(jiǎn)化:

1)將需要持續(xù)監(jiān)視的物理目標(biāo)空間定義為二維幾何空間;

2)對(duì)目標(biāo)空間用近似單元格分解方法進(jìn)行網(wǎng)格劃分;

3)為避免“漏掃”，假設(shè)每個(gè)單元格的中心與無(wú)人機(jī)傳感器的中心重合時(shí)，傳感器投影能夠覆蓋該單元格;

4)為每個(gè)單元格定義一個(gè)關(guān)聯(lián)壽命(Associated Age)，代表從上一次被搜索到目前所經(jīng)過(guò)的時(shí)間。圖1描述了三架無(wú)人機(jī)執(zhí)行持續(xù)監(jiān)視任務(wù)的示意圖。

持續(xù)監(jiān)視問(wèn)題的目標(biāo)可轉(zhuǎn)化為所有單元格的最大關(guān)聯(lián)時(shí)間最小化問(wèn)題(如式(1)所示)，即不能讓目標(biāo)空間內(nèi)留有任何一塊區(qū)域長(zhǎng)時(shí)間未被搜索。

圖1 持續(xù)監(jiān)視任務(wù)問(wèn)題描述示意圖

其中Ai為第i個(gè)單元格的關(guān)聯(lián)壽命。為了提高協(xié)同搜索策略的工程實(shí)用性，將無(wú)人機(jī)動(dòng)力學(xué)約束引入?yún)f(xié)同搜索策略，研究二者之間的耦合關(guān)系對(duì)協(xié)同搜索任務(wù)的影響。

2 FCM搜索策略

FCM搜索策略是一種基于空間縮減和空間分解的搜索策略。其基本思想是將模糊數(shù)學(xué)的方法引入多無(wú)人機(jī)協(xié)同搜索領(lǐng)域，將目標(biāo)區(qū)域的單元格以關(guān)聯(lián)壽命和空間位置為特征矢量進(jìn)行聚類(lèi)劃分，減少了無(wú)人機(jī)轉(zhuǎn)場(chǎng)次數(shù)，降低了搜索代價(jià)的無(wú)功消耗，提高了搜索性能。

2.1 FCM搜索策略描述

目前常用的搜索策略大多數(shù)為基于搜索信息的方法，無(wú)人機(jī)以單元格每個(gè)時(shí)刻的搜索信息作為搜索標(biāo)志量進(jìn)行決策。FCM搜索策略采用與文獻(xiàn)[1]相同的搜索信息——當(dāng)量時(shí)間作為搜索的標(biāo)志量。當(dāng)量時(shí)間的表達(dá)式如式(2)所示。

其中:νj表示第j個(gè)單元格的當(dāng)量時(shí)間，ω0為權(quán)重系數(shù)(在單無(wú)人機(jī)兩單元一維模型中，取 ω0=－1/Vmission)，δ1j為無(wú)人機(jī)到第j個(gè)單元格的距離。引入當(dāng)量時(shí)間后，無(wú)人機(jī)在進(jìn)行搜索決策時(shí)，首先計(jì)算每個(gè)單元格的當(dāng)量時(shí)間，然后選擇當(dāng)量時(shí)間最大的單元格作為目標(biāo)單元格進(jìn)行搜索。

FCM搜索策略是指無(wú)人機(jī)在獲取目標(biāo)區(qū)域內(nèi)單元格的關(guān)聯(lián)壽命和當(dāng)量時(shí)間信息后，通過(guò)聚類(lèi)劃分對(duì)目標(biāo)空間進(jìn)行縮減。然后將縮減后的空間進(jìn)行二次聚類(lèi)劃分，完成目標(biāo)空間的分解。將每個(gè)聚類(lèi)分配給一架無(wú)人機(jī)，每架無(wú)人機(jī)根據(jù)單元格每一時(shí)刻的當(dāng)量時(shí)間進(jìn)行搜索，從而減少轉(zhuǎn)場(chǎng)所帶來(lái)的搜索代價(jià)的無(wú)功消耗，提高搜索效率。FCM搜索策略的流程如圖 2所示。

圖2 FCM搜索策略流程圖

1)初始化:目標(biāo)空間網(wǎng)格化分解[1，5]，設(shè)置無(wú)人機(jī)數(shù)量，初始化無(wú)人機(jī)位置。

2)獲取(或更新)單元格的關(guān)聯(lián)壽命。

3)以單元格關(guān)聯(lián)壽命為特征值，對(duì)所有單元格進(jìn)行模糊c均值聚類(lèi)劃分，將所有單元格劃分為高關(guān)聯(lián)壽命單元格聚類(lèi)和低關(guān)聯(lián)壽命單元格聚類(lèi)，刪除低關(guān)聯(lián)壽命單元格聚類(lèi)，縮減搜索目標(biāo)空間。

4)以單元格的空間位置為觀測(cè)樣本的特征矢量，以無(wú)人機(jī)數(shù)量為聚類(lèi)數(shù)，對(duì)高關(guān)聯(lián)壽命聚類(lèi)的單元格進(jìn)行第二次模糊c均值聚類(lèi)劃分;根據(jù)無(wú)人機(jī)與二次聚類(lèi)劃分后的單元格聚類(lèi)中心的空間相對(duì)位置，分配一架無(wú)人機(jī)就近對(duì)某一聚類(lèi)進(jìn)行搜索。

5)無(wú)人機(jī)計(jì)算其隸屬聚類(lèi)內(nèi)所有單元格的當(dāng)量時(shí)間信息，根據(jù)基本搜索策略對(duì)其隸屬聚類(lèi)內(nèi)單元格進(jìn)行搜索。FCM搜索策略的示意圖如圖3所示。

圖3 FCM搜索策略示意圖

2.2 兩次聚類(lèi)過(guò)程

目標(biāo)空間內(nèi)單元格的狀態(tài)信息是FCM協(xié)同搜索算法進(jìn)行聚類(lèi)劃分和搜索決策的重要依據(jù)。X={x1，x2，…，xn}?Rs為目標(biāo)空間內(nèi)單元格的狀態(tài)信息集。其中 n為目標(biāo)空間內(nèi)單元格的數(shù)量，xk=(xkAge，xkx，xky)T為第k個(gè)單元格狀態(tài)信息的特征矢量。其中，xkAge為第k個(gè)單元格當(dāng)前時(shí)刻的關(guān)聯(lián)壽命，(xkx，xky)為第k個(gè)單元格中心點(diǎn)的空間位置。FCM搜索策略將分別以單元格的關(guān)聯(lián)壽命和空間位置為特征矢量，進(jìn)行兩次聚類(lèi)劃分。

2.2.1 對(duì)所有單元格進(jìn)行聚類(lèi)劃分

第一次聚類(lèi)劃分的樣本集合為所有單元格X1={x1，x2，…，xn}? Rs，其中 n 為目標(biāo)空間內(nèi)單元格的數(shù)量，特征量xk=xkAge為第k個(gè)單元格的關(guān)聯(lián)壽命。對(duì)給定樣本集合即所有單元格按照一定的準(zhǔn)則用模糊聚類(lèi)算法產(chǎn)生X1的c1劃分。其中c1=2，即劃分為高關(guān)聯(lián)壽命單元格和低關(guān)聯(lián)壽命單元格兩類(lèi)聚類(lèi)。表征聚類(lèi)性能的目標(biāo)函數(shù)為:

其中，樣本xk(第k個(gè)單元格)與第i類(lèi)聚類(lèi)中心pi之間的距離度量的一般表達(dá)式定義為:

聚類(lèi)的準(zhǔn)則為取Jm(U，P)的極小值:

求解得到使得Jm(U，P)取得極小值的μik和pi的值:

由式(6)可求得高低關(guān)聯(lián)壽命單元格的最佳模糊分類(lèi)矩陣U*和兩個(gè)聚類(lèi)中心P*。如此便可將低關(guān)聯(lián)壽命單元格從所有單元格中濾除，僅對(duì)具有高關(guān)聯(lián)壽命的單元格進(jìn)行任務(wù)分配，有助于提高搜索的針對(duì)性。

2.2.2 對(duì)高關(guān)聯(lián)壽命單元格進(jìn)行聚類(lèi)劃分

盡管第一次聚類(lèi)劃分濾除了目標(biāo)空間內(nèi)的低關(guān)聯(lián)壽命單元格，但如果將所有無(wú)人機(jī)都部署在整個(gè)縮減后的目標(biāo)空間內(nèi)執(zhí)行搜索任務(wù)，將導(dǎo)致無(wú)人機(jī)在搜索中多次途經(jīng)低關(guān)聯(lián)壽命單元格而降低搜索效率。為解決這一問(wèn)題，F(xiàn)CM搜索策略對(duì)高關(guān)聯(lián)壽命單元格按照單元格中心的空間位置進(jìn)行第二次聚類(lèi)劃分，將其劃分為與無(wú)人機(jī)數(shù)量相等的若干個(gè)聚類(lèi)，完成任務(wù)空間的分解。

第二次聚類(lèi)劃分的樣本集合為經(jīng)過(guò)第一次聚類(lèi)劃分后所得到的高關(guān)聯(lián)壽命單元格聚類(lèi)X2={xhigh1，xhigh2，…，xhighm}?Rs，其中m為當(dāng)前高關(guān)聯(lián)壽命單元格數(shù)量，聚類(lèi)特征矢量為 xhighk=(xhighk，X，xhighk，Y)T。xhighk，X，xhighk，Y分別表示第 k 個(gè)高關(guān)聯(lián)壽命單元格中心位置的X坐標(biāo)和Y坐標(biāo)。按照與第一次聚類(lèi)劃分相類(lèi)似的方法產(chǎn)生X2的c2劃分。其中c2為無(wú)人機(jī)數(shù)量。

2.3 無(wú)人機(jī)搜索任務(wù)分配

經(jīng)過(guò)兩次聚類(lèi)劃分后，得到iUAV類(lèi)(個(gè))聚類(lèi)。隨后部署離聚類(lèi)中心距離最近的無(wú)人機(jī)對(duì)隸屬于該聚類(lèi)的高關(guān)聯(lián)壽命單元格進(jìn)行搜索，即:

其中:pi為第i個(gè)聚類(lèi)的聚類(lèi)中心，pUAV，j為第j個(gè)無(wú)人機(jī)當(dāng)前的空間位置。多無(wú)人機(jī)協(xié)同搜索任務(wù)便可簡(jiǎn)化為每架無(wú)人機(jī)對(duì)隸屬于一個(gè)聚類(lèi)的若干高關(guān)聯(lián)壽命單元格單獨(dú)執(zhí)行搜索任務(wù)。

2.4 考慮動(dòng)力學(xué)約束的FCM搜索策略

為了使搜索策略更具實(shí)用性，需要在設(shè)計(jì)搜索策略時(shí)考慮無(wú)人機(jī)的動(dòng)力學(xué)(即最小轉(zhuǎn)彎半徑)約束。無(wú)人機(jī)動(dòng)力學(xué)會(huì)在以下方面對(duì)搜索策略產(chǎn)生影響:

1)無(wú)人機(jī)搜索航跡;

2)無(wú)人機(jī)與單元格的距離。

圖4 動(dòng)力學(xué)約束對(duì)無(wú)人機(jī)搜索航跡的影響示意圖

如圖4所示，在搜索航跡方面，不考慮無(wú)人機(jī)最小轉(zhuǎn)彎半徑約束的情況下，默認(rèn)無(wú)人機(jī)的可用過(guò)載無(wú)窮大，可以瞬間完成轉(zhuǎn)彎，無(wú)人機(jī)的飛行航跡是一條直線段。而考慮無(wú)人機(jī)最小轉(zhuǎn)彎半徑約束的情況下，無(wú)人機(jī)的航跡是由一條直線段和一段或兩段圓弧段組成，其中圓弧段的半徑不小于無(wú)人機(jī)的最小轉(zhuǎn)彎半徑

無(wú)人機(jī)考慮動(dòng)力學(xué)約束時(shí)的最短可行航跡可通過(guò)幾何關(guān)系建立，航跡長(zhǎng)度可以通過(guò)幾何關(guān)系解析得到。根據(jù)Dubins模型，任意具有初始航向角和目標(biāo)航向角的兩點(diǎn)間，最短軌跡由一條直線段和兩條半徑與最小轉(zhuǎn)彎半徑相等的弧線段組成。文中在Dubins模型的基礎(chǔ)上稍作簡(jiǎn)化，不設(shè)置目標(biāo)點(diǎn)的航向角要求，原因如下:

1)不設(shè)置目標(biāo)點(diǎn)的航向角，可以進(jìn)一步縮短搜索航跡的長(zhǎng)度，從而使無(wú)人機(jī)更快的飛抵目標(biāo)點(diǎn);

2)不設(shè)置目標(biāo)點(diǎn)的航向角，可以減少無(wú)人機(jī)轉(zhuǎn)彎的次數(shù)，使搜索航跡更具有可飛性。

修改后的無(wú)人機(jī)最短可飛航跡就變成由一條直線段和一條半徑與最小轉(zhuǎn)彎半徑相等的弧線段組成(如圖5所示)。

圖5 最短可飛航跡示意圖

通過(guò)上述最短可飛航跡模型得到最短可飛航跡的航跡長(zhǎng)度lmin后，搜索策略的搜索標(biāo)志量——當(dāng)量時(shí)間的表達(dá)式可修正為 νj=max{(Aj+ ω0lmin1，j)，0}。

3 數(shù)值仿真與效能分析

為了證明FCM搜索策略的高效性，與兩種基準(zhǔn)策略:貪婪搜索策略[6](Greedy Search Strategy)和多無(wú)人機(jī)反應(yīng)式搜索策略[5](Multi-agent Reactive Policy，MRP)針對(duì)持續(xù)監(jiān)視任務(wù)進(jìn)行仿真，然后根據(jù)仿真結(jié)果對(duì)各自搜索效能進(jìn)行對(duì)比分析。假設(shè)搜索目標(biāo)空間的范圍為2km×2km，無(wú)人機(jī)數(shù)量為4架，單元格邊長(zhǎng)為200m，無(wú)人機(jī)速度為Vmission=50m/s。三種多無(wú)人機(jī)搜索策略在1000s仿真時(shí)間內(nèi)的仿真搜索航跡如圖6～圖8所示，三種搜索策略暫不考慮動(dòng)力學(xué)約束。

圖6 Greedy策略4架無(wú)人機(jī)搜索航跡仿真結(jié)果

圖7 MRP策略4架無(wú)人機(jī)搜索航跡仿真結(jié)果

從上述三種搜索策略的搜索航跡圖中可以看出，兩種基準(zhǔn)搜索策略(Greedy策略和MRP策略)在搜索航跡上有明顯的重疊，并且無(wú)人機(jī)在執(zhí)行搜索任務(wù)時(shí)大范圍轉(zhuǎn)場(chǎng)，導(dǎo)致搜索性能降低。而FCM搜索策略通過(guò)對(duì)目標(biāo)區(qū)域的模糊聚類(lèi)劃分，縮減目標(biāo)區(qū)域，減少了搜索航跡的重疊以及大范圍的轉(zhuǎn)場(chǎng)，節(jié)約了搜索代價(jià)。

對(duì)比三種多無(wú)人機(jī)協(xié)同搜索策略的搜索性能。任務(wù)初始條件為:搜索目標(biāo)空間的范圍為2km×2km，單元格邊長(zhǎng)為200m，無(wú)人機(jī)速度為Vmission=50m/s，分別對(duì)無(wú)人機(jī)數(shù)量為2架、4架和6架的情況進(jìn)行測(cè)試。每種情況分別進(jìn)行50次試驗(yàn)，在1000s仿真時(shí)間內(nèi)，所有單元格的最大關(guān)聯(lián)壽命的變化情況如圖9～圖11所示。

圖8 FCM策略4架無(wú)人機(jī)搜索航跡仿真結(jié)果

圖9 2UAV三種策略最大關(guān)聯(lián)壽命仿真結(jié)果對(duì)比

如表1所示，在無(wú)人機(jī)數(shù)量相等的情況下FCM搜索策略的搜索性能優(yōu)于其它兩種基準(zhǔn)搜索策略。另外，Greedy搜索策略和MRP搜索策略在任務(wù)條件相同的情況下，隨無(wú)人機(jī)數(shù)量的增加，最大關(guān)聯(lián)壽命反而逐漸增大，F(xiàn)CM搜索策略的最大關(guān)聯(lián)壽命隨無(wú)人機(jī)數(shù)量的增加而減少。說(shuō)明這兩種基準(zhǔn)搜索策略的協(xié)同性能較差，F(xiàn)CM搜索策略的在協(xié)同性能方面優(yōu)于兩種基準(zhǔn)搜索策略。

圖10 4UAV三種策略最大關(guān)聯(lián)壽命仿真結(jié)果對(duì)比

圖11 6UAV三種策略最大關(guān)聯(lián)壽命仿真結(jié)果對(duì)比

表1 三種多無(wú)人機(jī)搜索策略在不同無(wú)人機(jī)數(shù)量情況下的最大關(guān)聯(lián)壽命

上述仿真結(jié)果表明，F(xiàn)CM搜索策略性能優(yōu)于其它兩種基準(zhǔn)搜索策略。為提高FCM搜索策略的工程實(shí)用性，將無(wú)人機(jī)動(dòng)力學(xué)約束引入FCM搜索策略。任務(wù)初始條件為:搜索目標(biāo)空間的范圍為2km×2km，單元格邊長(zhǎng)為200m，無(wú)人機(jī)速度為Vmission=50m/s，無(wú)人機(jī)數(shù)量為6架，在300s仿真時(shí)間內(nèi)，搜索航跡如圖 12所示。

圖12 引入無(wú)人機(jī)動(dòng)力學(xué)約束6架無(wú)人機(jī)FCM搜索策略航跡仿真結(jié)果

從圖12中可以看出，引入無(wú)人機(jī)動(dòng)力學(xué)約束后，無(wú)人機(jī)的搜索航跡沒(méi)有尖銳的拐點(diǎn)，所有航跡均為物理可飛航跡。所以，引入動(dòng)力學(xué)約束的FCM策略在兼顧良好搜索性能的同時(shí)，也有良好的工程實(shí)用性。

表2給出了FCM搜索策略在不同無(wú)人機(jī)最小半徑情況下的單元格最大關(guān)聯(lián)壽命。隨著無(wú)人機(jī)最小轉(zhuǎn)彎半徑的增大，單元格的最大關(guān)聯(lián)壽命也隨之增大，搜索性能下降。

表2 FCM搜索策略在不同無(wú)人機(jī)最小轉(zhuǎn)彎半徑情況下的最大關(guān)聯(lián)壽命

4 結(jié)論

文中針對(duì)持續(xù)監(jiān)視問(wèn)題，對(duì)多無(wú)人機(jī)協(xié)同搜索策略開(kāi)展研究。針對(duì)常見(jiàn)多無(wú)人機(jī)協(xié)同搜索策略的不足，將模糊數(shù)學(xué)的理論引入?yún)f(xié)同搜索領(lǐng)域，提出了基于模糊c均值聚類(lèi)的多無(wú)人機(jī)協(xié)同搜索策略，克服了常見(jiàn)多無(wú)人機(jī)協(xié)同搜索策略由于重復(fù)搜索以及頻繁轉(zhuǎn)場(chǎng)導(dǎo)致搜索代價(jià)無(wú)功消耗的不足，提高了搜索性能。將無(wú)人機(jī)動(dòng)力學(xué)約束引入?yún)f(xié)同搜索策略，使搜索策略更具實(shí)用價(jià)值。通過(guò)數(shù)值仿真與常見(jiàn)多無(wú)人機(jī)協(xié)同搜索策略的比較研究結(jié)果表明，F(xiàn)CM搜索策略具有搜索性能高與穩(wěn)定性強(qiáng)的優(yōu)點(diǎn)。

[1]Nigam N.Control and design of multiple unmanned air vehicles for persistent surveillance[D].Stanford University，2009.

[2]彭輝.分布式多無(wú)人機(jī)協(xié)同區(qū)域搜索中的關(guān)鍵問(wèn)題研究[D].長(zhǎng)沙:國(guó)防科學(xué)技術(shù)大學(xué)，2009.

[3]Phillip R，Chandler M P，Steven R，et al.Distributed control for multiple uavs with strongly coupled tasks[C]//AIAA Guidance，Navigation，And Control Conference And Exhibit，2003.

[4]Chandler P R.Cooperative control of a team of uavs for tactical missions[C]//AIAA 1st Intelligent Systems Technical Conference，2004.

[5]Baum M L，Passino K M.A search theoretic approach to cooperative control for uninhabited air vehicle[C]//AIAA Guidance，Navigation，And Control Conference And Exhibit，2002.

[6]田菁，陳巖，沈林成.不確定環(huán)境中多無(wú)人機(jī)協(xié)同搜索算法[J].電子與信息學(xué)報(bào)，2007，29(10):2325－2328.