基于貪心蟻群算法的無人水面艇全局路徑規劃

賀嘉　肖英杰

摘要：

為解決無人水面艇（unmanned surface vessel， USV）在地型較復雜小型水域內的全局路徑規劃問題，提出一種以貪心算法、蟻群算法、柵格法建模為基礎，通過加入雙向搜索算法來解決傳統貪心算法搜索時易陷入局部最優解等問題的貪心蟻群算法。該算法利用貪心算法規劃基礎路線，利用蟻群算法的信息素機制擺脫局部收斂狀態，并通過雙向搜索算法降低局部收斂概率。仿真結果表明：該算法搜索時間較傳統蟻群算法減少70%以上，迭代次數較傳統蟻群算法減少約85%;該算法在處理USV的全局路徑規劃問題中具有一定的有效性、合理性。

關鍵詞：

無人水面艇（USV）; 路徑規劃; 蟻群算法; 貪心算法

中圖分類號：? U675.79; TP273+.5

文獻標志碼：? A

收稿日期： 2020-04-05

修回日期： 2020-11-06

基金項目： 國家自然科學基金（51909155）

作者簡介：

賀嘉（1997—），男，湖南衡陽人，碩士研究生，研究方向為海上智能交通，（E-mail）457341658@qq.com;

肖英杰（1959—），男，廣東潮州人，教授，船長，博士，研究方向為載運工具應用工程、通航安全保障，（E-mail）xiaoyj@shmtu.edu.cn

Global path planning for unmanned surface vessels

based on? greedy ant colony algorithm

HE Jia， XIAO Yingjie

（Merchant Marine College， Shanghai Maritime University， Shanghai 201306， China）

Abstract：

In order to solve the global path planning problem for unmanned surface vessels （USVs） in small waters with complex terrain，? a greedy ant colony algorithm is proposed， where the greedy algorithm， the ant colony algorithm and the grid method modeling are based on， and the two-way search algorithm is added to solve the problem that the traditional greedy algorithm is easy to fall into the local optimal solution when searching. In the algorithm， the greedy algorithm is used to plan the basic route， the pheromone mechanism of the ant colony algorithm is used to get out of the local convergence state， and the two-way search algorithm is used to reduce the local convergence probability. The simulation results show that， the search time of the algorithm is reduced by more than 70% compared with the traditional ant colony algorithm， the number of iterations is reduced by about 85% compared with the traditional ant colony algorithm， and the algorithm is effective and reasonable in dealing with the USV global path planning problem.

Key words：

unmanned surface vessel （USV）; path planning; ant colony algorithm;? greedy algorithm

0 引 言

近年來，隨著計算機科學、傳感器、無線網絡等技術的快速發展，無人運輸設備的研究日新月異。無人水面艇（unmanned surface vessel， USV）技術得到了世界范圍內的關注和深入研究。熊勇等[1]對USV的研究現狀進行了總結，針對國內外USV研究普遍存在的問題，提出USV研究的根本目標是研發出穩定性強、通用性高、簡單好用的控制算法。王石等[2]分析了USV在軍事活動中的應用，得出USV在現代戰爭中有非常重大戰略意義的結論。無論是軍用USV還是民用USV，在復雜多變的水域內自主規劃出一條航程較短的、安全的路徑，是保證USV順利完成任務的基礎。

截至目前，國內外許多優秀學者提出了無人運輸設備路徑規劃方案。范云生等[3]通過融合電子海圖與雷達圖像對空間動態環境進行建模，并利用改進人工勢場法對USV路徑進行規劃。陶重犇等[4]用柵格法對搬運機器人工作環境進行簡化建模，并采用改進的模擬退火算法對模型進行求解。孫功武等[5]將改進的蟻群算法用于USV路徑規劃，通過在螞蟻發生不同死鎖時采取不同策略，大幅度提高了算法搜索過程中有效螞蟻的數量，加快了算法的收斂速度。DANANCIER等[6]在對無人機進行路徑規劃時發現，在障礙物隨機分布的情況下路徑點生成算法的收斂速度明顯比Dijkstra算法的快。張毅等[7]在對移動機器人進行路徑規劃時將獨狼視場機制引入精英蟻群算法中，改進了蟻群的尋徑能力并提高了算法的全局搜索能力。張岳星等[8]利用電子海圖建立靜態的三維環境模型，并使用改進的粒子群優化算法對模型進行求解，該方法基本可滿足自主式水下潛器在復雜海域航行的全局路徑規劃需求。

