[發明專利]一種基于空間約束A星算法的移動機器人路徑規劃方法

在審

• 申請號: 202210292480.8
• 申請日: 2022-03-23
• 公開（公告）號: CN114578828A
• 公開（公告）日: 2022-06-03
• 發明（設計）人: 路永樂;韓亮;楊杰;王汶新;修蔚然;邸克;劉宇;馮濤
• 申請（專利權）人: 重慶郵電大學
• 主分類號: G05D1/02
• 分類號: G05D1/02
• 代理公司: 重慶市恒信知識產權代理有限公司 50102
• 代理人: 劉小紅

1.一種基于空間約束A星算法的移動機器人路徑規劃方法，其特征在于，包括以下步驟：

步驟1：根據實際工作場景面積和所需地圖分辨率構建柵格地圖Map，將場景障礙物在Map中所占的柵格標記為不可通行柵格；

步驟2：結合步驟1建立的柵格地圖Map，確定機器人的實體覆蓋柵格矩陣S和安全制動距離L；

步驟3：在A星算法中，增加機器人實體覆蓋柵格矩陣S和安全制動距離L兩個約束進行路徑擇優規劃，得到機器人從起點格柵到目標格柵的安全有效的路徑。

2.根據權利要求1所述的一種基于空間約束A星算法的移動機器人路徑規劃方法，其特征在于：所述步驟1中根據實際工作場景面積和所需地圖分辨率構建柵格地圖Map，將場景障礙物在Map中所占的柵格標記為不可通行柵格，具體為：

根據實際工作場景面積和所需地圖分辨率m×n，利用柵格法構建柵格地圖Map，將工作環境劃分為m×n的柵格矩陣，每個柵格的長和寬都為k(mm)，并根據場景障礙物在柵格地圖Map中所占的柵格位置，標記出不可通行柵格，其余柵格則為可通行柵格。

3.根據權利要求1所述的一種基于空間約束A星算法的移動機器人路徑規劃方法，其特征在于：所述步驟2結合步驟1建立的柵格地圖Map，確定機器人的實體覆蓋柵格矩陣S和安全制動距離L，具體為：

機器人的實體覆蓋柵格矩陣S為當前時刻機器人在柵格地圖Map中所占柵格的集合，安全制動距離L為柵格地圖Map中柵格的邊長k。

4.根據權利要求1所述的一種基于空間約束A星算法的移動機器人路徑規劃方法，其特征在于：步驟3所述的路徑擇優規劃的方法為：

步驟3.1：在柵格地圖Map中，確定機器人路徑規劃的起點柵格和目標柵格，并將第j時刻機器人的實體覆蓋柵格矩陣S的中心柵格用M_j-1來表示，其中，j為整數(1～路徑規劃的柵格數)，j-1表示該中心柵格的父節點個數，j-1＝0時無父節點柵格；初始化時j＝1，初始中心柵格M₀與起點柵格重合，然后將所述初始中心柵格M₀的完整信息集放入closelist中完成路徑規劃的初始化，中心柵格的完整信息集包括：中心柵格M_j-1的坐標、該柵格的父節點柵格M_(j-1)-1坐標和路徑代價F；用close list存放已經路徑規劃過的中心柵格的完整信息集，放入close list中的柵格將不再參與后續的路徑規劃計算；用open list存放計算路徑規劃中的可通行柵格的部分信息集，所述可通行柵格的部分信息集包括：柵格的坐標和路徑代價F；

步驟3.2：判斷所述柵格M_j-1相鄰的八領域柵格N_i中的第i個柵格(i為1～8整數)，是否為不可通行柵格，或者是否為close list中的柵格，若為不可通行柵格，則忽略該柵格N_i；若為可通行柵格則進行下一步；

步驟3.3：根據可通行的柵格N_i和安全制動距離L對柵格矩陣S進行映射處理，得到映射柵格矩陣S'，然后判斷柵格矩陣S'中是否存在不可通行柵格，若存在，則忽略柵格N_i后返回步驟3.2；

步驟3.4：計算可通行柵格N_i的路徑代價F，判斷該柵格N_i是否在open list中，若不在則把該柵格N_i當前的部分信息集放入open list中，若該柵格N_i已經存在于open list中則將該柵格N_i當前的部分信息集替換已有的部分信息集；

步驟3.5：判斷柵格N_i中i是否小于等于8，若是，則返回步驟3.2，八領域柵格都遍歷后,對open list中的所有柵格根據F值從小到大進行排序，取F值最小的柵格作為下一時刻機器人的實體覆蓋柵格矩陣S的中心柵格M_j，然后將柵格M_j移出open list，再將當前時刻的中心柵格M_j-1設為下一時刻柵格M_j的父節點柵格；最后將柵格M_j-1的完整信息集移入closelist中；

步驟3.6：重復步驟3.2、步驟3.3、步驟3.4和步驟3.5,直至目標柵格加入了close list中，此時路徑規劃已經完成，從close list中所有柵格的完整信息集中的父節點柵格信息來逆向搜尋路徑，逆向的連線構成優化路徑，完成路徑規劃并保存路徑，若目標柵格沒有加入close list中，則路徑規劃計算繼續進行。