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

有效

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

本發(fā)明公開(kāi)一種有限單元地圖的移動(dòng)機(jī)器人路徑規(guī)劃方法，首先將連續(xù)的可行域離散為有限的單元組合體，用有限單元地圖的節(jié)點(diǎn)集合與長(zhǎng)度不相等的單元邊的集合建立賦權(quán)無(wú)向循環(huán)圖，然后根據(jù)賦權(quán)無(wú)向循環(huán)圖用Dijkstra搜索算法搜索從起始位置到結(jié)束位置的所有目標(biāo)點(diǎn)，通過(guò)DouglasPeucker算法對(duì)屬于冗余節(jié)點(diǎn)的非轉(zhuǎn)角點(diǎn)的邊緣節(jié)點(diǎn)進(jìn)行刪除，提取關(guān)鍵路標(biāo)，最后用三次自然樣條函數(shù)擬合提取到的關(guān)鍵路標(biāo)得到機(jī)器人的移動(dòng)路徑。本發(fā)明方法能夠根據(jù)機(jī)器人所處運(yùn)行環(huán)境的障礙物位置的不同，找到規(guī)劃的機(jī)器人的無(wú)碰撞移動(dòng)路徑，與實(shí)際更相符，尤其適用于在狹長(zhǎng)通道的地圖上進(jìn)行機(jī)器人移動(dòng)路徑規(guī)劃。

技術(shù)領(lǐng)域

本發(fā)明涉及路徑規(guī)劃領(lǐng)域，尤其涉及一種有限單元地圖的移動(dòng)機(jī)器人路徑規(guī)劃方法。

背景技術(shù)

機(jī)器人路徑規(guī)劃是機(jī)器人研究的一個(gè)重要領(lǐng)域，也是機(jī)器人技術(shù)的重要組成部分。機(jī)器人路徑規(guī)劃問(wèn)題的重點(diǎn)是尋找從初始配置到目標(biāo)配置的無(wú)碰撞路徑。近年來(lái)，該問(wèn)題通過(guò)路線圖、單元分解、勢(shì)場(chǎng)方法、基于抽樣的規(guī)劃和智能算法得到了很好的解決，但在不同的地圖上，特別是在狹長(zhǎng)通道的地圖上，往往不能很好地解決這一問(wèn)題。

為此，本發(fā)明給出一種有限單元地圖的移動(dòng)機(jī)器人路徑規(guī)劃方法，為得到最優(yōu)的無(wú)碰撞路徑，建立的有限單元地圖模型，讓其能夠無(wú)碰撞地通過(guò)長(zhǎng)而窄的通道，與實(shí)際情況更相符，為移動(dòng)機(jī)器人逃脫各種障礙，規(guī)劃最優(yōu)路徑提供了一種新思路。

發(fā)明內(nèi)容

本發(fā)明的目的在于提供一種有限單元地圖的移動(dòng)機(jī)器人路徑規(guī)劃方法，用于尋找從初始配置到目標(biāo)配置的無(wú)碰撞路徑，為尋找最優(yōu)的機(jī)器人移動(dòng)路徑提供了保障。

為了達(dá)成上述目的，本發(fā)明的解決方案是：

有限單元地圖的移動(dòng)機(jī)器人路徑規(guī)劃方法，包括以下步驟(1)～(7)：

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

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

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

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

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

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

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