基于改進(jìn)A*算法的水面無(wú)人艇路徑規(guī)劃

舒?zhèn)ラ≮w建森　謝宗軒　張學(xué)生　馬欣

摘要：為解決水面無(wú)人艇（unmanned surface vessel， USV）在礙航物比較密集水域的全局路徑規(guī)劃問(wèn)題，提出一種基于改進(jìn)A*算法的路徑規(guī)劃方法。利用像素閾值法剔除船載雷達(dá)圖像中的冗余信息，并使用柵格法進(jìn)行環(huán)境建模;提出節(jié)點(diǎn)礙航物檢測(cè)法，用于優(yōu)化無(wú)人艇路徑規(guī)劃，同時(shí)改進(jìn)評(píng)價(jià)函數(shù)來(lái)減少遍歷的節(jié)點(diǎn)總數(shù);對(duì)規(guī)劃路徑上的冗余節(jié)點(diǎn)進(jìn)行平滑處理。仿真結(jié)果表明：相較于A*算法，本文提出的改進(jìn)A*算法能夠確保USV遠(yuǎn)離礙航物，且算法遍歷節(jié)點(diǎn)總數(shù)和規(guī)劃路徑上的轉(zhuǎn)折點(diǎn)都較少。

關(guān)鍵詞：? 水面無(wú)人艇（USV）; 路徑規(guī)劃; A*算法; 礙航物檢測(cè)

中圖分類(lèi)號(hào)：? U675.7; TP273文獻(xiàn)標(biāo)志碼：? A

Path planning for unmanned surface vessels based on

improved A* algorithm

Abstract： To address the global path planning issue of unmanned surface vessels （USVs） in waters with dense obstacles， this paper proposes a path planning method based on the improved A* algorithm. The redundant information of shipborne radar images is removed by the pixel threshold method， and the grid method is used to carry out the environment modeling. The node obstacle detection method is proposed to optimize the path planning of USVs， and the evaluation function is improved to reduce the total number of traversal nodes. The redundant nodes on the planned path are smoothed. The simulation results show that， compared with A* algorithm， the proposed improved A* algorithm can ensure that USVs are away from obstacles， the total number of traversal nodes is fewer， and the turning nodes on the planned path are fewer.

Key words： unmanned surface vessel （USV）; path planning; A* algorithm; obstacle detection

引言

隨著人工智能技術(shù)的快速發(fā)展，路徑規(guī)劃在移動(dòng)機(jī)器人領(lǐng)域的應(yīng)用取得了很大的成就。水面無(wú)人艇（unmanned surface vessel， USV）是一種能夠?qū)崿F(xiàn)自主避碰的水上艦艇。當(dāng)前對(duì)USV的研究主要集中在路徑規(guī)劃和自主避障等方面。USV在復(fù)雜水域完成全局路徑規(guī)劃和在特殊情況下避障的能力越突出，則說(shuō)明其智能化水平越高。[1]

路徑規(guī)劃是指在有障礙物的情況下，在起點(diǎn)與終點(diǎn)之間尋找出一條盡可能短的安全路徑[2-3]。按照對(duì)周?chē)h(huán)境感知情況的不同，路徑規(guī)劃可以分為環(huán)境信息全部掌握的全局路徑規(guī)劃和環(huán)境信息部分未知的局部路徑規(guī)劃。A*算法具有搜索效率高的優(yōu)點(diǎn)，被廣泛應(yīng)用于多種類(lèi)型的搜索問(wèn)題中。國(guó)內(nèi)外學(xué)者已經(jīng)對(duì)A*算法及其改進(jìn)算法做了廣泛的研究，并且取得了一定的成果。薛雙飛[2]將人工勢(shì)場(chǎng)法與A*算法相結(jié)合，根據(jù)不同的障礙物類(lèi)型建立不同的斥力勢(shì)場(chǎng)，并將該方法應(yīng)用于東海大橋風(fēng)機(jī)維護(hù)船舶的路徑規(guī)劃。王紅衛(wèi)等[4]提出平滑A*算法，解決了規(guī)劃路徑轉(zhuǎn)折次數(shù)多的問(wèn)題。陳豪等[5]基于A*算法，引入方向矢量以?xún)?yōu)化開(kāi)放列表。WANG等[6]將船舶轉(zhuǎn)彎半徑融入A*算法，在估值函數(shù)中引入限制搜索方向的角度成本，生成與船舶實(shí)際轉(zhuǎn)彎角度更加契合的路徑。余必秀等[7]針對(duì)船舶避碰后無(wú)法快速回到預(yù)設(shè)航線(xiàn)的問(wèn)題，在估值函數(shù)中增加一個(gè)代價(jià)值，讓無(wú)人航道測(cè)量船在估值函數(shù)的使用上有不同的選擇。王錦川[8]利用二叉堆對(duì)A*算法中的Open列表進(jìn)行維護(hù)，加快了A*算法的搜索效率。楊瑤等[9]將車(chē)輛的最大轉(zhuǎn)向角約束和最大曲率約束加入啟發(fā)式函數(shù)中，同時(shí)提出車(chē)身輪廓代價(jià)改進(jìn)拓展節(jié)點(diǎn)，使路徑更符合車(chē)輛的運(yùn)動(dòng)學(xué)特性。榮少巍[10]將最小轉(zhuǎn)彎半徑作為約束條件對(duì)傳統(tǒng)A*算法進(jìn)行改進(jìn)，同時(shí)使得A*算法可以實(shí)現(xiàn)高速與低速結(jié)合的應(yīng)用。

