[發(fā)明專利]一種基于改進(jìn)D*lite算法的移動(dòng)機(jī)器人路徑規(guī)劃方法及系統(tǒng)

有效

• 申請(qǐng)?zhí)枺?/td>: 202010010351.6
• 申請(qǐng)日: 2020-01-06
• 公開（公告）號(hào): CN111176286B
• 公開（公告）日: 2022-08-23
• 發(fā)明（設(shè)計(jì)）人: 張毅;施明瑞
• 申請(qǐng)（專利權(quán)）人: 重慶郵電大學(xué)
• 主分類號(hào): G05D1/02
• 分類號(hào): G05D1/02
• 代理公司: 重慶市恒信知識(shí)產(chǎn)權(quán)代理有限公司 50102
• 代理人: 劉小紅;陳棟梁

本發(fā)明請(qǐng)求保護(hù)一種基于改進(jìn)D*lite算法的移動(dòng)機(jī)器人路徑規(guī)劃方法及系統(tǒng)。具體步驟為：首先，根據(jù)機(jī)器人所在環(huán)境的柵格地圖，使用地圖分割算法將地圖分割為若干內(nèi)部沒有障礙物的有界單元；然后，根據(jù)若干單元之間的連通關(guān)系得到單元連接圖，計(jì)算得到各單元之間的原始距離代價(jià)值和鄰接矩陣；接著，根據(jù)鄰接矩陣，使用雙向圖搜索算法，計(jì)算得到從目標(biāo)單元到起始單元所經(jīng)過的單元順序；之后，根據(jù)單元順序，依次按照核心網(wǎng)格設(shè)置方法在對(duì)應(yīng)單元中設(shè)置核心網(wǎng)格，按順序組成搜索鏈表；最后，根據(jù)搜索鏈表引導(dǎo)D*lite路徑規(guī)劃算法完成移動(dòng)機(jī)器人路徑規(guī)劃。實(shí)驗(yàn)結(jié)果證實(shí)了本方法能夠在保證路徑長(zhǎng)度接近最短的同時(shí)降低路徑規(guī)劃時(shí)間。

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

本發(fā)明屬于移動(dòng)機(jī)器人自主導(dǎo)航領(lǐng)域，特別是一種基于改進(jìn)D*lite算法的移動(dòng)機(jī)器人路徑規(guī)劃方法。

背景技術(shù)

移動(dòng)機(jī)器人的路徑規(guī)劃的能力，決定了機(jī)器人可勝任工作難度的高低。在構(gòu)建好的環(huán)境模型中，規(guī)劃一條從初始點(diǎn)到目標(biāo)點(diǎn)的無(wú)碰撞最優(yōu)路徑，是路徑規(guī)劃的主要內(nèi)容。在構(gòu)建環(huán)境模型中，柵格法應(yīng)用較多，該方法具有直觀簡(jiǎn)潔、分辨率可變、容易創(chuàng)建和存儲(chǔ)等優(yōu)點(diǎn)，適用于室內(nèi)環(huán)境路徑規(guī)劃地圖模型的建立，魯棒性強(qiáng)。圖搜索算法是路徑規(guī)劃中的一類算法，它被廣泛應(yīng)用于柵格地圖中的路徑規(guī)劃問題。A*算法是圖搜索算法中的經(jīng)典算法，它加入了啟發(fā)式搜索方法。啟發(fā)式搜索是評(píng)估狀態(tài)空間中的每個(gè)搜索位置，找出下一步要搜索的最好位置G，再?gòu)腉進(jìn)行類似搜索直到目標(biāo)位置。該搜索方法能節(jié)省大量搜索空間，提高搜索效率。在A*算法的基礎(chǔ)上，研究者們先后提出了改進(jìn)算法例如D*，LPA*與D*lite。學(xué)者們對(duì)路徑規(guī)劃算法的路徑安全性，路徑平滑度和重規(guī)劃策略進(jìn)行了諸多研究，但是在路徑搜索中仍然存在問題。

路徑規(guī)劃的速度仍然較慢，如何提高路徑規(guī)劃的效率是路徑規(guī)劃問題中的難點(diǎn)。在柵格地圖中，基于圖搜索的路徑規(guī)劃算法在進(jìn)行路徑搜索時(shí)，會(huì)根據(jù)搜索函數(shù)向八個(gè)鄰域方向?qū)ふ易顑?yōu)解，一些優(yōu)先級(jí)較高的網(wǎng)格延申出的路徑最后被障礙物阻擋而結(jié)束，這造成在這一搜索方向上大部分的之前進(jìn)行的擴(kuò)展操作變?yōu)闊o(wú)效，例如在凹型障礙物內(nèi)或者當(dāng)前網(wǎng)格與目標(biāo)網(wǎng)格分別在兩個(gè)房間中，都會(huì)有大量的無(wú)效網(wǎng)格被搜索和計(jì)算，這些無(wú)效的擴(kuò)展降低了規(guī)劃效率。如何確保路徑規(guī)劃算法在正確的搜索方向上進(jìn)行擴(kuò)展，是提高路徑規(guī)劃速度需要解決的問題。

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

本發(fā)明旨在解決以上現(xiàn)有技術(shù)的問題。提出了一種能夠在保證路徑長(zhǎng)度接近最短的同時(shí)降低路徑規(guī)劃時(shí)間的基于改進(jìn)D*lite算法的移動(dòng)機(jī)器人路徑規(guī)劃方法及系統(tǒng)。本發(fā)明的技術(shù)方案如下：

一種基于改進(jìn)D*lite算法的移動(dòng)機(jī)器人路徑規(guī)劃方法，其包括以下步驟：

步驟S1，首先，根據(jù)機(jī)器人所在環(huán)境的柵格地圖，使用地圖分割算法將地圖分割為若干內(nèi)部沒有障礙物的有界單元；

步驟S2，根據(jù)S1中所得的若干有界單元之間的連通關(guān)系得到單元連接圖，計(jì)算得到各單元之間的原始距離代價(jià)值和鄰接矩陣；

步驟S3，根據(jù)S2中得到的鄰接矩陣，使用雙向圖搜索算法，計(jì)算得到從目標(biāo)單元到起始單元所經(jīng)過的單元順序；

步驟S4，根據(jù)S3得到的單元順序，依次按照核心網(wǎng)格設(shè)置方法在對(duì)應(yīng)單元中設(shè)置核心網(wǎng)格，按順序組成搜索鏈表；

步驟S5，根據(jù)S4得到的搜索鏈表，將D*lite算法多方向的搜索依照搜索鏈表的順序分為多段的朝著正確方向的搜索，用搜索鏈表引導(dǎo)D*lite算法完成路徑規(guī)劃。

進(jìn)一步的，步驟S1根據(jù)機(jī)器人所在環(huán)境的柵格地圖，使用地圖分割算法將地圖分割為若干內(nèi)部沒有障礙物的有界單元，具體步驟為：

S11：用一條垂直線從左至右掃描柵格地圖；