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

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

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

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

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

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

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

0 引言

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

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

1 問題描述

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

2 算法描述

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

2.1 內(nèi)螺旋法

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

2.2 野火法

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

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

圖2 野火法示意圖

2.3 高效的全覆蓋路徑算法

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

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

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

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

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

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

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

Step 7算法結(jié)束.

2.4 算法的有效性證明

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

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

圖4 抽象后的連通圖

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

3 仿真結(jié)果

本文提出的算法在自行開發(fā)的機器人仿真平臺GA上進行多次仿真實驗，并與其他的算法進行了對比.

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

圖5 房間的平面圖

圖6 房間的柵格地圖

4 算法性能分析和改進

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

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

圖8 凹陷形障礙的野火法擴展

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

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

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

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

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

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

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

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

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

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

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

圖13 仿真對比

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

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

［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］ 林宗德.居家清潔機器人之全域覆蓋路徑規(guī)劃與實現(xiàn)［D］.臺南：國立成功大學(xué)工程科學(xué)系，2005.

［8］ 田春穎，劉瑜，馮申珅，等.基于柵格地圖的移動機器人完全遍歷算法——矩形分解法［J］.機械工程學(xué)報，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ā)展計劃重點項目（20100305）.

劉淑華（1970—），女，博士，副教授，主要從事移動機器人研究.

陶 理）