水庫(kù)庫(kù)容無人船自動(dòng)巡航路徑規(guī)劃算法與仿真實(shí)驗(yàn)

摘 要：該文主要探究水庫(kù)庫(kù)容無人船自動(dòng)巡航最短路徑的規(guī)劃算法，并對(duì)算法應(yīng)用效果進(jìn)行仿真驗(yàn)證。使用模擬退火算法可以基于補(bǔ)測(cè)點(diǎn)尋找最短路徑，但是循環(huán)次數(shù)較多、耗時(shí)較長(zhǎng);通過補(bǔ)測(cè)點(diǎn)聚類處理，將補(bǔ)測(cè)點(diǎn)分成若干點(diǎn)簇后再次尋找最短路徑，耗時(shí)明顯變短，但是仍然存在不同點(diǎn)簇之間路徑差值較大的問題。使用點(diǎn)簇調(diào)整算法后，保證不同點(diǎn)簇之間的最短路徑相近，達(dá)到降低能耗和提高效率的目的。仿真結(jié)果表明，在點(diǎn)簇調(diào)整后，3個(gè)點(diǎn)簇最短路徑的差值從70 398.48 m變?yōu)?5 356.29 m，在多艘無人船自動(dòng)巡航路徑規(guī)劃中達(dá)到能耗均衡、精度較高的效果。

關(guān)鍵詞：無人船;自動(dòng)巡航路徑規(guī)劃;模擬退火算法;聚類算法;最短路徑

中圖分類號(hào)：U664.82 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：2095-2945（2024）30-0012-04

Abstract： This paper mainly explores the shortest path planning algorithm for automatic cruising of unmanned ships in reservoir storage capacity， and carries out simulation verification to the application effect of the algorithm. Using the simulated annealing algorithm， the shortest path can be found based on the supplementary measurement points， but the number of cycles is large and the time is long. Through the supplementary measurement point clustering process， the supplementary measurement points are divided into several point clusters and then the shortest path is found again， which takes a significantly shorter time. However， there is still a problem of large path differences between different point clusters. After using the point cluster adjustment algorithm， the shortest paths between different point clusters are ensured to be similar， achieving the purposes of reducing energy consumption and improving efficiency. The simulation results show that after the adjustment of the point clusters， the difference between the shortest paths among the three point clusters changes from 70 398.48 m to 15 356.29 m， which achieves balanced energy consumption and high accuracy in the automatic cruise path planning of multiple unmanned ships.

Keywords： unmanned ship; automatic cruise path planning; simulated annealing algorithm; clustering algorithm; shortest path

水庫(kù)庫(kù)容的精確測(cè)算對(duì)提高水庫(kù)蓄洪能力、保障水庫(kù)安全有積極幫助。無人船在水庫(kù)庫(kù)容計(jì)算中具有自動(dòng)化程度和測(cè)算精度高的優(yōu)勢(shì)，尤其適用于大中型水庫(kù)的庫(kù)容測(cè)算。無人船的自動(dòng)巡航路徑規(guī)劃不僅決定了測(cè)算精度，而且與測(cè)算效率、測(cè)算成本也有密切關(guān)系。使用智能優(yōu)化算法規(guī)劃最短的巡航路徑，保證無人船在續(xù)航范圍內(nèi)一次性完成測(cè)算任務(wù)。基于此，探究無人船自動(dòng)巡航最短路徑的規(guī)劃算法成為影響無人船應(yīng)用效果的決定因素。

1 水庫(kù)庫(kù)容無人船自動(dòng)巡航路徑規(guī)劃算法

1.1 模擬退火算法

為了進(jìn)一步提高無人船的巡航效率，需要獲取補(bǔ)測(cè)點(diǎn)集的位置分布并計(jì)算無人船經(jīng)過所有補(bǔ)測(cè)點(diǎn)時(shí)的最短路徑。傳統(tǒng)的數(shù)學(xué)求解最短路徑隨著補(bǔ)測(cè)點(diǎn)數(shù)量的增加，解算難度會(huì)顯著提升，計(jì)算精度也會(huì)下降。隨著人工智能技術(shù)的發(fā)展，基于智能優(yōu)化算法的自動(dòng)巡航路徑規(guī)劃具有精度更高、速度更快等優(yōu)勢(shì)，因此得到了廣泛應(yīng)用。常用的智能優(yōu)化算法有遺傳算法（GA）、蟻群算法（ACO）和模擬退火算法（SA）等[1]。其中，模擬退火算法具有魯棒性強(qiáng)、通用性好、計(jì)算速度快等特點(diǎn)，本文選擇該算法進(jìn)行水庫(kù)庫(kù)容無人船自動(dòng)巡航路徑規(guī)劃。該算法的路徑搜索過程如圖1所示。

