[發(fā)明專利]基于比較式隨機路標圖法的無人船舶局部路徑規(guī)劃方法

有效

• 申請?zhí)枺?/td>: 201910059813.0
• 申請日: 2019-01-22
• 公開（公告）號: CN109799820B
• 公開（公告）日: 2020-12-22
• 發(fā)明（設計）人: 王曉原;夏媛媛;姜雨函;劉亞奇;伯佳更;董曉斐;朱慎超
• 申請（專利權）人: 智慧航海（青島）科技有限公司
• 主分類號: G05D1/02
• 分類號: G05D1/02
• 代理公司: 北京易捷勝知識產權代理事務所(普通合伙) 11613
• 代理人: 齊勝杰

本發(fā)明提供一種基于比較式隨機路標圖法的無人船舶局部路徑規(guī)劃方法，包括：S1獲取環(huán)境信息；S2獲取起始點、目標點，確定路標點個數(shù)K和最大迭代次數(shù)G；S3、采用多目標碰撞檢測方法獲取初始船舶航行路徑方案集合pop₀，S4、依據(jù)改進的遺傳算法對pop₀進行迭代處理，獲取迭代后的路徑集合pop_m；S5、獲取迭代后的路徑集合pop_m中每一條路徑方案的適應度值；S6、根據(jù)適應度值，選取用于輸出的最短船舶航行路徑方案。上述方法解決了現(xiàn)有技術存儲過程數(shù)據(jù)困難、船舶反應速度慢、耗費更多能源等問題。

技術領域

本發(fā)明涉及路徑規(guī)劃技術，特別是一種基于比較式隨機路標圖法的無人船舶局部路徑規(guī)劃方法。

背景技術

在移動機器人領域，隨機路徑圖法能夠有效解決高維空間和復雜約束中的路徑規(guī)劃問題，但是移動機器人使用的隨機路徑圖法常采用A*算法進行可行路徑搜索，而A*算法搜索可行路徑會產生大量的過程數(shù)據(jù)。對于應用于智能無人船舶來說，需要綜合考慮海洋環(huán)境的復雜性、船舶操縱性能及能耗，移動機器人使用的隨機路徑圖法缺乏實際航海應用的可行性。

以下對移動機器人使用的隨機路徑圖法進行說明如下。

隨機路徑圖(PRM)法尋找給定地圖中兩點之間的路徑，PRM進行路徑規(guī)劃的基本原理：

假設機器人運行環(huán)境是一個含有若干障礙物的二維封閉平面空間記為C。機器人可以自由移動的區(qū)域即除去障礙物及其邊緣的區(qū)域稱為自由空間記為C_free，將移動機器人看成C內質點，且不考慮運動動力學約束。

隨機路徑圖法的基本思想是用一個隨機的網絡來表示機器人系統(tǒng)運行的自由空間C_free，這一隨機網絡即是為機器人系統(tǒng)所建立的概率地圖。概率地圖是一個無向循環(huán)圖，用G＝(Ga,Ge)表示。其中Ga為節(jié)點集，其中的元素是在自由規(guī)劃空間C_free中為機器人隨機選取的位形，邊集Ge中的元素則表示節(jié)點之間的連線，代表位形之間的局部可行路徑。然后在這個隨機網絡中利用搜索算法為機器人系統(tǒng)搜索到一條可行的路徑。該算法可通過2個階段來完成：離線學習階段和在線查詢階段。

1)離線學習階段。該階段主要完成的任務是在C_free中為機器人建立一個概率地圖G＝(Ga,Ge)。

首先以隨機的方式在C_free中隨機采樣大量的機器人位置點，構成地圖G中的節(jié)點集Ga；其次，采用局部規(guī)劃器為Ga中的每個節(jié)點尋找它們的鄰居節(jié)點，并為它們建立連接，從而構成地圖中的邊集Ge。學習階段建立起來的路標圖供在線查詢規(guī)劃使用。

2)在線查詢階段。該階段主要完成的任務是在給定的初始位置點s和目標點g的條件下，根據(jù)離線階段構建的路標圖，搜索出一條連接s與g的可行路徑。首先，利用局部規(guī)劃器分別將s與g連接到路標圖中與其距離最近的2個節(jié)點與；然后，采用啟發(fā)式搜索算法從路標圖中搜索出一條連接與的可行路徑。

啟發(fā)式搜索算法常采用A*算法。A*算法是從出發(fā)點開始展開扇形捜索，通過計算當前節(jié)點與其8個方向鄰節(jié)點的代價估計值，查找出最小代價值的路徑即為最優(yōu)路徑，是應用較廣泛高效的方法。

上述方法在實際應用中存在的問題如下：

A1)上述隨機路徑圖法采用的局部規(guī)劃器并不能完全保證連接節(jié)點的邊一定位于自由空間；

A2)上述隨機路徑圖常使用A*算法來搜索可行路徑，會產生大量的過程數(shù)據(jù)，數(shù)據(jù)存儲量大；

A3)對于應用于智能無人船舶來說，需要綜合考慮海洋環(huán)境的復雜性、船舶操縱性能及能耗，使用A*算法搜索可行路徑的隨機路徑圖法缺乏實際航海應用的可行性。

為此，亟需一種能夠應用于智能無人船舶領域的且使用比較式隨機路標圖法的無人船舶局部路徑規(guī)劃方法。