路徑規劃主要分為靜態路徑規劃和動態路徑規劃[9-10]。當前，無人運輸設備常用的路徑規劃算法有Dijkstra算法、貪心算法、蟻群算法

[5，7，11-12]、A*算法[11，13]、遺傳算法[14-17]等。

其中貪心算法計算量小、算法簡單，且其第一個解通常是最優解，十分適合應用于復雜度較陸地來說偏低的水域，因此本文利用貪心算法解決USV的全局路徑規劃問題。為彌補貪心算法易陷入局部最優解的缺陷，引入蟻群算法。通過貪心算法規劃USV基礎路線，通過雙向搜索算法降低算法局部收斂的概率，利用蟻群算法的信息素機制使算法擺脫局部收斂狀態。

1 基于柵格法的水域模型建立

本文運用柵格法對水域進行建模。柵格法建模是采用一系列同樣大小的柵格對水域進行建模的方

法。用柵格法建立10×10的水域模型，見圖1。圖1中：白色柵格為可行柵格，代表可行水域;黑色柵格為不可行柵格，代表不可行水域，即該水域有礙航物，USV無法安全通過;左下角黑色圓點表示USV當前所處位置;右上角方塊表示USV需要到達的位置。柵格坐標由柵格的序號表示，如第一行第一列的柵格坐標為（0，0），第一行第二列柵格坐標為（0，1）。當USV處在模型中除模型邊緣外的任意柵格時，其周圍都應存在8個柵格，此時USV可以向周圍任意一個可行柵格移動。

用柵格法建立水域模型后，USV較為復雜的工作環境被轉化為簡單的環境，USV的路徑規劃問題問題也被轉化為在兩個柵格點之間尋找最優路徑的問題。

2 改進貪心算法

2.1 傳統貪心算法

貪心算法是一種在每一步都作出當前狀態下的最佳選擇，以期得到的最終結果也是整體最優的算法。比如在背包問題中，每次都選擇單位價值最高的一樣物品裝入背包，就是一種貪心算法。如果一個問題可以使用貪心算法解決，那么在一般情況下，貪心算法會是解決這個問題的最好辦法。由于貪心算法具有高效性，且運算所得到的結果比較接近最優結果，因此貪心算法也常被用作輔助算法或者直接被用于解決一些簡單問題。

如圖2所示，USV處于柵格0中。若USV周圍的8個柵格均為可行柵格，則這8個柵格均為USV下一步可以到達的位置;若8個柵格中存在不可行柵格，

則必須

在下一步計算前除去這些柵格。找到所有下一步可以到達的柵格后，計算柵格i與目標柵格end之間的距離：

Di=（xend-xi）2+（yend-yi）2，

i=0，1，2，…，n

式中：xend和yend分別表示柵格end的橫、縱坐標;

xi和yi分別表示柵格i的橫、縱坐標。D0表示柵格0（USV所處位置）與柵格end之間的距離。

從所有可行柵格中選出距離柵格end最近的柵格，即選取滿足條件min{D1，D2，…，Dn}

到達的柵格。若找不到滿足這一條件的柵格，則算法陷入局部收斂狀態，無法繼續進行搜索。

若存在兩個柵格a和b（a，b=0，1，2，…，n;a≠b）滿足Da=Db，

即USV在路線選擇時碰到“分岔路口”時，一般隨機作出選擇進行下一步計算并對該路線的總路程進行記錄。最終進行多次迭代，保留最短的路徑。

傳統的貪心算法收斂快、計算量小，但一旦該算法陷入局部收斂狀態，就無法自行脫出。因此，即使進行多次實驗也不一定能找到起始點與終點之間的最佳路徑。

2.2 貪心算法的改進

當USV在路徑搜索過程中移動到某個不是終點的柵格，找不出滿足條件的下一個柵格時，算法就無法繼續進行，此類問題即局部收斂問題。

圖3所示為

最常見的局部收斂問題：當USV由柵格7向目標點移動時，由貪心算法計算可得向柵格0移動是最優方案;而當USV移動到柵格0后，通過計算發現無法從集合{D1，D5，D6，D7，D8}中找出小于D0的元素，即USV到達柵格0后，找不到能進行下一步計算的最優解，路徑搜索陷入停滯，局部收斂問題出現。

實際上，在利用貪心算法進行路徑搜索的過程中，只要USV前進方向上存在凹型障礙區域，算法陷入局部收斂狀態的可能性就很大。

