基于啟發(fā)式搜索算法的水面自主無人艇避障策略

于琳文，葉 曦，錢同惠

（江漢大學(xué) 智能制造學(xué)院，湖北 武漢 430056）

0 引言

近年來，一種新型的現(xiàn)代化智能設(shè)備水面自主無人艇被廣泛應(yīng)用于軍事領(lǐng)域，具有輕便靈活、反應(yīng)迅速、自主能力強(qiáng)等優(yōu)點(diǎn)，有較好的軍用和民用應(yīng)用前景。對(duì)于水面自主無人艇設(shè)備來說，如何規(guī)劃出優(yōu)良的路線以及在多種復(fù)雜環(huán)境下如何成功實(shí)現(xiàn)避障功能是目前討論較多的方向［1-3］。水面自主無人艇自主進(jìn)行路徑規(guī)劃并規(guī)避危險(xiǎn)障礙物，能夠大大減輕人們的工作量并降低人為事故發(fā)生的概率，目前已經(jīng)被廣泛應(yīng)用于軍事探測(cè)、搜索救援、民用捕魚等領(lǐng)域［4］。

程向紅等［5］利用柵格法建立地圖模型，將地圖劃分為眾多形狀大小相同的小正方形，在算法方面采用蟻群算法驗(yàn)證了柵格法建模的有效性和可靠性，但路線規(guī)劃精度并沒有達(dá)到理想預(yù)期值。周宇杭等［6］介紹了A*算法并利用仿真實(shí)驗(yàn)驗(yàn)證了算法的可行性。Zhang等［7］利用柵格法建模，直觀呈現(xiàn)了二維地圖空間中路線的具體遍歷問題，得到的結(jié)果真實(shí)可靠。Tan等［8］為解決移動(dòng)目標(biāo)與移動(dòng)障礙物之間的沖突問題，采用網(wǎng)格法建立工作環(huán)境模型，該方法適用于動(dòng)態(tài)環(huán)境，但在解決局部路徑規(guī)劃問題上尚未提出較好的思路。通過分析以上文獻(xiàn)資料可知，路徑規(guī)劃系統(tǒng)承擔(dān)著為水面自主無人艇決策的重任，目前國(guó)內(nèi)外學(xué)者研究的路徑規(guī)劃又可以劃分為全局路徑規(guī)劃和局部路徑規(guī)劃，局部路徑規(guī)劃主要是針對(duì)區(qū)域內(nèi)的動(dòng)態(tài)障礙物來說，使得質(zhì)點(diǎn)能夠在局部范圍內(nèi)規(guī)避障礙物；全局路徑規(guī)劃主要是針對(duì)區(qū)域內(nèi)的靜態(tài)障礙物來說，使質(zhì)點(diǎn)能夠遍歷找到目標(biāo)位置［9-11］。

本文著重研究了多類型障礙物共存情形下的全局路徑規(guī)劃問題，通過柵格法建立地圖模型，從環(huán)境建模的角度闡述柵格法建模的優(yōu)點(diǎn)，提高系統(tǒng)路徑規(guī)劃的精度［12-13］。改善傳統(tǒng)的A*算法，設(shè)計(jì)新型的啟發(fā)搜索函數(shù)，實(shí)驗(yàn)數(shù)據(jù)顯示，利用MATLAB平臺(tái)能夠?qū)崟r(shí)觀測(cè)水面自主無人艇的運(yùn)動(dòng)軌跡變化，驗(yàn)證了避障策略的有效性。

1 柵格法建模

對(duì)于水面自主無人艇來說，建立環(huán)境區(qū)域模型是系統(tǒng)規(guī)劃研究的一個(gè)首要環(huán)節(jié)。自主無人艇導(dǎo)航過程中，需要根據(jù)人為所建立的具體環(huán)境信息情況來構(gòu)建區(qū)域模型，將所設(shè)置的多種障礙物放置到環(huán)境模型中。本文通過原始經(jīng)典柵格建模方法，利用網(wǎng)格細(xì)分法將大方格均等地劃分為多個(gè)小方格，縮小點(diǎn)與點(diǎn)之間的距離，進(jìn)而提高算法的精確度。

