[發(fā)明專利]一種基于改進(jìn)A星算法的無人艇全局路徑規(guī)劃方法

有效

• 申請?zhí)枺?/td>: 202010004408.1
• 申請日: 2020-01-03
• 公開（公告）號: CN111060109B
• 公開（公告）日: 2021-08-27
• 發(fā)明（設(shè)計）人: 張濤;秦彥樑;王立輝;夏茂棟;張佳宇;張晨;張江源
• 申請（專利權(quán)）人: 東南大學(xué)
• 主分類號: G01C21/20
• 分類號: G01C21/20;G05D1/02
• 代理公司: 南京眾聯(lián)專利代理有限公司 32206
• 代理人: 蔣昱

本發(fā)明提供的是一種基于改進(jìn)A星算法的無人艇全局路徑規(guī)劃方法，涉及路徑規(guī)劃領(lǐng)域。本發(fā)明改變傳統(tǒng)A星算法鄰點搜索策略，擴大搜索鄰域，對傳統(tǒng)啟發(fā)式函數(shù)進(jìn)行改進(jìn)，結(jié)合分權(quán)策略，加入角度因素，使路徑搜索時得到的結(jié)果偏向分布在起始點與目標(biāo)點連線附近，提高搜索效率。本發(fā)明利用電子海圖獲取海洋地理信息，將改進(jìn)A星算法與動態(tài)柵格法相結(jié)合，通過柵格動態(tài)細(xì)化構(gòu)建網(wǎng)格地圖模型，應(yīng)用改進(jìn)A星算法尋找路徑，使路徑精度逐步達(dá)到精度要求，再通過平滑路徑處理，進(jìn)一步減少多余的路徑節(jié)點。

技術(shù)領(lǐng)域

本發(fā)明涉及路徑規(guī)劃技術(shù)領(lǐng)域，具體為一種基于改進(jìn)A星算法的無人艇全局路徑規(guī)劃方法。

背景技術(shù)

無人艇作為一種無人操作的水面艦艇，主要用于執(zhí)行危險和不適于有人船只執(zhí)行的任務(wù)，在眾多領(lǐng)域得到廣泛應(yīng)用。目前，無人艇正在向著智能化發(fā)展，可以通過指令下達(dá)的方式進(jìn)行自主航行及作業(yè)，但是復(fù)雜海洋環(huán)境中無人艇的自航技術(shù)還有待提高。為了提高無人艇的智能化水平，完成在各種復(fù)雜環(huán)境中的特定任務(wù)，無人艇必須要具備自主的規(guī)劃能力。路徑規(guī)劃是無人智能平臺領(lǐng)域需要解決的關(guān)鍵問題之一，在某些層面上反映了無人艇智能化程度的高低。

電子海圖是以數(shù)字信息表示的，描寫海域地理要素和航海要素，利用電子海圖全局信息，規(guī)劃出一條避開所有已知靜態(tài)障礙物，并且到達(dá)目的點的路徑，從而指導(dǎo)無人艇更高效地完成路徑規(guī)劃任務(wù)。A星算法是靜態(tài)路網(wǎng)中求解最短路徑最有效的直接搜索方法，結(jié)合Dijkstra算法與最佳優(yōu)先算法BFS優(yōu)點，綜合考慮起始點到當(dāng)前節(jié)點的真實代價與當(dāng)前節(jié)點到終點的估計代價，在保證搜索效率的同時，得到最優(yōu)的路徑。

發(fā)明內(nèi)容

為了解決以上問題，本發(fā)明提供一種基于改進(jìn)A星算法的無人艇全局路徑規(guī)劃方法，本發(fā)明改變傳統(tǒng)A星算法鄰點搜索策略，擴大搜索鄰域，對傳統(tǒng)啟發(fā)式函數(shù)進(jìn)行改進(jìn)，結(jié)合分權(quán)策略，加入角度因素，使路徑搜索時得到的結(jié)果偏向分布在起始點與目標(biāo)點連線附近，提高搜索效率。本發(fā)明利用電子海圖獲取海洋地理信息，將改進(jìn)A星算法與動態(tài)柵格法相結(jié)合，通過柵格動態(tài)細(xì)化構(gòu)建網(wǎng)格地圖模型，應(yīng)用改進(jìn)A星算法尋找路徑，使路徑精度逐步達(dá)到精度要求，再通過平滑路徑處理，進(jìn)一步減少多余的路徑節(jié)點，為達(dá)此目的，本發(fā)明提供一種基于改進(jìn)A星算法的無人艇全局路徑規(guī)劃方法，具體包括如下步驟：

(1)獲取全局海圖信息，設(shè)置無人艇起點與終點位置的經(jīng)緯度信息，判斷無人艇起點或終點位置是否為不可通行區(qū)域，若是則重新設(shè)置起點與終點的經(jīng)緯度信息；

(2)構(gòu)建網(wǎng)格地圖，確定經(jīng)緯度范圍，以經(jīng)緯度縱橫比動態(tài)柵格細(xì)化海圖，形成M*N的網(wǎng)格海圖，將起點與終點的經(jīng)緯度坐標(biāo)轉(zhuǎn)換為笛卡爾坐標(biāo)；判斷起點與終點之間的連線是否通過不可通行區(qū)域，若不存在不可通行區(qū)域，則路徑即為起點與終點的連線，否則進(jìn)行改進(jìn)A星算法尋找路徑；

(3)改進(jìn)A星算法尋找路徑，創(chuàng)建OPEN集與CLOSE集，OPEN集用于存放待檢測的節(jié)點，CLOSE集用于存放已檢測過的節(jié)點；OPEN集與CLOSE集中每個節(jié)點有父節(jié)點、F值、G值、H值；父節(jié)點為路徑中通過該節(jié)點所經(jīng)過的上一節(jié)點，G值為從起點移動到當(dāng)前節(jié)點的代價，H值為從當(dāng)前節(jié)點移動到終點的估計代價，F(xiàn)值是G值與H值之和；遍歷OPEN集，查找F值最小的節(jié)點，將此節(jié)點作為當(dāng)前要處理的節(jié)點；若將終點加入到OPEN集中，則路徑已經(jīng)找到，回溯路徑，將從終點開始沿著父節(jié)點移動直至起點的節(jié)點依次加入PATH集；若未將終點加入到OPEN集中且OPEN集已空，則未找到路徑；

(4)判斷是否達(dá)到導(dǎo)航精度要求，即單位網(wǎng)格邊長實際經(jīng)緯度數(shù)，若達(dá)到要求且找到路徑，則進(jìn)行平滑路徑處理；若達(dá)到要求但未找到路徑，則表明當(dāng)前分辨率下無法找到路徑；若未達(dá)到導(dǎo)航精度要求但找到路徑，按找到的路徑的范圍再次柵格化，若未達(dá)到導(dǎo)航精度要求也未找到路徑則將M與N乘以同一倍數(shù)，以原經(jīng)緯度范圍再次柵格化；

(5)平滑路徑，刪去PATH集中保存的共線的節(jié)點以及多余轉(zhuǎn)折點，只保留必要轉(zhuǎn)折點的位置，并利用網(wǎng)格圖的經(jīng)緯度范圍大小，M值與N值，將PATH集中節(jié)點橫縱坐標(biāo)轉(zhuǎn)換為經(jīng)緯度坐標(biāo)。