[發(fā)明專利]一種仿人機(jī)器人路徑規(guī)劃方法及裝置

有效

• 申請(qǐng)?zhí)枺?/td>: 201810715045.5
• 申請(qǐng)日: 2018-06-29
• 公開（公告）號(hào): CN109163722B
• 公開（公告）日: 2020-06-30
• 發(fā)明（設(shè)計(jì)）人: 張雷;劉卉玲;劉晨曦;于佳圓;張華琰;楊瀚霆;袁飛;沈瑞婷
• 申請(qǐng)（專利權(quán)）人: 北京建筑大學(xué)
• 主分類號(hào): G01C21/20
• 分類號(hào): G01C21/20
• 代理公司: 北京路浩知識(shí)產(chǎn)權(quán)代理有限公司 11002
• 代理人: 王瑩;吳歡燕

本發(fā)明提供一種仿人機(jī)器人路徑規(guī)劃方法及裝置，所述方法包括：對(duì)進(jìn)行路徑規(guī)劃的待檢索列表中目標(biāo)柵格地圖各結(jié)點(diǎn)的評(píng)價(jià)函數(shù)值進(jìn)行排序，將最小的所述評(píng)價(jià)函數(shù)值對(duì)應(yīng)的結(jié)點(diǎn)作為當(dāng)前結(jié)點(diǎn)；根據(jù)各所述相鄰結(jié)點(diǎn)和所述預(yù)設(shè)終點(diǎn)結(jié)點(diǎn)的坐標(biāo)，獲取各所述相鄰結(jié)點(diǎn)與所述預(yù)設(shè)終點(diǎn)結(jié)點(diǎn)之間的連線；若所述連線中沒有所述預(yù)設(shè)障礙結(jié)點(diǎn)，則將所述連線作為從各所述相鄰結(jié)點(diǎn)到所述預(yù)設(shè)終點(diǎn)結(jié)點(diǎn)之間的第一分段路徑，將所述第一分段路徑和預(yù)先基于A*算法獲取的第二分段路徑作為從所述預(yù)設(shè)起始結(jié)點(diǎn)到所述預(yù)設(shè)終點(diǎn)結(jié)點(diǎn)的總路徑。本發(fā)明通過對(duì)目標(biāo)柵格地圖的整體判斷，直接將確定的連線作為從相鄰結(jié)點(diǎn)到預(yù)設(shè)終點(diǎn)結(jié)點(diǎn)的路徑，從而大大提高路徑規(guī)劃的效率。

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

本發(fā)明屬于智能機(jī)器人技術(shù)領(lǐng)域，更具體地，涉及一種仿人機(jī)器人路徑規(guī)劃方法及裝置。

背景技術(shù)

隨著人工智能和自動(dòng)化領(lǐng)域的發(fā)展，仿人機(jī)器人的研究也越來越深入。“人機(jī)”自然共居是仿人機(jī)器人服務(wù)人類最主要的方式。在“人機(jī)”自然共居的環(huán)境中，仿人機(jī)器人作業(yè)控制最迫切需要解決的問題是作業(yè)環(huán)境的理解和作業(yè)路徑規(guī)劃。

A*(A-Star，A星)算法是一種常用的仿人機(jī)器人路徑規(guī)劃方法。A*算法既擁有類似BFS(Breadth First Search，廣度優(yōu)先搜索)算法等啟發(fā)式算法快速搜索路徑的優(yōu)點(diǎn)，同時(shí)還能保證找到一條最短路徑。根據(jù)傳統(tǒng)A*方法搜索策略可以發(fā)現(xiàn)，A*算法對(duì)所有OPEN列表中的節(jié)點(diǎn)逐步進(jìn)行檢索。根據(jù)檢索的情況選擇合適的節(jié)點(diǎn)在進(jìn)行下一循環(huán)的檢索。這種亦步亦趨的搜索策略可以避免優(yōu)秀節(jié)點(diǎn)的疏漏。但是環(huán)境地圖中有可能出現(xiàn)一些其他的情況，例如環(huán)境中沒有障礙；或者機(jī)器人作業(yè)初始位置與目標(biāo)終點(diǎn)位置之間沒有障礙的情況；又或者路徑搜索過程進(jìn)行到某節(jié)點(diǎn)時(shí)，該節(jié)點(diǎn)到初始點(diǎn)的路徑已經(jīng)搜索結(jié)束，該點(diǎn)與目標(biāo)節(jié)點(diǎn)之間不存在阻塞。A*算法依然是亦步亦趨地檢索列表中的節(jié)點(diǎn)，并沒有對(duì)當(dāng)前的作業(yè)環(huán)境進(jìn)行任何的整體判斷。如果環(huán)境地圖的精度不高，地圖中的單位柵格數(shù)目并不多，例如在20×20的地圖上，直接應(yīng)用傳統(tǒng)A*算法進(jìn)行路徑搜索不會(huì)花費(fèi)多少時(shí)間，但如果作業(yè)環(huán)境要求精度非常高，地圖中單位柵格數(shù)目很多，例如640×480的地圖中，直接應(yīng)用傳統(tǒng)A*算法進(jìn)行路徑搜索就會(huì)大大增加檢索時(shí)間。

