[發明專利]全覆蓋路徑規劃方法、裝置及存儲介質

在審

• 申請號: 202110498296.4
• 申請日: 2021-05-08
• 公開（公告）號: CN113359699A
• 公開（公告）日: 2021-09-07
• 發明（設計）人: 羅兵;黃月琴;吳衛東;鄺嘉業
• 申請（專利權）人: 五邑大學
• 主分類號: G05D1/02
• 分類號: G05D1/02
• 代理公司: 廣州嘉權專利商標事務所有限公司 44205
• 代理人: 葉恩華

本發明公開了全覆蓋路徑規劃方法、裝置及存儲介質，其中全覆蓋路徑規劃方法包括將地圖分解成多個訪問單元；獲取多個訪問單元的訪問序列；根據訪問序列獲取最短連接路徑；根據最短連接路徑獲取全規劃路徑；其中將地圖分解成多個訪問單元的步驟包括獲取地圖的每一列的連通域；獲取相鄰兩列的鄰接矩陣；根據鄰接矩陣將連通域轉換為訪問單元；其使得訪問單元的數量減少，進而減少全規劃路徑中的重復路徑和轉彎數目，降低機器人的工作時長和能量消耗。

技術領域

本發明涉及路徑規劃領域，特別是全覆蓋路徑規劃方法、裝置及存儲介質。

背景技術

全覆蓋路徑規劃是指機器人在某一區域內的自由空間實現快速全覆蓋，是機器人應用技術中的研究內容之一，是掃地機、割草機、水下機器人、工業自動檢測等移動機器人必須用到的一項重要技術。在全覆蓋路徑規劃中常用到牛耕式單元分解方法對地圖進行單元分解，以便后續對訪問單元進行路徑規劃。但牛耕式單元分解方法在尺寸小的障礙物環境中產生面積小和數目多的訪問單元，導致重復路徑和轉彎數目增多，增加機器人的工作時長和能量消耗。

發明內容

本發明的目的在于至少解決現有技術中存在的技術問題之一，提供全覆蓋路徑規劃方法、裝置及存儲介質。

本發明解決其問題所采用的技術方案是：

本發明的第一方面，全覆蓋路徑規劃方法，包括以下步驟：

將地圖分解成多個訪問單元；

獲取多個所述訪問單元的訪問序列；

根據所述訪問序列獲取多個所述訪問單元間的最短連接路徑；

根據所述最短連接路徑獲取全規劃路徑；

其中，所述將地圖分解成多個訪問單元的步驟包括：

獲取所述地圖的每一列的連通域；

獲取所述地圖相鄰兩列的鄰接矩陣，其中所述鄰接矩陣用于表示兩列連通域之間的相連情況；

根據所述鄰接矩陣將所述連通域轉換為所述訪問單元。

根據本發明的第一方面，所述獲取地圖相鄰兩列的連接矩陣的步驟具體為：

設地圖的尺寸為m*k，地圖的第i列具有a個連通域，地圖的第i-1列具有b個連通域，建立a*b大小的所述鄰接矩陣，其中所述鄰接矩陣的列一一對應地表示地圖的第i列的連通域，所述鄰接矩陣的行一一對應地表示地圖的第i-1列的連通域，i∈{2,3,…,k}；

將所述鄰接矩陣的元素標記為0或1，其中0表示兩個連通域相連，1表示兩個連通域不相連。

根據本發明的第一方面，所述根據鄰接矩陣將連通域轉換為訪問單元的步驟包括：

當所述鄰接矩陣中的一行元素之和等于0，閉合當前訪問單元，產生一個新的訪問單元；當所述鄰接矩陣中的一行元素之和等于1，與該行元素對應的所述連通域歸于當前訪問單元；當所述鄰接矩陣中的與一行元素之和大于1，閉合所有的當前訪問單元，與該行元素對應的所述連通域產生新的訪問單元；

當所述鄰接矩陣中的一列元素之和等于0或1，閉合所有的當前訪問單元；當所述鄰接矩陣中的與一列元素之和大于1，該列的最后一個連通域所對應的訪問單元與相連的連通域所對應的訪問單元合并。

根據本發明的第一方面，所述獲取多個所述訪問單元的訪問序列包括：

隨機生成多個父個體，并由多個父個體組成種群，其中所述父個體為所述訪問單元的隨機組合序列；

計算每個所述父個體的覆蓋路徑長度，得到覆蓋路徑長度最短的最優個體；

重復以下步驟，直至迭代完成，將最終的最優個體作為多個所述訪問單元的訪問序列輸出：