清掃機(jī)器人的新型田埂式路徑規(guī)劃方法

傅思程++陳中柘++向羽

摘 要 路徑規(guī)劃是清掃機(jī)器人的關(guān)鍵技術(shù)，通常采用柵格法進(jìn)行全覆蓋路徑規(guī)劃，但在遇到死角和凹型地形時(shí)，會(huì)存在著容易被死角困住或重復(fù)率過高等問題。本文在柵格法的田埂式路徑規(guī)劃的基礎(chǔ)上進(jìn)行了改進(jìn)：加入優(yōu)先級的行走規(guī)則，融入回溯法，最后在單元格加入特征標(biāo)記。提出的改進(jìn)方法使新型田埂式的路徑規(guī)劃即能做到全覆蓋，又能從死角中走出，且降低了路徑的重復(fù)率，具有更高的工作效率。

【關(guān)鍵詞】清掃機(jī)器人 路徑規(guī)劃 新型田埂式

1 引言

路徑規(guī)劃和避障是移動(dòng)機(jī)器人的關(guān)鍵技術(shù)之一，比如家庭服務(wù)機(jī)器人，包括清掃機(jī)器人、修剪機(jī)器人等，在工作的時(shí)候都必須進(jìn)行路徑規(guī)劃和避障。路徑規(guī)劃和避障是移動(dòng)機(jī)器人是否能高效率工作的關(guān)鍵，因此，具有很高的工程應(yīng)用價(jià)值和理論研究價(jià)值。

依據(jù)機(jī)器人的任務(wù)可以把路徑規(guī)劃法分成環(huán)境區(qū)域內(nèi)全覆蓋路徑規(guī)劃算法以及特定點(diǎn)到特定點(diǎn)之間的路徑規(guī)劃算法即兩點(diǎn)間的路徑規(guī)劃算法。全覆蓋路徑規(guī)劃是指在機(jī)器人從起始點(diǎn)到終點(diǎn)的行進(jìn)過程中，必須全覆蓋整個(gè)環(huán)境區(qū)域中除障礙物以外的其他所有區(qū)域，并且做到重復(fù)率低、無碰撞并且安全。

常用的路徑規(guī)劃方法主要有人工勢場法、柵格法、神經(jīng)網(wǎng)絡(luò)法、混沌遺傳算法等。清掃機(jī)器人常使用柵格法，柵格法的行走路線有內(nèi)外螺旋方式運(yùn)行，田埂式運(yùn)行等，但都存在著路徑重復(fù)率過高或者對于死角遺漏，需要重新啟動(dòng)再次清掃的問題。因此本文對傳統(tǒng)柵格法進(jìn)行了多方面的改進(jìn)，提出了一種新型田埂式運(yùn)行方法，此種方法在算法上并不復(fù)雜，并且路徑重復(fù)率大大降低，做到全覆蓋，下面介紹這種運(yùn)行方法。

2 田埂式路徑規(guī)劃的基本運(yùn)行方式

田埂式路徑規(guī)劃的核心原理是使清掃機(jī)器人沿著直線一個(gè)柵格一個(gè)柵格的向前運(yùn)行，遇到障礙物則以90度為單位進(jìn)行轉(zhuǎn)向，進(jìn)入相鄰的柵格中，然后再次同方向轉(zhuǎn)動(dòng)90度，繼續(xù)直線方式行走，按照此規(guī)律反復(fù)運(yùn)行，一直到覆蓋整個(gè)清掃區(qū)域?yàn)橹埂５窃谇鍜邫C(jī)器人遇到障礙物的情況下，就不能做到全覆蓋，如圖1，會(huì)使得一部分的區(qū)域被遺漏，盡管使用橫縱復(fù)合的方式運(yùn)行可以解決，即當(dāng)?shù)谝淮蔚倪\(yùn)行方向?yàn)闄M向運(yùn)行，那么第二次的運(yùn)行方向就為縱向運(yùn)行，但是這樣的話，清掃率重復(fù)率過高，效率極低，且只能在障礙物較少并且不密集的情況取得較好的效果，因此，本文將田埂法做出了以下改進(jìn)。