USV具有慣性大、時(shí)滯大的特性，且在惡劣海況下易受風(fēng)浪流的影響。USV只有與礙航物保持一定的安全距離，才能在碰撞危險(xiǎn)出現(xiàn)時(shí)有足夠的反應(yīng)時(shí)間和操縱空間。A*算法的搜索特點(diǎn)可能會(huì)使規(guī)劃路徑貼近礙航物，影響USV航行安全。鄧博文等[11]對(duì)障礙物做膨脹處理，王中玉等[12]在障礙物周?chē)O(shè)置禁止搜索區(qū)，雖然效果都較好，但都需要對(duì)環(huán)境中的障礙物進(jìn)行處理。針對(duì)A*算法應(yīng)用在USV上的缺陷，本文提出礙航物檢測(cè)方法：首先對(duì)A*算法遍歷的候選節(jié)點(diǎn)進(jìn)行篩選，使路徑上的每個(gè)節(jié)點(diǎn)都能與礙航物保持一定的安全距離;然后對(duì)評(píng)價(jià)函數(shù)進(jìn)行改進(jìn)，使算法遍歷的節(jié)點(diǎn)數(shù)更少;最后對(duì)所規(guī)劃路徑上的冗余節(jié)點(diǎn)進(jìn)行平滑處理。

1環(huán)境模型建立

USV路徑規(guī)劃的前提是搭建出合適的環(huán)境模型。目前，常用的環(huán)境建模方法有柵格法、幾何法和拓?fù)浞╗1]。由于采用柵格法規(guī)劃的環(huán)境能夠表現(xiàn)出一致性、規(guī)范性、簡(jiǎn)單性，所以本文使用柵格法建立環(huán)境模型。柵格法將環(huán)境空間劃分為多個(gè)大小相同的柵格，每個(gè)柵格都用二進(jìn)制數(shù)值表示。設(shè)整個(gè)環(huán)境空間S被劃分為a×b個(gè)大小相同的柵格，每個(gè)柵格都對(duì)應(yīng)著一個(gè)環(huán)境狀態(tài)，用Nij表示，則S可以表示為（1）每個(gè)柵格的環(huán)境狀態(tài)信息如下：Nij=0，自由空間5694CAD6-5319-4D70-9CE8-1A0831F542B3

1，礙航物（2）本文基于船載雷達(dá)圖像進(jìn)行路徑規(guī)劃，具體方法如下：（1）利用像素閾值法剔除雷達(dá)圖像中的冗余信息，如背景顏色、航向線(xiàn)和距標(biāo)圈等，只保留海冰回波（礙航物）;（2）將雷達(dá)圖像轉(zhuǎn)換為二值圖像;（3）將二值圖像柵格化。雷達(dá)圖像處理前后對(duì)比示意圖見(jiàn)圖1。本文利用像素來(lái)描述環(huán)境空間中的圖像柵格。圖像柵格化可以把雷達(dá)圖像轉(zhuǎn)化成網(wǎng)格環(huán)境地圖，給USV利用網(wǎng)格進(jìn)行路徑規(guī)劃提供所需的環(huán)境信息。

