[發(fā)明專(zhuān)利]機(jī)器人全局路徑規(guī)劃方法

在審

• 申請(qǐng)?zhí)枺?/td>: 201710253824.3
• 申請(qǐng)日: 2017-04-18
• 公開(kāi)（公告）號(hào): CN108731678A
• 公開(kāi)（公告）日: 2018-11-02
• 發(fā)明（設(shè)計(jì)）人: 謝鋒
• 申請(qǐng)（專(zhuān)利權(quán)）人: 深圳市豐巨泰科電子有限公司
• 主分類(lèi)號(hào): G01C21/20
• 分類(lèi)號(hào): G01C21/20
• 代理公司: 深圳市神州聯(lián)合知識(shí)產(chǎn)權(quán)代理事務(wù)所(普通合伙) 44324
• 代理人: 周松強(qiáng)

本發(fā)明公開(kāi)了一種機(jī)器人全局路徑規(guī)劃方法，該方法包括環(huán)境建模、路徑規(guī)劃，該方法通過(guò)二維空間進(jìn)行環(huán)境建模，且通過(guò)基于切比雪夫距離的算法實(shí)現(xiàn)路徑規(guī)劃。本發(fā)明通過(guò)二維建模和相關(guān)算法，能夠有效且準(zhǔn)確地規(guī)劃?rùn)C(jī)器人的路徑，運(yùn)算量小，運(yùn)算速度快，能夠滿(mǎn)足機(jī)器人實(shí)時(shí)進(jìn)行路徑規(guī)劃的需要。

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

本發(fā)明屬于機(jī)器人的技術(shù)領(lǐng)域，特別涉及機(jī)器人移動(dòng)的路徑規(guī)劃方法。

背景技術(shù)

機(jī)器人是自動(dòng)執(zhí)行工作的機(jī)器裝置。它既可以接受人類(lèi)指揮，又可以運(yùn)行預(yù)先編排的程序，也可以根據(jù)以人工智能技術(shù)制定的原則綱領(lǐng)行動(dòng)。它的任務(wù)是協(xié)助或取代人類(lèi)工作的工作，例如生產(chǎn)業(yè)、建筑業(yè)，或是危險(xiǎn)的工作。隨時(shí)技術(shù)水平的提高，機(jī)器人的智能化越來(lái)越高，已經(jīng)逐步進(jìn)入到人們的日常工作和生活領(lǐng)域。

全路徑規(guī)劃是指機(jī)器人在具有障礙物的環(huán)境內(nèi)，按照一種或多種性能指標(biāo)，尋找一條從起始點(diǎn)到目標(biāo)點(diǎn)的最優(yōu)無(wú)碰撞路徑。針對(duì)目前已有的路徑規(guī)劃算法，根據(jù)機(jī)器人所處的具體環(huán)境選擇合適的算法，使得機(jī)器人在環(huán)境中能夠穩(wěn)定運(yùn)行變得至關(guān)重要。針對(duì)已知地圖的全局路徑規(guī)劃，其基本問(wèn)題是環(huán)境建模和搜索運(yùn)動(dòng)路徑。

對(duì)于機(jī)器人來(lái)說(shuō)，一個(gè)重要的任務(wù)是模擬人的行走，以實(shí)現(xiàn)動(dòng)態(tài)地為人們提供各種服務(wù)。傳統(tǒng)的方式是通過(guò)傳感器感知環(huán)境及物體，從而計(jì)算出移動(dòng)路線。但是僅靠傳感器探測(cè)與實(shí)時(shí)規(guī)劃路線，機(jī)器人可能達(dá)到不了終點(diǎn)，因此，人們提出了全局路徑規(guī)劃的概念，全局路徑規(guī)劃首先要建立環(huán)境模型，然后搜索路徑、規(guī)劃路線。全局路徑規(guī)劃方法有可視圖法、自由空間法、環(huán)境地圖法和柵格法，其中，環(huán)境建模是對(duì)機(jī)器人實(shí)際的工作環(huán)境進(jìn)行抽象轉(zhuǎn)換成算法可以識(shí)別的空間。根據(jù)構(gòu)型空間理論，取機(jī)器人能自由活動(dòng)并考慮安全閾值后的最小矩形空間作為柵格單元，將機(jī)器人的工作空間劃分為柵格。這樣可以根據(jù)機(jī)器人及實(shí)驗(yàn)場(chǎng)地大小選擇合適的柵格尺寸，既保證了柵格數(shù)目不會(huì)過(guò)量，又提高了精度。目前柵格法以基于勢(shì)場(chǎng)的柵格法為主，然而上述柵格法需要進(jìn)行三維運(yùn)算，運(yùn)算數(shù)據(jù)量很大，效率低，且具有一定的誤差，難以滿(mǎn)足機(jī)器人路徑實(shí)時(shí)規(guī)劃的需要。

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

