李亞南，黃海濱，莊宇飛，蔡春偉

（哈爾濱工業(yè)大學(xué)（威海），威海264209）

0 引言

面向無人水面艇（Unmanned Surface Vehicle，USV）的海上無人系統(tǒng)覆蓋問題可被廣泛應(yīng)用于搜索營救、區(qū)域偵察觀測、火力打擊、信息采集、巡邏、地形測繪等任務(wù)［1］，軍用和民用的大量需求使得研究無人系統(tǒng)覆蓋問題有著十分重要的意義。

無人系統(tǒng)覆蓋問題既要求個體有高度的自主性，又要求個體有很強的協(xié)同合作性。自主性要求個體有自主實現(xiàn)環(huán)境感知、信息處理、決策和行為的能力；協(xié)同的目的是獲得有效的、無碰撞的覆蓋路徑，指示無人系統(tǒng)在給定的時間內(nèi)覆蓋搜索感興趣的目標(biāo)，盡可能多地獲取任務(wù)區(qū)域的信息，獲取最大收益，降低任務(wù)區(qū)域信息的不確定性。

對無人系統(tǒng)覆蓋任務(wù)而言，為避免局部最優(yōu)、降低優(yōu)化或控制難度，一種有效的解決思路就是采用多邊形分割、模糊C均值聚類、質(zhì)心Voronoi圖劃分等方法把任務(wù)區(qū)域分割為與無人機（Unmanned Aerial Vehicle，UAV）等數(shù)量的子區(qū)域進(jìn)行覆蓋偵察［2?3］。另一種解決思路為編隊的方法：系統(tǒng)中所有個體保持相對于領(lǐng)導(dǎo)者的期望距離和方向，通過控制領(lǐng)導(dǎo)者的運動并同時保持編隊結(jié)構(gòu)來簡化無人系統(tǒng)的覆蓋問題［4］。在未知環(huán)境下執(zhí)行覆蓋的一種簡單方法是完全隨機覆蓋，個體在保持避障的基礎(chǔ)上采用完全隨機策略實現(xiàn)任務(wù)區(qū)域覆蓋［5］。就區(qū)域覆蓋和檢測有效性而言，分區(qū)及編隊這兩種方法在已知環(huán)境下是一種非常有效的方式。這種優(yōu)勢來自于有效的任務(wù)分配，但是不能將其運用到高度動態(tài)變化的現(xiàn)實環(huán)境中，因其不具備節(jié)點故障的魯棒性及不具備擴展性。與分區(qū)及編隊這兩種方法相比，隨機覆蓋可以在未知環(huán)境中獲得使用。然而，隨機覆蓋不是有效的策略，因為個體可能會重復(fù)訪問相同的區(qū)域而不是探索未訪問的區(qū)域。為了克服上述缺點，Miao等人［6］提出一種模仿獨居動物社會行為的反集群算法，并將其運用到移動監(jiān)控系統(tǒng)中，通過鄰居交流或通過環(huán)境進(jìn)行交流來最大限度地擴大搜索范圍并最大限度地減少重疊。仿真結(jié)果表明，反集群算法在探測率及探測時間方面均優(yōu)于隨機覆蓋。在文獻(xiàn)［6］的基礎(chǔ)上，Ganganath等人［7］提出了分布式反集群算法并使用信息圖來最小化覆蓋區(qū)域的重疊。

本文采用分布式反集群算法解決了USV對海面區(qū)域的區(qū)域覆蓋問題，通過計算每個個體在每一時刻的最大化收益方向，使得每個個體能夠最大化累計覆蓋面積及最小化個體之間的重疊覆蓋部分。首先建立每個個體的包含覆蓋歷史的信息圖，然后進(jìn)行反集群算法的避障、去中心化及自私這3個基本屬性的數(shù)學(xué)公式描述，最后進(jìn)行Matlab仿真，以及進(jìn)行區(qū)域覆蓋性能的評估。

1 問題描述

1.1 系統(tǒng)建模

考慮n個USV在R2凸區(qū)域移動，將n個USV組成的無人系統(tǒng)定義為Vα={1，2，…，n}。 所有USV均配有取值范圍為rs（rs＞0）的傳感器，每艘USV都有一個范圍為rc的無線通信模塊。在實際應(yīng)用中，rc＞2rs，使得USV能夠在感知區(qū)域不重疊的情況下相互通信。

采用雙積分動態(tài)模型描述USV在n維Euclid空間中的運動學(xué)模型，如式（1）所示。

其中，xi（t）、vi（t）、ui（t）分別表示第i個 USV在t時刻的位置、速度及控制輸入，i=1，2，…，n。

1.2 碰撞規(guī)避

定義一個非負(fù)成對相斥勢能

