朱 利，符小衛(wèi)

（1.中國(guó)電子科技集團(tuán)第十研究所，成都 610036；2.西北工業(yè)大學(xué)電子信息學(xué)院，西安 710129）

1 引 言

無(wú)人機(jī)是一種由動(dòng)力驅(qū)動(dòng)，機(jī)上為無(wú)人駕駛，可以重復(fù)使用的飛行器［1］。在無(wú)人機(jī)承擔(dān)的各種作戰(zhàn)任務(wù)中，搜索和偵察是目前無(wú)人機(jī)系統(tǒng)的首要任務(wù)［2］，對(duì)任務(wù)區(qū)域執(zhí)行偵察和搜索并發(fā)現(xiàn)目標(biāo)是進(jìn)行情報(bào)搜集、目標(biāo)定位乃至打擊等一系列作戰(zhàn)活動(dòng)的前提。這種無(wú)人機(jī)通常被稱為無(wú)人偵察機(jī)，典型的包括中國(guó)的翔龍和美軍的全 球鷹。

組織多架無(wú)人機(jī)協(xié)同執(zhí)行任務(wù)是未來(lái)網(wǎng)絡(luò)化戰(zhàn)場(chǎng)上的一種重要作戰(zhàn)方式，而如何有效控制多架無(wú)人機(jī)在復(fù)雜環(huán)境中協(xié)同執(zhí)行搜索任務(wù)也逐漸成為近年來(lái)協(xié)同控制領(lǐng)域的研究熱點(diǎn)［3］。

在搜索環(huán)境信息描述與建模方面，最主要的方法是基于搜索區(qū)域網(wǎng)格化的建模，例如占用圖［4-6］、概率圖［7-9］、不確定圖［10-12］等?？偟膩?lái)說(shuō)，這類方法在本質(zhì)上都是構(gòu)造一個(gè)二維離散的網(wǎng)格地圖，該網(wǎng)格地圖可以反映無(wú)人機(jī)對(duì)當(dāng)前目標(biāo)和環(huán)境信息的認(rèn)知情況，這樣的二維離散的網(wǎng)格地圖統(tǒng)稱為環(huán)境感知地圖。隨著搜索任務(wù)的執(zhí)行，無(wú)人機(jī)對(duì)環(huán)境的不斷感知，環(huán)境感知地圖則按照合理的規(guī)則動(dòng)態(tài)更新，以便反映最新的環(huán)境和目標(biāo)信息，從而使得無(wú)人機(jī)可以有效利用實(shí)時(shí)探測(cè)信息，適用于動(dòng)態(tài)搜索過(guò)程。

在多無(wú)人機(jī)搜索決策方面，主要是區(qū)域分割方法［13-15］，這類方法主要將區(qū)域根據(jù)不同的指標(biāo)劃分給各架無(wú)人機(jī)，再由各架無(wú)人機(jī)對(duì)各自的搜索區(qū)域進(jìn)行搜索，從而達(dá)到協(xié)同搜索。滾動(dòng)時(shí)域優(yōu)化（Receding Horizon Optimization）方法［16-18］，同時(shí)考慮了無(wú)人機(jī)短期和長(zhǎng)期搜索代價(jià)，能夠從宏觀上提升無(wú)人機(jī)的搜索效率。

Voronoi圖（V圖）在搜索路徑中已經(jīng)有了廣泛的應(yīng)用，如果障礙物可以近似成質(zhì)點(diǎn)，那么機(jī)器人沿著障礙物的V圖的邊行走是最安全的。如果障礙物不能用質(zhì)點(diǎn)來(lái)近似，那么就該應(yīng)用擴(kuò)展的 V圖（站點(diǎn)為線段、多邊形或多面體等）。同時(shí)，考慮V圖本身的特殊性，黃長(zhǎng)強(qiáng)等［19］提出基于質(zhì)心V圖劃分的無(wú)人機(jī)搜索決策方法對(duì)多架無(wú)人機(jī)進(jìn)行搜索空間的分配，建立了質(zhì)心V圖的數(shù)學(xué)模型，并在此基礎(chǔ)上提出了基于質(zhì)心V圖的目標(biāo)分配算法，結(jié)果表明提出的搜索策略能夠有效進(jìn)行隨機(jī)目標(biāo)搜索且算法具有良好的自適應(yīng)能力。

總的來(lái)說(shuō)，國(guó)內(nèi)外學(xué)者在多無(wú)人機(jī)協(xié)同搜索、傳感器信息感知、V圖路徑規(guī)劃方面已經(jīng)做了大量的研究工作，并且取得了豐富的研究成果，為接下來(lái)的研究奠定了堅(jiān)實(shí)的基礎(chǔ)。由于問(wèn)題的復(fù)雜性，目前還存在一些問(wèn)題有待進(jìn)一步研究，主要表現(xiàn)為以下幾個(gè)方面：對(duì)多機(jī)協(xié)同的控制；對(duì)傳感器進(jìn)行更符合現(xiàn)實(shí)規(guī)律的建模；對(duì)V圖動(dòng)態(tài)劃分的研究。