柵格法作為建立地圖模型的一種常用方法，它的主要原理是把一個(gè)運(yùn)動(dòng)的物體視為一個(gè)質(zhì)點(diǎn)，將地圖模型均等劃分為多個(gè)密集的正方形方格，將此質(zhì)點(diǎn)放置于建立好的正方形方格中。該方法需要將一大塊地圖區(qū)域進(jìn)行網(wǎng)格劃分，劃分的一個(gè)重要標(biāo)準(zhǔn)是當(dāng)方格填充不滿時(shí)，需要將不完整方格填補(bǔ)為完整的單元方格。通過這種劃分方式就可以將錯(cuò)綜復(fù)雜的三維空間變成簡(jiǎn)單的二維模型，復(fù)雜的路徑規(guī)劃問題便可以看作從一個(gè)小方格到另一個(gè)小方格的問題，將復(fù)雜的問題做簡(jiǎn)單化處理，水面自主無人艇最終的運(yùn)動(dòng)路線便是依次經(jīng)過的小方格。通過對(duì)環(huán)境劃分，地圖被劃分成障礙物方格和自由方格，其中自由方格表示允許通行，障礙物方格表示不可通行，由于水面障礙物漂移作用的影響，水面自主無人艇在路線搜尋時(shí)遇到的障礙物形態(tài)會(huì)隨機(jī)發(fā)生變化，此模型環(huán)境在計(jì)算機(jī)中用二進(jìn)制0、1表示，其中0代表自由空間，1代表環(huán)境中不可通行區(qū)域。

本文將地圖柵格細(xì)分為40×40，為了直觀呈現(xiàn)無人艇的運(yùn)動(dòng)軌跡，將水面自主無人艇看作一個(gè)質(zhì)點(diǎn)，在地圖區(qū)域內(nèi)布置多種不同形狀、大小的障礙物模型，構(gòu)建一個(gè)二維平面環(huán)境，在地圖中存儲(chǔ)無人艇的運(yùn)動(dòng)軌跡和障礙物等相關(guān)信息，通過實(shí)驗(yàn)測(cè)試得到多組水面自主無人艇搜尋路線和時(shí)間結(jié)果。為了準(zhǔn)確模擬水面無人艇所在區(qū)域的具體位置，假設(shè)無人艇路徑規(guī)劃的場(chǎng)地為正方形，通過劃分形狀大小完全相等的區(qū)域，根據(jù)預(yù)先設(shè)置的質(zhì)點(diǎn)可以運(yùn)動(dòng)的區(qū)域位置和大小，確定水面自主無人艇所處環(huán)境的區(qū)域大小，保證水面自主無人艇可以在已知的區(qū)域范圍內(nèi)遍歷所有位置點(diǎn)并找到較優(yōu)路線。模型區(qū)域的白色小圓圈代表區(qū)域環(huán)境中的障礙物，表示質(zhì)點(diǎn)不能遍歷通過的環(huán)境，其他位置的白色小網(wǎng)格區(qū)域表示質(zhì)點(diǎn)能夠遍歷通過的環(huán)境，環(huán)境區(qū)域中小方格的劃分是通過測(cè)得整片區(qū)域的長(zhǎng)度劃分成均等的40小份，使得每個(gè)小份的邊長(zhǎng)相等。

圖1是建立的障礙物地圖模型，方格數(shù)為40×40，水面自主無人艇與不可通行物體之間的間距為

圖1 障礙物地圖模型Fig.1 Obstacle map model

式中，（x i，yi）為動(dòng)態(tài)水面自主無人艇運(yùn)動(dòng)實(shí)時(shí)方位坐標(biāo)，（x j，yj）為區(qū)域中預(yù)先設(shè)置好的靜態(tài)障礙物體所處的方位坐標(biāo)。

2 避障策略算法

2.1 A*算法

2.1.1 算法原理 傳統(tǒng)A*算法作為常用于車輛路徑規(guī)劃問題研究的一種啟發(fā)性搜索算法，其原理是通過設(shè)定一個(gè)目標(biāo)函數(shù)即估價(jià)函數(shù)，對(duì)區(qū)域環(huán)境下的所有小方格網(wǎng)絡(luò)各個(gè)位置進(jìn)行遍歷評(píng)估，通過目標(biāo)函數(shù)求得方格各個(gè)位置處的價(jià)值，對(duì)其進(jìn)行評(píng)估從而判斷函數(shù)的最小值，搜索到較優(yōu)點(diǎn)，從而確定質(zhì)點(diǎn)下一個(gè)應(yīng)該到達(dá)的位置。A*算法全局路徑代價(jià)為

