基于改進(jìn)A*算法的海上物資投送路徑規(guī)劃*

李航天，黃子奇，張安琳，黃道穎*，李建春

（1.鄭州輕工業(yè)大學(xué)計算機(jī)與通信工程學(xué)院，鄭州 450001；2.北方信息控制研究院集團(tuán)有限公司，南京 211153；3.鄭州輕工業(yè)大學(xué)工程訓(xùn)練中心，鄭州 450001）

0 引言

海上物資投送作為處理突發(fā)應(yīng)急事件的關(guān)鍵環(huán)節(jié)，正受到越來越多的關(guān)注，路徑規(guī)劃是海上物資智能化投送的重要組成部分，其目的是在有障礙物環(huán)境中按照某種評價指標(biāo)尋找一條從起始點到目標(biāo)點的最優(yōu)無碰撞路徑，不僅要避開島嶼、暗礁等靜態(tài)障礙物，還要盡可能地追求航路規(guī)劃速度和路徑平滑度。廣闊海域下，當(dāng)柵格地圖節(jié)點較多時，如何使航行路徑規(guī)劃速度更快、路徑更平滑是亟待解決的關(guān)鍵問題。

近年來，路徑規(guī)劃領(lǐng)域最常用的基于先驗信息的路徑算法有Dijkstra 算法、A*算法、粒子群算法、蟻群算法等［1-4］。Dijkstra 算法通過貪心原理遍歷最小子節(jié)點來保證最優(yōu)路徑，不過遍歷所有節(jié)點信息耗時太長，導(dǎo)致運(yùn)行效率低［5］。雖然蟻群算法具有較強(qiáng)全局優(yōu)化能力，但是在面對大規(guī)模問題時存在運(yùn)行時間較長、收斂速度慢和編碼復(fù)雜的缺點［6］。A*算法基于知情搜索，是最具有代表性的二維網(wǎng)格圖最短路徑算法，其原理簡單、全局搜索能力強(qiáng)、易于實現(xiàn)且效率高，得到了廣泛的應(yīng)用，也被認(rèn)為是求解靜態(tài)路網(wǎng)最短路徑最有效的直接搜索方法［7］。隨著網(wǎng)格數(shù)量的增加，傳統(tǒng)的A*算法存在計算量大、搜索速度慢、路徑轉(zhuǎn)折點多等問題，使得規(guī)劃路徑時遍歷大量不必要的搜索節(jié)點，故無法滿足當(dāng)前尋路問題的需求。對此，已經(jīng)有很多學(xué)者進(jìn)行了研究，程傳奇等在傳統(tǒng)A*算法的基礎(chǔ)上，結(jié)合曼哈頓距離和歐氏距離優(yōu)化，提出了一種啟發(fā)式搜索函數(shù)，并利用關(guān)鍵點選擇策略進(jìn)行搜索，進(jìn)而得到一條最優(yōu)路徑［8］；王中玉等改進(jìn)了算法評價函數(shù)的權(quán)重比例，減少了全局路徑中冗余的拐點，改進(jìn)了路徑生成策略，提高了路徑的平滑度，使機(jī)器人能夠快速找到最優(yōu)路徑［9］；WU 等提出了一種雙向自適應(yīng)A*算法，該算法的方向搜索策略提高了展開效率，同時保證了路徑的平滑性，并使用自適應(yīng)步長和權(quán)值提高了搜索的速度和精度，該方法在復(fù)雜環(huán)境下具有較高的搜索能力［10］；ZHENG 等改進(jìn)的A*算法應(yīng)用到AGV 的路徑規(guī)劃中，利用跳點搜索的特點提高節(jié)點搜索的有效性和運(yùn)行速度，在A*算法的代價函數(shù)中增加角度評估函數(shù)機(jī)制，充分減少拐點數(shù)量［11］。

基于柵格的路徑規(guī)劃效率很大程度上取決于檢索節(jié)點的數(shù)量。為了提高路徑規(guī)劃任務(wù)的效率，特別是對于在節(jié)點多的小粒度柵格地圖進(jìn)行的路徑規(guī)劃，可以改進(jìn)子節(jié)點拓展方式和搜索策略進(jìn)行路徑搜索。本文在傳統(tǒng)A*算法的基礎(chǔ)上，提出了一種基于節(jié)點距離大小拓展子節(jié)點的雙向搜索策略，不僅減少了大量無用節(jié)點的計算，而且使用雙向搜索策略，可以提高路徑的搜索速度，然后進(jìn)行路徑平滑處理，縮短路徑長度，減少轉(zhuǎn)折點數(shù)，使路徑更平滑。