針對(duì)上述問(wèn)題，本發(fā)明的目的在于提供一種機(jī)器人全局路徑規(guī)劃方法，該方法能夠有效且準(zhǔn)確地規(guī)劃?rùn)C(jī)器人的路徑，運(yùn)算量小，運(yùn)算速度快，能夠滿(mǎn)足機(jī)器人實(shí)時(shí)進(jìn)行路徑規(guī)劃的需要。

為實(shí)現(xiàn)上述目的，本發(fā)明的技術(shù)方案為：

一種機(jī)器人全局路徑規(guī)劃方法，該方法包括環(huán)境建模、路徑規(guī)劃，其特征在于該方法通過(guò)二維空間進(jìn)行環(huán)境建模，且通過(guò)基于切比雪夫距離的算法實(shí)現(xiàn)路徑規(guī)劃。

進(jìn)一步，所述二維空間是將機(jī)器人的工作空間取為二維空間，無(wú)障礙物的柵格稱(chēng)為自由柵格，含有障礙物的柵格成為障礙柵格，為保證安全性，不滿(mǎn)一個(gè)柵格的均按一個(gè)柵格處理；對(duì)于二維空間中劃分的柵格采用直角坐標(biāo)系法來(lái)進(jìn)行標(biāo)識(shí)，通過(guò)這種方式進(jìn)行環(huán)境建模。

更進(jìn)一步，所示環(huán)境模型建立后，對(duì)柵格環(huán)境模型進(jìn)行信息編碼：障礙柵格信息記為1；自由柵格信息記為0，然后用整型二維數(shù)組來(lái)存儲(chǔ)環(huán)境模型信息，形成信息模型。

進(jìn)一步，通過(guò)算法對(duì)環(huán)境中的節(jié)點(diǎn)進(jìn)行搜索，使得從初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的估價(jià)函數(shù)最小或接近最小。

更進(jìn)一步，所述估價(jià)函數(shù)定義如下：

f(n)＝g(n)+h(n)

其中f(n)是初始節(jié)點(diǎn)經(jīng)過(guò)節(jié)點(diǎn)n到達(dá)目標(biāo)節(jié)點(diǎn)的估價(jià)函數(shù)，g(n)是初始節(jié)點(diǎn)到節(jié)點(diǎn)n的實(shí)際代價(jià)，h(n)是節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)最理想路徑的估計(jì)代價(jià)。

進(jìn)一步，所述算法中涉及兩個(gè)隊(duì)列：OPEN隊(duì)列和CLOSED隊(duì)列，OPEN隊(duì)列保存了所有沒(méi)有訪問(wèn)的節(jié)點(diǎn)，該隊(duì)列中估價(jià)值最小的節(jié)點(diǎn)將被父節(jié)點(diǎn)優(yōu)先訪問(wèn)，CLOSED隊(duì)列中保存了已經(jīng)訪問(wèn)過(guò)的節(jié)點(diǎn)，選取最后訪問(wèn)的節(jié)點(diǎn)向周?chē)?jié)點(diǎn)試探，將可以移動(dòng)且估價(jià)值最小的節(jié)點(diǎn)放入CLOSED隊(duì)列。

更進(jìn)一步，所述具體規(guī)劃流程如下：