[發明專利]有限單元地圖的移動機器人路徑規劃方法

有效

• 申請號: 201910342026.7
• 申請日: 2019-04-26
• 公開（公告）號: CN110057362B
• 公開（公告）日: 2022-09-16
• 發明（設計）人: 姜媛媛;時美樂;劉延彬
• 申請（專利權）人: 安徽理工大學
• 主分類號: G01C21/20
• 分類號: G01C21/20
• 代理公司: 暫無信息
• 代理人: 暫無信息

本發明公開一種有限單元地圖的移動機器人路徑規劃方法，首先將連續的可行域離散為有限的單元組合體，用有限單元地圖的節點集合與長度不相等的單元邊的集合建立賦權無向循環圖，然后根據賦權無向循環圖用Dijkstra搜索算法搜索從起始位置到結束位置的所有目標點，通過DouglasPeucker算法對屬于冗余節點的非轉角點的邊緣節點進行刪除，提取關鍵路標，最后用三次自然樣條函數擬合提取到的關鍵路標得到機器人的移動路徑。本發明方法能夠根據機器人所處運行環境的障礙物位置的不同，找到規劃的機器人的無碰撞移動路徑，與實際更相符，尤其適用于在狹長通道的地圖上進行機器人移動路徑規劃。

技術領域

本發明涉及路徑規劃領域，尤其涉及一種有限單元地圖的移動機器人路徑規劃方法。

背景技術

機器人路徑規劃是機器人研究的一個重要領域，也是機器人技術的重要組成部分。機器人路徑規劃問題的重點是尋找從初始配置到目標配置的無碰撞路徑。近年來，該問題通過路線圖、單元分解、勢場方法、基于抽樣的規劃和智能算法得到了很好的解決，但在不同的地圖上，特別是在狹長通道的地圖上，往往不能很好地解決這一問題。

為此，本發明給出一種有限單元地圖的移動機器人路徑規劃方法，為得到最優的無碰撞路徑，建立的有限單元地圖模型，讓其能夠無碰撞地通過長而窄的通道，與實際情況更相符，為移動機器人逃脫各種障礙，規劃最優路徑提供了一種新思路。

發明內容

本發明的目的在于提供一種有限單元地圖的移動機器人路徑規劃方法，用于尋找從初始配置到目標配置的無碰撞路徑，為尋找最優的機器人移動路徑提供了保障。

為了達成上述目的，本發明的解決方案是：

有限單元地圖的移動機器人路徑規劃方法，包括以下步驟(1)～(7)：

(1)機器人運行環境是一個二維封閉平面空間，將機器人可以自由移動的除去障礙物及邊緣的區域稱為可行域，記為C，平面空間C中的障礙物集合為C_Obs＝{Obstacle(1),Obstacle(2),…,Obstacle(n)}，其中，n為障礙物個數；

(2)按照步驟(1)中可行域集合形狀的變化，用普通三角形將連續的可行域離散為有限的單元組合體，用單元邊的集合表示機器人的可行路徑，建立有限單元地圖，將單元地圖中的節點及單元進行編號，并將節點編號轉為節點坐標；

(3)根據步驟(2)中有限單元地圖對各個單元進行組裝，將單元矩陣元素按照相關節點的編號放到整體節點關聯矩陣中，用有限單元地圖的節點集合與長度不相等的單元邊的集合建立賦權無向循環圖；

(4)根據步驟(3)中的賦權無向循環圖將路徑節點分為網格地圖邊緣節點和網格地圖內部節點，網格地圖邊緣節點又分為處于轉角位置的節點和處于非轉角位置的節點；

(5)根據步驟(3)中的賦權無向循環圖，任意確定初始位姿點B₁和終點B_u，用Dijkstra搜索算法依次求取點B₂，B₃，……一直到B_u-1，然后依次連接目標點B₁，B₂，B₃，……一直到B_u其中，u為確定的搜索出的目標點的個數；

(6)根據步驟(5)中搜索出的目標點，采用Douglas-Peucker算法提取機器人行走的關鍵路標K₁，K₂，……K_a，其中步驟(4)中非轉角點的邊緣節點是冗余節點，不作為關鍵路標，直接剔除，a為提取的關鍵路標的個數；

(7)采用三次自然樣條函數擬合步驟(6)中提取的關鍵路標，得到機器人的移動路徑。