[發明專利]并行-交替式雙向跳點搜索的移動機器人路徑規劃方法

在審

• 申請號: 202211095135.1
• 申請日: 2022-09-05
• 公開（公告）號: CN115355924A
• 公開（公告）日: 2022-11-18
• 發明（設計）人: 齊本勝;苗紅霞
• 申請（專利權）人: 南京奧特文智能科技有限公司
• 主分類號: G01C21/34
• 分類號: G01C21/34
• 代理公司: 北京中濟緯天專利代理有限公司 11429
• 代理人: 丁燕華

本發明公開了一種并行?交替式雙向跳點搜索的移動機器人路徑規劃方法，包含以下步驟：（1）構建柵格地圖；（2）對障礙物進行膨脹處理；（3）確定中心熱點區域；（4）使用并行式雙向跳點搜索算法，分別規劃從起點到中心熱點區域的路徑和目標點到中心熱點區域的路徑；（5）在中心熱點區域內部，使用交替式雙向跳點搜索算法，從正反兩個方向規劃路徑；（6）修正存在碰撞隱患的局部路徑。本方法先后使用了并行式和交替式的雙向跳點搜索算法對移動機器人的運行路徑進行規劃，有效地縮短了路徑規劃的時間，同時針對跳點搜索算法存在的路徑緊貼障礙物問題，進行了路徑優化，增加了機器人運行的安全性，具有良好的應用前景。

技術領域

本發明涉及移動機器人路徑規劃技術領域，尤其是一種并行-交替式雙向跳點搜索的移動機器人路徑規劃方法。

背景技術

隨著科學技術的進步，移動機器人的應用領域越來越多，包括工業生產領域、救援探索領域、服務領域以及軍事領域等等。移動機器人的出現給人們生活帶來了許多便利，因此移動機器人技術得到了世界各國的普遍關注。路徑規劃技術是移動機器人技術的重要內容，其在降低移動機器人的能耗、提高移動機器人的安全性等方面發揮了重要作用。2011年D.Harabor提出了跳點搜索算法，跳點搜索算法是在A*算法的基礎上進行優化，其跳過了A*算法在擴展過程中的無用節點，只保留用于擴展的關鍵跳點。因此，跳點搜索算法極大地提高了路徑規劃的速度。然而，跳點搜索算法在障礙物位置復雜或障礙物位置隨機的情況下，關鍵跳點數量攀升，路徑規劃速度將大大降低，同時由于跳點搜索算法沒有考慮移動機器人的體積大小，其規劃出的路徑存在著緊貼障礙物的問題，這將給移動機器人的運行帶來安全風險。

發明內容

為解決上述存在的技術問題，本發明提供了一種并行-交替式雙向跳點搜索的移動機器人路徑規劃方法。本方法先后使用了并行式和交替式的雙向跳點搜索算法對移動機器人的運行路徑進行規劃，有效地縮短了路徑規劃的時間，同時針對跳點搜索算法存在的路徑緊貼障礙物問題，進行了路徑優化，增加了機器人運行的安全性。

本發明的技術方案如下：

一種并行-交替式雙向跳點搜索的移動機器人路徑規劃方法，包括以下步驟：

(1)構建柵格地圖；

(2)對障礙物進行膨脹處理；

(3)確定中心熱點區域；

(4)使用并行式雙向跳點搜索算法，分別規劃從起點到中心熱點區域的路徑和目標點到中心熱點區域的路徑；

(5)在中心熱點區域內部，使用交替式雙向跳點搜索算法，從正反兩個方向規劃路徑；

(6)修正存在碰撞隱患的局部路徑。

優選地，上述步驟(2)中對障礙物進行膨脹處理的步驟如下：

步驟(2-1)：使用2*2大小的正方形滑動窗口，掃描柵格地圖；

步驟(2-2)：判斷正方形滑動窗口的對角線上是否存在障礙物，若是則執行步驟(2-3)，若否則退出膨脹處理；

步驟(2-3)：在正方形滑動窗口內部的柵格地圖中填補虛擬障礙物。

優選地，上述步驟(3)里中心熱點區域的形狀為圓形，確定中心熱點區域的步驟如下：

步驟(3-1)：根據公式(1)，計算起點與目標點的中心點柵格位置；

公式(1)中，x_center和y_center是起點與目標點的中心點的柵格位置坐標，x_start和y_start是起點的柵格位置坐標，x_goal和y_goal是目標點的柵格位置坐標；