針對(duì)上述問(wèn)題，本文將V 圖引入多機(jī)協(xié)同搜索中來(lái)。首先，針對(duì)多機(jī)協(xié)同搜索問(wèn)題，以最短時(shí)間內(nèi)降低環(huán)境不確定度為目標(biāo)，結(jié)合環(huán)境建模，根據(jù)各架無(wú)人機(jī)位置將環(huán)境進(jìn)行V圖劃分，各架無(wú)人機(jī)在自身所在的V圖區(qū)域內(nèi)進(jìn)行搜索，隨著搜索的不斷進(jìn)行，各自V圖區(qū)域內(nèi)的環(huán)境不確定度不斷降低。且通過(guò)無(wú)人機(jī)之間的通信，各無(wú)人機(jī)能夠掌握當(dāng)前整個(gè)環(huán)境的不確定度，從而根據(jù)當(dāng)前環(huán)境信息的重新規(guī)劃路徑。針對(duì)單無(wú)人機(jī)在V圖區(qū)域內(nèi)如何運(yùn)動(dòng)的問(wèn)題，將環(huán)境不確定度作為網(wǎng)格質(zhì)量求解各V圖區(qū)域的質(zhì)心，并證明得到無(wú)人機(jī)在各自的V圖質(zhì)心處搜索時(shí)，環(huán)境不確定度降低最大，同進(jìn)提出了Discrete Combined Partition and Search（DCPS）策略，并考慮在傳感器半徑約束下搜索策略的有效性。該策略下，每搜索一次都會(huì)進(jìn)行一次V圖劃分，所有無(wú)人機(jī)在每個(gè)時(shí)刻都處于搜索狀態(tài)，保證了所有無(wú)人機(jī)的充分利用。因此，DCPS算法能夠在保證協(xié)同的基礎(chǔ)上同時(shí)保證搜索的有效性。

2 問(wèn)題描述

如圖1所示，假設(shè)n架無(wú)人機(jī)在未知環(huán)境E= {(i,j)|i= 1,2,...,L x,j= 1,2,...,Ly}中搜索，為降低整個(gè)環(huán)境的不確定度，問(wèn)題可以描述為：

（1）E= { (i,j)|i=1 ,2,...,L x,j= 1,2,...,Ly}為一個(gè)矩形待搜索區(qū)域；

（2）φ(i,j) → [0,1]表示網(wǎng)格(i,j)處的不確定度；

（3）n架無(wú)人機(jī)，配備了相同的傳感器和通訊設(shè)備，n架無(wú)人機(jī)在區(qū)域E中搜索，收集信息，從而降低環(huán)境的不確定度；

（4）P(t) ={p1(t),p2(t),...p N(t)}表示無(wú)人機(jī)t時(shí)刻在搜索區(qū)域E中的位置。pi(t)表示第i架無(wú)人機(jī)在t時(shí)刻的位置，為了方便起見(jiàn)，在后文中我們直接使用pi表示pi(t)；

（5）傳感器對(duì)位置(i,j)的搜索效率隨傳感器到(i,j)的距離變大而降低；

（6）在理想情況下，我們可以尋找一種利用無(wú)人機(jī)獲取關(guān)于搜索區(qū)域E的完整信息的最佳方法，從而達(dá)到φ(i,j) = 0, ?(i,j)∈E.

圖1 多無(wú)人機(jī)協(xié)同區(qū)域搜索Fig.1 Illustration of mutiple UAVs cooperative area search

3 協(xié)同區(qū)域搜索建模

3.1 無(wú)人機(jī)平臺(tái)模型

假設(shè)無(wú)人機(jī)i在時(shí)刻k的狀態(tài)為statei(k)，statei(k)由以下三個(gè)方面構(gòu)成：

其 中λi(k) = (xi(k),y i(k)) ∈ {1,2,...,Lx} × {1,2,...,Ly} 表示第i架無(wú)人機(jī)在k時(shí)刻的位置；οi(k) ∈{0,1,2,...,7}表示第i架無(wú)人機(jī)在k時(shí)刻的方位且分別定義為｛0（東），1（東北），2（北），3（西北），4（西），5（西南），6（南），7（東南）｝；δi(k) ∈ {0,1}表示在k時(shí)刻第i架無(wú)人機(jī)是否已經(jīng)被摧毀，或者是由于故障不能執(zhí)行搜索任務(wù)，δi(k) = 0表示無(wú)人機(jī)由于被摧毀或者是故障不能正常執(zhí)行搜索任務(wù)，δi(k) = 1表示無(wú)人機(jī)狀態(tài)良好，可正常執(zhí)行搜索任務(wù)。

由于無(wú)人機(jī)的動(dòng)力學(xué)模型服從轉(zhuǎn)彎半徑的限制，假設(shè)無(wú)人機(jī)的最大轉(zhuǎn)彎角度為 4 5ο，在這種轉(zhuǎn)彎半徑的限制下，各架無(wú)人機(jī)在下一個(gè)時(shí)間步長(zhǎng)內(nèi)有三種可選位置，分別為左轉(zhuǎn)、直行和右轉(zhuǎn)，可以表示為{l(left),f(front),r(right)}，無(wú)人機(jī)當(dāng)前航向與下一時(shí)間步長(zhǎng)內(nèi)可選航向關(guān)系如圖2所示。

