[發明專利]一種移動機器人全局路徑規劃方法

在審

• 申請號: 202110872923.6
• 申請日: 2021-07-30
• 公開（公告）號: CN113791610A
• 公開（公告）日: 2021-12-14
• 發明（設計）人: 王磊;李卓恒;王毓
• 申請（專利權）人: 河南科技大學
• 主分類號: G05D1/02
• 分類號: G05D1/02
• 代理公司: 洛陽公信知識產權事務所(普通合伙) 41120
• 代理人: 李現艷

本發明提供了一種移動機器人全局路徑規劃方法，包括以下操作步驟：S1、二維地圖柵格化，同時映射障礙物于對應柵格內，構建“障礙物塊”結構體系；S2、利用障礙物塊與“起點?終點”連線的位置關系繪制邊緣柵格點映射角，比較映射角大小篩選出障礙物塊的左、右登陸點；S3、對所有障礙物塊登陸點進行N鄰域擴展，以擴展結點為頂點，利用碰撞檢測法構建賦權圖；S4、引入Dijkstra算法計算圖中起點至終點的最短路徑并輸出結果。本發明設計了一種活躍于障礙物塊邊緣區域的結點擴展規則，通過尋找位于障礙物塊邊緣的登陸點來限定結點搜索范圍，目的是改進A*的無差別大規模擴展策略，提高大場景下的路徑規劃效率，提升機器人響應速度。

技術領域

本發明涉及智能機器人技術領域，具體涉及一種移動機器人全局路徑規劃方法。

背景技術

人工智能時代的到來已經深刻改變了人類的生活，機器人已不再是簡單的指令執行角色，而是通過對環境的感知朝著更加智能的方向不斷發展。當前，移動機器人已經在各行各業得到廣泛應用，如搬運機器人、送餐機器人、掃地機器人、救援機器人等在執行任務時均要通過路徑規劃準確、高效的計算移動路線。其中，常用的路徑規劃算法有遺傳算法、蜂群算法、蟻群算法、人工勢場法、A*算法等等，不同算法適用場景各有差異，但是在大場景地圖中現有算法均存在著搜索效率低的問題。為此，國內外學者已做了大量工作，但仍存在一些缺陷，如搜索空間大、算法復雜度高等問題。

A*算法以環境適應能力強的特性獲得了非常廣泛的應用，它是 Dijkstra算法與BFS算法的結合，利用啟發函數指導尋路過程，通過計算各結點的代價值，選取待擴展的最佳結點，直至找到最終目標點位置，但缺點是隨著地圖規模的擴大，算法效率大幅下降。

發明內容

為解決上述問題，本發明提供一種移動機器人全局路徑規劃方法，本發明設計了一種活躍于障礙物塊邊緣區域的結點擴展規則，通過尋找位于障礙物塊邊緣的登陸點來限定結點搜索范圍，目的是改進A*的無差別大規模擴展策略，提高大場景下的路徑規劃效率，提升機器人響應速度。

本發明為解決上述技術問題采用的技術方案是：一種移動機器人全局路徑規劃方法，包括以下操作步驟：

S1、二維地圖柵格化，同時映射障礙物于對應柵格內，構建“障礙物塊”結構體系；

S2、利用障礙物塊與“起點-終點”連線的位置關系繪制邊緣柵格點映射角，比較映射角大小篩選出障礙物塊的左、右登陸點；

S3、對所有障礙物塊登陸點進行N鄰域擴展，以擴展結點為頂點，利用碰撞檢測法構建賦權圖；

S4、引入Dijkstra算法計算圖中起點至終點的最短路徑并輸出結果。

進一步的，S1包括如下步驟：

S11、已知地圖大小及障礙物具體分布情況；

S12、依據機器人實際尺寸定義地圖柵格大小，忽略機器人高度，以機器人最長邊作為地圖柵格邊長；

S13、地圖柵格共定義4種類型：起點、終點、自由、障礙；

S14、將地圖中相互鄰接的障礙柵格劃分為一個整體，定義為“障礙物塊”。

進一步的，S14中“障礙物塊”結構體系構建方法如下：

S141、定義柵格地圖對應的二維數組為T并全部賦值為false、存放待檢測結點列表為L_obstacle、當前障礙物塊為B_obstacle、障礙物塊列表為L_OB；

S142、檢測當前柵格點，如果是障礙物，則將當前柵格點存入列表L_obstacle中，并將當前柵格點在數組T的相應位置寫入true；