[發明專利]一種針對柵格圖模型下的移動機器人路徑優化方法

有效

• 申請號: 202110845931.1
• 申請日: 2021-07-26
• 公開（公告）號: CN113467471B
• 公開（公告）日: 2022-12-09
• 發明（設計）人: 李東東;王雷;江本赤;王安恒;黃勝洲;王風濤;耿賽;馬康康
• 申請（專利權）人: 安徽工程大學
• 主分類號: G05D1/02
• 分類號: G05D1/02
• 代理公司: 安徽省蚌埠博源專利商標事務所(普通合伙) 34113
• 代理人: 楊晉弘

1.一種針對柵格圖模型下的移動機器人路徑優化方法，設定已知真實環境柵格化建模后的0-1矩陣M，以及算法初步給出的最短路徑的節點列表??=[(0,0),(??₁,??₁),(??₂,??₂),…(??_??,??_??)]，其中，每個元素(??_I,??_j)代表坐標第i列第j行的節點，并定義路徑節點列表中所有發生轉折的節點成為轉折點，所有與障礙物“擦肩而過”的節點稱為臨界點，考慮到這兩種節點中的一部分將構成最終優化路徑的轉折點，將這兩種轉折點與臨界點統稱為奇異點，其特征在于包括以下步驟：

S1、找到路徑節點列表中的所有奇異點，存入并輸出列表L1；

S2、令i=0；

S3、并判斷i≤len(L1)-2其中len(L1)為列表L1的長度，若滿足則執行S4，否則執行S9；

S4、依次從L1中取出位置為i、i+1、i+2的三個節點信息并設為a、b、c；

S5、判斷b是否為臨界點，若是，則令i = i+1，并執行S2，否則執行S6；

S6、調用優化函數opt_fun()，并將返回結果存于result變量中，執行S7；

S7、判斷result是否為空，若是，執行S7.1；若否，則執行S8；

S7.1、此時，代表a、c節點可以直接相連，刪除節點b，并令i = i-1，執行S3；

S8、若為否，則代表a、c無法直接相連，需要添加中間節點result，即在a、b之間插入新節點result，并令i = i+1，執行S3；

S9、輸出L1，即為優化后的最短路徑節點信息；

其中，優化函數opt_fun()的步驟如下：

S1、調用is_accross_barrier(a,c)函數判斷a、c兩個節點是否能直接連接，并將結果存入re中，執行S2；

S2、是否re[0]=True，若是，執行S3；否則執行S4；

S3、返回值None，退出子程序；

S4、調用deep_opt(a,b,c)進行優化，并將結果存于pot中；執行S5；

S5、返回值pot，退出子程序。

2.根據權利要求1所述的一種針對柵格圖模型下的移動機器人路徑優化方法，其特征在于：

所述is_accross_barrier(a,c)函數判斷a、c兩點之間是否能直接連接的方法如下：

借助分治算法的思想，通過逐個優化處理局部線段，最終將所有的局部優化結果進行組合，從而構成整體的優化最終效果；

整體優化問題轉化為局部的優化問題，經過一定分析可得，局部的待處理情況分為可直接連接與不可直接連接兩種，具體方法是，連接S與T，設為線段Q，則通過微元法從Q上，以S為起點，以T為終點，選取N個等間距點，先依據其坐標判定其所處的柵格的坐標，檢查該柵格是否存在障礙物，若所有等間距點所處的柵格皆為非障礙物柵格，則意味著兩點可以直接連接，反之，則不能直接連接。

3.根據權利要求1所述的一種針對柵格圖模型下的移動機器人路徑優化方法，其特征在于：

所述deep_opt(a,b,c)函數尋找a、c兩點之間中介節點的方法如下：

先連接S與T，依據公式在ST上找到M＇，連接MM＇，以M為起點，以M＇為終點，選取若干等間距點M₁, M₂, M₃,… ,M_n，逐一取出，并判斷S-M_i–T是否可以直接連接，若可以直接連接，則繼續判斷S-M_i+1–T，否則，當存在某一條邊不能直接連接時，先找到阻隔的障礙物柵格的位置，判斷其4個頂點分別與線段SM_i+1與線段M_i+1 T的距離，找到距離最小的那個頂點，頂點P為距離最小的頂點，因此，頂點P為中介節點。