摘 要：研究丁多簡單機器人協作覆蓋的問題。針對簡單機器人只能用接觸傳感器感知外部環境的局限性，提出了基于柵格地圖表示法的多機器人內螺旋覆蓋算法進行在線覆蓋規劃。該方法通過對部分區域的重復覆蓋和設置GATE柵格實現了對環境的完全覆蓋，同時該方法保證了只要有一個機器人不出現故障就可以完成覆蓋，提高了系統穩定性。最后用仿真試驗驗證了該方法的可行性。 關鍵詞：多簡單機器人；覆蓋算法；完全覆蓋；穩定性 Abstract：Cooperative coverage by multi—simple-robot is discussed．For online coverage planning，a Multi-robot Internal Spiral Coverage algorithm based on grid map is presented to overcome the sensing limitation of simple robot that can sense the environment only by contact sensors．The algorithm guarantees complete coverage by repeating covering portion of the environment and setting the GATE grids．The algorithm improves system stability in the sense that coverage can be cometed if only one robot is not in catastrophic failure．Simulation experiment proves the feasibility of the algorithm． Keywords：multi—simple-robot；coverage algorithm；complete coverage；stability 1引言（Introduction） 機器人的許多應用領域需要用到覆蓋算法，如探測地雷、清掃地面、創建地圖等。這些應用領域要求機器人（或機器人的探測器）覆蓋環境中的所有未被障礙物占據的區域。在未知環境中，機器人必須利用自身攜帶的傳感器感知環境并規劃覆蓋路徑，該任務被稱為基于傳感器的覆蓋任務[1]。多機器人系統由于其并行性，可以提高系統效率，縮短完成任務的時間，并且在單個機器人出現故障時其它機器人仍能完成任務，從而提高了系統穩定性，因此多機器人覆蓋任務的研究越來越受到人們的關注。 多機器人覆蓋任務根據對環境知識的了解可分為離線和在線規劃兩種。離線規劃中機器人預先知道環境地圖，因此在開始覆蓋之前將覆蓋任務和運動路徑規劃好并分配給各機器人，如文[2]。文[2]是在單機器人STC（spanningtreecovering）算法的基礎上擴展而來的，在覆蓋之前將以柵格表示的覆蓋路徑分配給各機器人，在覆蓋過程中各機器人相互通信，如果某個機器人出現故障停止運動，其后面的機器人在執行完自己的任務之后接著完成故障機器人的任務。該文還討論了機器人起始位置對覆蓋效率的影響。在線多機器人覆蓋中，Rekleitis等人研究了多臺具有局部通信能力的機器人的覆蓋問題[3]。該文用兩個在相互可視的情況下才能通信的機器人探索環境并劃分覆蓋單元，其它機器人按劃分的單元進行覆蓋。Wagner等人研究了類蟻群算法的多機器人覆蓋問題[4]。他們假設機器人在地圖上留下類似于昆蟲信息素的信息進行通信，協調各機器人共同完成任務。在這些研究中，機器人都配備外部傳感器，可以感知一定范圍內的環境，或環境地圖已知，對于未知環境下的簡單機器人覆蓋并不適用。簡單機器人是指只配備接觸傳感器和內部測距傳感器的機器人[5]。本文針對簡單機器人提出了多機器人內螺旋覆蓋算法（Multi—robotInternalSpiralCoverage。MISC）。該算法是在作者提出的內螺旋覆蓋（InternalSpiralCoverage，ISC）算法的基礎上實現的。 2 ISC算法簡介（ISCalgorithm） ISC算法用簡單圓形機器人覆蓋環境，該算法是基于柵格地圖的在線覆蓋算法，算法假設機器人全局坐標可以由機器人內部測距傳感器（里程計）精確得出。在覆蓋過程中ISC算法分為兩個階段：邊界探索階段和在線覆蓋階段。在邊界探索階段，機器人從環境的任一頂點開始，采取右側沿環境邊界行走的方式運動一周。在探索過程中，將機器人右側接觸傳感器所在柵格賦值為0，表示該柵格無法覆蓋，將機器人走過的柵格賦值為1，表示該柵格已被覆蓋，將機器人左側柵格賦值為2，表示下一圈要覆蓋的柵格，即在線規劃的覆蓋路徑。因此，當邊界探索階段結束之后，環境邊界已經獲得，機器人完成了邊界附近的一圈覆蓋，并規劃了下一圈的運動路徑，之后進入在線覆蓋階段。 在線覆蓋階段，機器人沿著上一圈生成的值為2的連續柵格運動，在運動過程中將已走過的值為2的柵格賦值為1，將機器人左側未賦值的柵格賦值為2。當第二圈覆蓋結束時第三圈的覆蓋路徑已經生成，機器人以此方式向內螺旋完成所有區域的覆蓋。 如果環境內部有障礙物，則障礙物會阻斷規劃的路徑，導致值為2的柵格不連續，但該障礙物在下圈的覆蓋過程中必將被機器人前面的接觸傳感器檢測到，機器人仍然采取右側沿物體邊界行走的方式繞著障礙物運動，直到前方重新出現值為2的柵格，機器人回到原規劃路徑上繼續原來的覆蓋。 對于常見的單個矩形環境，應用上述方法可以從環境邊界向內螺旋完成完全覆蓋，但對于多個房間組成的復雜環境，會在每個房間的人口處出現問題。因為房間的入口處比兩側的空間都窄，如圖1所示，因此當人口處兩側都還有未覆蓋區域時，該狹窄區域先完成覆蓋，因此引入GATE柵格的概念。 定義1：如果欲將某柵格賦值為2時該柵格已被賦值萬I或2，且該柵格左側前后都有尚未被覆蓋的柵格（值為2的柵格），則稱該柵格為GATE柵格。 在圖1中，當機器人沿MN從房間B進入房間A欲將PQ段賦值為2時，PQ段已在機器人上一圈運動時被規劃，已被賦值為2，因此在PQ段設置GATE柵格，然后對房間A進行完全覆蓋。如果不定義GATE柵格，則機器人會在覆蓋完OQ之后先覆蓋（并將其賦值為1，打斷了房間A、B未覆蓋部分的連通性，導致機器人無法再進入房間A進行覆蓋。因此當出現一個GATE柵格時，機器人記錄該柵格的位置，先完成GATE柵格某一側的覆蓋，當GATE柵格該側不存在值為2的柵格時，表明該側已完全覆蓋，機器人回到GATE處繼續另一側的覆蓋，直到所有環境中沒有值為2的柵格，表明已完成了完全覆蓋，算法結束。 3多機器人內螺旋覆蓋算法（MISCalgo-rithm） 在多機器人覆蓋任務中，各機器人共享環境地圖，即所有機器人都把自己已覆蓋的和規劃的柵格信息與其它機器人共享。設由k個機器人共同完成環境的覆蓋。 3．1多機器人協作覆蓋邊界探索 設k個機器人隨機分布在環境邊界上，右側沿邊界同時運動并記錄環境信息。k個機器人將環境邊界分為k段，記最短的那段為第m段，由機器人m探索。當機器人m運動至第m+1個機器人的初始位置處時，會在共享地圖中發現前方的柵格已被賦值為1，同時左前方柵格已被賦值為2，則機器人m結束邊界探索階段，運動至機器人m+1規劃的第二圈柵格上開始在線覆蓋階段，同樣其它機器人都在運動至下一個機器人的初始位置處轉為在線覆蓋階段，并沿著下一個機器人規劃好的路徑運動。 3．2多機器人在線覆蓋 進入在線覆蓋階段之后，每個機器人（以第m個機器人為例）都會沿著下一個（第m+1個）機器人上一圈規劃好的路徑運動，同時為上一個（m-1）機器人規劃下一圈的運動路徑，直至完成整個環境的完全覆蓋。當環境內部出現障礙物時同ISC算法一樣，機器人轉為右側沿障礙物邊界運動的探索模式，直到機器人前方重新出現值為2的柵格，機器人又采取在線覆蓋模式。 對于不規則形狀的環境，如圖2所示，環境某～側有一枝狀凸出，當凸出區域未覆蓋部分的高度CD>3d時（d為柵格邊長），規劃按上述方法進行。當CD=3d時，機器人m沿B→C→D→E覆蓋之后未覆蓋部分為高度為d的一條T形“死胡同”，機器人m-1將沿著該路徑運動至頂點C處發現周圍沒有規劃的路徑，則m-l在共享地圖中搜索離當前位置最近的值為2的柵格（E點處柵格），機器人運動到該點繼續原來的覆蓋。如果CD=2d，機器人m沿B→C到達C處時只有D→E是規劃好的路徑，則m沿D→E運動。如果m-1與m距離很近，在m尚未完成D→E覆蓋時m-1就到達E處，m-1也會沿E→D運動，勢必與m在DE段相遇，這時兩個機器人周圍都沒有規劃好的路徑可走，同樣機器人搜索離當前位置最近的值為2的柵格（在E點下方）。則m-l旋轉180。沿D→E后退，m仍然前進（為敘述方便，將機器人m-1和m的序號交換，使得機器人m始終在m-l的前方）。當新的機器人m到達E處時重新回到m+1規劃的路徑上，繼續覆蓋，機器人m-1也按m在線規劃的路徑運動。 多機器人覆蓋中也會在房間的入口處出現先完成覆蓋的情況，因此在這些地方設置GATE柵格，不過每個機器人設置自己獨立的GATE柵格。如圖3所示，當機器人m沿MN進入房間時，將PQ段設為GATE柵格，并完成房間的完全覆蓋。機器人m-1沿著RP到達P點處時，因為PQ段不是值為2的柵格，相反PS是上一圈某個機器人離開房間A時規劃好的路徑，因此機器人m-1沿著PS運動。機器人m完成房間的完全覆蓋之后回到自己設置的GATE柵格，并按從后向前的順序對GATE柵格覆蓋。如果設置的GATE柵格全部覆蓋完并且在第一個GATE柵格周圍找到值為2的柵格，說明機器人m-1與m相距較遠，還沒有到達P處，則機器人m沿PS運動即可；如果在附近沒有值為2的柵格，說明機器人m-1已經覆蓋了路徑PS并將其賦值為1，則m因為找不到路徑而停止運動。因為至少有一個機器人會因為GATE柵格處的路徑被其它機器人覆蓋而停止運動，因此MISC算法可以完成所有區域的完全覆蓋。 4算法分析（Algorithmanalysis） 在算法分析部分主要討論MISC算法的覆蓋完全性和系統穩定性。 4．1覆蓋完全性分析 對于常見的矩形環境，MISC算法可以逐層向內螺旋完成完全覆蓋。當環境內部無障礙物時，機器人m一直沿著m+1規劃的路徑無重復地運動，同時為m～1規劃下一圈的運動路徑，直到出現T形路徑或隨著覆蓋路徑向內螺旋出現GATE柵格。由3.2節可知，當出現T形路徑時，可以通過機器人m-1和機器人m對T形路徑的部分重復覆蓋退出T形路徑并繼續原來的覆蓋，并且機器人m-1為機器人m-2在線規劃的下一圈路徑不再受T形路徑的影響，而是一條直線。當在空間狹窄區域出現GATE柵格時，機器人m進入GATE柵格某側進行覆蓋，同時設置GATE柵格阻止其它機器人再進入GATE柵格該側，因此該狹窄區域及其被機器人m覆蓋的一側對于其它機器人可以看作無法訪問（也不需覆蓋）的障礙物，解決了狹窄區域打斷未覆蓋路徑連通性的問題。當機器人m完成GATE柵格一側和GATE柵格的完全覆蓋之后，如果可以找到路徑則繼續覆蓋，否則停止。如果環境內部存在未知障礙物，且機器人m+1在上一圈規劃路徑時沒有檢測到，則該障礙物位于機器人肌的運動路徑上，機器人m運動到該障礙物處時采用右側沿物體邊界運動的方式繞過該障礙物直到重新回到原路徑上，同時為機器人m-1規劃的路徑直接繞開該障礙物，不再受障礙物的影響。因此，如果不出現故障，則機器人只在GATE柵格處和環境完全覆蓋之后找不到路徑時停止運動。但由3.2節可知，至少有一個機器人不會因為GATE柵格停止運動。因此，MISC算法可以完成環境的完全覆蓋。 4．2系統穩定性分析 由于每個機器人在運動過程中都實時規劃下一圈覆蓋的路徑，將其左側柵格賦值為2，并且在覆蓋階段機器人都是沿著值為2的柵格路徑運動，因此機器人并不知道自己運動的路徑是哪個機器人規劃的，甚至不知道是多個機器人在協作覆蓋，這種好處是顯而易見的：在覆蓋過程中如果某個機器人突然出現故障而停止運動，對其它的機器人無任何影響。假設機器人肌在覆蓋中停止運動，那么當機器人m-1追上機器人m時，只需將機器人m當作障礙物，右側沿其繞行并繼續執行機器人肌原來執行的運動路徑即可，機器人m對剩下的覆蓋任務不再有任何影響。同理，在覆蓋過程中增加或減少一個機器人也不會對其它機器人造成影響。因此，只要不是所有的機器人都出現故障，MISC算法即可完成環境的完全覆蓋，提高了系統穩定性。 5多機器人協作覆蓋仿真試驗（Simulationtestofmulti-robotcooperativecoverage） 本文在仿真實驗平臺上仿真了室內環境的多機器人覆蓋任務。本試驗用基于顏色識別的方法模擬接觸傳感器，即只有當機器人與障礙物接觸上（有像素重疊）時才能檢測到障礙物。本文環境為900×700的矩形房間，分成3個小房間，房間的入口處比兩側狹窄。環境內部隨機分布少量障礙物，用3個20×20的圓形機器人覆蓋。由3.2節可知，兩個機器人相距越遠，前邊的機器人因GATE柵格提前停止運動的可能性越小，因此盡可能將3個機器人均勻分布在環境邊界上，本文中將機器人分布在3個墻角處同時開始邊界探索。如圖4（a）所示，當2號機器人到達3號機器人的初始位置時轉為在線覆蓋階段。圖中灰色柵格代表障礙物所在柵格，橫線柵格代表已覆蓋區域，斜線柵格代表規劃的路徑。在圖4（b）中，2號機器人進入左上角房問并設立GATE柵格，用豎線柵格表示，先完成左上角房間的完全覆蓋，1號和3號機器人將不再進入該房間。在圖4（C）中，2號機器人覆蓋完左上角的房間和GATE柵格之后，1號機器人已經將第一個GATE柵格附近覆蓋，因此2號機器人找不到規劃的路徑，停止運動，并且隨著覆蓋的進行，3號機器人先檢測到房間內部的三角形障礙物，沿著障礙物邊界繞行。圖4（d）是完全覆蓋之后各個機器人的運動軌跡。黑色實線代表l號機器人的運動軌跡，黑色虛線代表2號，灰色實線代表3號機器人。環境中共有1117個可覆蓋柵格并被全部覆蓋到，其中1號機器人用493步完成了454個柵格的覆蓋，2號機器人用230步完成了223個柵格的覆蓋，3號機器人用456步完成了440個柵格的覆蓋，整個系統的覆蓋重復率為5.55%。 6結論（Conclusion） 本文提出了多簡單機器人協作覆蓋算法——MISC算法，該算法通過對環境部分區域的重復覆蓋和設置GATE柵格保證了環境的完全覆蓋。由于每個機器人在線規劃時只利用共享地圖而不考慮其它機器人的影響，因此提高了系統穩定性，保證只要有一個機器人不出現故障就能完成環境的完全覆蓋。該算法實現簡單，適用于配置不高的簡單機器人。 參考文獻 （References） [1]Butler Z，Rizzi A，Hollis R．Contact sensor-based coverage of recti-linear environments[A]．Proceedings of the 1999 IEEE Interna- tional Symposium on Intelligent Control／Intelligent Systems and Se- mioties[C]．Piseataway，NJ，USA：IEEE，1999 266—271． [2]Hazon N，Kaminka G．Redundancy，efficiency and robustness in multi robot coverage[A]．Proceedings of the IEEE International Conference on Robotics and Automation[C]．Piseataway，Nj， USA：IEEE，2005．1199—1205． [3]Rekleitis I，Lee-Shue V，Peng A，a1．Limited communication，multi-robot team based coverage[A]．Proceedings of‘the IEEE International Conference on Robotics and Automation[C]．Pisca-taway，NJ，USA：IEEE，2004．3462—3468． [4]Wagner I，Lindenbaum M，Bruckstein A．Distributed covering by ant-robots using evaporating traces[J]．IEEE Transactions on Ro-boties and Automation，1999，15（5）：918—933． [5]Rekleitis I，Dudek G，Milios E．Multi-robot exploration of an un-known environment，efficiently～dueing the odometry eu‘or[A]．Proceedings of the 1 5th International Joint Cotfference in Artificial Intelligence[C]．San Francisco，USA：Morgan Kaufmann Publish-ers Inc．，1997．1340-1346． 作者簡介： 郝宗波 （1977-），男，博士生．研究領域：服務機器人，智能機器人． 洪炳椿 （1937．），男，博士，教授 。博士生導師．研究領域：服務機器人，機器人足球，虛擬現實．