多方向無(wú)人水面艇路徑規(guī)劃算法

童心赤，張華軍，郭 航

（武漢理工大學(xué)自動(dòng)化學(xué)院，武漢 430070）

（?通信作者電子郵箱zhanghj@whut.edu.cn）

0 引言

近年來(lái)，隨著無(wú)人平臺(tái)在軍事和民用等企業(yè)中的推廣，無(wú)人水面艇作為一種能夠在復(fù)雜海洋環(huán)境下自主航行并完成各項(xiàng)任務(wù)的水面平臺(tái)受到了極大關(guān)注［1-3］。路徑規(guī)劃是無(wú)人艇自主控制部分的關(guān)鍵要素，其任務(wù)是對(duì)當(dāng)前海洋環(huán)境信息進(jìn)行感知，對(duì)收集的信息進(jìn)行分析計(jì)算，實(shí)現(xiàn)有效且安全的路徑規(guī)劃。過(guò)去，最佳路徑通常與最短路徑相一致，隨著此問(wèn)題的定義不斷發(fā)展，最佳路徑的選取已與最小行進(jìn)距離、平均高度、燃油消耗、雷達(dá)輻射等諸多因素有關(guān)，因此相關(guān)研究工作通常選擇啟發(fā)式搜索算法來(lái)實(shí)現(xiàn)路徑規(guī)劃［4］。目前對(duì)無(wú)人艇路徑規(guī)劃的方法主要有遺傳算法［5-6］、粒子群算法［7-8］、人工勢(shì)場(chǎng)算法［9-11］、A*算法［12-14］等，其中遺傳算法與粒子群算法等仿生進(jìn)化算法能有效利用已獲取的環(huán)境信息，同時(shí)又能不斷探索新路徑，避免了復(fù)雜的數(shù)學(xué)計(jì)算。另外人工勢(shì)場(chǎng)法通過(guò)產(chǎn)生包括排斥力和吸引力的勢(shì)場(chǎng)來(lái)描述障礙物和目標(biāo)點(diǎn)對(duì)路徑搜索的影響，但在解決大規(guī)模問(wèn)題時(shí)易陷入局部最優(yōu)解。A*算法是一類適用于全局環(huán)境信息已知的路徑規(guī)劃方法，它利用啟發(fā)函數(shù)值來(lái)估計(jì)任意點(diǎn)到目標(biāo)點(diǎn)的遠(yuǎn)近程度，從而減少搜索空間，提高搜索效率。

目前普遍使用A*算法實(shí)現(xiàn)無(wú)人艇在不確定的海洋環(huán)境中的路徑規(guī)劃，但該算法生成的路徑只以路徑長(zhǎng)度為優(yōu)化目標(biāo)，沒(méi)有考慮路徑的安全性與平滑度等因素。文獻(xiàn)［15］為避免障礙物與無(wú)人艇距離過(guò)近，對(duì)障礙物進(jìn)行一定的膨脹處理，結(jié)果顯示規(guī)劃的路徑具有較好的安全性，但該方法并不適用于復(fù)雜的海況環(huán)境；文獻(xiàn)［16］通過(guò)評(píng)估與障礙物間應(yīng)保持的最佳距離建立無(wú)人艇安全模型，并采用三次樣條插值算法擬合離散的路徑節(jié)點(diǎn)以獲得平滑連續(xù)的路徑；文獻(xiàn)［17］以三階貝塞爾曲線為基礎(chǔ)設(shè)計(jì)了滿足二階幾何連續(xù)的路徑平滑算法，并對(duì)平滑后的路徑進(jìn)行碰撞檢測(cè)，仿真結(jié)果表明該算法能夠有效規(guī)劃出安全平滑的路徑。

針對(duì)無(wú)人水面艇路徑規(guī)劃問(wèn)題，本文首先結(jié)合電子海圖生成柵格化環(huán)境信息，建立無(wú)人艇安全區(qū)域模型并以此作為生成最優(yōu)路徑點(diǎn)的安全距離約束；其次針對(duì)常規(guī)A*算法生成的路徑轉(zhuǎn)折次數(shù)多且轉(zhuǎn)折角大等問(wèn)題，設(shè)計(jì)一種多方向A*優(yōu)化算法與路徑平滑算法以規(guī)劃一條距離更短且更有效的受約束的全局最優(yōu)路徑；最后仿真結(jié)果驗(yàn)證了該改進(jìn)算法的有效性和可行性。

