通信距離約束下的無人船集群覆蓋搜索方法

尹 洋, 楊全順, 王 征, 劉 洋

(海軍工程大學電氣工程學院, 湖北 武漢 430033)

0 引 言

近年來,搭載多種探測設備、通信設備或各型武器的水面無人船(unmanned surface vessel, USV),成為了執行搜索救助、水文勘察、海洋環境檢測等任務的重要平臺[1]。USV可搭載聲納、光電等傳感器來感知環境情況,實現對指定水域的暗礁、海底地形、水下目標等進行探測、識別和定位[2]。單艇的覆蓋搜索算法目前已有較多研究。對于形狀規則、環境已知的目標水域,USV的覆蓋搜索問題可以視作完全遍歷路徑規劃問題[3],可以使用遍歷算法進行覆蓋搜索[4-5]。對于沒有先驗知識的未知水域,USV需要實現自主探索并構建環境地圖,目前主要方法有邊界探索算法[6]及其改進算法[7-10]。

中小型USV的平臺載荷有限,存在一定的局限性[11],而以集群的方式執行任務可以功能互補,發揮組織靈活、抗毀重構性強的優勢[12],因此集群協同技術成為了當前的研究熱點之一。

面對集群協同探測問題,向庭立等[13]使用最小覆蓋圓法來確定待探測區域的軌跡點,將區域探索問題轉換為集群任務分配問題,進而使用改進灰狼算法求得最優分配。但此方法只能處理邊界已知的待探測區域,靜態地為集群個體分配搜索任務。高春慶等[14]基于集群規模和初始位置劃分搜索任務子區域,將集群協同覆蓋問題轉換為單遍歷路徑規劃問題,再基于生成樹節點交換法優化規劃路徑。但該方法需要提前給出障礙區域和危險區域,對環境的適應性不高。張耀中等[15]根據異構型集群和多任務區協同偵察的特點構建“資源-需求”矩陣,再基于一致性束算法生成任務分配方案。但其無法處理任務數量的突然增減、任務區移動等突發情況。Wang等[16]基于分布式粒子群算法編碼個體信息和任務決策信息,針對不同戰術意圖分別設計協同算法。但該算法需要根據集群的機動性和通信約束等特點設計專門的適應度函數,擴展性和適應性較低。對于集群通信距離受到限制的情況,張民強等[17]給出了一種分布式的Voronoi區域計算方法,分析了通信和采樣周期異步時的信息更新公式。王寧等[18]設計了一種根據有效通信距離自主切換的信息交互機制。符小衛等[19]研究了多種通信約束條件對集群搜索目標任務分配的影響。上述文獻均是在已知環境中進行覆蓋搜索,對未知環境下的協同搜索研究較少。

針對通信距離受限時,中小型USV集群對未知水域執行覆蓋搜索任務的應用場景,本文基于聚類任務劃分和競拍任務分配的思想,推廣單艇的邊界探索算法,提出一種集群的競拍協同邊界(auction collaborate frontier, AC-Frontier)探索算法,使用改進的聚類算法動態生成邊界搜索任務,消除不安全的和無價值的探索任務點,使用分布式競拍算法進行任務分配,最大化集群搜索效率。設計仿真實驗驗證該算法在搜索效率上的提升和對不同規模集群的通用性。

1 USV集群覆蓋搜索問題描述

考慮USV集群的協同覆蓋搜索問題,在沒有任何環境先驗知識的情況下,USV集群自主分配搜索任務,規劃航行路徑,在不與障礙物發生碰撞的前提下,盡快地遍歷覆蓋并構建整個環境地圖,完成指定水域的覆蓋搜索探測任務。

(1)

式中:mi為USVUi所覆蓋搜索的水域。

式(1)表示盡可能地均勻分配搜索水域,且避免重復搜索同一水域,從而在航速一定的情況下,盡快完成覆蓋搜索任務。

約束條件為

(2)

式中:(xi,yi)k為Ui在k時刻的坐標;(xb,yb)為障礙物距離Ui最近的坐標點;R為安全避障距離。

約束式(2)表示USV探測距離D遠大于轉彎半徑Rv;任意時刻Ui和障礙物之間需保持安全距離;集群所搜索的水域要覆蓋整個指定水域。