圖2 無(wú)人機(jī)當(dāng)前航向與下一時(shí)間步長(zhǎng)內(nèi)可選航向Fig.2 Current heading and next step heading of an UAV

3.2 戰(zhàn)場(chǎng)環(huán)境建模

在多無(wú)人機(jī)協(xié)同搜索過(guò)程中，由于環(huán)境是動(dòng)態(tài)變化的，因此建立良好的環(huán)境模型至關(guān)重要，需要其能夠基于多個(gè)傳感器信息和多架不同無(wú)人機(jī)進(jìn)行構(gòu)建和更新，環(huán)境模型的有效性將最終影響無(wú)人機(jī)的決策行為。基于上述討論，本文采用環(huán)境不確定度模型來(lái)描述任務(wù)區(qū)域各個(gè)單元格。首先將搜索區(qū)域劃分為L(zhǎng)x×Ly的離散單元，并且稱所有矩形單元的集合E= {(i,j)|i= 1,2,...,L x,j=1,2,...,Ly}為搜索環(huán)境，(i,j)表示位于第i行第j列的單元，如圖3所示。

圖3 搜索環(huán)境柵格化Fig3 Discreted search area

假設(shè)有n架完全相同的無(wú)人機(jī)在區(qū)域內(nèi)執(zhí)行搜索任務(wù)，無(wú)人機(jī)使用傳感器感知環(huán)境，收集環(huán)境中的信息和定位目標(biāo)。假設(shè)無(wú)人機(jī)之間有一定的通信能力，能保證無(wú)人機(jī)之間信息交換的正確性，在該模型中，無(wú)人機(jī)使用地圖存儲(chǔ)環(huán)境中每個(gè)單元的狀態(tài)信息，將每架無(wú)人機(jī)視為一個(gè)質(zhì)點(diǎn)，在每一個(gè)步長(zhǎng)都可以滿足無(wú)人機(jī)操縱限制的前提下，從一個(gè)單元 (x1,y1)的中心點(diǎn)移動(dòng)到與之相鄰的單元 (x2,y2)的中心點(diǎn)，并在此處執(zhí)行搜索任務(wù)。

每一個(gè)單元(i,j)都有一個(gè)屬性值φ表示此單元的不確定度，也就是無(wú)人機(jī)對(duì)該網(wǎng)格的確定程度，φ(i,j)是指某單元(i,j)的不確定度，φ(i,j) = 1表示無(wú)人機(jī)對(duì)該處的環(huán)境信息一無(wú)所知，φ(i,j) = 0則表示無(wú)人機(jī)完全了解該處的環(huán)境信息，地圖中全部單元的φ值的集合為Φ。由于受到通信距離和通信角度的約束，導(dǎo)致各無(wú)人機(jī)之間不能實(shí)時(shí)交換不確定地圖信息，因此對(duì)于不同的無(wú)人機(jī)來(lái)說(shuō)，不確定地圖是不同的。

因此第i架無(wú)人機(jī)k時(shí)刻的不確定地圖為：

3.3 傳感器模型

用函數(shù)f表示傳感器搜索效率：

其中，r為待搜索位置到傳感器的距離，當(dāng) 0r=時(shí)，f最大，r→∞時(shí)，f最小且趨近于零。k和α為兩個(gè)可調(diào)參數(shù)，可以為多種傳感器建模。在k= 0.8,α= 0.1時(shí)，傳感器的探測(cè)效率如圖4所示。

圖4 傳感器效率更新曲線Fig.4 Sensor detection efficiency

本文將傳感器探測(cè)半徑進(jìn)行離散處理，假設(shè)在某個(gè)區(qū)域內(nèi)的傳感器探測(cè)效率是相同的，在k= 0.8,α= 0.1時(shí)，傳感器的探測(cè)效率如圖5所示。

圖5 離散傳感器效率更新曲線Fig.5 Discreted sensor detection efficiency

柵格化地圖后傳感器的探測(cè)效率如圖6所示，搜索區(qū)域距離無(wú)人機(jī)位置可被離散為r=1,2,…,n，假設(shè)無(wú)人機(jī)位于O處，顏色相同的區(qū)域表示無(wú)人機(jī)的探測(cè)效率是相同的。

如圖6所示，灰白色區(qū)域表示傳感器探測(cè)半徑為1的所有網(wǎng)格區(qū)域，紅色區(qū)域表示傳感器探測(cè)半徑為2的所有網(wǎng)格區(qū)域，藍(lán)色區(qū)域表示傳感器探測(cè)半徑為3的所有網(wǎng)格區(qū)域。也就是說(shuō)無(wú)人機(jī)對(duì)灰白色區(qū)域的探測(cè)效率為f(1)=ke-a·12，無(wú)人機(jī)對(duì)紅色區(qū)域的探測(cè)效率為f(2)=ke-a·22，無(wú)人機(jī)對(duì)藍(lán)色區(qū)域的探測(cè)效率為f(3)=ke-a·32。假設(shè)網(wǎng)格(i, j) 在圖6中紅色區(qū)域，當(dāng)前網(wǎng)格的不確定度為 φ(i,j) ，經(jīng)過(guò)傳感器探測(cè)之后，當(dāng)前網(wǎng)格的不確定度變?yōu)?/p>