基于A*算法的移動(dòng)機(jī)器人運(yùn)動(dòng)方向通常為四鄰域方向或八鄰域方向?？紤]到USV模型的適用性和復(fù)雜性，本文采取八鄰域方向，即USV有上、下、左、右、右上、右下、左上、左下等8個(gè)運(yùn)動(dòng)方向可選擇，見(jiàn)圖2。

2A*算法的基本原理

A*算法是一種典型的啟發(fā)式算法[13-14]，主要依據(jù)評(píng)價(jià)函數(shù)拓展節(jié)點(diǎn)。評(píng)價(jià)函數(shù)表示為（3）式中：f（n）表示節(jié)點(diǎn)n的評(píng)價(jià)函數(shù);g（n）表示從起始點(diǎn)到節(jié)點(diǎn)n的實(shí)際代價(jià)值;h（n）表示從節(jié)點(diǎn)n到目標(biāo)點(diǎn)的估計(jì)代價(jià)值。h（n）對(duì)評(píng)價(jià)函數(shù)的影響是最大的，本文采用歐幾里得距離衡量h（n），即（4）式中：xn、yn分別為節(jié)點(diǎn)n的橫、縱坐標(biāo);xg、yg分別為目標(biāo)點(diǎn)的橫、縱坐標(biāo)。

A*算法根據(jù)評(píng)價(jià)函數(shù)對(duì)所有候選節(jié)點(diǎn)進(jìn)行計(jì)算，選出f（n）值最小的節(jié)點(diǎn)，再將該節(jié)點(diǎn)作為父節(jié)點(diǎn)繼續(xù)遍歷剩余節(jié)點(diǎn)，直至遍歷完所有節(jié)點(diǎn)或者成功找到目標(biāo)點(diǎn)。具體實(shí)施步驟如下：

步驟1將起始點(diǎn)放入Open列表中，并對(duì)Open列表進(jìn)行判斷。如果Open列表為空列表，則執(zhí)行步驟5，否則執(zhí)行步驟2。如果Open列表包含目標(biāo)點(diǎn)，則執(zhí)行步驟4，否則執(zhí)行步驟2。

步驟2從Open列表中選出具有最小f（n）值的節(jié)點(diǎn)，放入Closed列表中，并將其標(biāo)記為父節(jié)點(diǎn)。

步驟3考察父節(jié)點(diǎn)的8個(gè)鄰域節(jié)點(diǎn)。對(duì)于已經(jīng)在Open列表中的節(jié)點(diǎn)，若其f（n）值小于原始值，則更新它。對(duì)于已經(jīng)在Closed列表中的節(jié)點(diǎn)，跳過(guò)它，繼續(xù)搜索。如果節(jié)點(diǎn)不在兩個(gè)列表中，就將其放入Open列表中。跳到步驟1。

步驟4將目標(biāo)點(diǎn)放入Closed列表中。在Closed列表中，復(fù)原從目標(biāo)點(diǎn)到起始點(diǎn)的路徑。

步驟5結(jié)束。

3改進(jìn)的A*算法

針對(duì)A*算法規(guī)劃出的路徑貼近礙航物、遍歷節(jié)點(diǎn)數(shù)較多等問(wèn)題，采用礙航物檢測(cè)方法將距離礙航物太近的節(jié)點(diǎn)剔除，同時(shí)對(duì)評(píng)價(jià)函數(shù)進(jìn)行改進(jìn)，使算法遍歷的節(jié)點(diǎn)減少。最后對(duì)所規(guī)劃路徑上的冗余節(jié)點(diǎn)進(jìn)行平滑處理。

3.1改進(jìn)評(píng)價(jià)函數(shù)

將節(jié)點(diǎn)間的向量夾角值引入評(píng)價(jià)函數(shù)中，對(duì)其進(jìn)行改進(jìn)。如圖3所示，S（xs，ys）是起始點(diǎn)，G（xg，yg）是目標(biāo)點(diǎn)，N（xN，yN）是當(dāng)前節(jié)點(diǎn)，n（xn，yn）、m（xm，ym）是當(dāng)前節(jié)點(diǎn)的兩個(gè)候選節(jié)點(diǎn)。假設(shè)起始點(diǎn)到目標(biāo)點(diǎn)的向量為SG，起始點(diǎn)到兩個(gè)候選節(jié)點(diǎn)的向量分別為Sn、Sm，則α、β分別為向量Sn、Sm與向量SG的夾角。