式中，g(m)表示水面自主無人艇到達(dá)當(dāng)前位置m之前質(zhì)點(diǎn)走過的路線的總代價(jià)；h(m)表示質(zhì)點(diǎn)從當(dāng)前實(shí)時(shí)位置m到預(yù)先設(shè)置的終止位置之間還需要走的路線的總代價(jià)。通過增加h(m)的權(quán)重，可以降低h(m)對(duì)消耗路徑的感應(yīng)靈敏程度，從而減小無人艇的搜尋范圍，減小全局路徑規(guī)劃的時(shí)間，h(m)的權(quán)重一般根據(jù)經(jīng)驗(yàn)值選取。在已知的環(huán)境區(qū)域模型下，假設(shè)區(qū)域中不存在任何的障礙物，無人艇的航行沒有任何干擾，此時(shí)公式中的h(m)代表開始點(diǎn)到目標(biāo)點(diǎn)在直角坐標(biāo)系下的距離總和，即

式中，（x1，y1）表示當(dāng)前節(jié)點(diǎn)，（x2，y2）表示目標(biāo)節(jié)點(diǎn)。

A*算法包含兩個(gè)數(shù)據(jù)集合：一個(gè)為openlist列表，另一個(gè)為closedlist列表，openlist列表用于存儲(chǔ)質(zhì)點(diǎn)還沒有搜索過的節(jié)點(diǎn)，closedlist列表用于存儲(chǔ)質(zhì)點(diǎn)已經(jīng)搜索的節(jié)點(diǎn)。由（3）式可知，h(m)表示當(dāng)前位置與目標(biāo)位置之間的路線代價(jià)，故g(m)和h(m)的數(shù)學(xué)表達(dá)式可以根據(jù)無人艇的實(shí)時(shí)位置而定，實(shí)時(shí)位置不同，對(duì)應(yīng)的質(zhì)點(diǎn)實(shí)時(shí)坐標(biāo)也不同。g(m)表達(dá)式為

式中，A i代表在區(qū)域范圍內(nèi)的第i個(gè)節(jié)點(diǎn)的位置，質(zhì)點(diǎn)在區(qū)域中的起始位置為A0，A m表示質(zhì)點(diǎn)在區(qū)域內(nèi)的實(shí)時(shí)節(jié)點(diǎn)m的位置，D（A i-1，A i）代表區(qū)域內(nèi)A i-1與A i兩個(gè)位置之間的距離，ρi是節(jié)點(diǎn)（i-1）與節(jié)點(diǎn)i之間的環(huán)境加權(quán)系數(shù)，ρi與規(guī)劃路徑的易通程度與能量消耗系數(shù)有關(guān)。

2.1.2 算法流程圖 傳統(tǒng)A*算法流程圖見圖2。

圖2 A*算法流程圖Fig.2 A*algorithm flow chart

如圖2所示，算法首先將起始節(jié)點(diǎn)存入openlist表中，計(jì)算表中所有節(jié)點(diǎn)的代價(jià)，選擇最小代價(jià)的節(jié)點(diǎn)作為目標(biāo)節(jié)點(diǎn)，計(jì)算該節(jié)點(diǎn)已經(jīng)走過路線的代價(jià)g，將此節(jié)點(diǎn)作為起始節(jié)點(diǎn)，計(jì)算到達(dá)下一個(gè)目標(biāo)節(jié)點(diǎn)需要的代價(jià)h，秉承質(zhì)點(diǎn)總路徑規(guī)劃代價(jià)最小的原則，對(duì)openlist表中節(jié)點(diǎn)的g值進(jìn)行更新，直至質(zhì)點(diǎn)到達(dá)最終設(shè)置的目標(biāo)節(jié)點(diǎn)位置，算法結(jié)束。

2.2 啟發(fā)式算法改進(jìn)

有障礙的搜索路徑問題是在有障礙模型的情形中，按照某個(gè)或者多個(gè)判斷標(biāo)準(zhǔn)，在數(shù)學(xué)上轉(zhuǎn)化為求解某個(gè)目標(biāo)函數(shù)極值的問題，水面自主無人艇能夠成功搜尋目標(biāo)位置，并且能夠成功繞開區(qū)域內(nèi)的所有障礙物，求解函數(shù)極小值的約束條件，目標(biāo)函數(shù)數(shù)學(xué)表達(dá)式為

