[發(fā)明專利]機(jī)器人導(dǎo)航路徑的搜索方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201710698659.2
• 申請(qǐng)日: 2017-09-18
• 公開（公告）號(hào): CN107478232B
• 公開（公告）日: 2020-02-21
• 發(fā)明（設(shè)計(jì)）人: 李明;肖剛軍;李根唐
• 申請(qǐng)（專利權(quán)）人: 珠海市一微半導(dǎo)體有限公司
• 主分類號(hào): G01C21/20
• 分類號(hào): G01C21/20
• 代理公司: 暫無(wú)信息
• 代理人: 暫無(wú)信息

本發(fā)明屬于一種機(jī)器人導(dǎo)航路徑的搜索方法及芯片，通過(guò)采用分區(qū)搜索的方式，每次只在一個(gè)柵格區(qū)域內(nèi)，搜索與該區(qū)域相鄰的待過(guò)柵格區(qū)域的交界線上的交接點(diǎn)，從而確定從出發(fā)位置點(diǎn)到交接點(diǎn)之間的路徑。當(dāng)一個(gè)柵格區(qū)域搜索完后，就釋放內(nèi)存，然后再搜索下一個(gè)待過(guò)柵格區(qū)域，最終形成從出發(fā)位置點(diǎn)到第一交接點(diǎn)、第二交接點(diǎn)、第N+1交接點(diǎn)和目標(biāo)位置點(diǎn)的導(dǎo)航路徑。如此，可以減小路徑搜索時(shí)的內(nèi)存占用量，提高路徑搜索效率，同時(shí)擴(kuò)大了搜索的應(yīng)用范圍，滿足不同的搜索需求。

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

本發(fā)明涉及機(jī)器人領(lǐng)域，具體涉及一種機(jī)器人導(dǎo)航路徑的搜索方法及芯片。

背景技術(shù)

掃地機(jī)器人，又稱自動(dòng)打掃機(jī)、智能吸塵、機(jī)器人吸塵器等，是智能家用電器的一種，能憑借一定的人工智能，自動(dòng)在房間內(nèi)完成地板清理工作。掃地機(jī)器人需要按照一定的路徑規(guī)劃來(lái)覆蓋整個(gè)房間區(qū)域，完成清掃的目的。路徑規(guī)劃，有隨機(jī)清掃和規(guī)劃清掃兩種。隨機(jī)清掃，是指機(jī)器人根據(jù)一定的移動(dòng)算法，如三角形、五邊形軌跡嘗試性的覆蓋作業(yè)區(qū)，如果遇到障礙，則執(zhí)行對(duì)應(yīng)的轉(zhuǎn)向函數(shù)。這種方法是一種以時(shí)間換空間的低成本策略，如不計(jì)時(shí)間可以達(dá)到100％覆蓋率。隨機(jī)覆蓋法不用定位、也沒有環(huán)境地圖，也無(wú)法對(duì)路徑進(jìn)行規(guī)劃。規(guī)劃清掃，是指機(jī)器人行走過(guò)程中建立起環(huán)境地圖，實(shí)時(shí)分析地圖，將房間劃分成不同區(qū)域，分區(qū)域清掃。這種方法效率高，在保證覆蓋率的前提下，能夠以最快的速度完成清掃。

目前，有的規(guī)劃清掃方式采用的是路徑搜索算法，其中，A*(A-Star)算法是一種柵格地圖中求解最短路徑最有效的直接搜索方法，也是解決許多搜索問(wèn)題的有效算法。算法中的距離估算值與實(shí)際值越接近，最終搜索速度越快。但是，A*算法有一個(gè)最主要的缺點(diǎn)：A*算法非常消耗內(nèi)存，每個(gè)加入被搜索的柵格，都要消耗十幾個(gè)字節(jié)，因此當(dāng)柵格地圖很大時(shí)，對(duì)內(nèi)存的消耗非常大，從而降低搜索效率，導(dǎo)致該算法的應(yīng)用受到一定局限性。

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

為解決上述問(wèn)題，本發(fā)明提供了一種機(jī)器人導(dǎo)航路徑的搜索方法及芯片，通過(guò)采用分區(qū)搜索的方式來(lái)提高機(jī)器人路徑搜索的效率，從而擴(kuò)大搜索應(yīng)用范圍。本發(fā)明的具體技術(shù)方案如下：

本發(fā)明所述的機(jī)器人導(dǎo)航路徑的搜索方法，包括如下步驟：

基于機(jī)器人的行進(jìn)路徑創(chuàng)建柵格地圖；

基于柵格地圖進(jìn)行區(qū)域劃分，形成多個(gè)柵格區(qū)域；

基于目標(biāo)位置點(diǎn)，確定從出發(fā)位置點(diǎn)到達(dá)目標(biāo)位置點(diǎn)需要經(jīng)過(guò)的待過(guò)柵格區(qū)域；

基于出發(fā)位置點(diǎn)所在的起點(diǎn)柵格區(qū)域，搜索所述起點(diǎn)柵格區(qū)域與相鄰的第一待過(guò)柵格區(qū)域交界線上的第一交接點(diǎn)；

確定所述第一交接點(diǎn)后，再搜索所述第一待過(guò)柵格區(qū)域與相鄰的第二待過(guò)柵格區(qū)域交界線上的第二交接點(diǎn)；

以此類推，

確定所述第N交接點(diǎn)后，最后搜索所述第N待過(guò)柵格區(qū)域與相鄰的目標(biāo)位置點(diǎn)所在目標(biāo)柵格區(qū)域交界線上的第N+1交接點(diǎn)；

從出發(fā)位置點(diǎn)到第一交接點(diǎn)、第二交接點(diǎn)、第N+1交接點(diǎn)和目標(biāo)位置點(diǎn)構(gòu)成的路徑作為導(dǎo)航路徑；

其中，所述N為自然數(shù)。

進(jìn)一步地，所述基于機(jī)器人的行進(jìn)路徑創(chuàng)建柵格地圖，包括如下步驟：

機(jī)器人在行進(jìn)過(guò)程中，基于柵格單元的形式，標(biāo)示行進(jìn)過(guò)的柵格單元為已行進(jìn)單元，標(biāo)示碰到障礙物的柵格單元為障礙單元，標(biāo)示未行進(jìn)過(guò)的柵格單元為未行進(jìn)單元；

基于所述已行進(jìn)單元、障礙單元和未行進(jìn)單元，創(chuàng)建所述柵格地圖。

進(jìn)一步地，所述基于柵格地圖進(jìn)行區(qū)域劃分，形成多個(gè)柵格區(qū)域，包括如下步驟：

以出發(fā)點(diǎn)為原點(diǎn)，構(gòu)建XY軸坐標(biāo)系；

將預(yù)定長(zhǎng)度和預(yù)定寬度的方形區(qū)域作為柵格區(qū)域排布在XY軸坐標(biāo)系中；