[發明專利]基于蟻群算法的無人船節能路徑規劃方法

有效

• 申請號: 202110547020.0
• 申請日: 2021-05-19
• 公開（公告）號: CN113341954B
• 公開（公告）日: 2023-03-21
• 發明（設計）人: 陳芳炯;張健銘;季飛;余華;官權升
• 申請（專利權）人: 華南理工大學
• 主分類號: G05D1/02
• 分類號: G05D1/02
• 代理公司: 廣州粵高專利商標代理有限公司 44102
• 代理人: 何淑珍;江裕強

本發明公開了基于蟻群算法的無人船節能路徑規劃方法。所述方法包括以下步驟：通過柵格法對環境進行建模，在建模后的地圖上設立n個任務點，選取兩個任務點i,j，通過Lazy theta*算法計算兩個任務點的中間路徑點，將中間路徑點連成線得到最短路徑；根據中間路徑點，全局風浪流干擾方向和干擾大小，計算任務點i到任務點j的最短距離d_ij和能量消耗e_ij；計算n個任務點兩兩之間的最短距離和能量消耗，構建距離矩陣D和能量消耗矩陣E；將距離矩陣D和能量消耗矩陣E作為啟發式信息進行蟻群算法計算，獲取全局最優節能路徑規劃。本發明提出的將距離和能量消耗用作蟻群算法的啟發式信息是一種可以得到全局最優節能路徑規劃的方法，有效節約無人船的能量消耗。

技術領域

本發明涉及路徑規劃領域，具體涉及一種基于蟻群算法的無人船節能路徑規劃方法。

背景技術

無人船目前在科研，監測，軍事，環保等領域有了廣泛應用和前景，在路徑規劃領域，研究人員已經在探索更多的可能性。A*算法可以計算兩點間的一條較短路徑，避開障礙物。蟻群算法將任務點間距離作為啟發式信息，進行全局路徑規劃，對于多任務點的旅行商問題有著較好的性能。往往在一個全局多任務點路徑規劃中，利用A*算法進行兩點間的路徑規劃，蟻群算法進行全局調配。

A*算法是一種很常用的路徑查找和圖形遍歷算法，有著較好的性能和準確度。它根據代價函數的大小選擇相鄰節點進行搜尋，直至搜尋到終點。可是它尋找的路徑往往有兩個缺點。一是只能沿8個方向進行移動，也就是上下左右、左上、右上、左下、右下，無法任意角度移動，在實際場景中有所欠缺。二是可移動的下一個節點必定是相鄰節點，所以導致從起點到終點會有大量中間路徑點。綜合上面兩個缺點，A*算法計算出的路徑是不平滑的。

Lazy theta*算法是一種改進的平滑A*算法。

蟻群算法是一種模擬螞蟻覓食行為的模擬優化算法，螞蟻在走過的路徑上釋放信息素，越多螞蟻走的路信息素越多，再根據信息素濃度和路徑距離概率性選擇下一條路，最終多次迭代達到最優解。而蟻群算法的局限性在于僅將路徑距離作為啟發式信息，在無人船水面運功中，由于波浪流等外界干擾下，往往最短路徑并不是最低的能量消耗。

考慮海流與無人艇動力學影響的節能A星路徑規劃方法(CN109489672A) 這一專利就曾闡述了兩節點的節能路徑規劃，其利用的是傳統的A*算法進行改進，可是A*算法有路徑不平滑和大量中間路徑點的缺點。而且該方法僅僅考慮兩點的路徑規劃，在許多實際的測量任務中，多任務點的節能遍歷是必不可少的。

發明內容

本發明的目的是解決現有技術中的不足，提供一種計算兩點間最短路徑和能量消耗的算法，并利用路徑最短距離和能量消耗作為啟發式信息，對多任務點遍歷旅行商問題進行節能路徑規劃。是一種可以得到全局最優節能路徑規劃的方法，有效節約無人船的能量消耗。

本發明的目的至少通過如下技術方案之一實現。

基于蟻群算法的無人船節能路徑規劃方法，包括以下步驟：

S1、通過柵格法對環境進行建模，在建模后的地圖上設立n個任務點，選取兩個任務點i,j，通過Lazy theta*算法計算兩個任務點的中間路徑點，將中間路徑點連成線得到最短路徑；

S2、根據步驟S1中得出的中間路徑點，全局風浪流干擾方向和干擾大小，計算任務點i到任務點j的最短距離d_ij和能量消耗e_ij；

S3、計算n個任務點兩兩之間的最短距離和能量消耗，構建距離矩陣D和能量消耗矩陣E；

S4、將距離矩陣D和能量消耗矩陣E作為啟發式信息進行蟻群算法計算，獲取全局最優節能路徑規劃。