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

在審

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

1.一種基于改進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)使用平滑器對離散的所述整條路徑進行平滑即可。

2.根據權利要求1所述基于改進A星策略的移動機器人路徑規劃方法，其特征在于：步驟(a)中，遍歷所述柵格地圖的像素，當其value為0，那么賦值0；否則value＞0，賦值1。

3.根據權利要求1所述基于改進A星策略的移動機器人路徑規劃方法，其特征在于：步驟(c)中，控制α和的參數值使勢能值均勻地從障礙物到Voronoi圖的邊上連續分布。

4.根據權利要求1所述基于改進A星策略的移動機器人路徑規劃方法，其特征在于：步驟(d)中，還判斷所述起點和終點的柵格是否被障礙物占據。

5.根據權利要求1所述基于改進A星策略的移動機器人路徑規劃方法，其特征在于，當所述開列表不為空且所述終點的g代價值為無窮時進入循環，包括以下步驟：

(e1)定義f代價值中最小的節點為當前節點，標記為正在被訪問，并將該節點從所述開列表中刪除；

(e2)選取在地圖上且不存在障礙物的節點作為所述當前節點的相鄰節點；

當所述相鄰節點的g代價值為無窮，計算所述當前節點的g代價值：當所述相鄰節點位于直線上時，g代價值為g(v_i)＝g(v_i-1)+1×(1+w×p(v_i))；當所述相鄰節點位于對角斜線上時，g代價值為其中，v_i表示第i個節點，w為勢能的權值系數，p(v_i)表示在該點的勢能值；計算所述當前節點的總代價值f(v_i)＝g(v_i)+α₁×h(v_i)，h(v_i)為啟發函數代價值h(v_i)＝|x₁-x₂|+|y₁-y₂|，并把所述當前節點裝入開列表；

當所述相鄰節點的g代價值非無窮，跳過所述相鄰節點不再訪問；

(e3)重復步驟(e1)和(e2)繼續尋找，直至找到終點，回溯整條路徑。

6.根據權利要求1所述基于改進A星策略的移動機器人路徑規劃方法，其特征在于，步驟(f)包括以下步驟：

(f1)將所述整條路徑按照公式分成k段；其中為向上取整，length為路徑長度；step為步長且step＝λ/resolution，λ是可設步長參數，resolution是地圖分辨率；

隨后對每段路徑按以下公式求平均坐標點：ave_x_i＝sum_x_i/step_i、ave_y_i＝sum_y_i/step_i，其中i∈[1,k)為整數，sum_x_i＝sum_x_i-1+x_i，sum_y_i＝sum_y_i-1+y_i；收集所述平均坐標點作為采樣點；

(f2)使用三次樣條插值算法對所述采樣點進行插值即可。