1 地圖環(huán)境建模

地圖環(huán)境建模是路徑規(guī)劃中很重要的一個步驟，準(zhǔn)確提取海洋環(huán)境信息，用恰當(dāng)?shù)姆椒枋龊铰吠ê江h(huán)境，是后續(xù)環(huán)節(jié)開展的前提［12］。本文基于海洋環(huán)境信息，選取南海西沙群島部分區(qū)域作為研究區(qū)域來進(jìn)行二維平面柵格法建模，首先基于電子海圖獲取海洋環(huán)境靜態(tài)信息，如島嶼、暗礁、淺灘、沉船等，然后對靜態(tài)環(huán)境信息進(jìn)行坐標(biāo)轉(zhuǎn)換處理，根據(jù)浪高，將6 級以上海況區(qū)域也視為靜態(tài)障礙物，使用柵格法進(jìn)行海洋環(huán)境建模，建立靜態(tài)環(huán)境信息所對應(yīng)的數(shù)學(xué)模型，該模型在航路規(guī)劃中代表海洋中真實的靜態(tài)信息情況。

1.1 環(huán)境信息處理

構(gòu)建適合A*算法規(guī)劃路徑的地圖需要去考慮影響船舶通航安全的靜態(tài)障礙物信息，如：島嶼、暗礁、淺灘等。本文基于S-57 電子海圖獲取相關(guān)靜態(tài)障礙物的經(jīng)緯度坐標(biāo)信息，使用墨卡托投影將坐標(biāo)信息轉(zhuǎn)換成笛卡爾坐標(biāo)。如式（1）～式（3）所示：

其中，RE表示地球半徑，取RE=6 378.137；Ln表示經(jīng)度；La表示緯度；t 表示弧度；x 和y 表示經(jīng)墨卡托投影公式得到的平面坐標(biāo)。

1.2 柵格法建立環(huán)境模型

柵格法是由W.E.Howden 提出，主要是根據(jù)環(huán)境建立一個柵格地圖?；驹硎菍h(huán)境分割成很多具有二值信息連續(xù)且不交叉的網(wǎng)格單元，其中，黑色網(wǎng)格代表靜態(tài)障礙物，藍(lán)色網(wǎng)格代表極端天氣區(qū)域，它們表示不可航行區(qū)域，白色網(wǎng)格代表可航行區(qū)域。柵格法將不可航行區(qū)域和自由航行區(qū)域用一個矩陣表示，矩陣中1 代表不可通行區(qū)域，0 代表自由航行區(qū)域，由此建立一個可描述環(huán)境信息的地圖模型，如圖1 所示。

圖1 建立地圖環(huán)境模型Fig.1 Model the map environment

使用柵格法進(jìn)行海洋環(huán)境建模時，需要把海洋環(huán)境中的信息抽象到柵格中表示，但是實際的靜態(tài)障礙物信息總是不規(guī)則的，因此，大多時候無法將其抽象為一個柵格，如果某個柵格內(nèi)既存在可通行區(qū)域，又存在不可通行區(qū)域，則為充分保障船舶航行安全，如圖2 所示，使用障礙物膨脹法將其視為不可通行區(qū)域。

圖2 膨脹化處理不規(guī)則障礙物Fig.2 Expansion treatment of irregular obstacles

2 改進(jìn)A＊算法

2.1 基于節(jié)點距離大小進(jìn)行子節(jié)點拓展的雙向搜索策略

在傳統(tǒng)A* 算法每一次搜尋最短路徑的過程中，當(dāng)前節(jié)點所有的相鄰子節(jié)點通常都會被添加到Open 列表中，造成待檢查節(jié)點集合中出現(xiàn)大量的無用節(jié)點，從而導(dǎo)致算法計算量大，搜索速度慢，傳統(tǒng)A*算法拓展子節(jié)點方式如圖3 所示。

圖3 傳統(tǒng)A*算法拓展子節(jié)點示意圖Fig.3 Schematic diagram of expanding sub-nodes with traditional A*algorithm