1 模型建立

1.1 無(wú)人水面艇安全區(qū)域建模

為精確描述無(wú)人水面艇路徑規(guī)劃時(shí)的位置與狀態(tài)，本文所研究的無(wú)人艇均為六自由度運(yùn)動(dòng)學(xué)模型，在航行過(guò)程中可產(chǎn)生6 個(gè)自由度的運(yùn)動(dòng)信息?？紤]到無(wú)人艇在航行過(guò)程中需要較大的運(yùn)動(dòng)空間，在路徑規(guī)劃時(shí)不能簡(jiǎn)單地當(dāng)作一個(gè)質(zhì)點(diǎn)處理，因此設(shè)計(jì)一半徑為R 的圓形區(qū)域包圍無(wú)人艇作為生成最佳航路點(diǎn)的安全距離約束。半徑R 代表安全距離，安全距離約束下的路徑規(guī)劃應(yīng)保證無(wú)人艇與障礙物的最短距離大于安全距離，解決了無(wú)人艇在實(shí)際航行中的安全問(wèn)題。其搜索原理如圖1所示。

圖1 基于安全區(qū)域的路徑搜索原理Fig.1 Principle of path search based on safe area

1.2 環(huán)境建模

為便于實(shí)現(xiàn)路徑規(guī)劃，首先應(yīng)建立無(wú)人艇的航行環(huán)境模型，將實(shí)際的海洋環(huán)境預(yù)處理為便于在計(jì)算機(jī)中表示的連接圖，同時(shí)保留必要的原始信息。目前常用的環(huán)境建模方法有可視圖法［18］、柵格法［19］、拓?fù)鋱D法［20］等，本文采用柵格法將實(shí)際電子海圖轉(zhuǎn)化為二進(jìn)制網(wǎng)格圖，建立柵格化地圖模型，并將以經(jīng)緯度表示的導(dǎo)航數(shù)據(jù)轉(zhuǎn)換到柵格地圖坐標(biāo)系中。在柵格圖中，定義每一單位柵格狀態(tài)為H(x，y)，其中x、y分別代表柵格的橫向與縱向位置：白色部分H(x，y)=0表示可行區(qū)域；黑色部分H(x，y)=1 表示障礙物，這使得無(wú)人艇碰撞的風(fēng)險(xiǎn)度僅取決于柵格狀態(tài)值。對(duì)某一海域進(jìn)行柵格化處理，將環(huán)境信息離散化為一系列的二值化柵格，處理結(jié)果如圖2所示。

圖2 環(huán)境信息柵格處理圖Fig.2 Rasterization processing chart of environment information

為實(shí)現(xiàn)無(wú)人艇實(shí)時(shí)路徑導(dǎo)航，現(xiàn)將每一時(shí)刻的位置信息（經(jīng)度與緯度值）與柵格節(jié)點(diǎn)一一對(duì)應(yīng)。假設(shè)某一海圖內(nèi)的最大經(jīng)度為maxlon，最小經(jīng)度為minlon，最大緯度為maxlat，最小緯度為minlat，對(duì)應(yīng)的柵格地圖橫向劃分為a 個(gè)柵格，縱向劃分為b個(gè)柵格，則各經(jīng)緯度對(duì)應(yīng)的具體柵格位置為：

其中：floor 操作為取整運(yùn)算；x，y 分別為對(duì)應(yīng)柵格的橫向與縱向位置；lon，lat分別為當(dāng)前位置的經(jīng)度與緯度信息。

2 基于改進(jìn)A*算法的路徑規(guī)劃

A*算法作為一種啟發(fā)式搜索算法，根據(jù)啟發(fā)函數(shù)以最小代價(jià)快速返回最優(yōu)路徑，保證了路徑完整性以及搜索高效性，但是常規(guī)A*算法僅以路徑長(zhǎng)度作為啟發(fā)函數(shù)值，規(guī)劃出的路徑并不能有效引導(dǎo)無(wú)人艇在復(fù)雜海洋環(huán)境下安全平滑的運(yùn)動(dòng)。

針對(duì)該問(wèn)題，本文首先根據(jù)無(wú)人艇安全區(qū)域模型，建立安全距離約束下的A*啟發(fā)函數(shù)來(lái)搜索最短路徑。然后設(shè)計(jì)一種多方向A*搜索算法減少并修正不必要的路徑節(jié)點(diǎn)，獲得多方向A*優(yōu)化路徑。最后建立平滑處理安全區(qū)域，在此區(qū)域約束下采用三次樣條插值算法擬合離散的關(guān)鍵路徑節(jié)點(diǎn)以獲得連續(xù)平滑的路徑。

