[發(fā)明專利]有限單元地圖的移動機器人路徑規(guī)劃方法

有效

• 申請?zhí)枺?/td>: 201910342026.7
• 申請日: 2019-04-26
• 公開（公告）號: CN110057362B
• 公開（公告）日: 2022-09-16
• 發(fā)明（設計）人: 姜媛媛;時美樂;劉延彬
• 申請（專利權(quán)）人: 安徽理工大學
• 主分類號: G01C21/20
• 分類號: G01C21/20
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.一種有限單元地圖的移動機器人路徑規(guī)劃方法，其特征在于，包括以下步驟：

(1)機器人運行環(huán)境是一個二維封閉平面空間，將機器人可以自由移動的除去障礙物及邊緣的區(qū)域稱為可行域，記為C，平面空間C中的障礙物集合為C_Obs＝{Obstacle(1),Obstacle(2),…,Obstacle(n)}，其中，n為障礙物個數(shù)；

(2)按照步驟(1)中可行域集合形狀的變化，用普通三角形將連續(xù)的可行域離散為有限的單元組合體，用單元邊的集合表示機器人的可行路徑，建立有限單元地圖，將單元地圖中的節(jié)點及單元進行編號，并將節(jié)點編號轉(zhuǎn)為節(jié)點坐標；

(3)根據(jù)步驟(2)中有限單元地圖對各個單元進行組裝，將單元矩陣元素按照相關(guān)節(jié)點的編號放到整體節(jié)點關(guān)聯(lián)矩陣中，用有限單元地圖的節(jié)點集合與長度不相等的單元邊的集合建立賦權(quán)無向循環(huán)圖；

(4)根據(jù)步驟(3)中的賦權(quán)無向循環(huán)圖將路徑節(jié)點分為網(wǎng)格地圖邊緣節(jié)點和網(wǎng)格地圖內(nèi)部節(jié)點，網(wǎng)格地圖邊緣節(jié)點又分為處于轉(zhuǎn)角位置的節(jié)點和處于非轉(zhuǎn)角位置的節(jié)點；

(5)根據(jù)步驟(3)中的賦權(quán)無向循環(huán)圖，任意確定初始位姿點B₁和終點B_u，用Dijkstra搜索算法依次求取點B₂，B₃，……一直到B_u-1，然后依次連接目標點B₁，B₂，B₃，……一直到B_u其中，u為確定的搜索出的目標點的個數(shù)；

(6)根據(jù)步驟(5)中搜索出的目標點，采用Douglas-Peucker算法提取機器人行走的關(guān)鍵路標K₁，K₂，......K_a，其中步驟(4)中非轉(zhuǎn)角點的邊緣節(jié)點是冗余節(jié)點，不作為關(guān)鍵路標，直接剔除，a為提取的關(guān)鍵路標的個數(shù)；

(7)采用三次自然樣條函數(shù)擬合步驟(6)中提取的關(guān)鍵路標，得到機器人的移動路徑。

2.如權(quán)利要求1所述有限單元地圖的移動機器人路徑規(guī)劃方法，其特征在于，所述步驟(2)中用普通三角形將連續(xù)的可行域離散為有限的單元組合體，其中，三角形剖分的有限單元地圖用節(jié)點矩陣及單元連接矩陣表示，記剖分后的可行域有m個節(jié)點和k個單元，第i個節(jié)點P_i的坐標為(x_i,y_i)，則節(jié)點矩陣P可以表示為單元連接矩陣可以表示為其中表示第j個單元的第i個節(jié)點的編號；此外單元連接矩陣還表示單元連接節(jié)點的關(guān)系，即在第j個單元中，與連接，與連接，與連接。

3.如權(quán)利要求1所述有限單元地圖的移動機器人路徑規(guī)劃方法，其特征在于，所述步驟(3)將單元矩陣元素按照相關(guān)節(jié)點的編號放到整體節(jié)點關(guān)聯(lián)矩陣中，由單元連接矩陣，構(gòu)造節(jié)點關(guān)聯(lián)矩陣T與S，T＝[t₁ t₂ … t_n]，S＝[s₁ s₂ … s_n]，節(jié)點連接矩陣T與S中的元素均是網(wǎng)格節(jié)點編號，T中的第i個節(jié)點t_i與S中的第i個節(jié)點s_i相互關(guān)聯(lián)，且表示節(jié)點t_i與節(jié)點s_i連接，由于任意兩節(jié)點之間的距離不同，故定關(guān)聯(lián)矩陣T與S的距離矩陣D＝[d₁ d₂ … d_n]，D中的元素d_i表示節(jié)點關(guān)聯(lián)矩陣T中的第i個節(jié)點t_i與S中的第i節(jié)點s_i的距離，節(jié)點關(guān)聯(lián)矩陣T、S與節(jié)點距離矩陣D可以構(gòu)成稀疏矩陣表示的賦權(quán)無向連通矩陣G＝sparse(Τ,S,D)，基于有限單元的地圖矩陣map表示為節(jié)點矩陣P與無向連通圖矩陣組成的關(guān)聯(lián)矩陣map＝(P,G)。

4.如權(quán)利要求1所述有限單元地圖的移動機器人路徑規(guī)劃方法，其特征在于，所述步驟(6)中從步驟(4)得到的非轉(zhuǎn)角點的邊緣節(jié)點是冗余節(jié)點，不作為關(guān)鍵路標，直接剔除，對剔除非轉(zhuǎn)角點后的邊緣集合點采用Douglas-Peucker算法提取關(guān)鍵路標點。