為解決傳統(tǒng)A* 算法過多拓展無用節(jié)點的問題，本文提出一種基于節(jié)點距離大小拓展子節(jié)點的方法，根據(jù)節(jié)點距離大小信息，選擇性地拓展子節(jié)點。距離大小評估函數(shù)如式（4）所示，其中，n 代表當(dāng)前節(jié)點；m 代表當(dāng)前節(jié)點子節(jié)點；g 代表終點；Dist（n，g）表示當(dāng)前節(jié)點與終點之間的歐式距離；Dist（m，g）表示子節(jié)點與終點之間的歐式距離；Ln為節(jié)點距離大小信息。

如果當(dāng)前節(jié)點的子節(jié)點中存在障礙物節(jié)點，則仍按原節(jié)點拓展方式將除障礙物外的其他子節(jié)點加入Open 列表當(dāng)中。否則，將Ln值大于0 的子節(jié)點加入到Open 列表中，舍棄Ln值小于0 的子節(jié)點。圖4 是基于節(jié)點距離大小進(jìn)行子節(jié)點拓展的流程圖。

圖4 子節(jié)點拓展流程圖Fig.4 Expansion flowchart of sub-nodes

在面對多節(jié)點、小粒度的柵格地圖環(huán)境時，只進(jìn)行單向搜索的傳統(tǒng)A*算法性能較差，為提高A*算法在這種地圖環(huán)境下的路徑搜索速度，本文將雙向搜索思想與基于節(jié)點距離大小的子節(jié)點拓展方式相融合，即從起點和終點開始分別使用基于節(jié)點距離大小的子節(jié)點拓展方式進(jìn)行最優(yōu)路徑搜索。在依次交替搜索的過程中，設(shè)定每一次正向搜索的臨時終點是此時反向搜索得到的代價值最小的子節(jié)點，即反向最優(yōu)候選者，同樣，每一次反向搜索的臨時終點是此時正向搜索的代價值最小的子節(jié)點，即正向最優(yōu)候選者，直到候選者是同一節(jié)點即完成算法搜索。圖5 是基于節(jié)點距離大小進(jìn)行子節(jié)點拓展的雙向搜索策略流程。

圖5 雙向搜索策略流程圖Fig.5 Flowchart of bi-directional search strategy

圖6 刪除冗余轉(zhuǎn)折點和共線點示意圖Fig.6 Schematic diagram of deletion of redundant turning points and collinear points

2.2 基于相鄰路徑向量夾角的路徑平滑處理

傳統(tǒng)A*算法受到啟發(fā)式搜索原則的限制，不允許跨網(wǎng)格對角搜索，導(dǎo)致規(guī)劃路徑中存在大量冗余轉(zhuǎn)折點。本文采用的雙向搜索策略中由于每一次正向搜索和反向搜索的終點均在變化，所以相比傳統(tǒng)A*算法，其規(guī)劃的路徑會產(chǎn)生較多的路徑轉(zhuǎn)折點和路徑節(jié)點。為解決上述問題，本文在優(yōu)化的搜索策略基礎(chǔ)上，通過計算相鄰路徑向量之間的夾角，刪除不必要的共線點和轉(zhuǎn)折點，最終得到一條搜索時間短、路徑平滑的最優(yōu)路徑，具體的優(yōu)化方法如下：

Step 1 Path=［P1，P2，P3，…，Pn］表示使用改進(jìn)搜索策略的A*算法得到的路徑節(jié)點，n 代表初始的路徑節(jié)點數(shù)，初始化參數(shù)i=1，將起始點P1作為當(dāng)前討論的路徑節(jié)點。

Step 2 判斷此時的路徑節(jié)點數(shù)n 是否大于或等于i+2，如果是，則轉(zhuǎn)Step 3，否則表示完成路徑節(jié)點優(yōu)化，結(jié)束循環(huán)，獲得最終路徑節(jié)點為Path=［P1，…，Pn］，算法結(jié)束。

Step 3 判斷節(jié)點Pi和Pi+1之間的路徑向量與節(jié)點Pi+1和Pi+2之間的路徑向量夾角是否為0，若夾角為0，即3 點是否在一條直線上，則刪除中間節(jié)點Pi+1，重新計算當(dāng)前路徑節(jié)點個數(shù)n，并返回Step 2，否則轉(zhuǎn)Step 4。

