[發明專利]一種基于Delaunay三角形的移動機器人安全路徑規劃方法

有效

• 申請號: 202110206299.6
• 申請日: 2021-02-24
• 公開（公告）號: CN112987735B
• 公開（公告）日: 2022-06-14
• 發明（設計）人: 陳啟軍;劉志浩;李樹;劉成菊
• 申請（專利權）人: 同濟大學
• 主分類號: G05D1/02
• 分類號: G05D1/02
• 代理公司: 上海科盛知識產權代理有限公司 31225
• 代理人: 林君如

本發明涉及一種基于Delaunay三角形的移動機器人安全路徑規劃方法，提取工作環境的全局代價地圖可行域的輪廓，按照設定的窗口尺寸和步長在地圖內滑動窗口，計算窗口覆蓋區域的分形維度；根據分形維度得到每個窗口內初始點的位置分布；以所有窗口內初始點為頂點構建Delaunay三角形網；遍歷三角形網，計算每個三角形的重心，以所有三角形的重心為頂點再次構建Delaunay三角形網；遍歷新生成的三角形網，剔除位于障礙物內的頂點和通過障礙物的邊，將剩余頂點、邊及其連接關系構成路徑網；在路徑網內搜索從起點至終點的一條路徑；逐漸收縮路徑，直至收縮前后路徑相同，獲取最優路徑。本發明規劃的路徑安全可靠，且極大地提高路徑搜索和剪枝的效率。

技術領域

本發明涉及移動機器人路徑規劃技術領域，尤其是涉及一種基于Delaunay三角形的移動機器人安全路徑規劃方法。

背景技術

路徑規劃是移動機器人移動的基礎，是保障移動機器人在不同目標點之間正確、安全移動的必要組成部分。如何基于全局代價快速地得到移動機器人當前位置到目標位置的最優路徑是移動機器人領域的一個研究熱點。現階段路徑規劃方法主要可以分為：

基于搜索的路徑規劃方法：例如利用A*算法、Dijkstra算法等進行路徑搜索，將代價地圖的每一個像素點作為一個節點，從某一節點出發遍歷鄰域尋找下一節點進而找到從起點到終點的路徑，能夠保證任意點可達，搜索效率較高，該類方法一般能夠搜索到最短或者接近最短的全局路徑，然而這種方法在搜索路徑的過程中遇到障礙物會選擇貼近障礙物邊界繞行，這種情況下得到的路徑貼近障礙物邊界，既不是最優路徑也不接近最優，且控制機器人沿著障礙物邊界移動對機器人的運動控制方法提出了較高的要求，這類方法得到的路徑并不安全。

基于概率的路徑規劃方法：例如基于快速搜索隨機樹算法(RRT)、概率路線圖算法(PRM)等進行路徑規劃，不可避免的使用隨機操作，或是隨機游走或是初始化隨機點，基于隨機通常不會使離散點靠近障礙物邊界，得到的路徑相較于搜索的路徑規劃方法更加安全，但是這類方法的搜索效率與任意點可達存在矛盾，如果任意點可達則搜索時間將會加長，保證搜索效率則難以保證任意點可達，而且此類方法搜索的路徑不具備穩定性，得到的路徑隨搜索次數的變化而變化。

基于智能的路徑規劃方法：如基于蟻群算法，魚群算法、遺傳算法、神經網絡等進行路徑規劃，主要仿照自然界生物的習性建立搜索算法；啟發式方法往往無法得到移動機器人當前位置到目標位置的最優路徑，此類方法相較于前兩種方法更加智能，但其搜索效率普遍低于其他方法，耗時長且很多情況下無法得到起點到終點的最佳路徑甚至無法得到可行路徑，且存在難以收斂和震蕩等問題，較難應用于實際。

發明內容

本發明的目的就是為了克服上述現有技術存在的缺陷而提供一種基于Delaunay三角形的移動機器人安全路徑規劃方法。

本發明的目的可以通過以下技術方案來實現：

一種基于Delaunay三角形的移動機器人安全路徑規劃方法，該方法包括如下步驟：

S1：建立并讀取工作環境的全局代價地圖，基于Canny算子提取全局代價地圖可行域的輪廓，獲取輪廓地圖。

S2：設定窗口尺寸和步長，按照設定的窗口尺寸和步長在輪廓地圖內滑動窗口，并計算每個窗口對應覆蓋區域的分形維度。

S3：根據每個窗口的分形維度，通過一個映射函數分別得到每個窗口內初始點的位置分布。

S4：以所有窗口內初始點為頂點構建Delaunay三角形網。

S5：遍歷步驟S4生成的Delaunay三角形網，計算其中每個三角形的重心，以所有三角形的重心為頂點再次構建Delaunay三角形網。

S6：遍歷步驟S5再次生成的Delaunay三角形網，基于Bresenham算法剔除位于障礙物內的頂點和通過障礙物的邊，將剩余的頂點、邊及其連接關系構成路徑網。