其中，kp是正常數(shù)，z為USV之間或USV與障礙物之間的距離。隨著z→0，成對相斥勢能φ（z，d）達(dá)到它的最大值。隨著z→d，成對相斥勢能平滑消失到0，在區(qū)間 [d，∞)保持在0。隨后，使用φ（z，d）來為USV之間實現(xiàn)中心化及為USV與障礙物之間實現(xiàn)避障。

1.3 分布式反集群算法

本文采用文獻(xiàn)［7］提出的分布式反集群算法，將分布式反集群算法概述如下。

第i個USV的控制輸入由式（3）給出

式中，hi是一個二進(jìn)制函數(shù)，將hi（t）定義為

去中心項的主要目的是使USV彼此保持距離，以避免碰撞，并引導(dǎo)其向著自私的目標(biāo)前進(jìn)，這最終有助于在更短的時間內(nèi)達(dá)到整個區(qū)域的覆蓋范圍。其中，dα（0＜dα≤2rs）是USV之間的最小期望距離。

使用式（4）、式（7），以及式（8）中給出的控制輸入，可將式（3）重寫為

2 計算最大化收益目標(biāo)

2.1 分布式信息更新

使用這個方法，第i個USV可以跟蹤其覆蓋歷史及與其通信的其他USV的最新信息。除此之外，第i個USV可能間接地訪問其非鄰居的覆蓋歷史。

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

為了最大限度地擴大區(qū)域覆蓋范圍，可引入最大化收益目標(biāo)，以引導(dǎo)USV轉(zhuǎn)向訪問次數(shù)較少的區(qū)域，向著其最大化收益目標(biāo)方向前進(jìn)。

使用信息圖，可以有效地確定目標(biāo)的位置。USV在時刻t（t＞0）的信息圖為Ii，引入效益函數(shù)λi（x，t）來評價Ii

其中，t-Ii（x）項是距離位置x上一次被訪問的時間跨度，其值越大表示越長時間未訪問其位置；σ為正常數(shù)。函數(shù)ηi（x）定義如下

3 區(qū)域覆蓋評估結(jié)果

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

所需覆蓋的區(qū)域為400m×400m正方形區(qū)域，半徑為30m的圓形障礙物位于（90m，250m）處，邊長為70m的方形障礙物左下角坐標(biāo)位于（270m，50m）。將所需覆蓋區(qū)域離散為1m×1m的單元格，USV在整個仿真過程中都保持在給定的區(qū)域內(nèi)。為便于比較，默認(rèn)在所有仿真中，下面的參數(shù)是固定的：rc=600m、dα=1.9rs、kp=25、ks=0.1、kv=0.3、σ=0.2、ε1=0.04，以及ε2=0.01，以下給出了幾組不同的仿真結(jié)果。

3.2 仿真結(jié)果分析

3.2.1 性能指標(biāo)分析

首先，分析在反集群算法控制下的系統(tǒng)采用不同數(shù)量USV在給定區(qū)域內(nèi)實現(xiàn)100%覆蓋所需的平均時間，USV 的數(shù)量為n（n∈［4，12］），rs=50m。仿真結(jié)果如圖1所示。從仿真結(jié)果可以看出，完全覆蓋所花費的平均時間隨著USV數(shù)量的增加而呈指數(shù)衰減。因此，稍微增加網(wǎng)絡(luò)規(guī)模，便可以大大提高覆蓋時間性能。然而，隨著網(wǎng)絡(luò)規(guī)模的增大，增益減少，基礎(chǔ)設(shè)施成本增加。因此，應(yīng)慎重決定規(guī)模以達(dá)到良好的投資回報效果。

圖1 在分布式反集群算法控制下實現(xiàn)100%覆蓋率所需平均時間與USV數(shù)量的函數(shù)關(guān)系Fig.1 Relationship between the number of USV and the average time required to achieve 100%coverage under the control of distributed antiflocking algorithm

其次，分析分布式反集群算法對系統(tǒng)瞬時面積覆蓋的影響。瞬時區(qū)域覆蓋的定義為：所有USV在t時刻所覆蓋的區(qū)域占總區(qū)域的百分比［8］。仿真結(jié)果如圖2所示。根據(jù)給出的結(jié)果，由于反群集算法的中心化項，因此系統(tǒng)的瞬時面積覆蓋率隨USV數(shù)量的增加而線性增加。

圖2 分布式反集群算法控制的USV的瞬時覆蓋面積與USV數(shù)量的函數(shù)關(guān)系Fig.2 Relationship between the number of USV and the instantaneous area coverage of USV under the control of distributed antiflocking algorithm