結(jié)合圖1，從補(bǔ)測(cè)點(diǎn)集Vs中隨機(jī)抽取一個(gè)點(diǎn)（假設(shè)為B點(diǎn)），計(jì)算此時(shí)的路程長(zhǎng)度。計(jì)算結(jié)束后，隨機(jī)交換B點(diǎn)與Vs中其他某個(gè)點(diǎn)（假設(shè)為C點(diǎn)）的訪問順序，來到了C點(diǎn)這個(gè)局部極值點(diǎn)形成的“陷阱”。為了跳出該陷阱，系統(tǒng)會(huì)基于Metropolis準(zhǔn)則尋找一個(gè)比當(dāng)前路徑更長(zhǎng)的解，從C點(diǎn)跳至D點(diǎn)。假設(shè)系統(tǒng)存在i和j 2種狀態(tài)，Ei和Ej分別為2種狀態(tài)下的能量（能量的高低與路徑的長(zhǎng)短正相關(guān)），T為系統(tǒng)溫度。則系統(tǒng)從狀態(tài)i轉(zhuǎn)換為狀態(tài)j的概率P可通過下式求得

， （1）

式中：ΔE為Ei與Ej的差值。經(jīng)過計(jì)算后，如果系統(tǒng)新狀態(tài)j的能量要低于原狀態(tài)i，則將系統(tǒng)狀態(tài)更新為j;反之，如果新狀態(tài)j的能量高于原狀態(tài)i，則降低系統(tǒng)溫度，并重新計(jì)算和對(duì)比降低溫度后系統(tǒng)狀態(tài)與原狀態(tài)的能量，直到系統(tǒng)溫度有最低值，即系統(tǒng)能量最小。在模擬退火算法中，能量與路徑相關(guān)，當(dāng)系統(tǒng)能量有最小值時(shí)，說明路徑長(zhǎng)度最短，從而獲取了最短路徑[2]。該算法流程如圖2所示。

1.2 基于能耗均衡的無人船自動(dòng)巡航路徑規(guī)劃算法

相比于數(shù)學(xué)計(jì)算，使用模擬退火算法能縮短無人船自動(dòng)搜索最短路徑的用時(shí)，但是當(dāng)水庫(kù)的庫(kù)容較大時(shí)，由于補(bǔ)測(cè)點(diǎn)數(shù)量較多，仍然要花費(fèi)較多的時(shí)間才能搜尋到較好的路徑。基于此，本文提出了一種基于能耗均衡的多無人船自動(dòng)巡航路徑規(guī)劃算法。其原理是：通過聚類處理，將距離較為靠近的若干個(gè)補(bǔ)測(cè)點(diǎn)劃分到同一個(gè)點(diǎn)簇內(nèi)，然后在點(diǎn)簇內(nèi)搜索最短路徑。由于點(diǎn)簇內(nèi)的補(bǔ)測(cè)點(diǎn)數(shù)量相對(duì)較少，可以縮短獲取最短巡航路徑的用時(shí)。同時(shí)，將補(bǔ)測(cè)任務(wù)平均分配給多艘無人船，每艘無人船分別完成一個(gè)點(diǎn)簇的路徑規(guī)劃任務(wù)，通過并行處理的方式在保證能耗均衡的前提下提升了補(bǔ)測(cè)效率[3]。

在多艘無人船的自動(dòng)巡航路徑算法中，補(bǔ)測(cè)點(diǎn)的聚類處理是核心步驟。目前常用的聚類算法有層次聚類、劃分聚類、密度聚類等若干種。劃分聚類算法具有時(shí)空復(fù)雜度低、可識(shí)別形狀多、抗噪聲性能好等優(yōu)勢(shì)，適合本文的研究需求，因此選取劃分聚類算法。如圖3所示，該區(qū)域內(nèi)分布有49個(gè)補(bǔ)測(cè)點(diǎn)，使用劃分聚類算法將49個(gè)補(bǔ)測(cè)點(diǎn)分成3個(gè)點(diǎn)簇，并計(jì)算各個(gè)點(diǎn)簇的最短路徑。點(diǎn)簇0的最短路徑為12 967.89 m，點(diǎn)簇1的最短路徑為12 920.51 m，點(diǎn)簇2的最短路徑為8 147.29 m。

如圖3所示，基于聚類處理的最短路徑搜索雖然縮短了用時(shí)，但是不同點(diǎn)簇的路徑存在較為明顯的差異。假設(shè)將3個(gè)點(diǎn)簇的路徑規(guī)劃任務(wù)分別派發(fā)給A（點(diǎn)簇0）、B（點(diǎn)簇1）、C（點(diǎn)簇2）三條無人船，那么當(dāng)C船完成點(diǎn)簇2的路徑規(guī)劃任務(wù)后，還需要等待A船和B船，浪費(fèi)了較多時(shí)間，無法保證多艘無人船的能耗均衡。在實(shí)際應(yīng)用中，會(huì)出現(xiàn)有些無人船提前完成任務(wù)，還有些無人船因?yàn)槁窂竭^程、巡航不足而無法完成任務(wù)的情況[4]。為了解決此類問題，本文提出了一種通過微調(diào)點(diǎn)簇、平衡點(diǎn)簇間路徑長(zhǎng)度差距的方法。