式中，Rn表示預(yù)設(shè)區(qū)域環(huán)境中的所有可以搜尋的位置；X表示水面自主無人艇在區(qū)域里的實(shí)時(shí)位置；gi（X）表示所要求解問題的目標(biāo)值，本文通過計(jì)算搜尋路線的時(shí)間長(zhǎng)短來判斷目標(biāo)函數(shù)解的好壞；W i表示權(quán)值，在這里對(duì)應(yīng)的是第i個(gè)目標(biāo)節(jié)點(diǎn)位置在整體區(qū)域環(huán)境中的權(quán)值；f(X)表示求得的目標(biāo)函數(shù)值大小；minf(X)表示多次實(shí)驗(yàn)后求出的目標(biāo)函數(shù)的最小值，在本文對(duì)應(yīng)的即為搜尋路線的最優(yōu)解。

A*算法在路徑規(guī)劃中，利用啟發(fā)函數(shù)f(m)，當(dāng)水面自主無人艇距離終點(diǎn)位置越來越近時(shí)，從當(dāng)前實(shí)時(shí)節(jié)點(diǎn)到終止節(jié)點(diǎn)的估計(jì)代價(jià)h(m)便會(huì)越來越小，實(shí)時(shí)節(jié)點(diǎn)與起始節(jié)點(diǎn)的距離越來越遠(yuǎn)，意味著從起始節(jié)點(diǎn)到當(dāng)前實(shí)時(shí)節(jié)點(diǎn)位置處質(zhì)點(diǎn)走過的路線總代價(jià)越來越大，由于無人艇可以搜索環(huán)境區(qū)域中的所有節(jié)點(diǎn)，故質(zhì)點(diǎn)并不會(huì)直接搜索目標(biāo)節(jié)點(diǎn)，環(huán)境區(qū)域內(nèi)的所有節(jié)點(diǎn)對(duì)質(zhì)點(diǎn)都會(huì)產(chǎn)生干擾，使得算法在搜尋中會(huì)求解許多無效節(jié)點(diǎn)，花費(fèi)很多不必要的時(shí)間，進(jìn)而得到的路徑并不是最優(yōu)路徑。

本文采用了一種新的啟發(fā)式信息函數(shù)，如圖3所示，在預(yù)先構(gòu)建好的環(huán)境方格地圖中，和之間的夾角為和之間的夾角為b，A、B分別為開始節(jié)點(diǎn)和終止節(jié)點(diǎn)。當(dāng)算法使用曼哈頓距離作為啟發(fā)信息，假設(shè)在算法求解代價(jià)函數(shù)過程中求得的C點(diǎn)和D點(diǎn)的代價(jià)值相同，此時(shí)C點(diǎn)相對(duì)于D點(diǎn)來說便可以看作干擾節(jié)點(diǎn)，即水面自主無人艇會(huì)對(duì)C、D兩點(diǎn)都進(jìn)行搜尋，由于D點(diǎn)距離目標(biāo)節(jié)點(diǎn)更近，所以應(yīng)該優(yōu)先考慮D點(diǎn)，而C點(diǎn)雖然被搜索但是會(huì)成為無效節(jié)點(diǎn)而被放棄。

圖3 不同位置的向量夾角余弦Fig.3 Cosine of vector angle at different positions

根據(jù)向量夾角余弦公式可知：

基于上述分析，設(shè)計(jì)節(jié)點(diǎn)m處的啟發(fā)函數(shù)為

式中，hcos（m）代表節(jié)點(diǎn)m和開始位置構(gòu)成的向量和節(jié)點(diǎn)m與終止節(jié)點(diǎn)構(gòu)成的向量的夾角p的余弦值，W表示目標(biāo)節(jié)點(diǎn)m處的權(quán)值?？梢郧蟪?/p>

由余弦角度定理可得，cosa＞cosb，hcos(C)＞hcos(D)，得fcos(D)＜fcos(C)，C點(diǎn)位置的代價(jià)值要高于D點(diǎn)，所以算法會(huì)優(yōu)先考慮D點(diǎn)，導(dǎo)致C點(diǎn)位置不會(huì)被考慮，水面自主無人艇便會(huì)放棄C點(diǎn)直接去搜尋D點(diǎn)，從而減少全局搜尋目標(biāo)的時(shí)間，對(duì)整體路徑起到了優(yōu)化的作用。

3 仿真實(shí)驗(yàn)與結(jié)果

