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

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

中圖分類號：U664.82 文獻標志碼：A 文章編號：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

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

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

1.1 模擬退火算法

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

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

， （1）

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

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

相比于數(shù)學計算，使用模擬退火算法能縮短無人船自動搜索最短路徑的用時，但是當水庫的庫容較大時，由于補測點數(shù)量較多，仍然要花費較多的時間才能搜尋到較好的路徑?；诖耍疚奶岢隽艘环N基于能耗均衡的多無人船自動巡航路徑規(guī)劃算法。其原理是：通過聚類處理，將距離較為靠近的若干個補測點劃分到同一個點簇內(nèi)，然后在點簇內(nèi)搜索最短路徑。由于點簇內(nèi)的補測點數(shù)量相對較少，可以縮短獲取最短巡航路徑的用時。同時，將補測任務(wù)平均分配給多艘無人船，每艘無人船分別完成一個點簇的路徑規(guī)劃任務(wù)，通過并行處理的方式在保證能耗均衡的前提下提升了補測效率[3]。

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

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

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

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

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

2 水庫庫容無人船自動巡航路徑規(guī)劃的仿真實驗

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

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

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

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

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

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

2.2 路徑規(guī)劃實驗

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

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

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

3 結(jié)束語

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

參考文獻：

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

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

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

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

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

第一作者簡介：吳?。?990-），男，碩士，工程師。研究方向為河道勘測，無人船。

*通信作者：何良（1982-），男，工程碩士，高級工程師。研究方向為河道勘測，無人機，點云。