[發明專利]一種針對凸形障航物確定船舶航行局部最優路徑的方法

有效

• 申請號: 201610946202.4
• 申請日: 2016-10-26
• 公開（公告）號: CN106546244B
• 公開（公告）日: 2018-03-13
• 發明（設計）人: 王紅波;申子豪;朱顯明;李小剛;劉洋;吳欽;呂紅軍
• 申請（專利權）人: 吉林大學
• 主分類號: G01C21/20
• 分類號: G01C21/20
• 代理公司: 吉林長春新紀元專利代理有限責任公司22100
• 代理人: 陳宏偉

技術領域

本發明提供一種針對凸形障航物確定船舶航行局部最優路徑的方法，屬于船舶航路安全航行技術領域。

背景技術

隨著航海需求的不斷增加，船舶航路規劃技術日益受到人們的關注。船舶航路規劃包括全局航路規劃和局部航路規劃，依據靜態的地理信息(島、礁等)和動態的氣象信息(風、浪、流等)，結合船體狀態及其運動性能，兼顧經濟性和安全性，從起始點到目標點規劃出一條以用時最少、距離最短、最省燃料或者按時到達為優化目標的航線。

船舶航路規劃技術中的A*算法是在Dijkstra算法的基礎上引入啟發式函數得到的，所以經典的A*算法實際上是改進的Dijkstra算法。雖然經典的A*算法已經得到了改進，但其仍然有不足之處，例如在網格地圖規劃航路過程中，采用經典的A*算法時，需將每個航路點相鄰所有可行航路點都遍歷一遍，當網格地圖中的航路點數量很大時，經典的A*算法尋找最優路徑的計算量將急劇增加，導致尋找最優路徑的效率降低。本方法提出一種可行的確定局部最優路徑的方法，可以在航路規劃中優化設計出遭遇凸形障航物時的航行路線。

發明內容

本發明的目的在于提供一種針對凸形障航物確定船舶航行局部最優路徑的方法，可以將本發明的方法植入到船舶航路規劃系統中，更加高效地為航海人員提供滿足實際需求的局部最優路徑，使船舶在整個航段的航行兼顧經濟性和安全性。

本發明的實現過程：結合任務信息明確航行的起始點、目標點以及區域；將航行區域內的凸形障航物生成禁航區；采用經緯線將航行區域生成網格地圖；計算航路規劃技術(A*算法)的各基本要素；用直線把起始點和目標點連接起來，測算該連線與正北方向的夾角；將該夾角作為啟發信息引入到航路規劃技術(A*算法)中去求取局部最優路徑。假設以航行時間為優化目標，本發明的航路規劃方法具體實現包括以下幾個步驟：

步驟1：結合任務信息明確航行的起始點和目標點并依據起始點SP和目標點EP確定航行區域(經度:λ_S1～λ_E1，緯度:)。

步驟2：將航行區域內的凸形障航物(包括靜態障航物和動態障航物)生成禁航區。

步驟3：采用p度*q度(單位經度*單位緯度)的經緯線將航行區域網格化，生成網格地圖。共得到t_c*t_k(橫向網格數*豎向網格數)個網格，每個網格的中心均為航路點，網格地圖為一個有向網絡圖，可以表示為：

G＝(N,A)

其中G是有向網絡圖，N是航路點的集合，A是有向弧的集合。

按由下而上以及從左至右的順序為航路點編號(n＝1,2,3,...,t_c*t_k)。對于本航行區域，設航路點編號為N_o，航路點的經緯度可由其編號求得：

其中λ是經度，是緯度。

弧表示從航路點i航行到航路點j，每個有向弧都有一個相對應的距離，有向弧距離的計算采用大圓航法距離計算公式：

其中，L是航路點i和航路點j之間的大圓航距離，R是地球半徑，是航路點i所在位置的緯度，是航路點j所在位置的緯度，λ₁是航路點i所在位置的經度，λ₂是航路點j所在位置的經度。

由于航行區域邊界的限制，航行區域角落的航路點僅有3個出度和3個入度，航行區域邊界的航路點僅有5個出度和5個入度，其余每個航路點均有8個出度和8個入度，按順時針方向，每個航路點的8個出度與正北方向的夾角依次為：

000°,045°,090°,135°,180°,225°,270°,315°

編號為N_o的航路點，其各個方向相鄰航路點的編號取值如下：

N_o+1,N_o+(t_k+1),N_o+t_k,N_o+(t_k-1),N_o-1,N_o-(t_k+1),N_o-t_k,N_o-(t_k-1)

步驟4：計算航路規劃技術(A*算法)的各基本要素：權值矩陣、估價函數、Open表以及Closed表。以下為各要素計算方法：