劉淑華，夏 菁，孫學(xué)敏，張 友

（東北師范大學(xué)計(jì)算機(jī)科學(xué)與信息技術(shù)學(xué)院，吉林 長(zhǎng)春 130117）

已知環(huán)境下一種高效全覆蓋路徑規(guī)劃算法

劉淑華，夏 菁，孫學(xué)敏，張 友

（東北師范大學(xué)計(jì)算機(jī)科學(xué)與信息技術(shù)學(xué)院，吉林 長(zhǎng)春 130117）

提出一種基于柵格表示的非結(jié)構(gòu)化環(huán)境下移動(dòng)機(jī)器人的高效全覆蓋路徑規(guī)劃算法.移動(dòng)機(jī)器人采取內(nèi)螺旋算法從起始點(diǎn)進(jìn)行覆蓋，當(dāng)陷入覆蓋死角時(shí)，采用野火法搜索周邊離它最近的未覆蓋點(diǎn)，找到后按A＊算法規(guī)劃出一條路徑到達(dá)新的覆蓋起點(diǎn)，直到全部覆蓋為止.仿真結(jié)果表明該算法的覆蓋率達(dá)到100%，重復(fù)率較其他算法低.而且從理論上進(jìn)一步證明了該算法的有效性.

全覆蓋路徑規(guī)劃；內(nèi)螺旋算法；野火法；A＊算法

0 引言

隨著智能服務(wù)型機(jī)器人的迅速發(fā)展，全覆蓋路徑規(guī)劃技術(shù)的研究越來(lái)越受到研究者的重視.全覆蓋路徑規(guī)劃是指機(jī)器人以盡可能低的重復(fù)率遍歷環(huán)境中的全部無(wú)障礙區(qū).因此，它包含兩個(gè)方面的技術(shù)指標(biāo)，即覆蓋率和重復(fù)率.全覆蓋路徑規(guī)劃技術(shù)有著廣泛的應(yīng)用背景，它對(duì)清潔機(jī)器人、草坪修剪機(jī)器人、礦藏探測(cè)機(jī)器人以及掃雷機(jī)器人等都具有重要意義.

已有的全覆蓋路徑規(guī)劃算法主要包括隨機(jī)方法，最大面積優(yōu)先算法，ISC（內(nèi)螺旋覆蓋算法），基于模板的完全覆蓋方法，Boustrophedon往復(fù)前進(jìn)法等［1－5］.隨機(jī)方法讓機(jī)器人隨機(jī)選擇一個(gè)方向前進(jìn)，遇到障礙物后轉(zhuǎn)向再繼續(xù)前進(jìn)［6］.該算法簡(jiǎn)單易行，但無(wú)法保證完全覆蓋.最大面積優(yōu)先算法將待覆蓋的區(qū)域劃分成許多柵格，機(jī)器人在行走過(guò)程中隨時(shí)計(jì)算當(dāng)前位置的前邊、左邊和右邊三個(gè)方向上未覆蓋柵格的數(shù)目，若前方有未覆蓋柵格，則繼續(xù)前進(jìn)，否則朝未覆蓋柵格較多的方向轉(zhuǎn)彎.基于模板的完全覆蓋方法則是利用已知的環(huán)境地圖和一系列模板規(guī)劃出覆蓋路徑，對(duì)不同的地形應(yīng)用不同的模板.該方法能實(shí)現(xiàn)完全覆蓋，但要求事先知道環(huán)境地圖.Boustrophedon往復(fù)前進(jìn)的方法分為簡(jiǎn)單的往復(fù)式策略和改進(jìn)的往復(fù)式策略.簡(jiǎn)單的策略會(huì)留有由障礙物引起的未覆蓋區(qū)域，而且障礙物越多，未覆蓋的區(qū)域就越多.改進(jìn)的策略是進(jìn)行與第一次行進(jìn)方向相垂直的第二次覆蓋，進(jìn)而提高覆蓋率.因此，上述方法在覆蓋效率方面都有待于提高.

1 問(wèn)題描述

