基于實時柵格法的多機器人協作建圖

王曙光，唐浩漾

(西安郵電大學自動化學院，陜西西安710121)

用于協作定位、環境探索、地圖構建的分布式多智能體系統成為研究的熱點［1－2］。多機器人同步定位與地圖構建(SLAM)要解決控制結構、協作模式、局部子地圖融為全局地圖的融合算法等問題。柵格地圖是一種比較成功的地圖標示方法，它簡單、易擴展。二維柵格地圖是把環境分割成若干正方形小區域，即柵格［3］，被障礙物占據的柵格賦值為1，無障礙物的柵格賦值為0。但柵格地圖需要較大的存儲空間，定位時計算量也很大。目前機器人對環境的探測，往往用激光雷達、GPS 定位儀等昂貴的傳感器。文中提出一種實時柵格建圖方法，依靠多機器人編隊，進行定位建圖，使用簡單的傳感器即可實時生成地圖，不需要局部地圖融合的過程，減少了計算量和存儲空間［4］。

1 實時柵格法基本原理

1.1 原理

傳統的柵格法，最初用于單個機器人建圖，后來推廣到多機器人協作，也只是各自劃分一個小區域，獨立探索，最后把局部地圖融合成全局地圖。而實時柵格法，柵格的劃分是由機器人編隊直接完成的，柵格也不再局限于正方形。

在機器人編隊區域內，如果有障礙物的話，會遮擋機器人之間的“視線”，可以認為，被擋住的視線兩側的區域內存在障礙物，而未被遮擋的視線所圍成的區域無障礙。如果機器人自身的位置已知，根據遮擋視線的情況，可以按照柵格法的原理確定障礙物的位置。假設有A、B、C、D 4 個機器人，排成正方形，如圖1所示。X部分為障礙物。

圖1 實時柵格法示意圖

在圖1所示情況下，機器人之間的視線“B－C”和“A－B”被遮擋，則AOB 和BOD 這兩個三角形區域內，存在部分障礙。由視線“A－C”、“B－D”和“C－D”圍成的區域無障礙。顯然，圖1 的探測結果誤差太大。如果能把檢測區域分割得較小，就能使檢測誤差變小。假定機器人在運動過程中，能一直保持正方形編隊進行障礙探索。機器人編隊在行進過程中，連續快速探測障礙，理論上應該能得出障礙物的基本形狀。但連續檢測，需要處理的數據多，通信協調也需要不斷進行，效率很低，需要進行簡化。

1.2 檢測步距的確定

機器人編隊每行進一段距離，進行一次“對視”檢測，這個距離稱為檢測步距。對圖1 的機器人編隊，如果取檢測步距為正方形邊長的一半，將得到圖中所示的檢測效果。

若以C 為坐標原點，圖1 中關于障礙的檢測可以看成是3 次檢測的合成:機器人C 在原點，初始位置的檢測;編隊沿x 軸平移1 個步距，C 到C1處，進行一次檢測;編隊沿y 平移，C 到C2處，進行一次檢測。綜合3 次的檢測結果，圖1 中，右上角的小正方形部分，表示有障礙的區域。與編隊初始的一次檢測結果比較，障礙物區域縮小了1 倍。如果要更加精確地描述障礙物區域，則需進一步減小步距。如果大正方形邊長分成m 步，推算可知，對某一區域，最終結果是(2m－1)次檢測的疊加，即(2m－1)個陰影的重疊部分。

由圖可見:理論上，障礙物尺寸的最大誤差是步距的一半，由實際誤差要求，反推可得步距的大小。

1.3 計算

可以認為機器人對視的視線把檢測區域分割成了一種特殊的柵格地圖，參照柵格地圖的處理方法，用一個2m×2m 的矩陣H 來表示，m 為步數。有障礙的柵格用1 表示，無障礙的柵格用0 表示。

每次檢測，由于編隊位置的變化，需要作坐標平移變換。設初始檢測區域的矩陣為。多步平移后的檢測，在始檢測區域內的矩陣為Hx1，Hx2，……Hxm，及Hy1，Hy2，……Hym。

^表示矩陣對應元素相與。

2 編隊控制

實時柵格法檢測障礙，具有計算簡單的特點，不需要進行局部地圖的拼接。但是前提是機器人的編隊必須保持相對位置不變。實際上，機器人運行中，隊形肯定會有偏差;地面有起伏等環境因素也影響隊形。隊列的偏差，會造成柵格位置的誤差，影響檢測結果。所以，編隊控制是實時柵格法的關鍵技術［5］。

機器人之間，采用定向紅外器件進行障礙檢測，同時測量機器人間的距離。由此，可檢測機器人編隊間的障礙遮擋情況，判斷障礙物位置。機器人間使用無線傳感器網絡作為通信方式［6］。