通過仿真實(shí)驗(yàn)分析，可以進(jìn)一步理解算法改進(jìn)的思路，同時(shí)對(duì)系統(tǒng)仿真結(jié)果進(jìn)行進(jìn)一步驗(yàn)證。采用網(wǎng)格細(xì)分化操作將區(qū)域精確劃分為40×40的小方格，作為水面自主無人艇路徑規(guī)劃的實(shí)驗(yàn)區(qū)域，為了將復(fù)雜問題簡(jiǎn)單化，在此進(jìn)行理想化處理，在仿真實(shí)驗(yàn)中將水面自主無人艇、起始點(diǎn)位置、目標(biāo)點(diǎn)位置等全部看成質(zhì)點(diǎn)，通過利用x、y組成的二維坐標(biāo)將所有質(zhì)點(diǎn)顯示在柵格地圖中，分兩步分別分析、驗(yàn)證算法的準(zhǔn)確性以及改進(jìn)后算法的優(yōu)越性。

3.1 算法的準(zhǔn)確性

在MATLAB仿真環(huán)境中，設(shè)置相關(guān)的質(zhì)點(diǎn)信息，障礙物用白色圓圈表示，代表水面自主無人艇不能通過的區(qū)域，其余的柵格部分表示水面自主無人艇的自由空間。隨機(jī)設(shè)置不同的障礙物形狀以及大小，設(shè)置水面自主無人艇的開始位置坐標(biāo)start和目標(biāo)位置坐標(biāo)end，為了避免實(shí)驗(yàn)偶然性，在不同起始節(jié)點(diǎn)、目標(biāo)節(jié)點(diǎn)位置以及不同障礙物形狀、大小情況下，每組情況做3次仿真實(shí)驗(yàn)驗(yàn)證，實(shí)驗(yàn)結(jié)果表明在不同的障礙模型下水面自主無人艇均能夠找到目標(biāo)。

3.1.1 不同起始位置的路徑規(guī)劃 在MATLAB測(cè)試中，首先測(cè)試算法的準(zhǔn)確性，具體步驟如下：

設(shè)置開始位置坐標(biāo)為（40，40），目標(biāo)位置坐標(biāo)為（370，370），在MATLAB仿真平臺(tái)上驗(yàn)證實(shí)驗(yàn)結(jié)果如圖4所示。

設(shè)置開始位置坐標(biāo)為（30，30），目標(biāo)位置坐標(biāo)為（220，220），在MATLAB仿真平臺(tái)上驗(yàn)證實(shí)驗(yàn)結(jié)果如圖5所示。

圖4（40，40）—（370，370）路徑規(guī)劃Fig.4 （40，40）-（370，370）path planning

圖5（30，30）—（220，220）路徑規(guī)劃Fig.5 （30，30）-（220，220）path planning

比較上述兩種不同情形下的路徑規(guī)劃圖，圖中的白色圓圈表示所處環(huán)境中的障礙物，彩色線條表示水面自主無人艇的運(yùn)動(dòng)軌跡。由圖4和圖5仿真結(jié)果可以看出，在障礙物形狀大小已知不變的情況下，通過改變水面自主無人艇的起始節(jié)點(diǎn)位置坐標(biāo)與終止節(jié)點(diǎn)位置坐標(biāo)，發(fā)現(xiàn)水面自主無人艇能夠從起始節(jié)點(diǎn)出發(fā)，成功繞開范圍內(nèi)的所有障礙物到達(dá)終止節(jié)點(diǎn)，能夠在區(qū)域范圍內(nèi)規(guī)劃出一條有效路徑。

3.1.2 不同的障礙物的路徑規(guī)劃 在實(shí)際應(yīng)用中，考慮到海面上的物體時(shí)刻處于漂浮狀態(tài)，在水上障礙物漂移作用下，障礙物會(huì)呈現(xiàn)出不同的形態(tài)、大小。在本次實(shí)驗(yàn)中只考慮靜態(tài)障礙物的情形，在預(yù)設(shè)的區(qū)域范圍內(nèi)隨機(jī)放置多種不同種類、形狀的障礙模型，用三角形、直線、梯形等形狀模擬障礙物在水面的不同形態(tài)，區(qū)域范圍內(nèi)白色圓圈代表不同形狀的障礙物類型，將原始梯形障礙物參數(shù)由1∶9調(diào)整為1∶15，從而改變梯形障礙物直角邊的長(zhǎng)度，水面自主無人艇運(yùn)動(dòng)路線在MATLAB仿真平臺(tái)上驗(yàn)證實(shí)驗(yàn)結(jié)果如圖6所示。仿真結(jié)果表明，當(dāng)梯形障礙物大小發(fā)生改變時(shí)，水面自主無人艇能夠重新規(guī)劃出新的路徑到達(dá)目標(biāo)點(diǎn)位置。