任意節(jié)點(diǎn)n的評(píng)價(jià)函數(shù)可表示為

（5）

式中：f（n）、g（n）、h（n）與式（3）定義相同;θ（n）是起始點(diǎn)S到任一候選節(jié)點(diǎn)n的向量Sn與向量SG的夾角。在評(píng)價(jià)函數(shù)中增加θ（n）的目的是使算法趨向于拓展起始點(diǎn)與目標(biāo)點(diǎn)連線(xiàn)附近的節(jié)點(diǎn)。α、β越大，表明候選節(jié)點(diǎn)距離起始點(diǎn)與目標(biāo)點(diǎn)連線(xiàn)越遠(yuǎn)，算法遍歷的節(jié)點(diǎn)數(shù)會(huì)越多;α、β越小，表明候選節(jié)點(diǎn)距離起始點(diǎn)與目標(biāo)點(diǎn)連線(xiàn)越近，算法遍歷的節(jié)點(diǎn)數(shù)會(huì)越少。同時(shí)，改進(jìn)評(píng)價(jià)函數(shù)可以使算法遍歷的節(jié)點(diǎn)更加集中在起始點(diǎn)與目標(biāo)點(diǎn)連線(xiàn)附近。候選節(jié)點(diǎn)n的θ（n）的計(jì)算式為

（6）

其中：（7）

（8）

（9）

（10）θ（m）也根據(jù)式（6）計(jì)算。

3.2礙航物檢測(cè)

A*算法在應(yīng)用于機(jī)器人路徑規(guī)劃時(shí)，將機(jī)器人視為一個(gè)質(zhì)點(diǎn)，不考慮機(jī)器人的實(shí)際寬度和大小，這就使得按照規(guī)劃路徑行走的機(jī)器人會(huì)非常貼近礙航物。在水面航行的USV具有速度高、慣性大和不易操控的特點(diǎn)，如果規(guī)劃出的路徑太貼近礙航物，則極易導(dǎo)致USV與礙航物發(fā)生碰撞，因此需要讓路徑與礙航物保持一定的距離。

本文提出礙航物檢測(cè)方法，并將該方法的實(shí)施放在A*算法步驟3之前，用來(lái)確保規(guī)劃出的路徑與礙航物之間保持一定的安全距離。礙航物檢測(cè)就是判斷每個(gè)候選節(jié)點(diǎn)周?chē)欢ǚ秶鷥?nèi)是否有礙航物，如果有礙航物，就將該候選節(jié)點(diǎn)剔除。礙航物檢測(cè)方法的具體實(shí)施步驟如下：

步驟1確定待檢測(cè)的候選節(jié)點(diǎn)。圖4a中，紫色的點(diǎn)為當(dāng)前節(jié)點(diǎn)，將8個(gè)候選節(jié)點(diǎn)放入序列N（={n1，n2，…，n8}）中。

步驟2依次選取序列N中的候選節(jié)點(diǎn)。圖4b中，n1為候選節(jié)點(diǎn)之一。為保證USV與礙航物之間有足夠的安全距離，本文以?xún)蓚€(gè)柵格單位為安全距離，確定節(jié)點(diǎn)n1周?chē)?個(gè)鄰域節(jié)點(diǎn)序列M（={m1，m2，…，m8}）。

步驟3礙航物檢測(cè)。判斷n1與節(jié)點(diǎn)序列M中每一個(gè)節(jié)點(diǎn)的連線(xiàn)是否經(jīng)過(guò)礙航物。如果任何一條連線(xiàn)通過(guò)的區(qū)域都有礙航物存在，則將節(jié)點(diǎn)n1從序列N中剔除。

步驟4對(duì)沒(méi)有被剔除的候選節(jié)點(diǎn)繼續(xù)執(zhí)行A*算法剩余程序。

礙航物檢測(cè)

在算法中增加了礙航物檢測(cè)之后，算法計(jì)算量會(huì)變大，因此對(duì)已經(jīng)遍歷過(guò)的節(jié)點(diǎn)進(jìn)行標(biāo)記，不再對(duì)其進(jìn)行篩選，以提高算法搜索效率。如果水域中礙航物比較多，在確保USV航行安全的情況下，可以將檢測(cè)范圍適當(dāng)減小。比如，在本文仿真所選擇的北極冰區(qū)，礙航物比較多，如果節(jié)點(diǎn)檢測(cè)范圍設(shè)置得太大，就會(huì)出現(xiàn)找不到最優(yōu)路徑的情況，因此可將檢測(cè)范圍適當(dāng)調(diào)小。

