基于柵格地圖的機器人覆蓋路徑規劃研究

摘要:研究了基于接觸傳感器的機器人覆蓋問題，提出了基于柵格地圖的內螺旋覆蓋(ISC)算法#65377;ISC算法通過邊界探索獲得環境邊界地圖之后，在線規劃覆蓋路徑，用距離轉變的搜索方法保證了完全覆蓋，通過設置gate柵格降低了重復覆蓋率#65377;通過對三個房間組成的室內環境的覆蓋仿真試驗驗證了該方法的可行性#65377;

關鍵詞:接觸傳感器;覆蓋算法;完全覆蓋

中圖分類號:TP24文獻標志碼:A

文章編號:1001-3695(2007)10-0056-03

0引言

在機器人的許多應用場合中需要用到覆蓋算法，如探測地雷[1]#65380;清掃地面[2]#65380;創建地圖等#65377;在這些應用中要求機器人(或機器人的探測器)覆蓋環境中所有未被障礙物占據的區域#65377;按照對環境知識的了解，覆蓋算法可分為已知環境覆蓋算法和未知環境覆蓋算法#65377;已知環境下要求機器人規劃出一條代價最小的路徑經過環境中的所有點#65377;此時該問題類似于旅行商問題(TSP)，因此它是NP難問題[3]#65377;未知環境下機器人必須利用自身攜帶的傳感器感知環境并規劃覆蓋路徑，該任務被稱為基于傳感器的覆蓋任務[4]#65377;

早期的一些覆蓋算法多是采用一些隨機方法[5，6]#65377;其實現簡單，機器人隨機選擇一個方向前進，遇到障礙物轉向然后繼續前進，但該方法無法保證完全覆蓋#65377;因此Carvalho等人研究了基于模板的完全覆蓋算法[7]#65377;該方法利用已知的環境地圖和一系列模板規劃覆蓋路徑，對不同的地形應用不同的模板，實現了完全覆蓋#65377;該方法需要已知的環境地圖#65377;Choset等人[8]和Acar等人[9]又分別提出了Boustrophedon分解方法和Morse分解方法對環境進行精確單元分解#65377;這兩種方法都是用一條假想的切面線掃過環境;當切面線與障礙物相交時，切面線的連通性發生變化，形成新的單元#65377;該方法將環境分成一些小單元，形成一個節點為各個單元#65380;相鄰單元有共同邊的圖表#65377;每個單元內部通過簡單的往返運動完成覆蓋;整個環境通過深度優先搜索的方法保證機器人訪問每個單元從而實現完全覆蓋，但這兩種方法假設障礙物的位置已知#65377;Gabriely等人提出了三種版本的基于柵格地圖的STC(spanning tree covering)覆蓋算法[10]#65377;STC算法用四倍于機器人尺寸的柵格劃分環境，并保證了對每個柵格都訪問且僅訪問一次#65377;從覆蓋路徑長度看，該方法實現了最優覆蓋，且三種版本實現了離線和在線規劃;但該方法只能覆蓋大于機器人四倍尺寸的自由空間，小于機器人四倍尺寸的地方均視為障礙物，不予規劃#65377;近年來的一些研究分別實現了對上述方法的在線規劃和多機器人實現方法[11，12]#65377;但上述方法或環境已知，或機器人攜帶聲納等距離傳感器，對于只配備接觸傳感器等#65380;探測范圍為機器人半徑的簡單機器人無法應用#65377;傳感器的探測范圍對機器人的規劃能力影響很大，探測半徑越小要求規劃能力越高#65377;Butler等人研究了基于接觸傳感器的覆蓋算法[4]，但是該環境為一線性環境，環境和障礙物的邊線都平行于機器人的運動方向#65377;為不失一般性并降低機器人成本，本文研究了基于接觸傳感器的機器人覆蓋算法，提出了基于接觸傳感器的在線機器人覆蓋算法，即內螺旋覆蓋(internal spiral coverage，ISC)算法#65377;該算法實現簡單且重復覆蓋少#65377;當周圍都覆蓋完畢后用距離轉換(DT)的方法搜索并運動到其他未覆蓋區域，保證了對環境的完全覆蓋#65377;

