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

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

0 引 言

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

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

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

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

1 USV集群覆蓋搜索問(wèn)題描述

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

(1)

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

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

約束條件為

(2)

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

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

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

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

(3)

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

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

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

(4)

式(4)表示集群優(yōu)化目標(biāo)為最大化各USV在任意時(shí)刻航跡點(diǎn)的搜索價(jià)值。

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

(5)

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

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

Nt≥Nu

(6)

(7)

(8)

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

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

2.1 AC-Frontier算法框架

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

圖1 AC-Frontier算法流程

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

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

2.2 邊界檢測(cè)與提取

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

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

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

2.3 改進(jìn)K-means++聚類(lèi)劃分搜索任務(wù)

過(guò)多的搜索任務(wù)會(huì)給任務(wù)分配流程帶來(lái)額外的計(jì)算量,考慮到相近的邊界點(diǎn)具有相似的收益和成本,可以對(duì)檢測(cè)到的邊界點(diǎn)進(jìn)行合理劃分,生成搜索任務(wù)。本文借鑒文獻(xiàn)[7-9]的方式,使用K-mean聚類(lèi)算法[20]劃分搜索任務(wù)點(diǎn)。

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

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

圖3 某時(shí)刻的邊界點(diǎn)聚類(lèi)生成搜索任務(wù)

2.4 集群搜索任務(wù)分配

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

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

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

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

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

(9)

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

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

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

USV集群的任務(wù)分配流程由競(jìng)拍階段和共識(shí)階段迭代執(zhí)行。每艘Ui在分配過(guò)程中存儲(chǔ)和更新長(zhǎng)度為Nt的兩個(gè)列表Pi和Vi,報(bào)價(jià)列表Pi存儲(chǔ)當(dāng)前迭代回合各個(gè)任務(wù)Tj的最高報(bào)價(jià),凈收益列表Vi存儲(chǔ)Ui執(zhí)行任務(wù)Tj凈收益的預(yù)測(cè)值。

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

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

(10)

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

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

Ui競(jìng)買(mǎi)Tj的凈收益為

vij=aij-pj

(11)

式中:pj為報(bào)價(jià)列表Pi存儲(chǔ)任務(wù)Tj的最新報(bào)價(jià)。

(12)

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

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

(13)

3 仿真驗(yàn)證與分析

3.1 仿真設(shè)計(jì)與實(shí)現(xiàn)

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

圖5 算法驗(yàn)證仿真地圖搭建

為了檢驗(yàn)算法的有效性,本文設(shè)計(jì)以下幾組對(duì)比實(shí)驗(yàn)。

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

表1 實(shí)驗(yàn)參數(shù)配置

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

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

3.2 仿真結(jié)果分析

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié) 論

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