基于實(shí)時(shí)柵格法的多機(jī)器人協(xié)作建圖

王曙光，唐浩漾

(西安郵電大學(xué)自動(dòng)化學(xué)院，陜西西安710121)

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

1 實(shí)時(shí)柵格法基本原理

1.1 原理

傳統(tǒng)的柵格法，最初用于單個(gè)機(jī)器人建圖，后來推廣到多機(jī)器人協(xié)作，也只是各自劃分一個(gè)小區(qū)域，獨(dú)立探索，最后把局部地圖融合成全局地圖。而實(shí)時(shí)柵格法，柵格的劃分是由機(jī)器人編隊(duì)直接完成的，柵格也不再局限于正方形。

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

圖1 實(shí)時(shí)柵格法示意圖

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

1.2 檢測(cè)步距的確定

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

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

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

1.3 計(jì)算

可以認(rèn)為機(jī)器人對(duì)視的視線把檢測(cè)區(qū)域分割成了一種特殊的柵格地圖，參照柵格地圖的處理方法，用一個(gè)2m×2m 的矩陣H 來表示，m 為步數(shù)。有障礙的柵格用1 表示，無障礙的柵格用0 表示。

每次檢測(cè)，由于編隊(duì)位置的變化，需要作坐標(biāo)平移變換。設(shè)初始檢測(cè)區(qū)域的矩陣為。多步平移后的檢測(cè)，在始檢測(cè)區(qū)域內(nèi)的矩陣為Hx1，Hx2，……Hxm，及Hy1，Hy2，……Hym。

^表示矩陣對(duì)應(yīng)元素相與。

2 編隊(duì)控制

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

機(jī)器人之間，采用定向紅外器件進(jìn)行障礙檢測(cè)，同時(shí)測(cè)量機(jī)器人間的距離。由此，可檢測(cè)機(jī)器人編隊(duì)間的障礙遮擋情況，判斷障礙物位置。機(jī)器人間使用無線傳感器網(wǎng)絡(luò)作為通信方式［6］。

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

圖2 機(jī)器人A 的工作流程

圖3 其他機(jī)器人的工作流程

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

文獻(xiàn)［8］指出:當(dāng)運(yùn)動(dòng)速度不高，一個(gè)采樣周期內(nèi)，機(jī)器人編隊(duì)可以穩(wěn)定保持。

當(dāng)環(huán)境探索結(jié)束時(shí)，可以測(cè)量機(jī)器人的相對(duì)位置，看是否出現(xiàn)較大偏差。如果有，進(jìn)行一定的反演補(bǔ)償。

3 硬件結(jié)構(gòu)

在此編隊(duì)中，4 個(gè)機(jī)器人的結(jié)構(gòu)和功能是相似的。A 起領(lǐng)導(dǎo)作用，功能稍強(qiáng)。圖4 是機(jī)器人A 的結(jié)構(gòu)，主要包括處理器、電池及電機(jī)驅(qū)動(dòng)模塊、光電編碼器、定向紅外發(fā)射電路、短距離無線通信模塊、外側(cè)障礙檢測(cè)模塊等部分。

圖4 機(jī)器人A 的結(jié)構(gòu)框圖

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

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

4 實(shí)驗(yàn)驗(yàn)證

在博創(chuàng)InnoSTAR 機(jī)器人平臺(tái)上，安裝傳感器及通信模塊，進(jìn)行了驗(yàn)證。實(shí)驗(yàn)中，取機(jī)器人正方形編隊(duì)的邊距為1.6 m，檢測(cè)步距為0.4 m，障礙物為一直徑約0.3 m的圓柱形物體。實(shí)驗(yàn)結(jié)果如圖5所示，圓形陰影部分所占據(jù)的柵格為理想檢測(cè)狀態(tài)，即用圓點(diǎn)表示的柵格。實(shí)驗(yàn)表明，編隊(duì)在運(yùn)動(dòng)10 個(gè)步距后，對(duì)圖中所示位置的檢測(cè)，出現(xiàn)誤差的概率小于2%。運(yùn)動(dòng)15 個(gè)步距后，出現(xiàn)誤差的概率顯著增大，在“－”或“+”標(biāo)注的柵格檢測(cè)到障礙的概率達(dá)到30%以上。

實(shí)驗(yàn)表明:在誤差允許的范圍內(nèi)，此方法能夠保持機(jī)器人編隊(duì)基本穩(wěn)定，能夠按照實(shí)時(shí)柵格法對(duì)有障礙的區(qū)域進(jìn)行探索建圖。

對(duì)于檢測(cè)誤差，根本原因還是機(jī)器人行進(jìn)距離累積誤差造成的。減小這個(gè)誤差，能夠提高建圖的準(zhǔn)確性，增大有效探測(cè)范圍。

圖5 實(shí)驗(yàn)檢測(cè)結(jié)果

5 結(jié)論

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

【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】于金霞，王璐，蔡自興.未知環(huán)境中移動(dòng)機(jī)器人自定位技術(shù)［M］.北京:電子工業(yè)出版社，2011:7，56.

【4】蔡自興.多移動(dòng)機(jī)器人協(xié)調(diào)原理與技術(shù)［M］.北京:國防工業(yè)出版社，2011:126，137.

【5】楊甜甜，劉志遠(yuǎn)，陳虹.移動(dòng)機(jī)器人編隊(duì)控制的現(xiàn)狀與問題［J］.智能系統(tǒng)學(xué)報(bào)，2007(2):21－27.

【6】馮國棟，劉敏，王國利.實(shí)現(xiàn)機(jī)器人隨動(dòng)的紅外感知方法［J］.機(jī)器人，2012，34(1):104－109.

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

【8】吳俊，陸宇平.基于網(wǎng)絡(luò)通信的多機(jī)器人系統(tǒng)的穩(wěn)定性分析［J］.自動(dòng)化學(xué)報(bào)，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.