Step 4 判斷Pi和Pi+2之間是否存在障礙物，如果沒有則刪除中間節(jié)點Pi+1，重新計算當(dāng)前路徑節(jié)點個數(shù)n，并返回Step 2，否則i=i+1，返回Step 2。

3 仿真實驗與分析

為驗證本文所提改進(jìn)A*算法的高效性，和在多節(jié)點、小粒度的柵格地圖環(huán)境進(jìn)行路徑規(guī)劃的適用性，本文基于二維靜態(tài)柵格地圖，對一次改進(jìn)A*算法（基于節(jié)點距離大小進(jìn)行子節(jié)點拓展的雙向搜索）、二次改進(jìn)A*算法（基于相鄰路徑向量夾角的路徑平滑處理）與傳統(tǒng)A*算法以及它們在不同柵格粒度地圖下的規(guī)劃路徑進(jìn)行了比較分析。由于本文的研究重點是物資投送船舶航路規(guī)劃算法，沒有考慮船舶的具體運(yùn)動特性，因此，將船舶在二維空間中進(jìn)行簡化，并將其近似為一個點來表示。實驗環(huán)境如下：1）操作系統(tǒng)：Windows 10 專業(yè)版；2）處理器：Intel（R）Core（TM）i5-8400，主頻2.80 GHz；3）內(nèi)存：8 GB；4）仿真軟件：MATLAB R2018b。

3.1 一次改進(jìn)A＊算法與傳統(tǒng)A＊算法的比較分析

為了驗證一次改進(jìn)A*算法在路徑搜索時間方面具有良好的性能，本文在200*200 二維靜態(tài)柵格地圖環(huán)境下，使用3 組不同起點和終點，對傳統(tǒng)A*算法和一次改進(jìn)A*算法在路徑搜索時間、路徑長度以及已遍歷柵格數(shù)3 個方面進(jìn)行了比較。其中，青色柵格和綠色柵格為已遍歷柵格，紫色柵格和黃色柵格為待遍歷柵格。

1）當(dāng)起點為（5，195），終點為（110，10）時，實驗對比結(jié)果如圖7 和表1 所示。

表1 傳統(tǒng)A*算法和一次改進(jìn)A*算法路徑參數(shù)Table 1 Path parameters of traditional A*algorithm and the first improved A*algorithm

圖7 傳統(tǒng)A*算法和一次改進(jìn)A*算法路徑規(guī)劃圖Fig.7 Path planning for traditional A*algorithm and first improved A*algorithm

仿真結(jié)果表明，當(dāng)起點為（5，195），終點為（110，10）時，一次改進(jìn)A* 算法在搜索時間上較傳統(tǒng)A* 算法縮短了91.5%，已遍歷柵格數(shù)減少了94.6%，但路徑長度略微增加。

2）當(dāng)起點為（140，185），終點為（85，10）時，實驗對比結(jié)果如圖8 和表2 所示。

表2 傳統(tǒng)A*算法和一次改進(jìn)A*算法路徑參數(shù)Table 2 Path parameters of traditional A*algorithm and the first improved A*algorithm

圖8 傳統(tǒng)A*算法和一次改進(jìn)A*算法路徑規(guī)劃圖Fig.8 Path planning for traditional A*algorithm and first improved A*algorithm

仿真結(jié)果表明，當(dāng)起點為（140，185），終點為（85，10）時，一次改進(jìn)A*算法在搜索時間上較傳統(tǒng)A*算法縮短了91.7%，已遍歷柵格數(shù)減少了95%，但路徑長度略微增加。

3）當(dāng)起點為（60，190），終點為（180，30）時，實驗對比結(jié)果如圖9 和表3 所示。

表3 傳統(tǒng)A*算法和一次改進(jìn)A*算法路徑參數(shù)Table 3 Path parameters of traditional A*algorithm and the first improved A*algorithm

圖9 傳統(tǒng)A*算法和一次改進(jìn)A*算法路徑規(guī)劃圖Fig.9 Path planning for traditional A*algorithm and first improved A*algorithm

仿真結(jié)果表明，當(dāng)起點為（60，190），終點為（180，30）時，一次改進(jìn)A* 算法在搜索時間上較傳統(tǒng)A* 算法縮短了96.6%，已遍歷柵格數(shù)減少了97.6%，但路徑長度略微增加。