定義USVUi搜索路徑點的時序集合為Ti={Ti1,Ti2,…,Tis}。隨著覆蓋搜索任務的進行,USV集群根據覆蓋搜索情況,動態決策出一系列目標路徑點分配給各艇,Ui執行完畢后,記錄到路徑點集合Ti中。

在USV航行過程中,由探測距離D可得到探測覆蓋的區域,為簡化問題,將Ui的航行路徑視作覆蓋搜索的水域mi,式(2)所描述的優化目標可等價于:

(3)

式中:L(Ti k)為Ui從路徑點Ti k-1至Ti k的航程。

式(3)表示在滿足覆蓋搜索約束的前提下使集群的總航程盡可能短。

本文研究未知環境下覆蓋搜索問題,由于沒有任何環境信息,無法通過求解路徑規劃問題得到集群最優航行路徑,因此本文將覆蓋搜索問題轉換為序列決策問題,在每個決策時刻評估挑選局部最優目標路徑點,最大化各艇搜索價值的期望,從而減少總航程。定義函數R(Ti k)評估Ui在路徑點Ti k完成搜索水域的價值,式(3)可轉換為

(4)

式(4)表示集群優化目標為最大化各USV在任意時刻航跡點的搜索價值。

搜索過程中的k時刻,各艇協調分配各自的搜索路徑點,使分配后的集群探測收益Jk最大。綜合考慮各艇抵達任務點的路程和各個任務點的探測收益等因素,在k時刻由Nt個搜索任務組成的任務集合T={T1,T2,…,TNt},其非對稱單分配問題的數學描述為

(5)

式中:A(i)?T,為可以分配給Ui的任務集合;xij為決策變量,表示任務Tj是否分配給Ui,是則xij=1,否則xij=0;aij為Ui執行搜索任務Tj的收益。

協同覆蓋搜索任務分配問題的約束條件為

Nt≥Nu

(6)

(7)

(8)

式(6)表示搜索任務的數量大于或等于USV數量;式(7)表示每一個任務Tj至多分配給一艘USV;式(8)表示任務分配完成后每艘USV有且只有一個搜索任務。

2 USV集群協同搜索算法設計

2.1 AC-Frontier算法框架

針對通信距離約束下USV集群對未知水域的協同覆蓋搜索問題,本文基于層次聚類和拍賣理論提出AC-Frontier協同覆蓋搜索算法,推廣邊界探索算法為集群協同探索算法,算法流程如圖1所示。

圖1 AC-Frontier算法流程

在k時刻,USV集群根據k-1時刻各艇的探索情況構建地圖環境信息,檢測已探測水域的邊界,然后使用改進的K-mean++算法對邊界點進行聚類,對不安全或低收益的目標搜索點重規劃,劃分出符合要求的任務區間,進而使用競拍算法為USV分派下一步的搜索任務,將集群協同問題轉換為單艇搜索問題,最后各USV自行導航至目標點進行探測并進入k+1時刻。算法迭代運行直至完成指定水域的覆蓋搜索。

若某USV完成了k時刻所指派的搜索任務,則其立即進入下一時刻,與相鄰的USV交換局部信息并分配新的搜索任務，而不必待機等候整個集群完成k時刻的搜索任務。同時,參與信息交換的USV根據分配結果與自身任務信息進行對照,若發生任務變更事件,則同步進入下一時刻,并更新任務信息,否則繼續執行原任務。

2.2 邊界檢測與提取

本文使用占據網格法對任務水域進行柵格化處理,每個柵格獨立地表示自身狀態信息:未知柵格、空閑柵格、障礙柵格。柵格在任意時刻的狀態信息都為三種狀態之一,更新構建地圖即更新柵格狀態的變化。定義邊界柵格為相鄰柵格中至少存在一個處于未知狀態的柵格。如圖2所示,分別以黑色、藍色、白色表示柵格狀態,以黃色表示提取到的邊界,紅色三角形為USV,綠色圓形為對邊界聚類得到的搜索點。

圖2 構建地圖與柵格信息表示

定義評價函數R(m)=n評估任務水域信息熵,n為水域m包含的未知狀態柵格數。提取長度大于閾值的邊界點到可訪問列表中,作為聚類算法的輸入數據。

2.3 改進K-means++聚類劃分搜索任務