解決該類問題的方案多為將此時USV所處的柵格加入禁忌表，即將圖3中的柵格0由可行柵格轉換為不可行柵格，以免USV再次進入該柵格。添加禁忌表的方法雖然有效，但將可行柵格轉換為不可行柵格后，路徑搜索必須從原點重新開始，會加大運算量，降低算法求得最終解的速度。

針對該類局部收斂問題，本文結合貪心算法的特點引入雙向搜索算法。雙向搜索算法，即在算法運行時同時進行兩個方向的搜索：一個是從起始點向目標點進行正向搜索，另一個是從目標點向起始點進行反向搜索。當兩個方向的搜索得到的路徑在中間交會或發生部分重疊時，搜索即可停止。

傳統貪心算法的路徑搜索是從起始點向目標點進行的正向搜索。雙向搜索算法在正向搜索的基礎上，增加了一個從目標點向起始點的反向搜索。搜索停止后，將正向搜索路徑與反向搜索路徑結合便可得出USV的最終路徑規劃結果。采用該方法對隨機生成的一張10×10水域模型進行路徑搜索，結果見圖4。

圖4a為采用傳統貪心算法計算的結果。由圖4a可知，當USV移動到坐標為（4，6）的柵格時，其周圍不存在滿足“與目標柵格之間的距離<坐標為（4，6）的柵格與目標柵格之間的距離”的可行柵格，USV的運動陷入停滯，算法被迫中斷。圖4b為在傳統貪心算法中引入雙向搜索算法后的計算結果。雙向搜索算法的正向搜索結果與傳統貪心算法的搜索結果相同，反向搜索得到的路徑與正向搜索得到的路徑交會于坐標為（5，4）的柵格。將正向與反向搜索得到的路徑相結合，便可得到最終路徑規劃結果。

通過多次實驗可知，在傳統貪心算法中引入雙向搜索算法，既不會影響算法的復雜度，又能解決大部分的局部收斂問題，大大加快了算法的收斂速度。

然而，當正向搜索和反向搜索的路徑上都存在凹型障礙區域時，用雙向搜索貪心算法也無法得出結果。此時便需結合前文所提到的添加禁忌表的方法來解決問題。在此，規定水域模型中坐標為（m，n）的柵格的一項指標Imn

Imn=1， 螞蟻優先選擇該柵格0， 禁止螞蟻選擇該柵格

式中：Imn代表坐標為（m，n）的柵格中螞蟻信息素的濃度，其中1為最高，0為最低。計算開始前，所有可行柵格中螞蟻信息素濃度都較低，而所有不可行

柵格中螞蟻信息素濃度為0。計算開始后，由貪心算法計算得到的下一步最優柵格中螞蟻信息素濃度變更為1，這樣設置的目的是加快下一步迭代的螞蟻的搜索速度。當雙向搜索中出現正向搜索路徑與反向搜索路徑無法會合的情況，算法陷入局部收斂（如圖5a所示）時，USV所處的柵格中螞蟻信息素濃度發生如下變化：

Imn=1Imn=0

即在發生局部收斂時，將正向和反向搜索路徑上USV所處的柵格由可行柵格轉換為不可行柵格。隨后算法開始進行第二次雙向搜索。本次搜索中USV不會進入初次搜索中發生局部收斂的柵格，而是跳出約束尋找更優路徑。

圖5a中，正向、反向搜索分別在坐標為（7，2）和（3，6）的柵格處陷入局部收斂，搜索中止。在第二次搜索開始時，這兩個柵格已經被更改為不可行柵格（如圖5b所示）。第二次搜索避開了第一次搜索時發生局部收斂的柵格，成功找到了一條新的最優路徑，正向、反向搜索路徑交會于坐標為（4，3）的柵格。

綜上，結合了雙向搜索算法、蟻群算法優勢的貪心算法，既能在很大程度上減少計算量，加快算法收斂速度，又能解決大部分復雜度不太高環境下的路徑尋優問題，可以用于USV的全局路徑規劃。

3 仿真驗證及結果分析

為使改進后的算法更具有說服力，在Unity3D 5.6平臺上將本文算法與傳統蟻群算法進行對比。傳統蟻群算法參數為：α=4，β=8，ρ=0.7，m=50，

其中α為信息啟發式因子，β為期望啟發式因子，ρ為信息揮發因子，m為螞蟻數量

