[發明專利]一種幾何折疊式機器人全覆蓋路徑及其生成方法

有效

• 申請號: 202011617560.3
• 申請日: 2020-12-30
• 公開（公告）號: CN112817309B
• 公開（公告）日: 2021-12-03
• 發明（設計）人: 朱利豐;姚帥;宋愛國
• 申請（專利權）人: 東南大學
• 主分類號: G05D1/02
• 分類號: G05D1/02
• 代理公司: 南京眾聯專利代理有限公司 32206
• 代理人: 蔣昱

本發明公開了一種幾何折疊式的機器人全覆蓋路徑及其生成方法。傳統的全覆蓋路徑規劃算法主要基于鋸齒形和螺旋形圖案或其組合，遍歷順序受限于其線性或從內到外的方式缺少變化。本發明通過使用幾何折疊操作，生成了一種新型機器人全覆蓋路徑圖案，稱為幾何折疊式路徑圖案，該類覆蓋路徑具有更靈活的遍歷順序。本發明建模了幾何折疊圖案的表示方法，之后介紹了一個隨機生成幾何折疊式全覆蓋路徑的方法、以及給定按順序通過指定點約束下的幾何折疊路徑搜索方法，從而為覆蓋路徑規劃問題提供了更多靈活可控的選擇。

技術領域

本發明屬于信息技術在機器人路徑規劃領域的應用，特別是涉及到一種幾何折疊式機器人全覆蓋路徑及其生成方法。

背景技術

全覆蓋路徑生成是機器人路徑規劃中的重要話題之一。通過生成一個給定區域的全覆蓋路徑，機器人可以不偏不漏不重復地通過區域內的每個位置，生成全覆蓋路徑是諸如無人機巡查、農業機器人耕種、工業機器人噴涂、掃地機器人運動等任務中關鍵的技術。

傳統的機器人全覆蓋路徑圖案一般沿著往復直線運動或螺旋型運動，此類路徑變化較少，不能滿足特定的路徑順序等要求，而一般的自由空間覆蓋曲線由于其指數級別的復雜度難以實現。

發明內容

為了解決上述存在問題。本發明提供一種幾何折疊式機器人全覆蓋路徑的生成方法，該方法為介于這兩類圖案之間的一種新型機器人全覆蓋路徑圖案，稱為幾何折疊式全覆蓋圖案，此類圖案相比往復直線運動或螺旋型運動擁有更多的變化，相比自由空間覆蓋曲線搜索空間大幅減少，可通過適量的計算進行有效的搜索。

本發明提供一種幾何折疊式機器人全覆蓋路徑，所述幾何折疊式機器人全覆蓋路徑通過建模生成，將全覆蓋路徑建模為沿著接縫折疊一序列郵票后從側面看折疊后郵票序列的幾何形態，由于郵票折疊會有產生很多不同的順序，從而對應于不同的幾何形態，稱這類幾何形態的全覆蓋路徑圖案為幾何折疊式全覆蓋路徑；

幾何折疊式全覆蓋路徑主要沿著一個方向行進，行進至此方向的兩端轉彎，在此方向的行進的中間不發生轉彎；

由于每一條幾何折疊式全覆蓋路徑對應于一個郵票折疊順序，定義幾何折疊式全覆蓋路徑的存儲方式為一個排列a＝{a1,a2,...,an}，其中ai為折疊前第i個郵票在折疊后所在的層數，由于任意排列下所對應的郵票折疊可能會出現郵票序列自相交的情況，雖然每個幾何折疊式全覆蓋路徑對應于一個排列，然而并非所有的排列a均可對應于一個幾何折疊式全覆蓋路徑，幾何折疊式機器人全覆蓋路徑表示為對應于無郵票折疊自交狀態的排列，將進一步提出隨機生成幾何折疊式全覆蓋路徑的算法、帶順序約束下生成幾何折疊式全覆蓋路徑的算法，以生成出不會產生自相交的排列a，從而進一步獲得幾何折疊式全覆蓋路徑；

本發明提供一種幾何折疊式機器人全覆蓋路徑的生成方法，所述幾何折疊式機器人全覆蓋路徑通過帶順序約束下生成幾何折疊式全覆蓋路徑的算法生成，所述帶順序約束下生成幾何折疊式全覆蓋路徑的算法，步驟如下：

(1)用戶在m x n的格子中，按順序指定需要通過的格點，假設全覆蓋路徑需要按順序通過的行數為L＝{l₁,l₂,…,l_k}；

(2)枚舉所有長度m的序列中選擇k個元素的可能，對于每個選擇，按順序填入l₁,l₂,…,l_k元素，其余元素填0，獲得一個集合的數組，假設所生成的所有數組形成的集合為A，A是幾何折疊式全覆蓋路徑的初始化集合；

(3)從L在{1,2,…,m}中的補集L’＝{1,2,…,m}-L中隨機選擇一個元素l‘，從A中隨機選擇一個數組a，隨機選擇一個a中填0的位置替換為l’，獲得一個新的數組a’；