2.1 安全距離約束下的A*啟發(fā)函數(shù)

基于上述構(gòu)建的柵格化地圖模型，采用具有安全距離約束的A*算法以實(shí)現(xiàn)路徑規(guī)劃。在柵格地圖中，A*算法采用啟發(fā)函數(shù)f(n)來(lái)估計(jì)地圖上任意柵格到目標(biāo)柵格的代價(jià)，從而引導(dǎo)搜索方向。函數(shù)f(n)表達(dá)式如下：

其中：g(n)為各單元柵格到起始柵格的距離，h(n)為各單元柵格到目標(biāo)柵格的啟發(fā)式代價(jià)。

如圖3 所示，在柵格地圖中，無(wú)人艇運(yùn)動(dòng)位置可由某一具體柵格表示，將A*搜索方式設(shè)置為八方向搜索，即與當(dāng)前柵格相鄰的八個(gè)柵格作為無(wú)人艇下一時(shí)刻的可選位置。在安全距離約束下，使用八方向A*算法搜索各柵格節(jié)點(diǎn)，設(shè)置各柵格對(duì)應(yīng)的啟發(fā)式代價(jià)為：

式中：DE為柵格到目標(biāo)柵格E 的距離，l 為柵格到周圍障礙物的最短距離，R 為無(wú)人艇安全半徑。l ≥R 代表當(dāng)前位置無(wú)人艇安全區(qū)域內(nèi)不存在障礙物；相反，l ＜R 則代表安全區(qū)域內(nèi)存在障礙物。

圖3 安全距離約束下的八方向搜索原理Fig.3 Principle of eight-directional search under safety distance constraint

根據(jù)式（3），安全距離約束下各柵格的啟發(fā)函數(shù)可定義為：

式中DS為柵格到起始柵格S的距離。

2.2 多方向A*搜索算法

八方向A*搜索算法只能以45°和90°方向作為路徑搜索選項(xiàng)，就整體路徑而言，該搜索方式并不能保證最優(yōu)性。因此以路徑距離最短為優(yōu)化目標(biāo)對(duì)已規(guī)劃出的路徑節(jié)點(diǎn)進(jìn)行調(diào)整以實(shí)現(xiàn)多方向A*搜索，定義某一路徑起點(diǎn)為PS、終點(diǎn)為PE、中間節(jié)點(diǎn)為Pi(i=1，2，…，n)，其具體步驟如下。

步驟1 提取安全距離約束下八方向A*算法規(guī)劃的路徑PS→P1→P2→…→Pi→PE中所有節(jié)點(diǎn)。

步驟2 從起點(diǎn)PS開(kāi)始判斷節(jié)點(diǎn)Pi(Pi=PS)與剩余節(jié)點(diǎn)的相連路徑Pi→Pi+1(Pi+1=P1，P2，…，PE)是否滿足安全距離約束，即判斷相連路徑上所有節(jié)點(diǎn)到障礙物的距離是否小于安全半徑。記錄滿足約束條件的最靠后節(jié)點(diǎn)Pj1。若Pj1=PE則執(zhí)行步驟4，若Pj1≠PE則執(zhí)行步驟3。

步驟3 判斷節(jié)點(diǎn)Pjk(Pjk=Pj1)與剩余節(jié)點(diǎn)的相連路徑是否滿足安全距離約束，記錄滿足約束條件的最靠后節(jié)點(diǎn)Pj2。若Pj2=PE則執(zhí)行步驟4，若Pj2≠PE則重復(fù)執(zhí)行步驟3。

步驟4 輸出節(jié)點(diǎn)Pi的最終優(yōu)化路徑Path_i 為：PS→…→Pi→Pj1→Pj2→…→PE。若Pi=PE則執(zhí)行步驟5，若Pi≠PE則令Pi=Pi+1并執(zhí)行步驟2。

步驟5 比較所有節(jié)點(diǎn)優(yōu)化路徑長(zhǎng)度，選擇其中最短路徑作為多方向A*搜索算法優(yōu)化路徑。

