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

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

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

1 引言

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

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

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

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

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

3 田埂式運行方法的改進

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

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

3.2 加入回溯法的新型田埂式運行方法

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

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

3.3 加入特征標記的新田埂式運行方法

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

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

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

5 結論

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

（通信作者：陳中柘）

參考文獻

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

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

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

[4]任亞楠，賈瑞清，何金田.基于超聲波傳感器的移動機器人避障系統(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)為電子科技大學副教授、博士，主要研究方向為機械電子及機器人。

作者單位

1.四川省成都市石室中學 四川省成都市 610050

2. 電子科技大學 四川省成都市 610000