由于柵格地圖易于計(jì)算是否實(shí)現(xiàn)完全覆蓋，因此本文研究柵格環(huán)境下移動(dòng)機(jī)器人的全覆蓋路徑規(guī)劃技術(shù).環(huán)境中存在任意形狀的障礙物，機(jī)器人先按一定的算法進(jìn)行自主覆蓋，只有當(dāng)機(jī)器人陷入死角（周邊的所有柵格都已經(jīng)覆蓋完）時(shí)才“拿”出地圖進(jìn)行搜索，搜索到下一個(gè)未覆蓋的區(qū)域后移動(dòng)到新的區(qū)域繼續(xù)進(jìn)行自主覆蓋，直到全部完成為止.因此，本文研究的是已知非結(jié)構(gòu)化環(huán)境下的半自主全覆蓋路徑算法.

2 算法描述

本文首先采用內(nèi)螺旋算法進(jìn)行覆蓋，當(dāng)機(jī)器人陷入局部死鎖點(diǎn)時(shí)，用野火法搜索離機(jī)器人當(dāng)前點(diǎn)最近的未覆蓋點(diǎn)，找到以后用A＊算法規(guī)劃出從當(dāng)前點(diǎn)到未覆蓋點(diǎn)的最短路徑，再開(kāi)始新區(qū)域的覆蓋，直到全部覆蓋完成為止.

2.1 內(nèi)螺旋法

內(nèi)螺旋算法的基本思想是機(jī)器人按一定的方向（如順時(shí)針或逆時(shí)針）進(jìn)行覆蓋，當(dāng)前方有未覆蓋的柵格時(shí)，機(jī)器人就向前運(yùn)動(dòng)，如果前方有障礙物或者已經(jīng)覆蓋過(guò)，則向右轉(zhuǎn)90°，如圖1.

2.2 野火法

野火法又稱廣義的寬度優(yōu)先搜索法，是一種在固定尺寸的單元陣列中有效且易于實(shí)現(xiàn)的尋找路徑技術(shù).算法采用從目標(biāo)位置向外的前波擴(kuò)展，直到找到所需要的單元格為止.本文對(duì)該算法進(jìn)行了擴(kuò)展，即采用全方位的擴(kuò)展波，當(dāng)機(jī)器人陷入死角時(shí)，算法向機(jī)器人的8個(gè)方向一起擴(kuò)展，直到找到一個(gè)空閑的單元為止.如圖2-A.當(dāng)機(jī)器人陷入死角時(shí)，首先按圖2-B查找機(jī)器人周圍的8個(gè)柵格，如果沒(méi)有找到空閑的柵格，則繼續(xù)擴(kuò)大搜索范圍，查找距離機(jī)器人為3的柵格，如圖2-C.按此方法依次擴(kuò)大查找的范圍，直到找到一個(gè)空閑的柵格為止.

圖1 內(nèi)螺旋算法示意圖

圖2 野火法示意圖

2.3 高效的全覆蓋路徑算法

結(jié)合內(nèi)螺旋算法、野火法以及A＊算法，本文提出了一種高效的全覆蓋路徑規(guī)劃算法.算法的具體步驟如下.

Step 1按內(nèi)螺旋算法進(jìn)行全覆蓋.

Step 2如果前方柵格有障礙或已經(jīng)被覆蓋，則向右旋轉(zhuǎn)90°.

Step 3如果機(jī)器人陷入死角，轉(zhuǎn)Step 4；否則轉(zhuǎn)Step 1.

Step 4用野火法搜索離機(jī)器人最近的未覆蓋柵格，如果沒(méi)找到，說(shuō)明地圖已經(jīng)被全覆蓋，轉(zhuǎn)Step 7；否則轉(zhuǎn)Step 5.

Step 5用A＊算法規(guī)劃出從機(jī)器人當(dāng)前位置到搜索到的未覆蓋點(diǎn)之間的最短路徑，然后機(jī)器人按該路徑到達(dá)未覆蓋的柵格，此時(shí)會(huì)出現(xiàn)一定數(shù)量的重復(fù)覆蓋，但由于A＊算法得到的是最短路徑，所以盡可能保證較低的重復(fù)率.

Step 6機(jī)器人從新的起點(diǎn)繼續(xù)執(zhí)行覆蓋任務(wù)，轉(zhuǎn)Step 1.

Step 7算法結(jié)束.

2.4 算法的有效性證明

如果環(huán)境中存在多個(gè)待覆蓋的區(qū)域B，C，D和E，當(dāng)前機(jī)器人在A點(diǎn)陷入死角，如圖3所示.內(nèi)螺旋算法的特點(diǎn)是由區(qū)域的四周向中間覆蓋，所以每個(gè)未覆蓋區(qū)域可近似地抽象為它的中心點(diǎn).因此，圖3可以抽象為圖4.