在柵格圖中，假設(shè)某一路徑的路徑節(jié)點(diǎn)為P1，P2，…，Pm，則該路徑長(zhǎng)度DP可計(jì)算為：其中：Pi(x)、Pi(y)表示節(jié)點(diǎn)的橫坐標(biāo)和縱坐標(biāo)，m為路徑的節(jié)點(diǎn)數(shù)。

其次在多方向優(yōu)化過(guò)程中，需判斷兩節(jié)點(diǎn)相連路徑是否安全，因此需計(jì)算路徑所經(jīng)過(guò)的所有柵格是否滿足安全距離約束。假設(shè)兩柵格P(i1，j1)和P(i2，j2)之間的坐標(biāo)位置差異為Δi、Δj，且i1＜i2、j1＜j2。若Δi ＜Δj 則路徑所有柵格坐標(biāo)位置計(jì)算方法如下：

同理，若Δi ＞Δj 則被路徑所有柵格坐標(biāo)位置計(jì)算方法如下：

如圖4 所示，現(xiàn)基于傳統(tǒng)八方向A*算法得到路徑1 為PS→P1→P2→P3→P4→P5→P6→P7→PE，對(duì) 該路徑進(jìn)行多方向搜索優(yōu)化處理，其具體優(yōu)化步驟如下。為便于描述優(yōu)化過(guò)程，圖中柵格為實(shí)際柵格放大所得，并不代表相連路徑與障礙物間的實(shí)際距離。

圖4 多方向A*搜索算法示例圖Fig.4 Example of multi-directional A*search algorithm

取出路徑所有節(jié)點(diǎn)，從節(jié)點(diǎn)PS開(kāi)始依次判斷該點(diǎn)與節(jié)點(diǎn)P1，P2，P3，P4，P5，P6，P7，PE的相連路徑是否滿足安全距離約束，取出滿足約束條件的最靠后節(jié)點(diǎn)P4。然后依次判斷節(jié)點(diǎn)P4與節(jié)點(diǎn)P5，P6，P7，PE的相連路徑是否滿足約束條件，同樣取出滿足約束條件的最靠后節(jié)點(diǎn)PE，最后輸出節(jié)點(diǎn)PS的優(yōu)化路徑為Path_S：PS→P4→PE。

路徑剩余節(jié)點(diǎn)P1，P2，P3，P4，P5，P6，P7的優(yōu)化步驟與節(jié)點(diǎn)PS一致，依次得到各節(jié)點(diǎn)的優(yōu)化路徑為：

Path_1：PS→P1→P4→PE

Path_2：PS→P1→P2→P4→PE

Path_3：PS→P1→P2→P3→P6→P7→PE

Path_4：PS→P4→PE

Path_5：PS→P4→P5→P6→P7→PE

Path_6：PS→P4→P5→P6→PE

Path_7：PS→P4→P5→P6→P7→PE

最后依次比較各優(yōu)化路徑長(zhǎng)度大小并取出其中較短路徑，得到最終優(yōu)化路徑2為PS→P4→PE，明顯相較于路徑1該路徑長(zhǎng)度大大減小且規(guī)劃更為合理。

2.3 多方向A*搜索算法

路徑由多方向A*算法優(yōu)化后，雖刪除并整合了不必要的節(jié)點(diǎn)，但優(yōu)化路徑仍由許多剩余節(jié)點(diǎn)相連的短線段組成，導(dǎo)致路徑轉(zhuǎn)折角較大。針對(duì)該問(wèn)題，本文采用與原始路徑偏差較小的三次樣條插值算法進(jìn)一步改善路徑的平滑性。該算法的主要原理是使用由三階多項(xiàng)式組成的樣條來(lái)連接一組路徑節(jié)點(diǎn)，通過(guò)求解此多項(xiàng)式以擬合原路徑。若給定n個(gè)路徑節(jié)點(diǎn)，則存在n -1個(gè)節(jié)點(diǎn)區(qū)間，設(shè)每個(gè)區(qū)間[xk，xk+1]的三次樣條函數(shù)為：

為保證生成的路徑光滑連續(xù)，該多項(xiàng)式應(yīng)滿足以下約束條件：