綜上，在不同的起點和終點搜索路徑時，本文所提一次改進(jìn)A*算法可以大幅度減少尋路過程中所遍歷柵格的個數(shù)，從而縮短搜索時間。但雙向搜索中正向和反向搜索終點的不斷變化，會導(dǎo)致路徑轉(zhuǎn)折點數(shù)、路徑節(jié)點數(shù)及路徑長度略有增加。

3.2 不同柵格粒度地圖下改進(jìn)A＊算法與傳統(tǒng)A＊算法的比較分析

為驗證二次改進(jìn)A*算法在路徑轉(zhuǎn)折點、路徑長度及搜索時間方面的優(yōu)越性，也驗證其更適用于小粒度、更精準(zhǔn)的柵格地圖環(huán)境中，本文通過設(shè)置不同的柵格粒度地圖，對改進(jìn)A*算法和傳統(tǒng)A*算法在路徑長度、轉(zhuǎn)折點數(shù)、路徑節(jié)點數(shù)和路徑搜索時間4 個方面進(jìn)行了對比，其中，100*100 柵格粒度地圖起點為（3，97），終點為（95，13），200*200 柵格粒度地圖起點為（6，194），終點為（190，26），實驗結(jié)果如圖10 和下頁表4 所示。

表4 不同柵格粒度的地圖環(huán)境下傳統(tǒng)A*算法與改進(jìn)A*算法路徑參數(shù)結(jié)果對比Table 4 Comparison of path parameter results between traditional A*algorithm and improved A*algorithm in map environment with different grid granularity

圖10 不同柵格粒度地圖環(huán)境下算法路徑對比圖Fig.10 Comparison of algorithm paths in map environment with different grid granularity

仿真結(jié)果表明，在兩種不同柵格粒度地圖環(huán)境下規(guī)劃路徑時，一次改進(jìn)A*算法相較于傳統(tǒng)A*算法并沒有減少路徑長度、轉(zhuǎn)折點數(shù)和路徑節(jié)點數(shù)，但是通過使用基于相鄰路徑向量的路徑平滑操作而得到的路徑，不僅轉(zhuǎn)折點數(shù)和路徑節(jié)點數(shù)大幅度減少，路徑長度和路徑搜索時間也隨之減少。在200*200 粒度柵格地圖環(huán)境中，二次改進(jìn)A*算法相較于一次改進(jìn)A*算法，所得路徑轉(zhuǎn)折點減少86.4%，路徑節(jié)點數(shù)量減少96.2%，路徑長度減少約4.2%，與傳統(tǒng)A*算法相比，路徑搜索時間縮短了約96%，轉(zhuǎn)折點個數(shù)和路徑節(jié)點數(shù)分別減少約74%和96%。而在100*100 柵格粒度的地圖中，二次改進(jìn)A*算法相較于傳統(tǒng)A* 算法在搜索時間上縮短了91.9%，轉(zhuǎn)折點個數(shù)和路徑節(jié)點數(shù)分別減少約73%和92%，且最終規(guī)劃的路徑較長。故本文所提二次改進(jìn)A*算法相較于傳統(tǒng)A*算法在小粒度、更精準(zhǔn)的200*200 柵格粒度的地圖環(huán)境中規(guī)劃路徑的效率更高。

4 結(jié)論

本文提出的改進(jìn)A*算法能夠在多節(jié)點、更精準(zhǔn)的柵格地圖環(huán)境下，對物資投送船進(jìn)行更快的航路規(guī)劃，并減少路徑規(guī)劃的長度以及轉(zhuǎn)彎次數(shù)，更適合船舶行駛。首先，基于電子海圖提取環(huán)境信息，建立二維靜態(tài)柵格地圖，其次，在傳統(tǒng)的A*算法中優(yōu)化了搜索策略，設(shè)計了基于節(jié)點距離大小進(jìn)行子節(jié)點拓展的雙向搜索策略，減少不必要節(jié)點的搜索，之后使用基于相鄰距離向量夾角的路徑平滑操作，刪除一次改進(jìn)A*算法搜索路徑中的直線冗余點以及不必要的轉(zhuǎn)折點。結(jié)果表明，該改進(jìn)A*算法可以快速地規(guī)劃出一條較短、平滑的路徑，且適用于多節(jié)點、小粒度、更精準(zhǔn)的柵格地圖。