1ISC算法

ISC算法用四周只配備接觸傳感器和里程計的簡單圓形機器人實現對環境的完全覆蓋#65377;該算法有三個前提假設:a)機器人尺寸遠小于環境尺寸，因此將環境分為一系列大小為機器人尺寸大小的柵格，部分被障礙物占據的柵格即視為無法覆蓋的柵格;b)機器人進入某柵格即視為完全覆蓋該柵格;c)機器人坐標可以從里程計精確得出#65377;ISC算法分為邊界探索和在線覆蓋兩個階段#65377;ISC算法的頂層結構如下所示:

a)機器人從任一頂點開始邊界探索

b)while前方未出現已覆蓋柵格do

c)記錄邊界#65380;已覆蓋路徑信息并規劃柵格路徑

d)結束邊界探索，進入在線覆蓋

e)if前面接觸傳感器發現障礙物then

f)右側沿障礙物繞行，直到前方出現規劃路徑

g)if周圍有規劃好的路徑then

h)沿規劃路徑運動并記錄覆蓋信息和新規劃路徑

i)else 

j)用DT方法搜索其他區域的已規劃路徑并運動到該位置繼續覆蓋，如果有路徑goto g)，否則goto l)

k)if 環境中沒有已規劃柵格

l)stop

1.1邊界探索

機器人在進行規劃并覆蓋整個環境之前需先繞環境邊界運動一周獲得邊界信息#65377;如果環境邊界不可逾越，如室內環境的墻壁，則機器人可用接觸傳感器自主沿邊界行走并創建邊界地圖;如果是草坪等接觸傳感器無法感知的邊界，則需人為輔助(如遙控)沿邊界行走一周#65377;在本文中假設環境為第一種類型，即障礙物和環境邊界都可以通過接觸傳感器感知#65377;

首先機器人從任一頂點開始(假設機器人都從頂點處開始)運動#65377;文中采用機器人右側沿墻壁行走的方式探索，機器人保持右側傳感器接觸環境邊界前進，逆時針運動一周回到出發點#65377;在運動過程中將機器人右側傳感器所在柵格賦值為0，表示該柵格無法覆蓋;同時將機器人所在柵格賦值為1，表示該柵格已被覆蓋;將機器人左側柵格賦值為2，規劃出下一次要覆蓋的路徑#65377;如果左側柵格已被賦值，表明該柵格為障礙物(0)或已被覆蓋(1)，或已被規劃(2)#65377;因此當邊界探索結束機器人運動一周后，邊界地圖已經建立，機器人完成了邊界附近的一圈覆蓋并規劃出了下一次的運動路徑，如圖1所示#65377;灰色柵格表示環境邊界，橫線柵格表示已覆蓋區域，斜線柵格表示下一次欲覆蓋區域即規劃出的路徑#65377;

1.2在線覆蓋

邊界探索結束后，也生成了一圈與環境邊界形狀相似的覆蓋路徑(值為2的柵格)，機器人沿此路徑進行第二圈覆蓋#65377;在運動過程中將已走過的值為2的柵格賦值為1，將機器人左側未賦值柵格賦值為2#65377;當第二圈覆蓋結束時第三圈的覆蓋路徑已經生成#65377;因此如果環境內部無障礙物，以此方式循環即可向內螺旋完成所有區域覆蓋，如圖2所示#65377;

如果環境內部有障礙物則障礙物會阻斷規劃的路徑，導致值為2的柵格不連續，但該障礙物在下一圈的覆蓋過程中必定被機器人前面的碰撞傳感器檢測到#65377;機器人仍然采用右側沿物體邊界行走的方式繞著障礙物運動，直到前方重新出現值為2的柵格，機器人回到原規劃路徑上繼續原來的覆蓋#65377;

