朱寶艷，李彩虹,王小宇，宋 莉

(山東理工大學 計算機科學與技術學院，山東 淄博 255049)

基于柵格的移動機器人區(qū)域分解遍歷算法

朱寶艷，李彩虹,王小宇，宋 莉

(山東理工大學 計算機科學與技術學院，山東 淄博 255049)

針對不同類型障礙物提出基于柵格的區(qū)域分解方法使移動機器人實現(xiàn)全覆蓋遍歷.算法包含區(qū)域分解、子區(qū)域連接和子區(qū)域內遍歷三部分.區(qū)域分解是按照凹型障礙物邊緣和工作環(huán)境邊界將柵格區(qū)域分解成若干個子區(qū)域.區(qū)域內遍歷按照障礙物不同類型，對存在凸型障礙物的區(qū)域采用內螺旋方法，對于凹型障礙物區(qū)域采用梳狀遍歷方法.子區(qū)域之間通過兩點法求最短路徑，然后按照逆時針方向形成遍歷連通圖.通過MATLAB對算法進行仿真，結果驗證了該算法的可行性和有效性.

移動機器人；柵格；區(qū)域分解；遍歷規(guī)劃

近年來，伴隨著智能服務機器人[1]迅速發(fā)展的同時，智能服務機器人研究領域的一個重要分支——全覆蓋路徑規(guī)劃技術也逐漸受到眾多研究者的關注.與通常所說的點到點的路徑規(guī)劃不同，全覆蓋遍歷路徑規(guī)劃的最終目標是使機器人能夠按照一定的標準，在具有障礙物的環(huán)境中，無碰撞的合理而高效的遍歷除障礙物以外的全部區(qū)域.移動機器人全覆蓋遍歷算法的研究分為機器人環(huán)境建模方法和路徑搜索算法兩個方面，對于未知環(huán)境建?？梢圆捎眠呑哌吔５姆椒?，也可以通過SLAM(Simultaneous Localization and Mapping)[2]轉換成已知環(huán)境，對于已知環(huán)境建模的方法主要有柵格表示法[3]、可視圖法[4](幾何表示法)和拓撲圖法[5]等.對于全覆蓋路徑搜索算法主要有基于柵格表示法[6]的路徑規(guī)劃、基于行為的路徑規(guī)劃[7]、基于勢場柵格地圖的生物激勵法、模板模型法[8]、單元分解法[9-10]等.

基于柵格地圖常用的搜索算法是區(qū)域分解法.該方法將機器人所要遍歷的區(qū)域根據環(huán)境中的障礙物或其它方法分為若干子區(qū)域，通過對各子區(qū)域的遍歷實現(xiàn)對整個區(qū)域的遍歷.這種思想在很大的程度上降低了全局覆蓋實現(xiàn)的難度，因此對區(qū)域分解法的研究是近年來的主要趨勢.本文采用基于柵格區(qū)域分解的方法對環(huán)境建模，機器人依次遍歷每個子區(qū)域并通過局部路徑規(guī)劃方法實現(xiàn)各個子區(qū)域的高效連接.對每個子區(qū)域的遍歷按照障礙物的不同類型，對凸型障礙物存在的區(qū)域采用內螺旋的方式，對凹型障礙物存在的區(qū)域采用梳狀遍歷的方式.

1 環(huán)境建模

環(huán)境建模主要是機器人通過傳感器獲取實時環(huán)境信息并將環(huán)境進行柵格量化，這里將地圖環(huán)境按照機器人大小進行柵格化處理，建立柵格地圖，以此為基礎進行路徑規(guī)劃算法研究.

1.1 建立量化柵格的環(huán)境地圖

將工作環(huán)境柵格化后，整個區(qū)域分成n×n個柵格，每個柵格生成相應坐標cell(x,y)，其中，1≤x≤n, 1≤y≤n.然后針對每個柵格設定屬性值：

(1)

當柵格屬性cell(x,y).block=0時，說明該柵格為自由柵格，此時該柵格可以被覆蓋，可以被覆蓋的柵格還有一個覆蓋屬性cell(x,y).visited，其初始值設置為0，柵格每被覆蓋一次，其覆蓋屬性值依次累加1，即

cell(x,y).visited=cell(x,y).visited+1

(2)