在編隊中，指定A 為主機器人，作為基準參考，B、C、D 跟隨A 運動，并依次進行隊形位置校正。A安裝3 套紅外收發器，分別指向B、C、D。機器人B向C、D 定向發射;C 向D 定向發射，D 只安裝紅外接收電路。紅外接收器做成一個接收陣列，接收定向發來的信息。當機器人位置偏移時，接收陣列會檢測到偏移的方向，據此來調整機器人的位置，保持隊形。每個機器人的位置都由另外兩個機器人的光束定位。當出現偏移時，按順序依次校正，防止循環出現誤差。為防止隊形出現向心或離心的縮放，機器人A同時利用紅外傳感器測距，保持機器人的相對距離也不發生變化。機器人A 的運動方向靠電子羅盤來檢測并保持。假定編隊以機器人AB 為前方，程序處理流程如圖2 和圖3所示。

圖2 機器人A 的工作流程

圖3 其他機器人的工作流程

還有一種情況，就是機器人的行進路徑上存在障礙物，它必須繞行，這會破壞編隊的隊形。采用基于觀察者的多機器人編隊控制方法，結合領導－跟隨法和VHF+避障法，能夠有效地繞過障礙。指定被阻擋的機器人作為觀察者，利用VFH + 避障法繞過障礙;領導者根據觀察者的運動軌跡和傳感器信息，并根據隊形的可通過性控制跟隨者繞過障礙［7］。通過障礙后，編隊要初始化，重新組織隊形。

文獻［8］指出:當運動速度不高，一個采樣周期內，機器人編隊可以穩定保持。

當環境探索結束時，可以測量機器人的相對位置，看是否出現較大偏差。如果有，進行一定的反演補償。

3 硬件結構

在此編隊中，4 個機器人的結構和功能是相似的。A 起領導作用，功能稍強。圖4 是機器人A 的結構，主要包括處理器、電池及電機驅動模塊、光電編碼器、定向紅外發射電路、短距離無線通信模塊、外側障礙檢測模塊等部分。

圖4 機器人A 的結構框圖

處理器采用ARM7;定向紅外發射器有3 組，分別指向B、C 和D;紅外避碰檢測傳感器安裝在編隊外側，用來判斷機器人是否遇到障礙或到達環境邊界;光電編碼器用來計算編隊行進距離。

機器人B、C 和D 不安裝電子羅盤和光電編碼器。機器人A 依靠角度和里程計算確定編隊的位置［9］，進而劃分柵格的位置。

4 實驗驗證

在博創InnoSTAR 機器人平臺上，安裝傳感器及通信模塊，進行了驗證。實驗中，取機器人正方形編隊的邊距為1.6 m，檢測步距為0.4 m，障礙物為一直徑約0.3 m的圓柱形物體。實驗結果如圖5所示，圓形陰影部分所占據的柵格為理想檢測狀態，即用圓點表示的柵格。實驗表明，編隊在運動10 個步距后，對圖中所示位置的檢測，出現誤差的概率小于2%。運動15 個步距后，出現誤差的概率顯著增大，在“－”或“+”標注的柵格檢測到障礙的概率達到30%以上。

實驗表明:在誤差允許的范圍內，此方法能夠保持機器人編隊基本穩定，能夠按照實時柵格法對有障礙的區域進行探索建圖。

對于檢測誤差，根本原因還是機器人行進距離累積誤差造成的。減小這個誤差，能夠提高建圖的準確性，增大有效探測范圍。

圖5 實驗檢測結果

5 結論

實時柵格法是綜合了機器人編隊控制的柵格建圖法，方法簡單，不需要精密昂貴的探測儀器和設備，能夠在低成本的小型機器人上實現，缺點是探測速度較慢。由于編隊的特點，實時柵格法最適合檢測孤立的“島型”障礙物，不適合檢測尺寸龐大的障礙物或迷宮走廊式環境。對編隊控制還可以進一步研究，使其環境適應性更好，能及時調整機器人的位置，減小誤差。

【1】SIM R，ROY N.Global A-Optimal Robot Exploration in SLAM［C］// Proceedings of the 2005 IEEE International Conference on Robotics and Automation，2005:661－666.

【2】AMIGONI F，CAGLIOTI V.An Information-based Exploration Strategy for Environment Mapping with Mobile Robots［J］.Robotics and Autonomous Systems，2010，58(5):684－699.

【3】于金霞，王璐，蔡自興.未知環境中移動機器人自定位技術［M］.北京:電子工業出版社，2011:7，56.

【4】蔡自興.多移動機器人協調原理與技術［M］.北京:國防工業出版社，2011:126，137.

【5】楊甜甜，劉志遠，陳虹.移動機器人編隊控制的現狀與問題［J］.智能系統學報，2007(2):21－27.

【6】馮國棟，劉敏，王國利.實現機器人隨動的紅外感知方法［J］.機器人，2012，34(1):104－109.

【7】雷斌，曾良才.未知環境中基于觀察者的多機器人編隊控制方法［J］.武漢科技大學學報，2011，34(6):195－197.

【8】吳俊，陸宇平.基于網絡通信的多機器人系統的穩定性分析［J］.自動化學報，2010，36(12):1706－1710.

【9】ZHU Yanping，HUANG Daqing.Location Algorithm Using Distance and Angle Information in Wireless Sensor Networks［J］.Transactions of Nanjing University of Aeronautics ＆ Astronauti，2009，26(1):58－64.