過多的搜索任務會給任務分配流程帶來額外的計算量,考慮到相近的邊界點具有相似的收益和成本,可以對檢測到的邊界點進行合理劃分,生成搜索任務。本文借鑒文獻[7-9]的方式,使用K-mean聚類算法[20]劃分搜索任務點。

但此類算法存在聚簇個數k需要事先給定的固有缺陷。在本文應用中,若k值過大,則計算量較大,且大量搜索任務相似,失去了劃分任務的意義;若k值過小,則易出現如圖2(a)中無價值的搜索點,即USV受探測距離D的限制,抵達該搜索點后沒有探索新水域的效果,和圖2(b)中處于未知區域或障礙區域的不安全搜索點,這兩種搜索點都需要進行重規劃。

基于層次聚類的思想,本文對K-mean++算法做出改進,在初步規劃完成后,根據聚類效果決定是否需要進一步細分:首先由集合U的元素數量Nu確定初始聚類中心的數量k,再以輪盤賭算法逐個選出初始點,距離越大的點被選中的概率越大;然后開始對可訪問列表中的邊界點進行均值聚類,得到k個搜索任務區間;最后對這些任務區間逐個進行評估,若該區間沒有一定的價值,或者是不安全的搜索點,則對這個聚類進一步劃分,直到得到一組滿足要求的搜索任務。改進算法流程如圖3所示。

圖3 某時刻的邊界點聚類生成搜索任務

2.4 集群搜索任務分配

在k時刻獲取一組搜索任務后,需綜合考慮USV的狀態、執行任務的收益和成本,為集群各艇分配搜索任務,消解沖突,使式(5)描述的集群搜索收益最大化。如圖4所示,USV集群的控制結構可分為主從式和分布式[21]。圖4(a)表示的主從式控制結構需要一個通信中心,記錄全局任務信息和各艇狀態信息,統一分配搜索任務;圖4(b)表示的分布式控制結構則由各艇自行組網,僅與網絡內相鄰的其他USV交換局部信息。

圖4 USV集群控制結構

考慮USV集群在通信距離有限的條件下,采用主從式控制的可擴展性和魯棒性較弱;此外,集群各艇在執行分配到的搜索任務時,各艇完成指定任務的時間不一定相同,若采取待機等候其余USV搜索完畢統一進行下一輪任務分配的方式,則計算資源開銷較大,且覆蓋搜索效率低下。因此，本文采用分布式結構進行任務分配。

考慮在實際海域中USV之間能否通信受到可靠通信距離約束的應用背景。本文假設各艇之間通信無延遲,可靠通信距離均為H,處于通信距離內的兩艘USV之間才能交換信息,則k時刻能夠與Ui進行通信的USV集合Ni定義為

Ni={j∈U,j≠i|‖(xi,yi)k-(xj,yj)k‖≤H}

(9)

若H為無窮大,即在理想情況下集群內各艇無通信約束,則分布式競拍算法可視為主從式競拍算法;若H為0,則各艇之間無協作。

現有的任務分配方法可劃分為最優化方法、啟發式方法和類市場機制方法[22]。最優化方法如整數規劃法、約束規劃法、窮舉法等算法簡潔直接,能求出理論最優解,但計算量較大,限制了集群規模的擴展[23];啟發式方法如列表算法、進化算法、粒子群算法、模擬退火算法等,通過權衡算法時用時和求解效果來得到近似解,但需要專家根據實際情況對復雜的超參數進行整定,以平衡算法效率和求解效果,難以在工程中應用[24]。同時,使用最優化方法和啟發式方法前需要先耗費大量的數據吞吐量和計算量,使集群通過一致性算法實現一致的態勢感知。

競拍算法是一種應用廣泛的類市場機制的任務分配方法,其核心思想是各競拍者對收益最高的拍賣品展開競價,以出價最高者得到該拍賣品的方式解決各競拍者之間的分配沖突,使總體收益最大化。本文使用競拍算法進行搜索任務分配的優點主要體現在:① 競拍算法可以靈活增減競標者和拍賣品,適用于本文通信距離約束下,集群網絡拓撲動態變化的分布式結構;② 相較于其他分配算法,競拍算法在處理本文搜索任務數量大于USV數量的非對稱分配問題中具備較大優勢[25];③ 本文應用分布式競拍算法時,各艇僅和相鄰USV交換局部信息,數據吞吐量小,相較于最優化方法和啟發式方法,其計算量受分配問題規模大小的影響較小;④ 競拍算法不需要USV集群達成一致的態勢感知,各艇可僅根據集合Ni獲得動態局部搜索信息從而實現協同。

