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

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

0 引言

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

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

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

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

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

2)對目標空間用近似單元格分解方法進行網(wǎng)格劃分;

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

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

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

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

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

2 FCM搜索策略

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

2.1 FCM搜索策略描述

目前常用的搜索策略大多數(shù)為基于搜索信息的方法，無人機以單元格每個時刻的搜索信息作為搜索標志量進行決策。FCM搜索策略采用與文獻[1]相同的搜索信息——當量時間作為搜索的標志量。當量時間的表達式如式(2)所示。

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

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

圖2 FCM搜索策略流程圖

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

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

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

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

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

圖3 FCM搜索策略示意圖

2.2 兩次聚類過程

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

2.2.1 對所有單元格進行聚類劃分

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

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

聚類的準則為取Jm(U，P)的極小值:

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

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

2.2.2 對高關聯(lián)壽命單元格進行聚類劃分

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

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

2.3 無人機搜索任務分配

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

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

2.4 考慮動力學約束的FCM搜索策略

為了使搜索策略更具實用性，需要在設計搜索策略時考慮無人機的動力學(即最小轉彎半徑)約束。無人機動力學會在以下方面對搜索策略產(chǎn)生影響:

1)無人機搜索航跡;

2)無人機與單元格的距離。

圖4 動力學約束對無人機搜索航跡的影響示意圖

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

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

1)不設置目標點的航向角，可以進一步縮短搜索航跡的長度，從而使無人機更快的飛抵目標點;

2)不設置目標點的航向角，可以減少無人機轉彎的次數(shù)，使搜索航跡更具有可飛性。

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

圖5 最短可飛航跡示意圖

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

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

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

圖6 Greedy策略4架無人機搜索航跡仿真結果

圖7 MRP策略4架無人機搜索航跡仿真結果

從上述三種搜索策略的搜索航跡圖中可以看出，兩種基準搜索策略(Greedy策略和MRP策略)在搜索航跡上有明顯的重疊，并且無人機在執(zhí)行搜索任務時大范圍轉場，導致搜索性能降低。而FCM搜索策略通過對目標區(qū)域的模糊聚類劃分，縮減目標區(qū)域，減少了搜索航跡的重疊以及大范圍的轉場，節(jié)約了搜索代價。

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

圖8 FCM策略4架無人機搜索航跡仿真結果

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

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

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

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

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

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

圖12 引入無人機動力學約束6架無人機FCM搜索策略航跡仿真結果

從圖12中可以看出，引入無人機動力學約束后，無人機的搜索航跡沒有尖銳的拐點，所有航跡均為物理可飛航跡。所以，引入動力學約束的FCM策略在兼顧良好搜索性能的同時，也有良好的工程實用性。

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

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

4 結論

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

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

[2]彭輝.分布式多無人機協(xié)同區(qū)域搜索中的關鍵問題研究[D].長沙:國防科學技術大學，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)境中多無人機協(xié)同搜索算法[J].電子與信息學報，2007，29(10):2325－2328.