根據(jù)式（9），對(duì)所有路徑節(jié)點(diǎn)區(qū)間進(jìn)行平滑處理可獲得原路徑的擬合平滑曲線。而多方向A*搜索算法新生成的路徑相鄰節(jié)點(diǎn)距離較遠(yuǎn)，導(dǎo)致平滑曲線與原路徑擬合程度較差。因此本研究?jī)H對(duì)路徑關(guān)鍵節(jié)點(diǎn)即航向改變節(jié)點(diǎn)進(jìn)行平滑處理，假設(shè)某一關(guān)鍵節(jié)點(diǎn)為Pi(xi，f(xi))，則取該節(jié)點(diǎn)前后相鄰四個(gè)節(jié)點(diǎn)Pi-2、Pi-1、Pi+1、Pi+2生成4 個(gè)節(jié)點(diǎn)區(qū)間以獲得關(guān)鍵節(jié)點(diǎn)平滑曲線。

為保障路徑的安全性，消除平滑處理所造成的路徑變化影響，設(shè)計(jì)一半徑為RS的圓形區(qū)域包圍路徑關(guān)鍵節(jié)點(diǎn)作為平滑區(qū)域。如圖5 所示，結(jié)合安全半徑R，將關(guān)鍵節(jié)點(diǎn)的安全區(qū)域擴(kuò)大為半徑R+RS的圓形區(qū)域。因此對(duì)關(guān)鍵節(jié)點(diǎn)平滑處理應(yīng)滿足條件：

式中l(wèi)為關(guān)鍵節(jié)點(diǎn)到障礙物的最短距離。

圖5 關(guān)鍵節(jié)點(diǎn)平滑處理的安全區(qū)域示例圖Fig.5 Example diagram of safe area smoothed by key nodes

3 基于改進(jìn)A*算法的路徑規(guī)劃

本實(shí)驗(yàn)采用微軟Core i5-4200M 處理器，主頻為2.5 GHz，內(nèi)存為8 GB。在Python 3.7 環(huán)境下，為驗(yàn)證上述算法的可行性，現(xiàn)提取經(jīng)度范圍為112.513 926°E ～112.700 695°E、緯度范圍為21.570 176°N ～21.735 468°N 的實(shí)際海上環(huán)境信息，并對(duì)其進(jìn)行柵格化處理，設(shè)置每個(gè)柵格代表的橫向與縱向?qū)嶋H距離均為20 m，處理結(jié)果如圖2 所示。根據(jù)無(wú)人艇操縱特性與航行環(huán)境，將安全半徑R 設(shè)置為20 m、60 m 與100 m，分別對(duì)應(yīng)1個(gè)、3個(gè)、5個(gè)柵格距離。

圖6 不同安全距離下的路徑規(guī)劃對(duì)比Fig.6 Comparison of path planning under different safety distances

將所設(shè)置的三種不同安全半徑作為無(wú)人艇的安全距離約束，設(shè)置路徑起始點(diǎn)為（100，280），目標(biāo)點(diǎn)為（320，20），重復(fù)進(jìn)行20次路徑規(guī)劃。圖6顯示了不同安全距離約束下的路徑規(guī)劃結(jié)果，三種路徑存在明顯差別，其中安全半徑越大的路徑距障礙物越遠(yuǎn)。

各路徑上的節(jié)點(diǎn)到周圍障礙物的最短距離如圖7 所示，橫坐標(biāo)代表路徑節(jié)點(diǎn)位置，縱坐標(biāo)代表各路徑節(jié)點(diǎn)到周圍障礙物的最短距離。其中所標(biāo)記的黑色節(jié)點(diǎn)為各路徑上距障礙物最近的節(jié)點(diǎn)，該點(diǎn)縱坐標(biāo)值均等于所設(shè)置的安全半徑大小，可見(jiàn)路徑節(jié)點(diǎn)均符合安全距離約束。

圖7 不同路徑節(jié)點(diǎn)與障礙物的最短距離對(duì)比Fig.7 Comparison of the shortest distances between different path nodes and obstacles

因此由圖6、圖7 可知：安全距離約束下的A*啟發(fā)函數(shù)能夠準(zhǔn)確搜索到一條從起點(diǎn)到終點(diǎn)的安全路徑。

在不同安全距離約束下，各路徑的總節(jié)點(diǎn)數(shù)、路徑長(zhǎng)度與規(guī)劃時(shí)間具體對(duì)比結(jié)果如表1 所示。隨著安全半徑的增加，路徑總節(jié)點(diǎn)數(shù)以及路徑長(zhǎng)度均小幅度地增加。另外安全半徑為R=60 m 與R=100 m 的規(guī)劃時(shí)間較R=20 m 分別增加了0.4 s 和1.77 s，這是由于路徑規(guī)劃過(guò)程中安全半徑設(shè)置得越大，需搜索的柵格節(jié)點(diǎn)增加得越多，所需的計(jì)算成本也更高。