USV集群的任務分配流程由競拍階段和共識階段迭代執行。每艘Ui在分配過程中存儲和更新長度為Nt的兩個列表Pi和Vi,報價列表Pi存儲當前迭代回合各個任務Tj的最高報價,凈收益列表Vi存儲Ui執行任務Tj凈收益的預測值。

競拍階段中,Ui首先對可分配任務集合A(i)中任務Tj的收益進行估值。定義式(5)中的收益aij為

aij=γeωR(mij)+(ω-1)P(L(Tij))

(10)

式中:ω∈(0,1)為權重因子;P為Ui執行Tj的成本函數,與路程L(Tij)相關;γ>0為縮放因子。

式(10)定義Ui執行任務Tj的收益與任務水域的信息熵呈正相關,與任務區間到USV的距離呈負相關,相關性由權重因子ω調節。任務收益均為正數,保證所有任務均能參與競拍。

Ui競買Tj的凈收益為

vij=aij-pj

(11)

式中:pj為報價列表Pi存儲任務Tj的最新報價。

(12)

由式(11)和式(12)可知,投標報價與最優凈收益和次優凈收益的差值有關,報價的增幅為利潤空間加上一個大于零的常數ε,使其在下一輪競價中不再參與此任務的競拍,而是選擇競拍次優任務。ε保證價格遞增,避免算法陷入死循環,其值越大,算法收斂越快,但誤差越大。

共識階段中,Ui與Ni中的相鄰USV交換報價列表Pi。若發生沖突,且報價最高,則令xib=1獲取此任務;若報價較低,則此輪迭代未能中標此任務,需返回競拍階段重新競拍,并更新報價列表:

(13)

3 仿真驗證與分析

3.1 仿真設計與實現

本文使用Unity3D進行仿真實驗,搭建所需要的地形要素,模擬艦船航行狀態、傳感器探測數據,檢測艦船碰撞事件等。綜合考慮地形復雜度和實驗效果,本文選取武漢梁子湖地區面積為64 km2的部分水域作為驗證地圖,以湖心島和湖岸陸地作為靜態障礙物,湖面為待覆蓋檢測的區域。如圖5所示,以地圖中心紅色區域為搜索起點,綠色高亮的部分為地形和障礙物,地圖中的每一個柵格的初始狀態都為未知柵格,等待各USV的抵近探測,檢測到的邊界點數量為0時視作搜索結束。地圖比例尺為1 units:100 m。

圖5 算法驗證仿真地圖搭建

為了檢驗算法的有效性,本文設計以下幾組對比實驗。

實驗 1集群規模Nu相同的情況下,分別以K-mean++聚類和本文改進聚類方法提取搜索任務點,使用AC-Frontier分布式算法和主從式算法、Near-Frontier算法、Random-Frontier算法[10]進行覆蓋搜索。部分實驗參數如表1所示。其中， “units”為Unity中的距離單位。

表1 實驗參數配置

實驗 2集群規模Nu相同的情況下,以實驗1參數配置為基礎,比較不同的有效通信距離H對分布式AC-Frontier算法搜索效率的影響。

實驗 3有效通信距離H相同的情況下,以實驗1參數配置為基礎,比較集群規模Nu不同時分布式AC-Frontier搜索效率的變化。

3.2 仿真結果分析

實驗 1在指定地圖下,指定規模的USV集群分別使用4種自主探索算法運行20次,運行結果如圖6和表2所示。圖6(a)比較了使用K-mean++聚類和使用本文改進聚類方法提取搜索任務時,各算法的覆蓋搜索時長;圖6(b)比較了各算法使用改進聚類方法完成覆蓋搜索任務時集群的航行總路程;表2列出了集群內各艇完成的搜索水域價值R、航程L、價值航程比G=R/L和相應的標準差變異系數CV。

圖6 規模相同時不同算法搜索效果對比

表2 集群內各USV的搜索效果

