[發明專利]機器人導航路徑的搜索方法

有效

• 申請號: 201710698659.2
• 申請日: 2017-09-18
• 公開（公告）號: CN107478232B
• 公開（公告）日: 2020-02-21
• 發明（設計）人: 李明;肖剛軍;李根唐
• 申請（專利權）人: 珠海市一微半導體有限公司
• 主分類號: G01C21/20
• 分類號: G01C21/20
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.一種機器人導航路徑的搜索方法，其特征在于，包括如下步驟：

基于機器人的行進路徑創建柵格地圖；

基于柵格地圖進行區域劃分，形成多個柵格區域；

基于目標位置點，確定從出發位置點到達目標位置點需要經過的待過柵格區域；

基于出發位置點所在的起點柵格區域，搜索所述起點柵格區域與相鄰的第一待過柵格區域交界線上的第一交接點；

確定所述第一交接點后，再搜索所述第一待過柵格區域與相鄰的第二待過柵格區域交界線上的第二交接點；

以此類推，

確定第N交接點后，最后搜索第N待過柵格區域與相鄰的目標位置點所在目標柵格區域交界線上的第N+1交接點；

從出發位置點到第一交接點、第二交接點、第N+1交接點和目標位置點構成的路徑作為導航路徑；

其中，所述N為自然數；

其中，所述基于目標位置點，確定從出發位置點到達目標位置點需要經過的待過柵格區域，包括如下步驟：

確定出發位置點所在的起點柵格區域；

確定與所述起點柵格區域相鄰的已行進區域的權值；

選擇權值最小的已行進區域作為第一待過柵格區域；

再確定與所述第一待過柵格區域相鄰的已行進區域的權值；

選擇權值最小的已行進區域作為第二待過柵格區域；

以此類推，

選擇權值最小的已行進區域作為第N待過柵格區域，所述第N待過柵格區域與所述目標柵格區域相鄰；

其中，如果有兩個或者兩個以上相鄰的已行進區域的權值最小且相同，則隨機選擇并確定其中一個作為待過柵格區域；

所述相鄰為一個柵格區域與另一個柵格區域之間通過一條共同的邊連接；

其中，所述已行進區域的權值的確定，包括如下步驟：

基于XY軸坐標系，賦予每個排布在XY軸坐標系中的柵格區域坐標值；

確定出發位置點所在的起點柵格區域的坐標值為(SX,SY)；

確定已行進區域的坐標值為(CX,CY)；

確定目標位置點所在目標柵格區域的坐標值為(DX,DY)；

確定從起點柵格區域到所述已行進區域的第一開銷為K1，K1＝sqrt((CX-SX)*(CX-SX)+(CY-SY)*(CY-SY))，其中，sqrt為開平方根；

確定從目標柵格區域到所述已行進區域的第二開銷為K2，K2＝abs(CX-DX)+abs(CY-DY)，其中，abs為絕對值；

確定所述已行進區域的權值為Q，Q＝K1+K2；

其中，搜索并確定交界線上的交接點，包括如下步驟：

確定相鄰的柵格區域的交界線；

判斷交界線上的第一參考交接點是否第一接近出發位置點或者上一個交接點，且所述第一參考交接點的通過性是否大于預設寬度；

如果是，則確定第一參考交接點為交接點；

如果否，則判斷交界線上的第二參考交接點是否第二接近出發位置點或者上一個交接點，且所述第二參考交接點的通過性是否大于預設寬度；

如果是，則確定第二參考交接點為交接點；

如果否，則判斷交界線上的第三參考交接點的通過性是否大于其它參考交接點的通過性，且大于預設寬度；

如果是，則確定第三參考交接點為交接點；

如果否，則搜索失敗；

其中，所述通過性為基于參考交接點為中心的連續排布的已行進單元所組成的通過寬度；

或者，搜索并確定交界線上的交接點，包括如下步驟：

確定相鄰的柵格區域的交界線；

判斷交界線上的第一參考交接點是否第一接近出發位置點或者上一個交接點，所述第一參考交接點的通過性是否大于預設寬度，且所述第一參考交接點與所述出發位置點或者上一個交接點之間的路徑是否為有效路徑；

如果是，則確定第一參考交接點為交接點；

如果否，則判斷交界線上的第二參考交接點是否第二接近出發位置點或者上一個交接點，所述第二參考交接點的通過性是否大于預設寬度，且所述第二參考交接點與出發位置點或者上一個交接點之間的路徑是否為有效路徑；

如果是，則確定第二參考交接點為交接點；

如果否，則判斷交界線上的第三參考交接點是否第三接近出發位置點或者上一個交接點，所述第三參考交接點的通過性是否大于預設寬度，且所述第三參考交接點與出發位置點或者上一個交接點之間的路徑是否為有效路徑；

如果是，則確定第三參考交接點為交接點；

以此類推，如果所述交界線上的所有參考交接點不能確定為交接點，則選取上一個交接點所在的交界線上的另一個參考交接點作為新的交接點，再分別與所述相鄰的柵格區域的交界線上的參考交接點進行判斷，直到確定所述參考交接點能夠作為交接點；

如果上一個交接點所在的交界線上的所有參考交接點作為新的交接點，都不能確定所述相鄰的柵格區域的交界線上的交接點，則搜索失敗；

其中，所述通過性為基于參考交接點為中心的連續排布的已行進單元所組成的通過寬度。