圖6 傳感器探測(cè)半徑模型Fig.6 Sensor detection radius model

3.4 搜索效能評(píng)估指標(biāo)

多無(wú)人機(jī)協(xié)同區(qū)域搜索的主要目標(biāo)為在保證各架無(wú)人機(jī)飛行安全的前提下，以最短的時(shí)間降低整個(gè)區(qū)域的平均不確定度，在本文中我們采用相同時(shí)間步長(zhǎng)下整個(gè)區(qū)域平均不確定度作為無(wú)人機(jī)系統(tǒng)協(xié)同搜索的評(píng)價(jià)指標(biāo)。

整個(gè)區(qū)域的平均不確定度可以表示為：

當(dāng)無(wú)人機(jī)每步搜索都能最大的降低整個(gè)區(qū)域的不確定度，那么區(qū)域的平均不確定度當(dāng)然也是最低的，因此評(píng)價(jià)指標(biāo)可以變?yōu)閰^(qū)域不確定度降低程度。

無(wú)人機(jī)每步搜索的不確定度降低的最大值如式（5）表示：

因此本文需要研究無(wú)人機(jī)如何運(yùn)動(dòng)從而使其每步運(yùn)動(dòng)都能最大限度的降低整個(gè)區(qū)域的不確定度。

4 基于V圖質(zhì)心的區(qū)域搜索策略

針對(duì)多無(wú)人機(jī)協(xié)同區(qū)域搜索的主要目標(biāo)，根據(jù)各架無(wú)人機(jī)當(dāng)前位置對(duì)搜索區(qū)域進(jìn)行V圖劃分。在對(duì)環(huán)境建模時(shí)將搜索區(qū)域劃分為 Lx× Ly的離散網(wǎng)格，每個(gè)網(wǎng)格(i, j) 都有一個(gè)屬性值 φ(i,j) 代表該網(wǎng)格的不確定度，將當(dāng)前環(huán)境不確定度作為網(wǎng)格質(zhì)量求解各無(wú)人機(jī)V圖的質(zhì)心。將V圖質(zhì)心用于引導(dǎo)無(wú)人機(jī)運(yùn)動(dòng)。在文獻(xiàn)［20］搜索策略的基礎(chǔ)上，考慮無(wú)人機(jī)的運(yùn)動(dòng)特性，將環(huán)境地圖、無(wú)人機(jī)運(yùn)動(dòng)、傳感器探測(cè)半徑都進(jìn)行了離散處理，提出DCPS策略。該策略下，能夠根據(jù)無(wú)人機(jī)當(dāng)前位置重新劃分V圖區(qū)域，通過(guò)當(dāng)前的環(huán)境不確定度重新求解質(zhì)心，保證了無(wú)人機(jī)的搜索效率。但在DCPS策略下，每個(gè)搜索時(shí)間步長(zhǎng)都會(huì)重新劃分V圖區(qū)域，當(dāng)無(wú)人機(jī)數(shù)量太多時(shí)，V圖劃分的計(jì)算量會(huì)變大，因此，當(dāng)無(wú)人機(jī)數(shù)量很大時(shí)，DCPS策略將不再適用，本文考慮無(wú)人機(jī)數(shù)量較少（10 個(gè)以內(nèi)）的情況，搜索策略計(jì)算量不大，可以保證在線實(shí)現(xiàn)，因此本節(jié)在計(jì)算量上不做過(guò)多研究，將研究重點(diǎn)放在無(wú)人機(jī)的搜索效率上。

4.1 柵格化的V圖質(zhì)心求解

將區(qū)域柵格化后再根據(jù)生成元位置進(jìn)行V圖劃分可以得到柵格化的V圖劃分［21］，如圖7所示。

圖7 柵格化V圖劃分Fig.7 Discreted Voronoi Diagram

圖7中，p1, p2,p3為柵形區(qū)域中的三個(gè)點(diǎn)，紅色折線以及邊界將柵形區(qū)域劃分為三個(gè)Voronoi區(qū)域，Voronoi邊由各個(gè)小網(wǎng)格的邊構(gòu)成。假設(shè)pi點(diǎn)的V圖區(qū)域內(nèi)有n個(gè)網(wǎng)格，且其網(wǎng)格中心的坐標(biāo)分別為 (x1,y1),(x2,y2),...,(xn,yn)，本文用網(wǎng)格不確定度表示網(wǎng)格的質(zhì)量，設(shè)各個(gè)網(wǎng)格的質(zhì)量分別為m1,m2,...,mn。 假設(shè)質(zhì)心的坐標(biāo)為，那么質(zhì)心公式為：

特殊情況下，當(dāng)各個(gè)網(wǎng)格質(zhì)量相同時(shí)，質(zhì) 心為：

4.2 目標(biāo)函數(shù)