圖1 柵格地圖 圖2 凸型障礙物

1.2 環(huán)境的障礙物模型

障礙物種類可以分為凹型障礙物和凸型障礙物兩種，凹型障礙物一般是半封閉型，比如U型、V型等，凹型障礙物以外的障礙物歸類為凸型障礙物.

凸型障礙物，如圖2所示.

凹型障礙物，比如U型障礙物，如圖3所示.

在環(huán)境地圖中，既有凹型障礙物又有凸型障礙物，如圖4所示.

圖3 凹型障礙物 圖4 混合類型障礙物

2 基于柵格區(qū)域分解法的算法設計

基于柵格的區(qū)域分解法包含區(qū)域分解、子區(qū)域連接和子區(qū)域遍歷三部分.在含有混合障礙物的環(huán)境里，首先以凹型障礙物邊緣和環(huán)境地圖邊界為標準進行區(qū)域劃分，然后通過局部路徑規(guī)劃算法求相鄰區(qū)域的最短路徑，最后將子區(qū)域按照逆時針方向連接起來，形成遍歷連通圖.子區(qū)域遍歷根據障礙物的不同類型采用不同的遍歷方法.

2.1 柵格的區(qū)域分解

在含有混合障礙物環(huán)境中，這里以含有U型障礙物為例說明，在可行區(qū)域按照U型障礙物邊緣和環(huán)境邊界進行分解，根據U型障礙物在環(huán)境地圖的不同位置，如圖5所示，有以下幾種分解情況：

1)當U型障礙物三邊與柵格地圖邊界均沒有接觸時為一般情況，可以分成四部分，分別為State1，State2，State3，State4，如圖5(a).

(a) 一般U型障礙物單元分解圖示 (b) 障礙物一邊靠在柵格地圖邊界

(c) 障礙物兩邊靠在柵格地圖邊界 (d) 障礙物三邊均在柵格地圖邊界

2)當U型障礙物一邊與柵格地圖邊界接觸時，可以分成三部分，分別為State1，State2，State3，如圖5(b).

3)當U型障礙物兩邊與柵格地圖邊界接觸時，可以分成兩部分，分別為State1，State2,如圖5(c).

4)當U型障礙物三邊都與柵格地圖邊界接觸時，除U型三邊外，將整個自由柵格區(qū)域看做U型內部區(qū)域，如圖5(d).

以圖5(a)為例說明算法設計過程.

2.2 子區(qū)域之間連接

子區(qū)域之間的連接包括子區(qū)域起點、終點位置確定，相鄰子區(qū)域連接方法設計和子區(qū)域連通圖設計三部分.

1) 子區(qū)域起點、終點位置確定

以圖5(a)為例，一共有四個子區(qū)域，分別為State1、State2、State3、State4，相鄰兩個子區(qū)域連接的起點在子區(qū)域的邊界.State1作為遍歷開始的子區(qū)域，設置機器人的起點為cell(1,n)，遍歷結束點為cell(x1,y1).State2起點有兩個，cell(1,j)或者cell(i,j)，通過計算結束點cell(x1,y1)到cell(1,j)或cell(i,j)的距離，取最短距離的點為State2的起點，State2遍歷結束點為cell(x2,y2).State3起點也有兩個，cell(i,1)或者cell(i,j2)，通過計算結束點cell(x2,y2)到cell(i,1)或cell(i,j2)的距離，取最短距離的點為State3起點，State3遍歷結束點為cell(x3,y3).State4起點是確定的，為U型障礙物的右下角，設U型障礙物上下邊緣長度為m，則起點為cell(i+m,j2)，遍歷結束點為cell(i+m,j).

State1結束點到State2起點的最短距離：

(3)

(4)

通過min(d1,d2) 確定State2的起點.

State2結束點到State3起點的最短距離：

(5)

(6)

通過min(d3,d4)確定State3的起點.

2) 相鄰子區(qū)域連接方法設計

圖6 兩點法局部路徑規(guī)劃

3) 子區(qū)域連通圖設計

四個子區(qū)域之間兩兩相鄰，因此直接按照逆時針(順時針)方向形成一張完全連通圖，即移動機器人按照State1→State2→State3→State4順序依次對每個子區(qū)域完成遍歷.

2.3 子區(qū)域遍歷