3.3路徑平滑

用改進(jìn)的A*算法規(guī)劃出的路徑會(huì)存在轉(zhuǎn)折次數(shù)多、冗余點(diǎn)多等問(wèn)題。在實(shí)際應(yīng)用中，這種頻繁的轉(zhuǎn)向會(huì)導(dǎo)致USV產(chǎn)生大幅度的航向改變，對(duì)USV的控制系統(tǒng)產(chǎn)生不利的影響。因此，需要對(duì)規(guī)劃出的路徑進(jìn)行平滑處理，具體步驟如下：5694CAD6-5319-4D70-9CE8-1A0831F542B3

步驟1對(duì)節(jié)點(diǎn)進(jìn)行共線(xiàn)判斷，如果任一節(jié)點(diǎn)與其前后兩個(gè)節(jié)點(diǎn)共線(xiàn)，就刪除該節(jié)點(diǎn)。比如，圖5a中的節(jié)點(diǎn)c與其前后節(jié)點(diǎn)b和d共線(xiàn)，則節(jié)點(diǎn)c會(huì)被刪除，結(jié)果見(jiàn)圖5b。

步驟2刪除多余的轉(zhuǎn)折點(diǎn)，處理方法是：遍歷航線(xiàn)中剩余的所有節(jié)點(diǎn)，判斷任一節(jié)點(diǎn)（起始點(diǎn)、目標(biāo)點(diǎn)除外）前后兩個(gè)節(jié)點(diǎn)連線(xiàn)上有沒(méi)有礙航物。如果沒(méi)有礙航物，就將該中間節(jié)點(diǎn)直接刪除。比如，圖5b中節(jié)點(diǎn)b的前后節(jié)點(diǎn)a與d的連線(xiàn)上沒(méi)有礙航物，則節(jié)點(diǎn)b會(huì)被刪除，結(jié)果見(jiàn)圖5c。

3.4改進(jìn)的A*算法路徑規(guī)劃流程

改進(jìn)的A*算法路徑規(guī)劃流程見(jiàn)圖6。

4仿真實(shí)驗(yàn)

為驗(yàn)證改進(jìn)A*算法的有效性和適用性，在不同的雷達(dá)圖像上進(jìn)行實(shí)驗(yàn)。經(jīng)處理后每張雷達(dá)柵格圖像尺寸為400×300像素，即橫坐標(biāo)和縱坐標(biāo)范圍分別是[0，400]和[0，300]。每張雷達(dá)圖像上，黃色五角星為USV的起始點(diǎn)，藍(lán)色三角形為USV的目標(biāo)點(diǎn)。

4.1改進(jìn)評(píng)價(jià)函數(shù)的A*算法仿真

在兩種具有不同礙航物的雷達(dá)圖像中，給USV設(shè)置不同的起始點(diǎn)和目標(biāo)點(diǎn)，用來(lái)驗(yàn)證改進(jìn)A*算法的適用性。圖7中藍(lán)色連線(xiàn)是用A*算法搜索得到的路徑，黑色連線(xiàn)是用改進(jìn)評(píng)價(jià)函數(shù)的A*算法得到的路徑。由圖7可以很直觀地看出，改進(jìn)了評(píng)價(jià)函數(shù)的A*算法趨向于選擇起始點(diǎn)與目標(biāo)點(diǎn)連線(xiàn)附近的節(jié)點(diǎn)。

由表1可知，與A*算法相比，改進(jìn)了評(píng)價(jià)函數(shù)的A*算法遍歷節(jié)點(diǎn)總數(shù)和節(jié)點(diǎn)向量夾角總和都是較小的。這表明，本文對(duì)A*算法的改進(jìn)具有明顯的效果，能夠使得算法遍歷的節(jié)點(diǎn)更少，且具有目的性。

4.2進(jìn)行礙航物檢測(cè)的A*算法仿真