為了尋找一種無(wú)人機(jī)在區(qū)域E的最優(yōu)搜索位置使得每次搜索都能最大化的降低整個(gè)區(qū)域的不確定度。建立目標(biāo)函數(shù)描述如下：

式（8）為區(qū)域離散化下的目標(biāo)函數(shù)，n表示第n次搜索，φn(i,j)表示第n次搜索時(shí)網(wǎng)格(i,j)處的不確定度，φn(i,j)表示在第n步搜索中，網(wǎng)格(i,j)處不確定度的降低值，φn(i,j)表示無(wú)人機(jī)m的V圖區(qū)域，表示第n架無(wú)人機(jī)的位置，||pm- (i,j)||表示無(wú)人機(jī)位置到網(wǎng)格(i,j)的歐式距離。

4.3 最優(yōu)解

為了求得目標(biāo)函數(shù)的最優(yōu)解，我們先討論未進(jìn)行區(qū)域柵格化的情況。

將目標(biāo)函數(shù)采取下面形式：

式（9）中m∈{1,2,...,N}表示第m架無(wú)人機(jī)，Q表示未柵格化之前的整個(gè)搜索區(qū)域，q∈Q表示區(qū)域中的任意一點(diǎn)，φn(q)表示q處的環(huán)境不確定度，式（9）關(guān)于mp的梯度可以表示為：

式（10）中，MVm和CVm分別代表V m的質(zhì)量和質(zhì)心，表示傳感器探測(cè)后的不確定度降低大小。因此，最優(yōu)性的必要條件是：

根據(jù)式（11）可以看出，在未柵格化的情況下，能夠?qū)φ麄€(gè)環(huán)境區(qū)域進(jìn)行效率最高的搜索位置是每個(gè)V圖的質(zhì)心處，因此，在柵格化以后，同樣是質(zhì)心處能夠最大的降低區(qū)域的不確定度。

4.4 搜索代價(jià)函數(shù)

無(wú)人機(jī)在向質(zhì)心運(yùn)動(dòng)的過(guò)程中，每架無(wú)人機(jī)需要滿足以下準(zhǔn)則：

（1）考慮到任務(wù)的完成效率，無(wú)人機(jī)將飛向距離質(zhì)心最近的地方；

（2）考慮到無(wú)人機(jī)的過(guò)載限制以及燃油經(jīng)濟(jì)性，無(wú)人機(jī)有沿當(dāng)前航向直飛的趨勢(shì)；

（3）考慮到無(wú)人機(jī)的作用區(qū)域，無(wú)人機(jī)的下一步航路點(diǎn)需在自身V圖區(qū)域內(nèi)。

基于以上的分析，可以建立無(wú)人機(jī)運(yùn)動(dòng)到質(zhì)心的過(guò)程中各個(gè)飛行點(diǎn)的代價(jià)函數(shù)公式：

式（12）中，cost k(i,j)表示無(wú)人機(jī)k飛向(i,j)的代價(jià)；q k(i,j)表示無(wú)人機(jī)的可行性，如果(i,j) ∈Vk，那么q k(i,j) =1，反之，如果航向變化以及距離的權(quán)重值且w1+w2= 1；Δφ(i,j)表示無(wú)人機(jī)從當(dāng)前位置運(yùn)動(dòng)到(i,j)時(shí)所(i,j) ?Vk，那么q k(i,j)=∞；w1,w2分別表示需要轉(zhuǎn)過(guò)的角度，該值越大則表示飛向(i,j)所需的過(guò)載也就越大；Dk(i,j))表示(i,j)到質(zhì)心的距離，無(wú)人機(jī)飛向距離質(zhì)心更近的位置。

無(wú)人機(jī)在執(zhí)行搜索任務(wù)的過(guò)程中，通過(guò)上述代價(jià)函數(shù)，運(yùn)動(dòng)到各自的質(zhì)心位置執(zhí)行搜索，能夠最大的降低環(huán)境的不確定度。

4.5 不確定度更新

無(wú)人機(jī)對(duì)環(huán)境信息的獲取主要包括三個(gè)方面：初始先驗(yàn)信息、探測(cè)信息和通信信息。

（1）初始先驗(yàn)信息

初始先驗(yàn)信息每架無(wú)人機(jī)都是相同的，對(duì)環(huán)境的掌握程度都為零，環(huán)境的不確定度都為1。

（2）探測(cè)信息

探測(cè)信息是無(wú)人機(jī)通過(guò)傳感器的探測(cè)對(duì)環(huán)境信息有了一定了解。

通過(guò)對(duì)傳感器的建模分析，我們知道探測(cè)效率為f(r) =ke-αr2,k∈ (0 , 1 ) andα＞0，也就是說(shuō)，假設(shè)網(wǎng)格區(qū)域(i,j)時(shí)刻k不確定度為φk(i,j)，那么經(jīng)過(guò)一次傳感器的搜索以后，該網(wǎng)格區(qū)域環(huán)境不確定度降低了：

k+ 1時(shí)刻網(wǎng)格(i,j)的不確定度為：

假設(shè)：