3 田埂式運(yùn)行方法的改進(jìn)

3.1 加入優(yōu)先級的新型田埂式運(yùn)行方法

首先，第一個(gè)改進(jìn)是在田埂式基本的運(yùn)行方式上加上優(yōu)先級的概念，即在清掃機(jī)器人的柵格之間的運(yùn)動(dòng)加上了一種規(guī)則，比如左方，上方，右方，下方，這樣的話，清掃機(jī)器人就不再是遇到障礙物就進(jìn)行90度的轉(zhuǎn)向，繼而進(jìn)行同向90度的轉(zhuǎn)向，而是在柵格地圖中按照絕對方向優(yōu)先向左方移動(dòng)，如左方有障礙物或者已經(jīng)清掃過，則向右方移動(dòng)，按照優(yōu)先級順序以此類推地進(jìn)行運(yùn)動(dòng)。這樣的話就能避免田埂式基本運(yùn)行方式所帶來的遺漏問題，如圖2所示。

3.2 加入回溯法的新型田埂式運(yùn)行方法

當(dāng)加入優(yōu)先級算法之后，在面對凹形障礙物時(shí)，某些凹形的死角可能會(huì)困住清掃機(jī)器人，如圖3所示。第二層的改進(jìn)是加入回溯法解決凹形區(qū)域的死角問題。所謂回溯法，就是當(dāng)清掃機(jī)器人不能前進(jìn)，或進(jìn)入死胡同時(shí)，應(yīng)往回移動(dòng)至最近的一個(gè)活結(jié)點(diǎn)處，并使這個(gè)活結(jié)點(diǎn)成為當(dāng)前的擴(kuò)展結(jié)點(diǎn)。回溯法即以這種工作方式遞歸地搜索，直至找到所要求的解或解空間中已沒有活結(jié)點(diǎn)時(shí)為止?；厮莘梢允瓜萑胨澜堑臋C(jī)器人按進(jìn)入的路徑退回，避免長時(shí)間陷在死角中，可以大大提高運(yùn)行效率。

當(dāng)清掃機(jī)器人陷入凹形陷阱時(shí)，如圖4所示，清掃機(jī)器人進(jìn)入到A柵格時(shí)，然后進(jìn)入到B柵格，可以看到A柵格除了與B柵格連接之外，不與任何其他待清掃柵格連接，清掃機(jī)器人就進(jìn)入了死角，此時(shí)清掃機(jī)器人將進(jìn)行回溯操作：即機(jī)器人先回到死角柵格B點(diǎn)的上一個(gè)柵格A，并且在B柵格上做上特定的標(biāo)記，回到A點(diǎn)時(shí)再度使用回溯法直至走出凹形區(qū)域。因此，回溯法就是當(dāng)清掃機(jī)器人陷入一些復(fù)雜的障礙物區(qū)域時(shí)，清掃機(jī)器人通過返回前一個(gè)狀態(tài)來繼續(xù)判斷可走區(qū)域，直至最終走出這種區(qū)域。

3.3 加入特征標(biāo)記的新田埂式運(yùn)行方法

如果采用了加入了固定的優(yōu)先級的田埂式運(yùn)行方式，雖然使用回溯法可以走出凹形區(qū)域，即通常所說的死角，但是由于優(yōu)先級規(guī)則所帶來的影響，使得出現(xiàn)下述情況的凹形區(qū)域時(shí)，清掃機(jī)器人在第一次經(jīng)過凹形區(qū)域時(shí)會(huì)從凹形區(qū)域的上方或下方直接通過，如圖5所示，而不會(huì)進(jìn)入凹形區(qū)域，造成此區(qū)域的遺漏。所以為了解決該問題，本文對凹形區(qū)域加入特征標(biāo)記的方法。