圖3 地圖中存在多個(gè)待覆蓋的區(qū)域

圖4 抽象后的連通圖

此時(shí)，要使重復(fù)覆蓋最少就轉(zhuǎn)變成了旅游商問(wèn)題（TSP），即求從某一頂點(diǎn)出發(fā)，遍歷完圖中全部的頂點(diǎn)且要求路徑最短.其中，最近鄰點(diǎn)法（Nearest Neighbor Procedure）是求解旅游商問(wèn)題的解法之一，即開(kāi)始以尋找離場(chǎng)站最近的需求點(diǎn)為起始路線的第一個(gè)顧客，此后尋找離最后加入路線的顧客最近的需求點(diǎn)，直到最后.該方法與本文用到的野火法尋找下一個(gè)結(jié)點(diǎn)，然后用A＊算法求到下一個(gè)結(jié)點(diǎn)的最短路徑是完全吻合的，因此，本文的方法從理論上能證明是最優(yōu)的.

3 仿真結(jié)果

本文提出的算法在自行開(kāi)發(fā)的機(jī)器人仿真平臺(tái)GA上進(jìn)行多次仿真實(shí)驗(yàn)，并與其他的算法進(jìn)行了對(duì)比.

首先，以文獻(xiàn)［7］中的地圖為例，用本文提出的算法進(jìn)行了仿真.圖5是一個(gè)家庭的結(jié)構(gòu)圖，圖6是對(duì)應(yīng)的柵格地圖，大小為40＊50.圖7是用本文提出的算法覆蓋后的效果，深灰色代表的是障礙，淺灰色代表清掃過(guò)的柵格，黑色代表重復(fù)的柵格.

圖5 房間的平面圖

圖6 房間的柵格地圖

4 算法性能分析和改進(jìn)

上述算法的性能已經(jīng)實(shí)現(xiàn)，重復(fù)率很低，但還存在一定的問(wèn)題，即對(duì)于凹陷形的障礙物或有較長(zhǎng)的障礙物阻擋時(shí)適應(yīng)性有所下降.原因在于用野火法尋找下一個(gè)未被覆蓋點(diǎn)時(shí)，沒(méi)有考慮被障礙物阻擋的問(wèn)題.如圖8.

圖7 重復(fù)率為3.3%的效果圖

圖8 凹陷形障礙的野火法擴(kuò)展

如果機(jī)器人陷入了“死角”A點(diǎn)，此時(shí)按野火法擴(kuò)展時(shí)，找到離A點(diǎn)最近的未覆蓋點(diǎn)是C，但實(shí)際情況是B點(diǎn)離A點(diǎn)最近.為此，對(duì)上述算法的Step 5進(jìn)行改進(jìn)，具體改進(jìn)方法如下：

假設(shè)機(jī)器人當(dāng)前處于“死角”A點(diǎn)，用野火法搜到離A點(diǎn)歐式距離最近的點(diǎn)為C.機(jī)器人先用A＊算法規(guī)劃出從A到C的路徑，然后在沿該路徑從A到C運(yùn)動(dòng)的過(guò)程中，增加機(jī)器人的視距，視距的大小依賴于視機(jī)器人的傳感器，本文分別對(duì)機(jī)器人的視距為1，2，4的情況進(jìn)行了仿真.機(jī)器人在行進(jìn)的過(guò)程中，如果發(fā)現(xiàn)視距范圍內(nèi)有未覆蓋的柵格，則停止向C點(diǎn)前進(jìn)，而是從視距內(nèi)發(fā)現(xiàn)的空閑柵格開(kāi)始進(jìn)行新一輪的內(nèi)螺旋覆蓋.

用改進(jìn)后的算法對(duì)圖6所示的環(huán)境再次進(jìn)行仿真，將機(jī)器人的視距分別設(shè)為2和4，得到的仿真結(jié)果如圖9和圖10.

圖9 機(jī)器人的視距為2，重復(fù)率為3.05%的仿真結(jié)果

10 機(jī)器人的視距為4，重復(fù)率為2.05%的仿真結(jié)果

接下來(lái)本文還做了其他仿真，包括不同起始點(diǎn)測(cè)試、障礙物的形狀和復(fù)雜度測(cè)試，以及與其他算法的對(duì)比.