綜上所述，采用傳統(tǒng)A*算法進(jìn)行仿人機(jī)器人路徑規(guī)劃僅亦步亦趨地檢索列表中的節(jié)點(diǎn)，對(duì)作業(yè)環(huán)境地圖缺乏整體的判斷，導(dǎo)致在一些情況下大大增加檢索時(shí)間，路徑規(guī)劃效率低。

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

為克服上述現(xiàn)有仿人機(jī)器人路徑規(guī)劃方法檢索時(shí)間長(zhǎng)和效率低的問題或者至少部分地解決上述問題，本發(fā)明提供一種仿人機(jī)器人路徑規(guī)劃方法及裝置。

根據(jù)本發(fā)明的第一方面，提供一種仿人機(jī)器人路徑規(guī)劃方法，包括：

對(duì)進(jìn)行路徑規(guī)劃的待檢索列表中目標(biāo)柵格地圖各節(jié)點(diǎn)的評(píng)價(jià)函數(shù)值進(jìn)行排序，將最小的所述評(píng)價(jià)函數(shù)值對(duì)應(yīng)的節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn)，并將所述當(dāng)前節(jié)點(diǎn)從所述待檢索列表移動(dòng)到封閉列表中；

若所述當(dāng)前節(jié)點(diǎn)的各相鄰節(jié)點(diǎn)不是預(yù)設(shè)終點(diǎn)節(jié)點(diǎn)和預(yù)設(shè)障礙節(jié)點(diǎn)，且各所述相鄰節(jié)點(diǎn)不在所述封閉列表中，則根據(jù)各所述相鄰節(jié)點(diǎn)和所述預(yù)設(shè)終點(diǎn)節(jié)點(diǎn)的坐標(biāo)，獲取各所述相鄰節(jié)點(diǎn)與所述預(yù)設(shè)終點(diǎn)節(jié)點(diǎn)之間的連線；

若所述連線中沒有所述預(yù)設(shè)障礙節(jié)點(diǎn)，則將所述連線作為從各所述相鄰節(jié)點(diǎn)到所述預(yù)設(shè)終點(diǎn)節(jié)點(diǎn)之間的第一分段路徑，將所述第一分段路徑和預(yù)先基于A*算法獲取的第二分段路徑作為從所述預(yù)設(shè)起始節(jié)點(diǎn)到所述預(yù)設(shè)終點(diǎn)節(jié)點(diǎn)的總路徑；

所述第二分段路徑為從預(yù)設(shè)起始節(jié)點(diǎn)到各所述相鄰節(jié)點(diǎn)的路徑。

根據(jù)本發(fā)明第二方面提供一種仿人機(jī)器人路徑規(guī)劃裝置，包括：

排序模塊，用于對(duì)進(jìn)行路徑規(guī)劃的待檢索列表中目標(biāo)柵格地圖各節(jié)點(diǎn)的評(píng)價(jià)函數(shù)值進(jìn)行排序，將最小的所述評(píng)價(jià)函數(shù)值對(duì)應(yīng)的節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn)，并將所述當(dāng)前節(jié)點(diǎn)從所述待檢索列表移動(dòng)到封閉列表中；