子區(qū)域遍歷根據障礙物的不同類型，在凸型障礙物區(qū)域采用內螺旋遍歷方式，在凹型障礙物區(qū)域采用梳狀遍歷方式.

1) 內螺旋遍歷算法

在凸型障礙物的環(huán)境地圖中，判斷程序結束的覆蓋率用coverage表示，最大覆蓋率用max表示.

根據設置的屬性值判斷機器人的動作目標：

G1 準目標柵格(即為前進方向的下一個柵格)

G2 障礙物柵格

G3 自由柵格(目標柵格相關的柵格)

具體算法如下：

Step1 初始化機器人位置坐標cell(1,n)，最大覆蓋率max=100%,機器人運行方向為順時針方向.

Step2 判斷覆蓋率coverage

Step3 判斷準目標柵格G1的屬性值cell(i,j).block=1時，轉移到Step5,否則繼續(xù)執(zhí)行.

Step4 該柵格為自由柵格G3，cell(x,y).visited=cell(x,y).visited+1，轉移到Step2.

Step5 判斷障礙物柵格G2內側的準目標柵格G1屬性值cell(i,j).block=0時，轉移到Step4，否則繼續(xù)執(zhí)行Step5.

Step6 退出循環(huán)，算法結束.

程序流程圖如圖7所示.

圖7 內螺旋程序流程圖

(a)遍歷中間過程 (b)遍歷結束

2) 梳狀遍歷算法

在U型障礙物柵格地圖中，(i,j2)為U型障礙物左下角柵格坐標，(i,j)為U型障礙物左上角柵格坐標。U型區(qū)域遍歷的初始位置橫坐標表示為x=i+m，縱坐標表示為y=j2，根據機器人起始點位置可知U型區(qū)域下邊緣為起始行，定義其為奇數(shù)行，運行方向為橫坐標增大的方向，相反的，在偶數(shù)行，運行方向為橫坐標減小的方向.用r表示奇數(shù)行或者偶數(shù)行的計算，用r0表示奇偶數(shù)計算結果.r的計算方法如式(7).

(7)

具體算法如下：

Step1 初始化U型區(qū)域的起始坐標為cell(x,y)，r0=0，初始運行方向為橫坐標增大的方向.

Step2 判斷y=j,是則轉移到Step7，否則繼續(xù)執(zhí)行.

Step3 判斷r=r0,是則轉移到Step9，否則繼續(xù)執(zhí)行.

Step4 機器人沿著當前方向橫坐標x=x+1，縱坐標不變，cell(x,y).visited=cell(x,y).visited+1.

Step5 判斷x=n，否則轉移到Step4，是則繼續(xù)執(zhí)行.

Step6 縱坐標y=y+1，并且轉移到Step2.

Step7 判斷x=i+m，是則轉移到Step12，否則機器人沿著當前方向橫坐標x=x-1，縱坐標不變，cell(x,y).visited=cell(x,y).visited+1，并繼續(xù)執(zhí)行Step7.

Step8 判斷x=i+1并且y=j-1，是則轉移到Step4，否則繼續(xù)執(zhí)行.

Step9 機器人沿著當前方向橫坐標x=x-1，縱坐標不變，cell(x,y).visited=cell(x,y).visited+1.

Step10 判斷x=i+1,否則轉移到Step6，是則繼續(xù)執(zhí)行.

Step11 判斷y=j-1，是則轉移到Step4，否則轉移到Step6.

Step12 退出循環(huán)，算法結束.

程序流程圖如9所示.

圖9 梳狀遍歷的流程圖

(a)遍歷開始 (b)遍歷結束

3 算法評價

根據移動機器人全覆蓋遍歷路徑規(guī)劃的要求，一是提高覆蓋率，二是降低重復率，通過計算得到覆蓋率和重復率的值，判斷該算法的可行性和有效性.

覆蓋率計算：

(8)

重復率計算：

(9)

式中：num為覆蓋柵格個數(shù)；numb為重復覆蓋柵格個數(shù)；n為環(huán)境區(qū)域邊長；ObsNumber為障礙物個數(shù).

4 實驗仿真和分析

在MATLAB上設計一個仿真實驗平臺，仿真的柵格區(qū)域大小為20×20，初始化機器人坐標cell(1,20)，障礙物柵格量化后用黑色表示.仿真結果如圖11所示.

