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

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

0 引 言

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

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

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

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

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

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

(1)

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

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

約束條件為

(2)

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

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

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

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

(3)

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

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

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

(4)

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

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

(5)

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

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

Nt≥Nu

(6)

(7)

(8)

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

2 USV集群協(xié)同搜索算法設計

2.1 AC-Frontier算法框架

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

圖1 AC-Frontier算法流程

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

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

2.2 邊界檢測與提取

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

圖2 構(gòu)建地圖與柵格信息表示

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

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

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

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

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

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

2.4 集群搜索任務分配

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

圖4 USV集群控制結(jié)構(gòu)

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

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

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

(9)

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

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

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

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

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

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

(10)

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

式(10)定義Ui執(zhí)行任務Tj的收益與任務水域的信息熵呈正相關,與任務區(qū)間到USV的距離呈負相關,相關性由權(quán)重因子ω調(diào)節(jié)。任務收益均為正數(shù),保證所有任務均能參與競拍。

Ui競買Tj的凈收益為

vij=aij-pj

(11)

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

(12)

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

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

(13)

3 仿真驗證與分析

3.1 仿真設計與實現(xiàn)

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

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

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

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

表1 實驗參數(shù)配置

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

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

3.2 仿真結(jié)果分析

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

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

表2 集群內(nèi)各USV的搜索效果

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

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

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

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

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

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

圖8 集群規(guī)模對算法效率的影響

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

Nu=10時,USV集群協(xié)同覆蓋搜索和地圖構(gòu)建過程如圖9所示,黃色柵格為檢測到的邊界,紫色線條為各USV的航行軌跡?？梢钥吹?USV集群從起始點出發(fā),使用AC-Frontier算法協(xié)同配合,動態(tài)檢測探索邊界,自主分配搜索任務,對指定水域完成了遍歷覆蓋搜索。

圖9 AC-Frontier集群協(xié)同覆蓋搜索過程

4 結(jié) 論

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