表1 不同安全距離下的路徑規(guī)劃結(jié)果Tab.1 Path planning results under different safety distances

另外，為驗(yàn)證多方向A*搜索算法以及路徑平滑算法性能，本文在上述仿真的基礎(chǔ)上設(shè)置平滑區(qū)域半徑RS=40 m，并對(duì)R=60 m 的常規(guī)A*搜索路徑重復(fù)進(jìn)行20 次優(yōu)化平滑處理。常規(guī)A*搜索路徑經(jīng)多方向A*搜索算法優(yōu)化后，僅由起始點(diǎn)、目標(biāo)點(diǎn)以及三個(gè)關(guān)鍵節(jié)點(diǎn)相連而成。多方向優(yōu)化路徑上各節(jié)點(diǎn)到障礙物的最短距離如圖8 所示，其中橫坐標(biāo)代表節(jié)點(diǎn)位置，縱坐標(biāo)代表節(jié)點(diǎn)距障礙物的最短距離。另外所標(biāo)記的黑色實(shí)心節(jié)點(diǎn)代表優(yōu)化路徑上距離障礙物最近的節(jié)點(diǎn)，黑色空心節(jié)點(diǎn)則為路徑上的三個(gè)關(guān)鍵節(jié)點(diǎn)。

圖8 多方向優(yōu)化路徑節(jié)點(diǎn)與障礙物最短距離圖Fig.8 The shortest distance between nodes of multi-directional optimized path and obstacles

由圖8 可知：多方向優(yōu)化路徑上距障礙物的最短距離為63.2 m，符合半徑R=60 m 的安全約束。另外路徑上關(guān)鍵節(jié)點(diǎn)距障礙物的最短距離分別為174.1 m、72.1 m、72.6 m，而關(guān)鍵節(jié)點(diǎn)平滑處理安全半徑為R+RS=100 m，可見(jiàn)僅第一個(gè)關(guān)鍵節(jié)點(diǎn)滿足平滑處理約束條件。對(duì)該關(guān)鍵節(jié)點(diǎn)進(jìn)行平滑處理后的最終優(yōu)化路徑及優(yōu)化結(jié)果如圖9以及表2所示。

圖9 不同算法優(yōu)化的路徑Fig.9 Optimized paths of different algorithms

由圖9、表2 可知：改進(jìn)A*多方向搜索算法可以有效地整合并去除傳統(tǒng)路徑中多余的節(jié)點(diǎn)，減少路徑長(zhǎng)度，其中路徑節(jié)點(diǎn)數(shù)與路徑長(zhǎng)度均明顯小于其余三種算法。同樣改進(jìn)A*算法消除了路徑轉(zhuǎn)折次數(shù)多且轉(zhuǎn)折角較大的問(wèn)題，轉(zhuǎn)向次數(shù)減少至3 次，在一定程度上達(dá)到最優(yōu)。另外改進(jìn)A*算法與其余三種算法時(shí)間復(fù)雜度均為O(n2)，雖然搜索節(jié)點(diǎn)數(shù)的增加導(dǎo)致路徑規(guī)劃時(shí)間小幅度地提高，但它始終提供一條距離成本更低且轉(zhuǎn)向次數(shù)更少的路徑，這更加符合無(wú)人艇路徑規(guī)劃時(shí)的實(shí)際需求。

4 結(jié)語(yǔ)

針對(duì)無(wú)人水面艇路徑規(guī)劃時(shí)的安全性、經(jīng)濟(jì)性及實(shí)用性要求，本研究改進(jìn)A*算法取得了較好的效果。通過(guò)建立無(wú)人艇安全區(qū)域模型，使該模型作為生成最優(yōu)路徑點(diǎn)的安全距離約束，并在八方向A*算法上設(shè)計(jì)一種多方向搜索算法以及路徑平滑算法以獲得更符合無(wú)人艇操縱特性的全局最優(yōu)路徑。所提出的改進(jìn)A*算法經(jīng)過(guò)對(duì)比分析，結(jié)果表明該方法可生成更安全、距離更短、平滑度更好的路徑，非常適用于復(fù)雜海洋環(huán)境下無(wú)人艇的實(shí)時(shí)路徑規(guī)劃。