距離轉變的路徑規劃方法是從目標位置向初始位置尋找路徑[13]#65377;該方法在柵格表示的環境下能夠很好地規劃路徑#65377;首先從目標柵格開始向外傳播，對每個非障礙物柵格賦距離值，當環境中的所有柵格都被賦值之后，機器人可以從相鄰的8個柵格中選擇距離值最小的柵格作為路徑點，即用距離值下降最快的方法規劃路徑#65377;如果當前柵格周圍沒有距離值更小的柵格，說明不存在到達目標柵格的路徑#65377;圖4為用距離轉變方法規劃的路徑#65377;

當機器人將某一部分區域覆蓋完畢周圍沒有規劃的路徑時，用距離轉變方法搜索最近已規劃(值為2)的柵格#65377;從機器人當前位置開始對所有非障礙物柵格賦距離值(不是規劃覆蓋路徑所賦的值)，將未知區域假設為自由可覆蓋區域，則最近已被賦值為2的柵格(圖3中E點處)必定是在規劃好的柵格中距離值最小的柵格;機器人將該柵格設為目標點，從該點開始重新對非障礙物柵格賦距離值并搜索路徑#65377;機器人沿此路徑重新回到覆蓋路徑上#65377;

1.3復雜環境的覆蓋

對于常見的單個矩形房間，應用上述方法可以從環境邊界向內螺旋完成完全覆蓋，但對于多個矩形房間組成的復雜環境(圖1)，會在每個房間的入口處出現問題#65377;因為房間的入口處比兩側的空間都窄，如圖5所示，當兩側都還有未覆蓋區域時，入口處先完成覆蓋#65377;為此引入gate柵格的概念#65377;

定義1如果欲將某柵格賦值為2時該柵格已被賦值為1或2，且機器人前后都有尚未被覆蓋的柵格(值為2的柵格)，則稱該柵格為gate柵格#65377;

由1.2節可知，即將被賦值為2的柵格位于機器人當前位置的左側，如果該柵格已被賦值，說明其已被覆蓋(值為1)或已被規劃(值為2)#65377;因此最多再經過一次覆蓋該位置即會打斷規劃路徑(值為2的柵格)的連通性#65377;如圖5所示，當機器人沿MN從房間1進入房間2欲將PQ段賦值為2時，PQ段已被上一圈所規劃，并被賦值為2，因此在PQ段設置gate柵格，然后對房間2進行覆蓋#65377;如果不定義gate柵格，則機器人會先覆蓋QP段并將其賦值1，然后完成房間1和其他地方的覆蓋;最后當其他地方都覆蓋完畢后，用距離轉變方法重新搜索時才返回房間2完成覆蓋#65377;如果環境很大如圖1所示，在房間A和房間B都沒有完全覆蓋時先完成房間C的覆蓋，則最后機器人必須再分別回到房間A#65380;B完成覆蓋，增大了重復覆蓋率，降低了覆蓋效率#65377;因此當出現一個gate柵格時，機器人先完成gate柵格某一側的覆蓋#65377;當gate柵格該側不存在值為2的柵格時，表明該側已完全覆蓋，機器人用DT方法回到gate柵格處并繼續另一側的覆蓋，直到所有環境中沒有值為2的柵格，表明已完成了完全覆蓋，算法結束#65377;

2室內環境覆蓋仿真試驗

為檢驗ISC算法的可行性，本文進行了仿真試驗#65377;在試驗中機器人為20×20的圓形機器人，環境大小為900×700，分為三個房間，環境內部隨機分布少量障礙物#65377;障礙物與邊界用顏色檢測的方法進行識別，即只有當機器人與環境碰撞并有像素重疊時才能檢測到，模擬接觸傳感器#65377;機器人從左上角開始沿墻壁運動一周，用230步完成邊界探索，如圖6(a)所示;之后機器人按規劃的路徑運動，并在覆蓋第二圈時生成gate柵格(豎線柵格);gate柵格打斷第三圈的覆蓋，先完成房間A的完全覆蓋，如圖6(b)所示;然后通過對四個柵格進行重復覆蓋回到gate處，繼續第三圈的覆蓋#65377;在第三圈對房間B覆蓋時圓形障礙物破壞下一圈規劃的連續路徑，機器人右側沿障礙物邊線行走直到回到原規劃路徑;同時規劃出下一圈的連續路徑#65377;該障礙物對以后的覆蓋不再產生影響，如圖6(c)所示#65377;斜線柵格不受障礙物影響，仍然是連續路徑，最終經過1 150步完成全部覆蓋#65377;覆蓋路線如圖6(d)所示#65377;