。為驗證本文算法的優越性，在不同復雜度的水域模型上進行對比。對真實水域進行精細建模，以驗證本文算法在實際情況下運用的可行性。

3.1 20×20水域模型上實驗對比

對比圖6a與6b可知：在較簡單的水域模型上，

本文算法與傳統蟻群算法規劃出來的最終路線相似，但本文算法規劃出來的路徑略短，且轉彎次數較少。從圖6a可以看出，從右下向左上的搜索很早就遇到凹形區域因而不能繼續搜索，但此時相反方向的搜索還在繼續并最終找到一條最短路徑。由表1中的實驗數據可知：傳統蟻群算法經過21次迭代，歷時2.024 s規劃出最終路徑;本文算法僅迭代1次，歷時0.227 s就規劃出了比傳統蟻群算法更優的路徑。

為進一步了解本文算法在更復雜環境下的全局路徑規劃能力，在30×30水域模型上將本文算法與傳統蟻群算法再次進行路徑規劃對比，實驗結果見圖7。由圖7可以看出，由本文算法規劃出的最終路徑明顯更為簡單。由圖7a可以看出，本文算法在正向、反向搜索中均遇到凹形區域，因此將陷入局部收斂

的柵格加入禁忌表，然后再次進行搜索得到了最優路徑。由表2可知，本文算法的迭代次數（3次）比傳統蟻群算法的迭代次數（17次）大

大減少，在迭代時間上也有著極大的優勢，并且最終規劃出來的路徑也更優。

經過大量對比實驗可以得出：相較于傳統蟻群算法，本文算法迭代次數平均減少約85%，路徑規劃時間平均減少70%以上。其原因大致如下：本文算法通過貪心算法確定初始路徑，可以極大地減少算法迭代次數;由于螞蟻信息素的存在，本文算法不會搜索多余路徑，在尋找最優路徑上的時間也大大減少;禁忌表的添加，較好地解決了貪心算法容易陷入局部收斂的問題。

3.3 真實水域模型搭建

為驗證本文算法在真實環境下的可行性，對現實水域進行精細建模。本文選定上海海事大學臨港校區智慧湖為水域環境的建模區域。

為使水域模型與原水域相似程度更為接近，算法搜索出的路徑更優，在建模時使用的柵格極小，可近似視為坐標點。

水岸應向水域內延伸的距離S的計算公式為

S=r+R

式中：r是根據USV實際尺寸將其視為圓形時的半徑;R是為防止USV觸岸所預留的安全距離。

3.4 實驗結果及分析

為方便算法搜索，在仿真時將USV視為質點。仿真時固定目標點，通過多次變換USV初始位置觀察算法運行情況。

圖8a顯示了在初始位置與目標位置間有小型障礙物阻擋時，用本文算法進行路徑規劃的結果。其中，黑色部分為水域模型，兩個方塊分別為USV初始位置和目標位置。由圖8a可見，USV在接近水岸或水面上的障礙物（不可行區域）時，會與水岸或障礙物保持一個安全距離（S）。最終，正向和反向搜索路徑在中段交會，搜索結束，生成最優路徑。

圖8b顯示了在初始位置與目標位置間有大型障礙物阻擋時，用本文算法進行路徑規劃的結果。由圖8b可見：在本次搜索過程中，反向搜索因較大障礙物的影響而無法到達USV初始位置，陷入局部收斂;正向搜索則成功繞過障礙物并在接近目標位置的地方與反向搜索的路徑交會，搜索結束，成功生成最優路徑。

仿真結果表明，采用結合雙向搜索和蟻群算法的貪心算法進行路徑規劃時，在絕大多數情況下都能夠安全避開水域中的障礙物而成功找到一條較優路徑。

4 結束語

針對傳統的路徑搜索算法迭代次數多、運算量較大的缺點，本文以計算簡單、迭代次數少的貪心算法為基礎算法，結合雙向搜索算法、蟻群算法較好擺脫局部收斂問題的優點對算法進行改進，最終提出一種針對無人水面艇（USV）全局路徑規劃的改進貪心算法。對上海海事大學臨港校區智慧湖進行建模，并在USV初始位置與目標位置之間設置障礙物進行路徑規劃仿真，發現USV能在避開水中障礙物的前提下成功找出一條最優路徑。仿真結果表明，本文提出的算法是一種比較合理、效率較高的USV路徑搜索算法。

參考文獻：

[1]熊勇， 余俊， 張加， 等. 無人艇研究進展及發展方向[J]. 船舶工程， 2020， 42（2）： 12-19.