凹形區(qū)域特征標(biāo)記法就是當(dāng)清掃機(jī)器人處于凹形區(qū)域的特征柵格時(shí)會(huì)在當(dāng)前的位置做一個(gè)標(biāo)記，本文是設(shè)置了一個(gè)活性參數(shù)，在未處于任何特征柵格時(shí)，活性參數(shù)為0，當(dāng)?shù)竭_(dá)第一個(gè)特征柵格時(shí)，將活性參數(shù)+1，即此時(shí)活性參數(shù)變?yōu)?，處于半活躍狀態(tài)，清掃小車?yán)^續(xù)運(yùn)行，當(dāng)?shù)竭_(dá)第二個(gè)特征柵格時(shí)，將活性參數(shù)+1，即此時(shí)活性參數(shù)變?yōu)?，處于活躍狀態(tài)，此時(shí)清掃小車將不再執(zhí)行田埂式運(yùn)行方法，而是執(zhí)行凹形區(qū)域運(yùn)行算法，當(dāng)進(jìn)入凹形區(qū)域后將活性參數(shù)復(fù)位，重新置0，等待再度遇到凹形特征柵格后激活。特征柵格的位置要根據(jù)周圍環(huán)境中障礙物柵格與非障礙物柵格的相對位置來判斷。當(dāng)清掃小車所處柵格的左上或右上為障礙柵格，正上為非障礙柵格，或者左下或右下為障礙柵格，正下為非障礙柵格，則清掃小車當(dāng)前位置的柵格即為特征柵格，特征柵格如圖6所示，其中A1，A2，A3即為特征柵格，當(dāng)清掃機(jī)器人通過A1，A2，或者A3，A2時(shí)就會(huì)通過A2柵格進(jìn)入凹形區(qū)域。通過新田埂式運(yùn)行方法，清掃小車就可以免去橫縱結(jié)合的田埂式全覆蓋算法，還可以方便地從凹形區(qū)域即死角中出來繼續(xù)執(zhí)行清掃任務(wù)，極大地提高了效率，節(jié)省了清掃時(shí)間。

綜上所述，這種結(jié)合優(yōu)先級法，回溯法，凹形區(qū)域特征標(biāo)記法而產(chǎn)生新方法，本論文稱之為新田埂式法。

5 結(jié)論

本文基于傳統(tǒng)的田埂式路徑規(guī)劃方法，進(jìn)行了三個(gè)方面的改進(jìn)：加入優(yōu)先級的行走規(guī)則，融入回溯法和在單元格加入特征標(biāo)記。本文提出的新型田埂式路徑規(guī)劃的路徑能夠做到全覆蓋，且遇到凹形區(qū)域死角時(shí)能夠執(zhí)行另一套回溯算法以快速地脫離凹形區(qū)域死角繼續(xù)完成清掃工作，通過加入標(biāo)記法一定程度上降低了由于優(yōu)先級法和回溯法所帶來的重復(fù)率?？傊倪M(jìn)的新型田埂式的路徑規(guī)劃方案即能做到全覆蓋，又能從死角中走出，且降低了路徑的重復(fù)率，具有更高的工作效率。

（通信作者：陳中柘）

參考文獻(xiàn)

[1]王顯.智能清掃機(jī)器人路徑規(guī)劃及自動(dòng)充電系統(tǒng)研究[D].河南：鄭州大學(xué)，2014.

[2]王儉，趙鶴鳴，陳衛(wèi)東.移動(dòng)機(jī)器人全覆蓋路徑規(guī)劃研究[J].微計(jì)算機(jī)信息，2006，3（02）：194-197.

[3]高麗宏.移動(dòng)機(jī)器人的路徑規(guī)劃和避障控制[D].遼寧：大連理工大學(xué)，2002.

[4]任亞楠，賈瑞清，何金田.基于超聲波傳感器的移動(dòng)機(jī)器人避障系統(tǒng)研究[J].中國測試，2012（03）：76-79.

[5]Ping-Min Hsu，Chun-Liang Lin，Meng-Yao Yang.On the Complete Coverage Path Planning for Mobile Robots[J].Intell Robot Syst，2014（74）：945-963.

作者簡介

傅思程，男，四川省成都市人。

陳中柘（1968-），女，四川省成都市人?，F(xiàn)為電子科技大學(xué)副教授、博士，主要研究方向?yàn)闄C(jī)械電子及機(jī)器人。

作者單位

1.四川省成都市石室中學(xué) 四川省成都市 610050

2. 電子科技大學(xué) 四川省成都市 610000