為驗(yàn)證礙航物檢測(cè)方法能夠使USV航線(xiàn)遠(yuǎn)離礙航物，在兩種不同的雷達(dá)圖像上進(jìn)行仿真實(shí)驗(yàn)。從圖7b和7d可以看出，A*算法規(guī)劃出的路徑（藍(lán)色連線(xiàn)）容易出現(xiàn)距離礙航物較近的情況，而對(duì)候選節(jié)點(diǎn)進(jìn)行礙航物檢測(cè)的改進(jìn)A*算法規(guī)劃出的路徑（黑色連線(xiàn)）能夠遠(yuǎn)離礙航物，保證了USV航行安全。表1改進(jìn)評(píng)價(jià)函數(shù)的A*算法與A*算法數(shù)據(jù)對(duì)比圖7子圖

序號(hào)起始點(diǎn)，目標(biāo)點(diǎn)A*算法遍歷

節(jié)點(diǎn)總數(shù)DA*算法遍歷

節(jié)點(diǎn)總數(shù)A*算法節(jié)點(diǎn)向量

夾角總和/（°）DA*算法節(jié)點(diǎn)向量

夾角總和/（°）a（350，100）， （200，150）1 8401 2162 121479b（320，200）， （120，100）1 6481 6003 7901 342c（350，100）， （200，150）2 9761 2402 1091 325d（380，120）， （80，250）5 5842 7205 0053 067注：改進(jìn)評(píng)價(jià)函數(shù)的A*算法用DA*算法表示

4.3路徑平滑

用改進(jìn)的A*算法進(jìn)行USV路徑規(guī)劃，并對(duì)規(guī)劃出的路徑進(jìn)行平滑處理。平滑處理前后的路徑見(jiàn)圖8。由圖8可以看出，平滑處理能夠?qū)⒍嘤嗟墓?jié)點(diǎn)刪除，最終剩余的轉(zhuǎn)折點(diǎn)也僅剩6個(gè)。本例中，改進(jìn)A*算法生成路徑所用時(shí)間是103 ms，改進(jìn)A*算法生成路徑后再進(jìn)行平滑處理所用時(shí)間是112 ms。這說(shuō)明改進(jìn)A*算法可以在不增加太多時(shí)間的情況下，生成能夠與礙航物保持安全距離的路徑，而且遍歷節(jié)點(diǎn)更少，轉(zhuǎn)折點(diǎn)也大幅減少，更加適用于USV航行。

圖9是基于本文提出的改進(jìn)A*算法得到的其他路徑規(guī)劃結(jié)果。由圖9可知，改進(jìn)A*算法規(guī)劃出的路徑均能遠(yuǎn)離礙航物，且效果較好。

5結(jié)論

針對(duì)A*算法規(guī)劃路徑存在較多冗余點(diǎn)、貼近礙航物等問(wèn)題，提出采用礙航物檢測(cè)方法篩選出比較安全的候選節(jié)點(diǎn)，同時(shí)在評(píng)價(jià)函數(shù)中引入節(jié)點(diǎn)向量夾角值進(jìn)行改進(jìn)，并通過(guò)對(duì)規(guī)劃路徑的平滑處理去除冗余點(diǎn)，最終提出一種基于改進(jìn)A*算法的水面無(wú)人艇（USV）路徑規(guī)劃方法。仿真實(shí)驗(yàn)表明，本文的改進(jìn)方法能夠生成遠(yuǎn)離礙航物的USV路徑，改進(jìn)后的A*算法趨向于選擇起始點(diǎn)與目標(biāo)點(diǎn)連線(xiàn)附近的節(jié)點(diǎn)，遍歷的節(jié)點(diǎn)總數(shù)明顯減少，平滑處理后生成的路徑更符合USV實(shí)際航行特性，能夠解決USV在內(nèi)河航道和沿海等礙航物密集水域的路徑規(guī)劃問(wèn)題。

參考文獻(xiàn)：

[1]莊佳園， 萬(wàn)磊， 廖煜雷， 等. 基于電子海圖的水面無(wú)人艇全局路徑規(guī)劃研究[J]. 計(jì)算機(jī)科學(xué)， 2011， 38（9）： 211214， 219. DOI： 10.3969/j.issn.1002137X.2011.09.049.

[2]薛雙飛. 基于改進(jìn)A*算法的近海船舶路徑規(guī)劃[D]. 武漢： 武漢理工大學(xué)， 2018.