假設(shè)補(bǔ)測(cè)點(diǎn)集合為V={v1，v2，…，vn}，使用劃分聚類算法對(duì)V進(jìn)行聚類處理后，得到了k個(gè)點(diǎn)簇，點(diǎn)簇表示為C={c1，c2，…，cn}。L={l1，l2，…，ln}表示點(diǎn)簇對(duì)應(yīng)的路徑最短長(zhǎng)度。任意一個(gè)點(diǎn)簇Ci中需要調(diào)整的點(diǎn)數(shù)ni可通過下式求得

式中：l0表示點(diǎn)簇內(nèi)平均路徑長(zhǎng)度。還是以圖3為例，已知該圖中包含3個(gè)點(diǎn)簇，計(jì)算出3個(gè)點(diǎn)簇的路徑平均長(zhǎng)度（12 967.89+12 920.51+8 147.29）/3=11 345.23 m。根據(jù)式（2）可以求得3個(gè)點(diǎn)簇需要調(diào)整的點(diǎn)數(shù)n，n值取整。點(diǎn)簇0的n0=round（2.28）=2，n1=round（2.22）=2，n3=round（-4.51）=-5。由此可得，點(diǎn)簇2需要從點(diǎn)簇0和點(diǎn)簇1中挑選5個(gè)距離它最近的補(bǔ)測(cè)點(diǎn)，如圖4中虛線橢圓所示。

點(diǎn)簇1去掉5個(gè)補(bǔ)測(cè)點(diǎn)后，n1值從2變?yōu)榱?3，因此點(diǎn)簇1需要從點(diǎn)簇0中挑選2個(gè)補(bǔ)測(cè)點(diǎn)（圖4）。經(jīng)過調(diào)整后，3個(gè)點(diǎn)簇的路徑長(zhǎng)度變成了11 084.59 m、12 233.58 m、10 772.38 m，最大差值為1 461.2 m;相比于處理前的4 820.6 m有了明顯的縮小，實(shí)現(xiàn)了多艘無人船的能耗均衡。

2 水庫(kù)庫(kù)容無人船自動(dòng)巡航路徑規(guī)劃的仿真實(shí)驗(yàn)

2.1 仿真數(shù)據(jù)的獲取與處理

為了驗(yàn)證本文設(shè)計(jì)的無人船自動(dòng)巡航路徑規(guī)劃算法的應(yīng)用效果，選擇美國(guó)國(guó)家海洋和大氣管理局（NOAA）提供的湖泊公開數(shù)據(jù)設(shè)計(jì)了仿真實(shí)驗(yàn)。選取600萬個(gè)測(cè)深采樣點(diǎn)數(shù)據(jù)，計(jì)算出該水庫(kù)的庫(kù)容值[5]。庫(kù)容計(jì)算方法如下：假設(shè)水平面的高度為0 m，將湖泊劃分成若干個(gè)條狀柵格。從第i個(gè)柵格中選擇A、B、C、D四個(gè)采樣點(diǎn)，得到以柵格為底、以4個(gè)采樣點(diǎn)水深為棱長(zhǎng)的四棱柱，該柱的體積V可通過下式求得

式中：hA、hB、hC、hD分別表示4個(gè)采樣點(diǎn)處的水深測(cè)量值;SABCD表示矩形ABCD的面積。將所有以條狀柵格為底的四棱柱面積相加，求和結(jié)果即為該水庫(kù)的庫(kù)容值，經(jīng)計(jì)算庫(kù)容值為1 684.36 km3。在該水庫(kù)中設(shè)計(jì)了60個(gè)補(bǔ)測(cè)點(diǎn)，根據(jù)補(bǔ)測(cè)點(diǎn)的位置分布情況為無人船規(guī)劃一條最短巡航路徑。用于仿真實(shí)驗(yàn)的硬件配置如下。

CPU：主頻2.8 GHz的酷睿i5-6400。

內(nèi)存：8 GB 2133 MHz的DDR4內(nèi)存條。

硬盤：512 GB的固態(tài)硬盤。

2.2 路徑規(guī)劃實(shí)驗(yàn)

