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

在審

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

1.全覆蓋路徑規劃方法，其特征在于，包括以下步驟：

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

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

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

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

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

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

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

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

2.根據權利要求1所述的全覆蓋路徑規劃方法，其特征在于，所述獲取地圖相鄰兩列的連接矩陣的步驟具體為：

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

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

3.根據權利要求2所述的全覆蓋路徑規劃方法，其特征在于，所述根據鄰接矩陣將連通域轉換為訪問單元的步驟包括：

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

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

4.根據權利要求1所述的全覆蓋路徑規劃方法，其特征在于，所述獲取多個所述訪問單元的訪問序列包括：

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

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

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

隨機選擇所述種群中的任意兩個所述父個體，利用遺傳算子產生多個子個體，其中所述子個體的數量和所述種群中的所述父個體的數量相同；

隨機變換每個所述子個體中的任意兩個所述訪問單元的序列順序，得到變換子個體；

將所述變換子個體替代種群的所述父個體，計算每個所述變換子個體的覆蓋路徑長度，比較每個所述變換子個體的覆蓋路徑長度與最優個體的覆蓋路徑長度的大小并更新最優個體。

5.根據權利要求1所述的全覆蓋路徑規劃方法，其特征在于，所述根據所述訪問序列獲取多個所述訪問單元間的最短連接路徑所采用的方法為可視圖法、A*法、快速隨機搜索法、人工勢場法或Dijkstra法。

6.全覆蓋路徑規劃裝置，其特征在于，包括：

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

序列計算單元，用于獲取多個所述訪問單元的訪問序列；

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

全規劃路徑計算單元，用于根據所述最短連接路徑獲取全規劃路徑；

其中，所述分解單元包括：

連通域計算單元，用于獲取所述地圖的每一列的連通域；

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

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