基于分布式反集群算法的無人水面艇區域覆蓋方法

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

（哈爾濱工業大學（威海），威海264209）

0 引言

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

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

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

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

1 問題描述

1.1 系統建模

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

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

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

1.2 碰撞規避

定義一個非負成對相斥勢能

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

1.3 分布式反集群算法

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

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

式中，hi是一個二進制函數，將hi（t）定義為

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

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

2 計算最大化收益目標

2.1 分布式信息更新

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

2.2 目標函數

為了最大限度地擴大區域覆蓋范圍，可引入最大化收益目標，以引導USV轉向訪問次數較少的區域，向著其最大化收益目標方向前進。

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

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

3 區域覆蓋評估結果

3.1 仿真參數設置

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

3.2 仿真結果分析

3.2.1 性能指標分析

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

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

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

圖2 分布式反集群算法控制的USV的瞬時覆蓋面積與USV數量的函數關系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進行仿真，仿真結果如圖3所示。累積覆蓋率的定義為：在 [0，t)時間間隔內，USV累計覆蓋面積占總區域面積的百分比［8］。根據圖3給出的仿真結果，隨著時間的推移，這兩種算法控制下的累計覆蓋率不斷增長。與執行隨機搜索算法相比，分布式反集群算法控制下的覆蓋給定區域所需的時間更短。因此，該算法可以提高能量利用率。雖然反集群算法的目的是以更小數量的個體提供更好的動態覆蓋性能，但分布式反集群算法也可用于大規模無人系統。

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

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

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

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

3.2.2 某個USV故障的情況

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

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

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

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

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

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

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

4 結論

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