圖6 梯形障礙物大小變化時(shí)的路徑規(guī)劃Fig.6 Path planning when the trapezoidal obstaclesize changes

將地圖模型的高度和寬度參數(shù)由5調(diào)整為10，將地圖區(qū)域范圍內(nèi)的障礙物等比例放大，水面自主無人艇運(yùn)動(dòng)路線在MATLAB仿真平臺(tái)上驗(yàn)證結(jié)果如圖7所示。仿真實(shí)驗(yàn)分析發(fā)現(xiàn)，水面自主無人艇仍能夠在區(qū)域范圍內(nèi)從起始節(jié)點(diǎn)到達(dá)終止節(jié)點(diǎn)，并且成功躲避所有障礙物規(guī)劃出一條準(zhǔn)確的路徑。

圖7 障礙物形狀變化時(shí)的路徑規(guī)劃Fig.7 Path planning when obstacle shape changes

3.2 算法的優(yōu)化性能對(duì)比

在二維地圖模型中預(yù)先放置障礙物模型，設(shè)置障礙物的幾何形狀以及參數(shù)大小，設(shè)置開始位置坐標(biāo)為（30，30），目標(biāo)位置坐標(biāo)為（390，390），對(duì)改進(jìn)前后的算法分別做3次仿真實(shí)驗(yàn)測(cè)試結(jié)果，對(duì)比算法的優(yōu)化效果。

沒有對(duì)啟發(fā)式函數(shù)進(jìn)行改進(jìn)之前，水面自主無人艇從開始位置到達(dá)目標(biāo)位置的運(yùn)動(dòng)軌跡如圖8所示。對(duì)啟發(fā)式函數(shù)改進(jìn)之后，水面自主無人艇從起始節(jié)點(diǎn)到達(dá)終止節(jié)點(diǎn)的運(yùn)動(dòng)軌跡如圖9所示。從圖中可以看出，算法改進(jìn)前后都可以使質(zhì)點(diǎn)規(guī)劃出一條從起始節(jié)點(diǎn)到達(dá)終止節(jié)點(diǎn)的路線。

圖8 算法優(yōu)化前路徑規(guī)劃Fig.8 Path planning before algorithm optimization

圖9 算法優(yōu)化后路徑規(guī)劃Fig.9 Path planning after algorithm optimization

本文判斷路徑規(guī)劃的好壞主要采用搜尋路線的時(shí)間長(zhǎng)短來體現(xiàn)，從仿真圖片上可以直觀地看出算法優(yōu)化前后的路徑規(guī)劃情況，本文算法優(yōu)化前后路徑規(guī)劃的時(shí)間見表1。

由表1可知，設(shè)定相同的起始節(jié)點(diǎn)位置以及終止節(jié)點(diǎn)位置，發(fā)現(xiàn)改進(jìn)前算法路徑規(guī)劃所用的平均時(shí)間為36.194 2 s，改進(jìn)后算法路徑規(guī)劃所用的平均時(shí)間為35.034 2 s，結(jié)果顯示算法在時(shí)間上平均可以節(jié)約1.16 s，優(yōu)化后的算法消耗的時(shí)間更短，較明顯地提高了算法效率。

表1 算法優(yōu)化前后路徑規(guī)劃需要的時(shí)間Tab.1 The time required for path planning before and after algorithm optimization

4 結(jié)語(yǔ)

研究水面自主無人艇避障策略，往往存在無法避障或者路徑不是最優(yōu)的問題，本文基于改進(jìn)的啟發(fā)式搜索算法，采用經(jīng)典柵格法建模，通過對(duì)場(chǎng)地內(nèi)的柵格進(jìn)行細(xì)分，提高系統(tǒng)路徑規(guī)劃的精度。針對(duì)傳統(tǒng)A*算法存在的精度以及復(fù)雜程度問題，本文在原始算法的基礎(chǔ)上提出了一種新的啟發(fā)式函數(shù)。仿真實(shí)驗(yàn)結(jié)果表明，改進(jìn)后的算法能夠使水面自主無人艇成功躲避障礙物并找到目標(biāo)點(diǎn)，通過數(shù)據(jù)對(duì)比分析得出改進(jìn)后算法比改進(jìn)前算法通過障礙區(qū)域耗時(shí)更短，減少了搜尋無效節(jié)點(diǎn)的數(shù)量，提高了工作效率。