在沒(méi)有傳感器半徑約束的情況下，無(wú)人機(jī)能探測(cè)整個(gè)搜索區(qū)域，由于是多機(jī)協(xié)同搜索，在同一位置有多架無(wú)人機(jī)搜索，但由于傳感器探測(cè)效率隨距離增加而降低，因此，僅考慮對(duì)該位置探測(cè)效率最高的無(wú)人機(jī)。

在搜索過(guò)程中，傳感器在執(zhí)行完第 1k+ 次搜索步驟后，環(huán)境的不確定度可以表示為：

其中，φk(q)表示在第k次搜索時(shí)環(huán)境的不確定度。pm表示第m架無(wú)人機(jī)的位置。表示對(duì)網(wǎng)格(, )i j搜索效率最高的傳感器對(duì)網(wǎng)格不確定度的影響。

由于V圖本身是一個(gè)根據(jù)距離劃分的區(qū)域，也就是說(shuō)，各無(wú)人機(jī)只搜索其V圖范圍內(nèi)的區(qū)域。圖8中，P1，P2，P3，P4，P5表示五架無(wú)人機(jī)，劃分的V圖區(qū)域表示各無(wú)人機(jī)傳感器的有效探測(cè)范圍。

如果任意無(wú)人機(jī)在其自身Voronoi單元內(nèi)搜索，根據(jù)V圖的勢(shì)力范圍特性，環(huán)境不確定度更新可由式（17）表示。

圖8 無(wú)人機(jī)傳感器探測(cè)距離Fig.8 The detection ranges of UAVs sensors

（3）通信信息

無(wú)人機(jī)傳感器在探測(cè)過(guò)程中只降低自身V圖區(qū)域內(nèi)的環(huán)境不確定度，各無(wú)人機(jī)之間的通信使得無(wú)人機(jī)能掌握自身V圖以外區(qū)域的環(huán)境信息。如圖9所示，陰影部分表示無(wú)人機(jī)1掌握的區(qū)域信息，假設(shè)無(wú)人機(jī)2在無(wú)人機(jī)1通信半徑內(nèi)，也就是無(wú)人機(jī)1與無(wú)人機(jī)2之間能夠進(jìn)行通信，那么這兩架無(wú)人機(jī)能夠同時(shí)掌握各自所在的V圖區(qū)域內(nèi)的不確定度。

圖9 兩架無(wú)人機(jī)通過(guò)通信更新不確定度Fig.9 Two UAVs update uncertainty by communication

因此，如果各架無(wú)人機(jī)之間不存在通信約束，即無(wú)人機(jī)能跟所有的無(wú)人機(jī)進(jìn)行通信，那么無(wú)人機(jī)則能夠掌握整個(gè)環(huán)境區(qū)域的不確定度信息。

4.6 傳感器半徑約束

在實(shí)際中，傳感器不可能有無(wú)限的探測(cè)范圍，假設(shè)傳感器存在探測(cè)半徑約束R，對(duì)距離大于R網(wǎng)格區(qū)域，傳感器對(duì)其沒(méi)有探測(cè)能力。如式（18）所示。

考慮下面的目標(biāo)函數(shù)：

根據(jù)得到的目標(biāo)函數(shù)的梯度由式（10）表示：

其中，質(zhì)量和質(zhì)心是根據(jù)區(qū)域計(jì)算得到的，這種情況下的極值點(diǎn)為：

圖10 傳感器探測(cè)半徑約束下的無(wú)人機(jī)搜索范圍Fig.10 The UAV search range under the constraint of sensor's detection radius

傳感器半徑約束下的DCPS策略流程圖如圖11所示。

圖11 基于DCPS策略的無(wú)人機(jī)協(xié)同區(qū)域搜索流程圖Fig.11 The flowchart of multiple UAVs cooperative area search based on DCPS

定理本文提出的DCPS策略可以將平均不確定性降低為任意小值。

證明：首先看任意點(diǎn)(, )i j E∈ 的不確定度更新函數(shù)：

式（22）中，rm表示點(diǎn)(i,j)∈E到無(wú)人機(jī)m的距離，(i,j) ∈Vm對(duì)應(yīng)于無(wú)人機(jī)m的Voronoi分區(qū)，遞歸地應(yīng)用上述更新規(guī)則，可以得到：

（1）0 1k≤ ＜ ；

（2）0 ≤ri≤D(Q)，且由于集合E有界，D(E)也是有界的。

（3）0 ≤γj≤ 1-ke-α{D(E)2}=l,j∈Nandl＜1 。

考慮序列：

且：

當(dāng)取n→∞時(shí)：

因此：

取極限時(shí)，每一點(diǎn)(, )i j E∈ 的不確定度φ都會(huì)趨于零，因此當(dāng)n→∞時(shí)，E的平均不確定度也會(huì)趨于零。

5 多無(wú)人機(jī)協(xié)同搜索仿真

5.1 仿真參數(shù)設(shè)置