再次，仿真比較了在分布式反集群算法和隨機搜索模型［9］控制下的累積面積覆蓋性能。分別采用5個USV進(jìn)行仿真，仿真結(jié)果如圖3所示。累積覆蓋率的定義為：在 [0，t)時間間隔內(nèi)，USV累計覆蓋面積占總區(qū)域面積的百分比［8］。根據(jù)圖3給出的仿真結(jié)果，隨著時間的推移，這兩種算法控制下的累計覆蓋率不斷增長。與執(zhí)行隨機搜索算法相比，分布式反集群算法控制下的覆蓋給定區(qū)域所需的時間更短。因此，該算法可以提高能量利用率。雖然反集群算法的目的是以更小數(shù)量的個體提供更好的動態(tài)覆蓋性能，但分布式反集群算法也可用于大規(guī)模無人系統(tǒng)。

圖3 由兩種不同算法控制的USV的平均累積面積覆蓋率與時間函數(shù)關(guān)系Fig.3 Relationship between the average cumulative area coverage of USV and the time under the control of two different algorithms

最后，驗證反集群算法在應(yīng)用過程中的避障能力。如圖4所示，采用8個USV進(jìn)行仿真，傳感器探測范圍為rs（rs=50m），8個USV從給定區(qū)域內(nèi)的隨機位置啟動。在圖4的左側(cè)圖中，圓圈和六角星分別表示USV和目標(biāo)，彎曲軌跡代表了USV的移動路徑歷史，黑色長方形和圓形表示障礙物。圖4右側(cè)圖表示USV在t時刻所覆蓋的區(qū)域占總區(qū)域的比例。

圖4 避障能力驗證Fig.4 Illustration of obstacle avoidance capability

隨著時間的推移，USV根據(jù)式（11）中給出的控制輸入在給定區(qū)域內(nèi)移動，在17.9s時已完成85%的區(qū)域覆蓋。在仿真過程中，沒有檢測到USV和障礙物之間及USV與USV之間的碰撞，證明了分布式反集群算法的避障能力。

3.2.2 某個USV故障的情況

假設(shè)某個USV出現(xiàn)故障，采用8個USV進(jìn)行仿真，傳感器探測范圍為rs（rs=50m），設(shè)置USV初始位置及初始速度方向與圖4仿真中相同，仿真結(jié)果如圖5所示。

圖5 模擬某個USV故障的情況Fig.5 Simulation in failure of a UAV

從提取的樣本中可以看出，USV一直在不斷地探索區(qū)域，同時最小化其感知覆蓋的重疊。當(dāng)覆蓋率為70%時，第8個USV（如左圖中玫紅色的標(biāo)記USV及其路徑所示）發(fā)生故障。由于USV軌跡是根據(jù)最新的信息動態(tài)獲取的，因此，這使得其可以在某些個體失效的情況下無縫工作，該算法可以很容易地適應(yīng)環(huán)境的變化。當(dāng)t=41.2s時，達(dá)到100%的覆蓋率。

3.2.3 USV傳感器探測范圍存在差異的情況

考慮到不同USV所攜帶的傳感器探測范圍的不同會導(dǎo)致區(qū)域覆蓋效率變化，仿真模擬了USV傳感器探測范圍不同的情況。采用8個USV進(jìn)行仿真，采用攜帶3種傳感器探測范圍的USV（rs=50m、rs=30m、rs=20m）共同進(jìn)行區(qū)域覆蓋，設(shè)置USV初始位置及初始速度方向與圖4仿真中相同，仿真結(jié)果如圖6所示。

圖6 模擬USV傳感器探測范圍差異情況Fig.6 Simulation the difference of detecting range of different USV sensors

從提取的樣本中可以看出，在t=0s初始時刻，由于部分USV所攜帶的傳感器探測范圍小于等于50m（rs≤50m），故其初始覆蓋率相較于圖4而言明顯減小，完成100%覆蓋率所需時間更長。從仿真結(jié)果來看，不同的探測范圍并不影響其避障及去中心化能力，并且最終仍能夠?qū)崿F(xiàn)100%的區(qū)域覆蓋。因此，分布式反集群算法同樣適用于USV傳感器探測范圍存在差異的情況。

4 結(jié)論

本文采用分布式反集群算法，在障礙物密集的環(huán)境中實現(xiàn)了有效的動態(tài)覆蓋。由于該算法具有完全分布式、智能化的控制機制，與隨機運動模型相比，具有更好的可擴展性、自適應(yīng)性及魯棒性。該算法基于相鄰個體間局部交互的自組織行為，使得無人系統(tǒng)更容易適應(yīng)動態(tài)環(huán)境。在今后的工作中，需要進(jìn)一步考慮洋流、旋渦及風(fēng)力等的干擾作用，使該算法更適用于實際系統(tǒng)。此外，需進(jìn)一步將算法中的避障機制推廣到更復(fù)雜的場景中，如凹形動態(tài)障礙及動態(tài)障礙物等。