圖11 起點(diǎn)在（0，0），重復(fù)率為4.2%的仿真結(jié)果

圖12 起點(diǎn)在（35，5），重復(fù)率為4.6%的仿真結(jié)果

表1 全覆蓋算法性能比較%

由圖9和圖11可以看出，障礙物的形狀越不規(guī)則、障礙物越多，覆蓋的重復(fù)率就越大；由圖11和圖12可以看出，本文的算法性能基本不受起始點(diǎn)的影響.

最后，用文獻(xiàn)［8］的地圖進(jìn)行對(duì)比實(shí)驗(yàn)，地圖的大小為30＊55柵格.仿真結(jié)果如圖13.

圖13 仿真對(duì)比

5 結(jié)論與未來(lái)的工作

本文提出了一種結(jié)合內(nèi)螺旋算法、野火法和A＊算法的全覆蓋路徑規(guī)劃算法，仿真結(jié)果表明，該算法適用于存在任意形狀障礙物的環(huán)境，對(duì)清掃的起點(diǎn)沒(méi)有依賴，清掃效率很高.另外，我們從理論上證明了該算法的有效性，理想情況下，該算法的效果與旅游商問(wèn)題的求解相吻合，但當(dāng)有較大長(zhǎng)度的障礙物阻擋時(shí)，算法的性能會(huì)有所下降.未來(lái)的工作是讓機(jī)器人加強(qiáng)對(duì)環(huán)境的理解，尤其是室內(nèi)房間結(jié)構(gòu)的學(xué)習(xí)和理解，然后再結(jié)合門柵格技術(shù)，使算法的效率得到進(jìn)一步的提高.

［1］ CARVALHO R N，VIDAL H，HIEIRA P.Complete coverage path planning and guidance for cleaning robots［C］／／Proceedings of the IEEE International Symposium on Industrial Electronics，Guimar?es，Portugal：Institute of Electrical and Electronics Enginee，1997：677-682.

［2］ ITAIA，PAPADIMITRIO C，SZWARCFITER L.Hamilton paths in grid graphs［J］.S IAM Journal on Computing，1982，11（4）：676-686.

［3］ GAGE D.Randomized search strategies with imperfect sensors［C］／／Proc of SPIE Mobile RobotsⅧ.Boston，1993：270-279.

［4］ BALCH T.The case for randomized search［C］／／Proc of IEEE Inter-national Conference on Robotics and Automation.San Francisco，CA，2000：264-275.

［5］ CHOSETH，PIGNON P.Coverage of known spaces：the Boustrophedon cellular decomposition［J］.Autonomous Robotics，2000，9（3）：247-253.

［6］ LATOME J-C，BARRAQUAND J.Robot motion planning：a distributed presentation approach［J］.International Journal of Robotics Research，1991，10：628-649.

［7］ 林宗德.居家清潔機(jī)器人之全域覆蓋路徑規(guī)劃與實(shí)現(xiàn)［D］.臺(tái)南：國(guó)立成功大學(xué)工程科學(xué)系，2005.

［8］ 田春穎，劉瑜，馮申珅，等.基于柵格地圖的移動(dòng)機(jī)器人完全遍歷算法——矩形分解法［J］.機(jī)械工程學(xué)報(bào)，2004，40（10）：56-61.

An efficient complete coverage path planning in known environments

LIU Shu-hua，XIA Jing，SUN Xue-min，ZHANG You
（College of Computer Science and Information Technology，Northeast Normal University，Changchun 130117，China）

This paper proposed a near-optimal complete coverage path planning algorithm based on unstructured grid environments.Initially，the robot adopts internal spiral coverage.Only when the robot enters into “deadlock”，namely，the grids around it either covered or occupied by obstacles，the grass fire algorithm is adopted to search a vacant grid that is nearest to the robot's current position.Then the robot performs A＊algorithm to plan a path to the new vacant grid and continues its coverage.Simulation results show the proposed algorithm can cover completely and the number of duplicated grids is relatively low.Finally，this paper testified the efficiency by the graph theory.

complete coverage path planning；internal spiral coverage；grassfire；A＊algorithm

TP 242

520·20

A

1000-1832（2011）04-0039-05

2010-12-08

吉林省科技發(fā)展計(jì)劃重點(diǎn)項(xiàng)目（20100305）.

劉淑華（1970—），女，博士，副教授，主要從事移動(dòng)機(jī)器人研究.

陶 理）