[2]王石， 張建強， 楊舒卉， 等. 國內外無人艇發展現狀及典型作戰應用研究[J]. 火力與指揮控制， 2019， 44（2）： 11-15. DOI： 10.3969/j.issn.1002-0640.2019.02.003.

[3]范云生， 柳健， 王國峰， 等. 基于異源信息融合的無人水面艇動態路徑規劃[J]. 大連海事大學學報， 2018， 44（1）： 9-16. DOI： 10.16411/j.cnki.issn1006-7736.2018.01.002.

[4]陶重犇， 雷祝兵， 李春光， 等. 基于改進模擬退火算法的搬運機器人路徑規劃[J]. 計算機測量與控制， 2018， 26（7）： 182-185. DOI： 10.16526/j.cnki.11-4762/tp.2018.07.040.

[5]孫功武， 蘇義鑫， 顧軼超， 等. 基于改進蟻群算法的水面無人艇路徑規劃[J/OL]. 控制與決策： 1-10[2020-11-04]. DOI： 10.13195/j.kzyjc.2019.0839.

[6]DANANCIERK， RUVIO D， SUNG I，et al. Comparison of path planning algorithms for an unmanned aerial vehicle deployment under threats[C]//9th IFAC Conference on Manufacturing Modelling， Management and Control MIM 2019. IFAC， 2019， 52（13）： 1978-1983. DOI： 10.1016/j.ifacol.2019.11.493.

[7]張毅， 權浩， 文家富. 基于獨狼蟻群混合算法的移動機器人路徑規劃[J]. 華中科技大學學報（自然科學版）， 2020， 48（1）： 127-132. DOI： 10.13245/j.hust.200123.

[8]張岳星， 王軼群， 李碩， 等. 基于海圖和改進粒子群優化算法的AUV全局路徑規劃[J]. 機器人， 2020， 42（1）： 120-128. DOI： 10.13973/j.cnki.robot.190100.

[9]劉軍， 馮碩， 任建華. 移動機器人路徑動態規劃有向D*算法[J]. 浙江大學學報（工學版）， 2020， 54（2）： 291-300. DOI： 10.3785/j.issn.1008-973X.2020.02.010.

[10]YANShuxue， LI Yiping， FENG Xisheng，et al. An AUV adaptive sampling path planning method based on online model prediction[C]//12th IFAC Conference on Control Applications in Marine Systems， Robotics， and Vehicles CAMS 2019. IFAC， 2019， 52（21）： 323-328. DOI： 10.1016/j.ifacol.2019.12.327.

[11]萬逸飛， 彭力. 改進A*蟻群算法求解機器人路徑規劃問題[J]. 傳感器與微系統， 2019， 38（12）： 153-156， 160. DOI： 10.13873/j.1000-9787（2019）12-0153-04.

[12]趙靜， 湯云峰， 蔣國平， 等. 基于改進蟻群算法的移動機器人路徑規劃[J]. 南京郵電大學學報（自然科學版）， 2019， 39（6）： 73-78. DOI： 10.14132/j.cnki.1673-5439.2019.06.011.

[13]CHENBiyu， CHEN Xiaowei， CHEN Huiping，et al. Efficient algorithm for findingk shortest paths based on reoptimization technique[J]. Transportation Research Part E， 2020， 133： 101819. DOI： 10.1016/j.tre.2019.11.013.

[14]杜勝， 劉軼華， 陳茜， 等. 基于遺傳算法的開敞水域帆船航線規劃[J]. 上海海事大學學報， 2018， 39（2）： 1-6. DOI： 10.13340/j.jsmu.2018.02.001.

[15]李天童， 寧平凡， 牛萍娟. 基于改進遺傳算法的工廠AGV安全路徑規劃[J]. 組合機床與自動化加工技術， 2020（3）： 160-163. DOI： 10.13462/j.cnki.mmtamt.2020.03.038.

[16]宋宇， 王志明. 基于改進遺傳算法的移動機器人路徑規劃[J]. 現代電子技術， 2019， 42（24）： 172-175. DOI： 10.16652/j.issn.1004-373x.2019.26.041.

[17]孫波， 姜平， 周根榮， 等. 基于改進遺傳算法的AGV路徑規劃[J]. 計算機工程與設計， 2020， 41（2）： 550-556. DOI： 10.16208/j.issn1000-7024.2020.02.038.

（編輯 賈裙平）