仿真設(shè)定了一塊40×40的矩形網(wǎng)格區(qū)域作為多無(wú)人機(jī)協(xié)同的任務(wù)區(qū)域，小網(wǎng)格長(zhǎng)度為1。設(shè)定了五架攜帶不同傳感器的無(wú)人機(jī)對(duì)該區(qū)域進(jìn)行搜索。無(wú)人機(jī)的狀態(tài)主要包括：無(wú)人機(jī)位置信息（x坐標(biāo)，y坐標(biāo)）、無(wú)人機(jī)方位信息{0,1,2,3,4,5,6,7,,8}、無(wú)人機(jī)狀態(tài)信息（1表示無(wú)人機(jī)狀態(tài)良好可以正常工作，0表示無(wú)人機(jī)損毀不能正常工作）以及所攜帶的傳感器探測(cè)半徑。五架無(wú)人機(jī)在地圖中的位置分布如表1所示：

表1 無(wú)人機(jī)初始狀態(tài)Table1 The initial states of UAVs

設(shè)無(wú)人機(jī)搜索之前區(qū)域的初始不確定度都為1，如圖12所示：

圖12 區(qū)域不確定度初始狀態(tài)圖Fig.12 The initial area uncertainty

隨著無(wú)人機(jī)對(duì)區(qū)域不斷搜索，區(qū)域的不確定度不斷降低，無(wú)人機(jī)搜索某個(gè)網(wǎng)格區(qū)域時(shí)，將該網(wǎng)格的不確定度根據(jù)離散傳感器模型進(jìn)行降低。設(shè)傳感器模型為通過(guò)對(duì)k,i的確定，也就確定了傳感器的探測(cè)效能。

5.2 DCPS策略仿真

圖13 表示區(qū)域平均不確定度隨搜索時(shí)間步長(zhǎng)降低的變化曲線，隨著無(wú)人機(jī)對(duì)區(qū)域的搜索，區(qū)域不確定度逐漸降低最后趨近于0.05。區(qū)域的最終不確定度如圖14所示。

圖13 區(qū)域不確定度隨時(shí)間步長(zhǎng)變化Fig.13 The reduction of area uncertainty

圖14 區(qū)域最終不確定度Fig.14 The final area uncertainty

圖15 為五架無(wú)人機(jī)在沒(méi)有傳感器半徑約束的情況下，搜索步長(zhǎng)分別為35、70、100時(shí)DCPS策略的搜索航跡圖，和根據(jù)當(dāng)前時(shí)刻無(wú)人機(jī)位置劃分的V圖。圖中紅色三角形代表當(dāng)前時(shí)刻無(wú)人機(jī)的位置，顏色相同的區(qū)域表示同一架無(wú)人機(jī)相對(duì)應(yīng)的V圖區(qū)域。

5.3 無(wú)人機(jī)新增或毀損對(duì)搜索效率的影響

在沒(méi)有傳感器半徑約束的情況下，假設(shè)在運(yùn)行第50 步時(shí)出現(xiàn)無(wú)人機(jī)毀損和無(wú)人機(jī)新增，圖16 分別表示出現(xiàn)毀損和新增時(shí)刻的V 圖重劃分，以及將不確定度降低到0.05 以下的整個(gè)搜索 航跡。

圖15 無(wú)人機(jī)搜索航跡圖Fig.15 The search trajectories of UAVs

圖16（a）中，紅色三角形表示當(dāng)前時(shí)刻無(wú)人機(jī)位置。黑色虛線表示在前50 步無(wú)人機(jī)5 的搜索路徑，在第50 步時(shí)，無(wú)人機(jī)5 毀損，不再工作，只剩下四架無(wú)人機(jī)繼續(xù)搜索直到不確定度降低到0.05以下。圖16（b）中，黑色虛線表示在第50步時(shí)，新增的無(wú)人機(jī)6 的搜索路徑，在前50 步，只有五架無(wú)人機(jī)在區(qū)域內(nèi)搜索，50 步時(shí)，新增無(wú)人機(jī)6加入與各架無(wú)人機(jī)一起協(xié)同搜索，直到區(qū)域不確定度降低到0.05以下。

圖16 無(wú)人機(jī)毀損和新增瞬間的V圖重劃分Fig.16 Voronoi diagrams reconstruction

5.4 傳感器探測(cè)半徑約束對(duì)搜索效率的影響

根據(jù)本文所給出的傳感器探測(cè)模型可得，在半徑大于6 時(shí)，傳感器的探測(cè)效率已經(jīng)非常低了，所以我們這里給出傳感器半徑小于6 時(shí)對(duì)搜索策略的影響，并且對(duì)比無(wú)人機(jī)數(shù)量分別為5 和10 時(shí)傳感器半徑對(duì)搜索效率的影響程度，如圖17 所示。

圖17 將區(qū)域不確定度降低到0.05以下所需時(shí)間步長(zhǎng)與傳感器探測(cè)半徑關(guān)系曲線Fig.17 The relation between the time step and the sensor detection radius when area uncertainty is 0.05