圖11 仿真結果

5 結束語

本文采用基于柵格的區(qū)域分解的方法實現(xiàn)了移動機器人全覆蓋遍歷，對柵格地圖按照凹型障礙物邊緣和環(huán)境邊界分成了幾個子區(qū)域，用兩點法搜索算法將這幾個子區(qū)域按逆時針方向形成一張完全連通圖，每個子區(qū)域根據障礙物不同類型對凸型障礙物采用內螺旋遍歷，對凹型障礙物采用梳狀遍歷.通過MATLAB仿真平臺模擬了遍歷過程，仿真結果表明，該算法在實現(xiàn)移動機器人全覆蓋遍歷的過程具有可行性和有效性.

基于柵格的移動機器人區(qū)域分解遍歷算法,能高效的完成全覆蓋遍歷的要求，但也存在一些不足，如進行區(qū)域分解時如果遇到復雜的凹型和凸型障礙物如何進行子區(qū)域分解才能達到重復率最低，進行局部路徑規(guī)劃時，尚不能保證遍歷路徑絕對最短等問題，這是今后要繼續(xù)研究的課題.

[1] 趙曉東，鮑方.清潔機器人路徑規(guī)劃算法研究綜述[J].機 電 工 程,2013,30(11):1 440-1 444.

[2] 季秀才,鄭志強,張輝.SLAM問題中機器人定位誤差分析與控制[J].自動化學報,2008,34(3):323-330.

[3] 劉松,李志蜀,李奇.機器人全覆蓋最優(yōu)路徑規(guī)劃的改進遺傳算法[J].計算機工程與應用,2009,45(31):245-248．

[4] 艾海舟,張鈸.基于拓撲的路徑規(guī)劃問題的圖形解法[J].機器人.1990,12(5):20-24.

[5] 紀晴,段培永,李連防.移動機器人全覆蓋路徑規(guī)劃算法綜述[J].山東建筑大學學報,2007,22(4):355-359.

[6] 陳鵬,李彩虹.移動機器人全遍歷覆蓋路徑規(guī)劃研究[J].山東理工大學學報(自然科學版),2013,27(5):22-27.

[7] 陳煒峰,薛冬,周旺平.基于行為模糊控制的移動機器人路徑規(guī)劃[J].計算機測量與控制,2014,22(11):3 600-3 602.

[8] 劉海,郭小勤,余得貴.清潔機器人全覆蓋路徑規(guī)劃算法綜述[J].機電產品開發(fā)與創(chuàng)新,2008,21(6):36-38.

[9]CHOSETH.Coverageofknownspaces:Theboustrophedoncellulardecomposition[J].AutonomousRobots, 2000,5(3):247-253.

[10]FABIOMM.Adirectionaldiffusionalgorithmoncellularautomataforrobotpath-planning[J].FutureGenerationComputerSystems,2002,18(7):982-994.

(編輯：劉寶江)

Cellular decomposition algorithm of coverage path planning based on the grid map for the mobile robot

ZHU Bao-yan, LI Cai-hong, WANG Xiao-yu, SONG Li

(School of Computer Science and Technology, Shandong University of Technology, Zibo 255049, China)

According to the different types of obstacles, this paper presents a cellular decomposition algorithm of the coverage path planning based on the grid map for the mobile robot.The algorithm consists of three parts, including the cellular decomposition, the sub-regions connections and the coverage of the sub-regions inside. The cellular decomposition is to divide the feasible regions of the grid map into several sub-regions according to the boundaries of the concave obstacles and workplace. According to the different types of obstacles in the sub-regions, an internal spiral method is adopted for the area with convex obstacles and a back-and-forth method is adopted for the area with concave obstacles. Two-points method is used to find the shortest path between the adjacent sub-regions. Then a complete connected graph is formed according to the counter clockwise direction. The feasibility and effectiveness of the algorithm are verified by the simulation of MATLAB.

mobile robot; grid; cellular decomposition; coverage path planning

2016-07-02

國家自然科學基金項目(61473179);山東省自然科學基金項目(ZR2014FM007)

朱寶艷, 女,zby0682@126.com; 通信作者：李彩虹, 女,lich@sdut.edu.cn

1672-6197(2017)04-0013-06

TP

A