從圖6(a)可以看到,面對相同水域環境,使用本文改進聚類方法時,分布式AC-Frontier算法執行遍歷覆蓋搜索任務的用時比Near-Frontier算法減少30.1%,比Random-Frontier算法減少76.9%,主從式AC-Frontier用時分別減少42.4%和82.8%,這表明搜索過程中USV集群進行了合理的任務分配,優化了搜索效率。主從式掌握更多全局信息,任務分配更合理,所以搜索效率略優于分布式。4種搜索算法使用改進聚類方法時,比使用普通K-mean++算法用時分別減少了39.4%、45.3%、48.8%、44.7%,可見改進聚類方法通過動態重規劃,消除了低收益或不安全的搜索任務點,提高了任務點的搜索收益。從圖6(b)可以看到,使用本文算法進行協同搜索時集群的航行總路程有明顯減少,分布式算法分別為無協同算法的78.7%和22.6%,主從式算法分別為61.5%和17.7%,這說明USV集群通過協同配合,以較少的能耗完成了覆蓋搜索任務。

從表2可以看到,使用本文AC-Frontier算法進行協同搜索時,搜索價值E和航程L的變異系數CV較小,說明集群內各艇分配到的搜索任務更為均勻,體現了集群任務分配的作用。各艇收益航程比G較大,說明各艇在單位路程內探索到的未知水域更多,從而使集群最終航行總路程更少,與圖6結果分析相同。

實驗 2在指定地圖下,指定規模的USV集群使用分布式AC-Frontier算法,以不同有效通信距離運行,仿真結果對比如圖7所示。其中,H=∞表示使用的是本文主從式算法。

圖7 通信距離對分布式算法效率的影響

從圖7中可以看到,隨著有效通信距離的增大,集群內各艇獲得的全局信息越多,集群探索任務的分配結果越好,使得完成覆蓋探索的時間更短,分配決策次數也更少,同時誤差帶較小,說明算法效果更為穩定。通信距離增大到一定程度后,受到仿真環境的限制,算法運行結果趨近于主從式任務分配的搜索算法。通信距離較短時,趨近于無協作的搜索算法,誤差帶較大,體現出算法效果隨機性較大。

實驗 3以不同的USV集群規模在相同地圖下分別運行,仿真結果如圖8所示。

圖8 集群規模對算法效率的影響

圖8比較了集群規模對搜索用時(紅色曲線)和任務分配決策次數(藍色曲線)的影響。可以看到,隨著集群規模的增大,搜索時間和決策次數穩步下降,Nu=6時,相較于Nu=3搜索用時縮短了50%。受限于仿真環境面積大小,繼續增大集群規模至過飽和,搜索效率不再有明顯提高。這體現了AC-Frontier算法在集群中起到的協同作用,同時說明本算法可以很好地適應不同規模的集群。

Nu=10時,USV集群協同覆蓋搜索和地圖構建過程如圖9所示,黃色柵格為檢測到的邊界,紫色線條為各USV的航行軌跡。可以看到,USV集群從起始點出發,使用AC-Frontier算法協同配合,動態檢測探索邊界,自主分配搜索任務,對指定水域完成了遍歷覆蓋搜索。

圖9 AC-Frontier集群協同覆蓋搜索過程

4 結 論

針對USV集群覆蓋探測指定水域的應用場景,本文基于邊界探索算法和拍賣理論,提出一種分布式的集群協同覆蓋搜索算法AC-Frontier。該方法提取邊界坐標和信息熵,使用改進的K-mean聚類算法劃分任務區間,再使用分布式的競拍算法為集群個體動態分配搜索任務,使集群對指定未知水域進行覆蓋探測,并構建環境地圖。仿真實驗驗證表明,集群規模相同時,該算法通過協同配合的方式提高了集群搜索效率,任務用時相較于無協同的Near-Frontier和Random-Frontier算法分別減少30.1%、76.9%,航行總路程縮短21.3%、77.4%,體現了該算法在集群覆蓋探測路徑規劃問題上的有效性;集群規模不同時,搜索效率隨著規模的增大而提高,體現了算法對不同規模集群的適用性。下一步將針對異構USV集群執行多任務的問題展開進一步研究,更貼近實際地設計USV集群協同算法。