由圖17 可以看出，不管是無(wú)人機(jī)數(shù)量為5 還是10，隨著傳感器探測(cè)半徑的增大，探測(cè)整個(gè)區(qū)域所需要的時(shí)間都是逐漸減少的，且在傳感器探測(cè)半徑為1時(shí)，無(wú)人機(jī)數(shù)量的增加能夠很明顯的降低搜索該區(qū)域的時(shí)間，但是隨著傳感器半徑的逐漸增加，無(wú)人機(jī)數(shù)量對(duì)于該區(qū)域的搜索已經(jīng)沒(méi)有那么明顯的優(yōu)勢(shì)，一方面由于搜索區(qū)域是固定的，無(wú)人機(jī)數(shù)量太多反而會(huì)導(dǎo)致重復(fù)性的搜索，另一方面，在無(wú)人機(jī)數(shù)量較少而傳感器的探測(cè)范圍又相對(duì)較大時(shí)就已經(jīng)能夠滿足搜索效率了。

根據(jù)圖17 可以看出，在傳感器半徑為1 時(shí)，要將區(qū)域不確定度降低到0.05 以下，五架無(wú)人機(jī)需要搜索的時(shí)間步長(zhǎng)為310 步左右。圖18 為傳感器探測(cè)半徑為1時(shí)五架無(wú)人機(jī)搜索310步的路徑圖以及最后的V圖劃分，紅色三角形表示當(dāng)前時(shí)刻無(wú)人機(jī)位置。

圖18 傳感器半徑為1時(shí)五架無(wú)人機(jī)的搜索航跡圖Fig.18 The search trajectories when sensors radius is 1

5.5 DCPS策略與貪婪搜索、隨機(jī)搜索策略對(duì)比

接下來(lái)，我們比較DCPS策略與貪婪搜索、隨機(jī)搜索的性能。貪婪搜索和隨機(jī)搜索是適用于任何情況下的搜索策略。

（1）貪婪搜索

貪婪搜索與DCPS的主要區(qū)別在于：在控制無(wú)人機(jī)運(yùn)動(dòng)時(shí)，DCPS 策略中，第m架無(wú)人機(jī)向的質(zhì)心運(yùn)動(dòng)，在進(jìn)行Voronoi分區(qū)的過(guò)程中，考慮了相鄰無(wú)人機(jī)之間的協(xié)同。在貪婪搜索中，只讓第m架無(wú)人機(jī)向著的質(zhì)心運(yùn)動(dòng)。

不確定度更新規(guī)則采用如下形式：

（2）隨機(jī)搜索

隨機(jī)搜索（RS）是最簡(jiǎn)單的搜索策略。假設(shè)無(wú)人機(jī)以恒定的速度移動(dòng)，無(wú)人機(jī)的方向是隨機(jī)產(chǎn)生的。

和DCPS策略一樣，VGS策略和RS策略無(wú)人機(jī)在每個(gè)時(shí)間步長(zhǎng)都執(zhí)行搜索操作，仿真設(shè)定五架無(wú)人機(jī)協(xié)同搜索，傳感器探測(cè)半徑 6R= 搜索過(guò)程中，沒(méi)有出現(xiàn)新增或者毀損。各搜索算法對(duì)整個(gè)區(qū)域不確定度的降低效率隨著時(shí)間步長(zhǎng)的變化關(guān)系如圖19所示。

圖19 算法效果對(duì)比圖Fig.19 The uncertainty comparison of different search strategies

可以看出，DCPS降低整個(gè)區(qū)域不確定度所需時(shí)間最短，值得注意的是，盡管所有這些策略在每個(gè)時(shí)間步中都執(zhí)行搜索任務(wù)，但是由于各架無(wú)人機(jī)之間通過(guò)Voronoi分區(qū)進(jìn)行協(xié)作，DCPS具有更好的搜索空間覆蓋率，因此性能更好。在大多數(shù)情況下，對(duì)于相同數(shù)量的搜索，DCPS比其他策略（如VGS和RS）能更快降低區(qū)域平均不確定度。

6 結(jié) 論

為了盡快降低不確定區(qū)域的環(huán)境不確定度，提出了一種基于V圖質(zhì)心的多無(wú)人機(jī)協(xié)同區(qū)域搜索算法，得到如下結(jié)論：

（1）本文提出的DCPS策略相對(duì)于隨機(jī)搜索和貪婪搜索能更快的將環(huán)境不確定度降低到指定范圍以下；且具有良好的魯棒性，能夠應(yīng)對(duì)無(wú)人機(jī)的突發(fā)情況，包括無(wú)人機(jī)的新增和毀損；

（2）在傳感器半徑的約束下，隨著傳感器探測(cè)半徑不斷減少，對(duì)整個(gè)區(qū)域的搜索時(shí)間會(huì)不斷增加，無(wú)人機(jī)的搜索路徑也就越密集，且在固定的搜索區(qū)域內(nèi)，無(wú)人機(jī)的增多會(huì)在一定程度上減少搜索時(shí)間，但由于區(qū)域是固定的，無(wú)人機(jī)數(shù)量太多反而會(huì)導(dǎo)致重復(fù)性的搜索，影響搜索效率。

本文在多機(jī)協(xié)同搜索過(guò)程中，沒(méi)有考慮各架無(wú)人機(jī)之間的通信約束，區(qū)域搜索指標(biāo)僅限于不確定度的降低，還需要進(jìn)一步考慮通信約束，以及更多的搜索指標(biāo)，對(duì)多無(wú)人機(jī)協(xié)同區(qū)域搜索算法進(jìn)一步完善。