[發(fā)明專利]一種基于柵格法的掃地機(jī)器人全遍歷路徑規(guī)劃方法有效
| 申請?zhí)枺?/td> | 201910654234.0 | 申請日： | 2019-07-19 |
| 公開（公告）號： | CN110361017B | 公開（公告）日： | 2022-02-11 |
| 發(fā)明（設(shè)計）人： | 龍強(qiáng);陳飛陽 | 申請（專利權(quán)）人： | 西南科技大學(xué) |
| 主分類號： | G01C21/32 | 分類號： | G01C21/32 |
| 代理公司： | 成都正華專利代理事務(wù)所(普通合伙) 51229 | 代理人： | 李蕊 |
| 地址： | 621010 四川*** | 國省代碼： | 四川;51 |
| 權(quán)利要求書： | 查看更多 | 說明書： | 查看更多 |
| 摘要： | |||
| 搜索關(guān)鍵詞： | 一種 基于 柵格 掃地 機(jī)器人 遍歷 路徑 規(guī)劃 方法 | ||
1.一種基于柵格法的掃地機(jī)器人全遍歷路徑規(guī)劃方法，其特征在于，包括以下步驟：
S1、根據(jù)掃地機(jī)器人的工作環(huán)境，建立柵格地圖并將其劃分為若干個矩形分區(qū)；
S2、依次規(guī)劃每個矩形分區(qū)的無重復(fù)遍歷路徑；
S3、確定柵格地圖中各個矩形分區(qū)的遍歷順序及跨越各個矩形分區(qū)時的路線，在每個矩形分區(qū)內(nèi)按照規(guī)劃的無重復(fù)遍歷路徑進(jìn)行清掃，完成掃地機(jī)器人的全遍歷路徑規(guī)劃；
所述步驟S1中建立柵格地圖的方法具體為：
A1、根據(jù)掃地機(jī)器人的清潔直徑確認(rèn)柵格的大??；
A2、用若干個柵格覆蓋掃地機(jī)器人的工作環(huán)境，并確定每個柵格的屬性；
其中，在工作環(huán)境掃地機(jī)器人不可達(dá)區(qū)域?qū)?yīng)的柵格屬性為黑色，其屬性值為-1，可達(dá)區(qū)域?qū)?yīng)的柵格屬性為白色，其屬性值為0；
A3、將每個柵格用二維數(shù)組表示其所在位置，完成柵格地圖的構(gòu)建；
其中，二維數(shù)組A(i,j)表示柵格地圖中第i行第j列的柵格；
所述步驟S1中進(jìn)行劃分矩形分區(qū)的方法具體為：
B1、通過貪心算法對柵格地圖進(jìn)行矩形分區(qū)的劃分，得到若干種矩形分區(qū)劃分方案；
B2、依次計算每種矩形分區(qū)劃分方案方差；
B3、將方差最小的矩形分區(qū)劃分方案作為柵格地圖的矩形分區(qū)；
其中，方差var的計算公式為：
式中，ksum為柵格地圖中所有矩形分區(qū)的個數(shù)；
avg為柵格地圖中所有矩形分區(qū)的平均面積；
x'k為編號為k的矩形分區(qū)的終點(diǎn)柵格的橫坐標(biāo)；
xk為編號為k的矩形分區(qū)的起點(diǎn)柵格的橫坐標(biāo)；
y'k為編號為k的矩形分區(qū)的終點(diǎn)柵格的縱坐標(biāo)；
yk為編號為k的矩形分區(qū)的起點(diǎn)柵格的縱坐標(biāo)。
2.根據(jù)權(quán)利要求1所述的基于柵格法的掃地機(jī)器人全遍歷路徑規(guī)劃方法，其特征在于，所述步驟B1具體為：
B11、確定矩形分區(qū)的起點(diǎn)柵格：
按照從左至右，從上至下的順序遍歷柵格地圖，將第一個屬性值為0的柵格作為一個矩形分區(qū)的起點(diǎn)柵格；
B12、確定該矩形分區(qū)的終點(diǎn)柵格：
從起點(diǎn)柵格開始，以從左至右從上到下的順序遍歷未分區(qū)的柵格，將未分區(qū)的柵格作為矩形分區(qū)的候選終點(diǎn)柵格，取使矩形分區(qū)面積最大，且該矩形分區(qū)中無已被分區(qū)和不可達(dá)柵格的柵格作為矩形分區(qū)的終點(diǎn)柵格；
B13、修改柵格屬性值：
將劃分出的矩形分區(qū)中的柵格的屬性值設(shè)置為該矩形分區(qū)的編號；
其中，矩形分區(qū)的編號為大于0且依次遞增的自然數(shù)；
B14、重復(fù)步驟B11-B13：
對柵格地圖中的所有柵格進(jìn)行遍歷并進(jìn)行矩形分區(qū)的劃分，直到柵格地圖中所有柵格的屬性值均不為0。
3.根據(jù)權(quán)利要求2所述的基于柵格法的掃地機(jī)器人全遍歷路徑規(guī)劃方法，其特征在于，
所述步驟B1中確定的矩形分區(qū)劃分方案有8種；
所述步驟B11確定第一個矩形分區(qū)的起點(diǎn)柵格時，其在柵格地圖中的候選位置包括右上角、左上角、左下角和右下角；
所述步驟B11中遍歷確定各矩形分區(qū)的終點(diǎn)柵格時，遍歷方式包括以起點(diǎn)柵格所在的行優(yōu)先和以起點(diǎn)柵格所在的列優(yōu)先。
4.根據(jù)權(quán)利要求1所述的基于柵格法的掃地機(jī)器人全遍歷路徑規(guī)劃方法，其特征在于，所述步驟S2具體為：
S21、將矩形分區(qū)中一個頂點(diǎn)柵格作為遍歷起點(diǎn)，將該矩形分區(qū)的中其他三個頂點(diǎn)作為路徑規(guī)劃時的候選遍歷終點(diǎn)；
其中，矩形分區(qū)的頂點(diǎn)柵格包括左上角頂點(diǎn)柵格、右上角頂點(diǎn)柵格、左下角頂點(diǎn)柵格和右下角頂點(diǎn)柵格；
S22、根據(jù)矩形分區(qū)的遍歷起點(diǎn)和遍歷終點(diǎn)所在位置，確定遍歷起點(diǎn)與遍歷終點(diǎn)的頂點(diǎn)關(guān)系；
S23、根據(jù)頂點(diǎn)關(guān)系，確定該矩形分區(qū)內(nèi)的無重復(fù)遍歷路徑。
該專利技術(shù)資料僅供研究查看技術(shù)是否侵權(quán)等信息，商用須獲得專利權(quán)人授權(quán)。該專利全部權(quán)利屬于西南科技大學(xué)，未經(jīng)西南科技大學(xué)許可，擅自商用是侵權(quán)行為。如果您想購買此專利、獲得商業(yè)授權(quán)和技術(shù)合作，請聯(lián)系【客服】
本文鏈接：http://www.szxzyx.cn/pat/books/201910654234.0/1.html，轉(zhuǎn)載請聲明來源鉆瓜專利網(wǎng)。
