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

在審

• 申請號: 201710253824.3
• 申請日: 2017-04-18
• 公開（公告）號: CN108731678A
• 公開（公告）日: 2018-11-02
• 發明（設計）人: 謝鋒
• 申請（專利權）人: 深圳市豐巨泰科電子有限公司
• 主分類號: G01C21/20
• 分類號: G01C21/20
• 代理公司: 深圳市神州聯合知識產權代理事務所(普通合伙) 44324
• 代理人: 周松強

1.一種機器人全局路徑規劃方法，該方法包括環境建模、路徑規劃，其特征在于該方法通過二維空間進行環境建模，且通過基于切比雪夫距離的算法實現路徑規劃。

2.如權利要求1所述的機器人全局路徑規劃方法，其特征在于所述二維空間是將機器人的工作空間取為二維空間，無障礙物的柵格稱為自由柵格，含有障礙物的柵格成為障礙柵格，為保證安全性，不滿一個柵格的均按一個柵格處理；對于二維空間中劃分的柵格采用直角坐標系法來進行標識，通過這種方式進行環境建模。

3.如權利要求2所述的機器人全局路徑規劃方法，其特征在于所示環境模型建立后，對柵格環境模型進行信息編碼：障礙柵格信息記為1；自由柵格信息記為0，然后用整型二維數組來存儲環境模型信息，形成信息模型。

4.如權利要求1所述的機器人全局路徑規劃方法，其特征在于通過算法對環境中的節點進行搜索，使得從初始節點到目標節點的估價函數最小或接近最小。

5.如權利要求4所述的機器人全局路徑規劃方法，其特征在于所述估價函數定義如下：

f(n)＝g(n)+h(n)

其中f(n)是初始節點經過節點n到達目標節點的估價函數，g(n)是初始節點到節點n的實際代價，h(n)是節點n到目標節點最理想路徑的估計代價。

6.如權利要求5所述的機器人全局路徑規劃方法，其特征在于所述算法中涉及兩個隊列：OPEN隊列和CLOSED隊列，OPEN隊列保存了所有沒有訪問的節點，該隊列中估價值最小的節點將被父節點優先訪問，CLOSED隊列中保存了已經訪問過的節點，選取最后訪問的節點向周圍節點試探，將可以移動且估價值最小的節點放入CLOSED隊列。

7.如權利要求1所述的機器人全局路徑規劃方法，其特征在于所述路徑具體規劃流程如下：

1)把起始柵格添加到OPEN列表中；

2)計算路徑；

3)保存路徑，從目標柵格開始，沿著每一柵格的父節點移動直到回到起始柵格，由此得到所搜索到的路徑。

8.如權利要求7所述的機器人全局路徑規劃方法，其特征在于步驟2)中，具體包括如下步驟：

a)尋找開啟列表中f值最低的柵格，將它作為當前柵格；

b)把它切換到CLOSED列表；

c)對相鄰的8個柵格均做如下處理：

如果它在CLOSED列表中或存在障礙，忽略它；否則執行如下操作：

如果它在OPEN列表中，對新的路徑求取g值；如果g值變小，則把該柵格的父節點改成當前柵格，并且重新計算該柵格的g和f值；

如果它不在OPEN列表中，把它添加進去。把當前柵格作為這一柵格的父節點。記錄這一柵格的f，g和h值。

d)退出，當：

把目標柵格添加進了CLOSED列表，此時路徑規劃完成。

9.如權利要求8所述的機器人全局路徑規劃方法，其特征在于，采用切比雪夫距離將二個點之間的距離定義為其各坐標數值差的絕對值的最大值，其切比雪夫距離為

Max(|x₂-x₁|,|y₂-y₁|)

采用此距離求取h(n)，公式為：

h(n)＝A×Max(dx,dy)

其中，dx，dy分別是當前節點n與目標點的x，y方向的坐標差的絕對值，系數A默認取1(可以調整)。