[發明專利]一種基于改進A星策略的移動機器人路徑規劃方法

在審

• 申請號: 201810506586.7
• 申請日: 2018-05-24
• 公開（公告）號: CN108549388A
• 公開（公告）日: 2018-09-18
• 發明（設計）人: 翟冬靈;葛凱;張二陽
• 申請（專利權）人: 蘇州智偉達機器人科技有限公司
• 主分類號: G05D1/02
• 分類號: G05D1/02
• 代理公司: 南京禾易知識產權代理有限公司 32320
• 代理人: 仇波

本發明涉及一種基于改進A星策略的移動機器人路徑規劃方法，它包括以下步驟：（a）將移動機器人獲取的激光數據和里程數據用slam算法進行處理；（b）利用動態維諾圖庫將二值化的所述柵格地圖構建成Voronoi圖；（c）根據所述Voronoi圖上的節點坐標，并構建對應的Voronoi代價地圖；（d）將所述移動機器人的起點和終點位置從其自身坐標系轉換到地圖坐標系上，檢查起點和終點的坐標索引是否合法；（e）初始化所有所述節點的g代價值；（f）使用平滑器對離散的所述整條路徑進行平滑處理。大大節約了內存和計算資源，加快了算法的收斂速度；還融入了Voronoi圖，使路徑遠離障礙物，最后使用平滑器得到一條最佳路徑。

技術領域

本發明屬于工業機器人領域，涉及一種移動機器人路徑規劃方法，具體涉及一種基于改進A星策略的移動機器人路徑規劃方法。

背景技術

全局路徑規劃的主要作用是在已知的靜態地圖上，找到一條從起點到終點的最優或近似最優路徑，該路徑一般為連續，平滑，無障礙物，且適合機器人直接執行的全局路徑。路徑規劃算法是整個導航系統中的基礎，它的結果為后續的局部軌跡規劃提供了路徑信息。

目前常用的路徑規劃算法有很多，主要可分為三大類：基于圖搜索的方法，如Dijkstra、A*(即A星)、D*、Theta*等；基于隨機采用的方法，如隨機路徑圖法(PRM)、快速搜索樹法(RRT)等；還有一些基于啟發式的算法，經典的有蟻群算法，遺傳算法，粒子群算法等。Dijkstra是圖搜索方法的鼻祖，保證能找到一條全局最優解，但其會遍歷整個地圖的所有柵格，因此計算量很大，尤其是在大地圖下。A*在Dijkstra基礎上引入了啟發式搜索解決了上述問題，在保證了最優解的前提下大大提高了搜索的效率，因其簡單且易于實現而盛行至今。基于啟發式的算法都需要對確定空間中的障礙物進行建模，通常收斂速度較慢，無法滿足機器人實時性的要求。隨機采樣的方法避免了對空間的建模，通過狀態空間的隨機采樣點來尋找一條概率完備且不最優的路徑；但該類方法對環境不敏感，當有較窄的通道時，往往會收斂很慢，甚至會被圍困在障礙物里；此外，安全性一直是工業機器人考慮的前提，現有算法規劃出的路徑都靠近障礙物，無法保證機器人行走過程中的安全。在工業上，往往會面臨工廠車間等大尺寸地圖的情形，因此，如何加快算法的收斂速度，提高機器人的實時性成為主要關注的焦點。

發明內容

本發明目的是為了克服現有技術的不足而提供一種基于改進A星策略的移動機器人路徑規劃方法。

為達到上述目的，本發明采用的技術方案是：一種基于改進A星策略的移動機器人路徑規劃方法，它包括以下步驟：

(a)將移動機器人獲取的激光數據和里程數據用slam算法進行處理獲得.pgm格式的柵格地圖，通過二維數組使所述柵格地圖二值化；

(b)利用動態維諾圖庫將二值化的所述柵格地圖構建成Voronoi圖；

(c)根據所述Voronoi圖上的節點坐標，通過公式(Ⅰ)計算獲得對應節點的勢能，并構建對應的Voronoi代價地圖；

式中，α為勢能的下降速率，為勢能的控制范圍；

(d)將所述移動機器人的起點和終點位置從其自身坐標系轉換到地圖坐標系上，檢查起到和終點的坐標索引是否合合法；所述地圖坐標系為所述移動機器人獲取的激光數據和里程數據坐標系；

(e)初始化所有所述節點的g代價值使g(n_i)＝∞，其中n為節點，i＝1,…,mapsize；新建一個開列表，計算所述起點的總代價值f(s)＝g(s)+α₁×h(s)，其中s為起點，α₁為權重系數，然后將所述起點裝入所述開列表；當所述開列表不為空且所述終點的g代價值為無窮時進入循環，直到找到目標點，然后回溯整條路徑；

(f)使用平滑器對離散的所述整條路徑進行平滑即可。