在上述試驗中，環境自由區域為1 117個柵格，邊線上凹入部分和障礙物周長為144，完成全部覆蓋用了1 150步，重復率為2.85%#65377;

3結束語

本文對基于接觸傳感器的機器人覆蓋問題進行了研究，并提出了基于柵格地圖的內螺旋覆蓋(ISC)在線規劃算法#65377;該算法分為兩個階段:a)機器人用接觸傳感器沿環境邊界運動一周，獲得環境邊界地圖并生成第二圈的覆蓋路徑;b)用向內螺旋的方式覆蓋整個環境，對于內部有障礙物和結構復雜的環境，通過DT搜索以及設置gate柵格保證了完全覆蓋#65377;最后對三室結構的室內環境覆蓋問題進行了仿真，驗證了該方法的可行性#65377;試驗證明該算法實現簡單#65380;計算量小#65380;重復覆蓋少，可保證對環境的完全覆蓋，適用于嵌入式系統#65377;

參考文獻:

[1]ZHANG Y，SCHERVISH M，ACAR E U，et al. Probabilistic methods for robotic landmine search[C]//Proc of IEEE/RSJ International Conference on Intelligent Robots and Systems.Hawaii:[s.n.]，2001:15251532.

[2]PALACIN J，LASA X，MARCO S.Straightline path following in cleaning robots using lateral ultrasonic sensors[C]//Proc of Instrumentation and Measurement Technology Conference.Vail， CO:[s.n.]，2003:14841487.

[3]ITAI A，PAPADIMITRIO C，SZWARCFITER L.Hamilton paths in grid graphs [J].SIAM Journal on Computing，1982，11(4):676-686.

[4]BUTLER Z，RIZZI A，HOLLIS R.Contact sonsorbased coverage of rectilinear environments[C]//Proc of IEEE International Symposium on Intelligent Control/Intelligent Systems and Semiotics.Cambridge， MA:[s.n.]，1999:266-271.

[5]GAGE D.Randomized search strategies with imperfect sensors[C]//Proc of SPIE Mobile Robots Ⅷ.Boston:[s.n.]，1993:270-279.

[6]BALCH T.The case for randomized search[C]//Proc of IEEE International Conference on Robotics and Automation.San Francisco，CA:[s.n.]，2000.

[7]CARVALHO R，VIDAl H，VIEIRA P，et al.Complete coverage path planning and guidance for cleaning robots[C]//Proc of IEEE International Symposium on Industrial Electronics.Guimaraes，Portugal:[s.n.]，1997:677-682.

[8]CHOSET H，PIGNON P.Coverage of known spaces:the Boustrophedon cellular decomposition[J]. Autonomous Robotics，2000，9(3): 247-253.

[9]ACAR E，CHOSET H，RIZZI A，et al.Morse decompositions for coverage tasks[J].The International Journal of Robotics Research，2002，21(4): 331-344.

[10]GABRIELY Y，RIMON E.Spanningtree based coverage of continuous areas by a mobile robot[J]. Annals of Mathematics and Artificial Intelligence，2001，31(1/4): 77-98.

[11]LATIMER D I V，SRINIVASA S，LEESHUE V，et al.Towards sensor based coverage with robot teams[C]//Proc of IEEE International Conference on Robotics and Automation.Washington， D C:[s.n.]，2002:961-967.

[12]HAZON N，KAMINKA G A.Redundancy efficiency and robustness in multirobot coverage[C]//Proc of IEEE International Conference on Robotics and Automation.Barcelona:[s.n.]， 2005:11991205.

[13]ZELINSKY A.A mobile robot exploration algorithm[J].IEEE Trans on Robotics and Automation，1992，8(6):707-717.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”