首先使用模擬退火算法對(duì)60個(gè)補(bǔ)測(cè)點(diǎn)計(jì)算最短巡航路徑，經(jīng)過16 500次循環(huán)后得到最短路徑。第1次的巡航路徑為3 071 733.84 m，最后1次的巡航路徑為613 173.60 m，總耗時(shí)13 605 ms。為了進(jìn)一步提高最短路徑規(guī)劃的效率，使用基于能耗均衡的多無人船自動(dòng)巡航路徑規(guī)劃算法。按照上文所述流程，首先對(duì)60個(gè)補(bǔ)測(cè)點(diǎn)進(jìn)行聚類處理，將其分成3個(gè)點(diǎn)簇，然后使用模擬退火算法再次計(jì)算每個(gè)點(diǎn)簇的最短巡航路徑，如圖5所示。

如圖5所示，3個(gè)點(diǎn)簇的最短巡航路徑依次是176 192.50、194 987.83、246 590.98 m。將3個(gè)點(diǎn)簇的路徑相加求和，結(jié)果為617 771.31 m，與首次計(jì)算所得結(jié)果613 173.60 m相差不大。但是聚類處理后的搜索過程僅耗時(shí)2 088 ms，相比于首次計(jì)算用時(shí)的13 605 ms，效率提升了6倍。橫向?qū)Ρ瓤梢园l(fā)現(xiàn)，3個(gè)點(diǎn)簇的最短巡航路徑仍然差距較大，為了讓多艘無人船的能耗趨于均衡，對(duì)3個(gè)點(diǎn)簇作出調(diào)整，根據(jù)點(diǎn)簇調(diào)整算法，點(diǎn)簇0需要從距離最近的點(diǎn)簇1中抽取1個(gè)點(diǎn)，點(diǎn)簇1需要從距離最近的點(diǎn)簇2中抽取2個(gè)點(diǎn)，如圖6所示。

經(jīng)過調(diào)整后，3個(gè)點(diǎn)簇的最短規(guī)劃路徑分別是204 664.82、216 269.08、220 021.11 m。最大差值從調(diào)整前的70 398.48 m變?yōu)?5 356.29 m。由此可見，點(diǎn)簇調(diào)整算法能夠有效平衡多個(gè)點(diǎn)簇之間的路徑長(zhǎng)度，從而保證了多艘無人船確定的最短巡航路徑大體相等，節(jié)約了能耗、提高了補(bǔ)測(cè)效率。

3 結(jié)束語

使用無人機(jī)測(cè)算水庫(kù)庫(kù)容時(shí)，如果待測(cè)水庫(kù)的平面面積較大，無人船的續(xù)航能力有限，無法保證一次性完成測(cè)算任務(wù)，不僅影響工作效率，而且對(duì)測(cè)算結(jié)果的精度也會(huì)產(chǎn)生影響。通過規(guī)劃無人船的最短巡航路徑，讓無人船能夠在續(xù)航范圍內(nèi)一次性完成測(cè)算任務(wù)，達(dá)到了降低能耗、提高精度的效果。使用模擬退火算法進(jìn)行無人船巡航路徑規(guī)劃，雖然能夠保證路徑最短，但是路徑尋找用時(shí)較長(zhǎng)。通過聚類處理后，路徑尋找用時(shí)變短，但是還存在不同點(diǎn)簇之間路徑差異明顯的問題。在此基礎(chǔ)上使用點(diǎn)簇調(diào)整算法，保證不同點(diǎn)簇之間的最短路徑趨于一致，在滿足最短路徑規(guī)劃要求的前提下節(jié)約了能耗。

參考文獻(xiàn)：

[1] 宋大雷，呂昆嶺，曹江麗.基于深度強(qiáng)化學(xué)習(xí)的無人船全覆蓋路徑規(guī)劃[J].現(xiàn)代電子技術(shù)，2022（22）：15-17.

[2] 吳昊，吳子昂，孟慶斌，等.水環(huán)境監(jiān)測(cè)場(chǎng)景中的自主巡航無人船系統(tǒng)[J].電子制作，2023（2）：14-17.

[3] 宋大雷，干文浩，許嚶枝.無人船實(shí)時(shí)路徑規(guī)劃與編隊(duì)控制仿真研究[J].系統(tǒng)仿真學(xué)報(bào)，2023（5）：957-970.

[4] 王朝飛，王慎執(zhí)，宋士吉.面向海域巡邏的多無人船路徑規(guī)劃方法及仿真[J].中國(guó)圖象圖形學(xué)報(bào)，2023（8）：2536-2548.

[5] 張乃天，陳世才，蒙子昕.基于改進(jìn)快速行進(jìn)法的水面無人船全局路徑規(guī)劃[J].上海海事大學(xué)學(xué)報(bào)，2023（3）：5-11.

第一作者簡(jiǎn)介：吳健（1990-），男，碩士，工程師。研究方向?yàn)楹拥揽睖y(cè)，無人船。

*通信作者：何良（1982-），男，工程碩士，高級(jí)工程師。研究方向?yàn)楹拥揽睖y(cè)，無人機(jī)，點(diǎn)云。