[3]ZUO L， GUO Q， XU X， et al. A hierarchical path planning approach based on A* and leastsquares policy iteration for mobile robots[J]. Neurocomputing， 2015， 170： 257266. DOI： 10.1016/j.neucom.2014.09.092.

[4]王紅衛(wèi)， 馬勇， 謝勇， 等. 基于平滑A*算法的移動(dòng)機(jī)器人路徑規(guī)劃[J]. 同濟(jì)大學(xué)學(xué)報(bào)（自然科學(xué)版）， 2010， 38（11）： 16471650， 1655. DOI： 10.3969/j.issn.0253374x.2010.11.016.

[5]陳豪， 李勇， 羅靖迪. 基于改進(jìn)A*算法優(yōu)化的移動(dòng)機(jī)器人路徑規(guī)劃研究[J]. 自動(dòng)化與儀器儀表， 2018（12）： 14. DOI： 10.14016/j.cnki.10019227.2018.12.001.

[6]WANG Z， XIANG X B. Improved A star algorithm for path planning of marine robot[C]//2018 37th Chinese Control Conference. IEEE， 2018： 54105414. DOI： 10.23919/ChiCC.2018.8483946.5694CAD6-5319-4D70-9CE8-1A0831F542B3

[7]余必秀， 初秀民， 柳晨光， 等. 基于改進(jìn)A*算法的無(wú)人航道測(cè)量船路徑規(guī)劃方法[J]. 武漢大學(xué)學(xué)報(bào)（信息科學(xué)版）， 2019， 44（8）： 12581264. DOI： 10.13203/j.whugis20170239.

[8]王錦川. 自主式水面航行器導(dǎo)航與制導(dǎo)算法的研究[D]. 大連： 大連海事大學(xué)， 2014.

[9]楊瑤， 付克昌， 蔣濤， 等. 改進(jìn)A*算法的智能車(chē)路徑規(guī)劃研究[J]. 計(jì)算機(jī)測(cè)量與控制， 2020， 28（10）： 170176. DOI： 10.16526/j.cnki.114762/tp.2020.10.035.

[10]榮少巍. 基于改進(jìn)A*算法的水下航行器自主搜索航跡規(guī)劃[J]. 電子科技， 2015， 28（4）： 1719， 22. DOI： 10.16180/j.cnki.issn10077820.2015.04.005.

[11]鄧博文， 張春華， 李娟， 等. 局部路徑規(guī)劃在無(wú)人工程機(jī)械作業(yè)中的應(yīng)用[J]. 兵工自動(dòng)化， 2016， 35（10）： 7073， 79. DOI： 10.7690/bgzdh.2016.10.018.

[12]王中玉， 曾國(guó)輝， 黃勃， 等. 改進(jìn)A*算法的機(jī)器人全局最優(yōu)路徑規(guī)劃[J]. 計(jì)算機(jī)應(yīng)用， 2019， 39（9）： 25172522. DOI： 10.11772/j.issn.10019081.2019020284.

[13]CHEN J C， LI M Y， YUAN Z Y， et al. An improved A* algorithm for UAV path planning problems[C]//2020 IEEE 4th Information Technology， Networking， Electronic and Automation Control Conference. IEEE， 2020： 958962. DOI： 10.1109/ITNEC48623.2020.9084806.

[14]陸皖麟， 雷景森， 邵炎. 基于改進(jìn)A*算法的移動(dòng)機(jī)器人路徑規(guī)劃[J]. 兵器裝備工程學(xué)報(bào)， 2019， 40（4）： 197201. DOI： 10.11808/bqzbgcxb2019.04.048.

（編輯賈裙平）

收稿日期： 20210429修回日期： 2021-06-18

基金項(xiàng)目： 國(guó)家自然科學(xué)基金（51709167）;國(guó)家重點(diǎn)研發(fā)計(jì)劃（2019YFB1600605）;上海市科技創(chuàng)新行動(dòng)計(jì)劃（18DZ1206101）

作者簡(jiǎn)介： 舒?zhèn)ラ?995—），男，安徽宿州人，碩士研究生，研究方向?yàn)榇皩?dǎo)航與海上通信，（Email）15755782120@163.com;

趙建森（1983—），男，黑龍江牡丹江人，副教授，博士，研究方向?yàn)橹悄芡ㄐ?、微波和天線(xiàn)，（Email）7230981@163.com05694CAD6-5319-4D70-9CE8-1A0831F542B3