[發明專利]基于Theta*回溯的單無人艇覆蓋路徑規劃方法

在審

• 申請號: 202110622746.6
• 申請日: 2021-06-04
• 公開（公告）號: CN113377105A
• 公開（公告）日: 2021-09-10
• 發明（設計）人: 馬勇;王京;嚴新平
• 申請（專利權）人: 武漢理工大學
• 主分類號: G05D1/02
• 分類號: G05D1/02
• 代理公司: 湖北武漢永嘉專利代理有限公司 42102
• 代理人: 劉秋芳;張宇

本發明公開了一種基于Theta*回溯的覆蓋路徑規劃方法，屬于路徑規劃算法及覆蓋路徑規劃算法技術領域，所述方法包括：將環境地圖柵格化，單無人艇按照南東北西的方向優先級開始進行迂回式掃測，若單無人艇進入Critical point，則原路返回繼續掃測，直到環境地圖最東側；計算最優回溯點，使用Theta*算法尋找最優回溯路徑，進行遺漏區域回溯覆蓋，直至所有區域覆蓋完畢。通過本發明可以使單無人艇回溯路徑更加平滑，轉向次數更少。

技術領域

本發明屬于路徑規劃算法及覆蓋路徑規劃算法技術領域，更具體地，涉及一種基于Theta*回溯的單無人艇覆蓋路徑規劃方法。

背景技術

目前無人艇覆蓋路徑主要分為點到點的路徑規劃和針對全區域的覆蓋路徑規劃。路徑規劃常用的方法有A*算法、人工勢場法、遺傳算法、蟻群算法、神經網絡算法等。覆蓋規劃方法常將任務區域進行分解，常用單元分解方法有梯形分解法、Boustrophedon分解法、Morse分解法和Voronoi分解法等。

但是，在復雜環境下，對區域進行分解會導致路徑的遍歷重復率大幅提高，使用A*算法等會使路徑不夠平滑，不符合航海實踐。

發明內容

針對現有技術的以上缺陷或改進需求，本發明提供了一種基于Theta*回溯的單無人艇覆蓋路徑規劃方法，可以使單無人艇回溯路徑更加平滑，轉向次數更少。

為實現上述目的，本發明提供了一種基于Theta*回溯的單無人艇覆蓋路徑規劃方法，包括：

S1：首先將環境地圖柵格化，根據已掃測區域和未掃測區域構建w_list和y_list，在環境地圖最靠近西北角的可掃測位置初始化單無人艇的位置；

S2：單無人艇按照南東北西的方向優先級開始進行迂回式掃測，并不斷更新w_list和y_list；

S3：若單無人艇進入臨界點，則單無人艇原路返回，直到可以按照步驟S2進行轉向；

S4：當單無人艇掃測至環境地圖最東側，則開始檢測w_list，遍歷回溯點，并找出最優回溯點；

S5：使用Theta*算法尋找到最優回溯點的最短路徑；

S6：單無人艇沿著步驟S5的最短路徑進入遺漏區域，并按照步驟S2和步驟S3進行掃測，直到整個待掃區域掃測完畢。

在一些可選的實施方案中，所述根據已掃測區域和未掃測區域構建w_list和y_list包括：

將已掃測區域的柵格加入w_list中，將未掃測區域的柵格和障礙物區域的柵格加入y_list中。

在一些可選的實施方案中，所述南東北西的方向優先級表示：單無人艇首先檢測其南方是否可行，若可行，則向南方前進掃測，若不可行，則檢測單無人艇東側是否可行，若可行，則向東方前進掃測，若不可行，則檢測單無人艇北側是否可行，若可行，則向北方前進掃測，若不可行，則檢測單無人艇西側是否可行，若可行，則向西方前進掃測。

在一些可選的實施方案中，單無人艇在某方向可行指：該方向無障礙物并且該方向未經掃測。

在一些可選的實施方案中，所述迂回式掃測指：從一方開始，循環往復的走之字形曲線，向另外一方推進。

在一些可選的實施方案中，所述單無人艇進入臨界點為：單無人艇進入的一個除了進入方向，其他方向都不可行或者已經被掃測完畢的位置或區域。

在一些可選的實施方案中，所述回溯點為單無人艇測至環境地圖最東側以后，w_list中的點。

在一些可選的實施方案中，所述最優回溯點為距離單無人艇歐氏距離最近的w_list中的點。

總體而言，通過本發明所構思的以上技術方案與現有技術相比，能夠取得下列有益效果：