張彥鐸，李哲靖，魯統(tǒng)偉

(1.武漢工程大學計算機科學與工程學院，湖北 武漢 430074； 2.智能機器人湖北省重點實驗室，湖北 武漢 430074)

0 引 言

機器人世界杯足球錦標賽(ROBOCUP)中型組全自主機器人系統(tǒng)是由機器人子系統(tǒng)、視覺子系統(tǒng)、決策子系統(tǒng)以及通訊子系統(tǒng)組成.其中視覺子系統(tǒng)由工業(yè)攝像機、全向反射鏡和圖像處理軟件構(gòu)成[1-2]，是此平臺獲取外部環(huán)境信息的核心.機器人也必須對環(huán)境進行地圖構(gòu)建[3-4]，才能完成自主的移動過程，并通過各種路徑規(guī)劃的方法安全高效的達到目標點[5].文章中所用的是基于ROBOCUP中型組足球機器人的平臺，其能夠自主完成目標識別以及比賽的決策規(guī)劃.

在多機器人系統(tǒng)中，多源信息的獲取以及融合處理十分重要，它是以多個傳感器信息融合為基礎，通過機器人與機器人或者機器人與系統(tǒng)之間的聯(lián)系，把分布在不同機器人上的多個同構(gòu)或異構(gòu)的傳感器提供的局部不完整、不確定的信息加以融合，讓此系統(tǒng)中的機器人個體對目標環(huán)境形成相對完整的認知[6].國內(nèi)外有一些對機器人聚類信息融合的研究，其通過對DBSCAN算法的運用達到融合多機器人觀測信息的目的，但是這種方法并沒有考慮到觀測信息的準確性，或者說在預處理階段可能忽略有效信息，導致誤差的出現(xiàn).本文借助全自主足球機器人系統(tǒng)為平臺，在研究單個機器人自定位的基礎上，利用多機器人在空間分布和多傳感器的優(yōu)勢，改進DBSCAN聚類算法對個體獲得的信息進行信息融合，有效的實現(xiàn)協(xié)同定位.

1 ROBOCUP中的機器人定位

1.1 單個機器人的定位方法

對于機器人來說，能夠進行定位也就意味著需要知道自身所處的環(huán)境信息，進而能夠定位自身的坐標和角度以及目標點的相對場地坐標.當機器人對圖像進行分割并形成有效的特征之后，就能得到場地中各種標識信息，如白色色塊的長度、寬度、面積，通過這些特征來識別出是屬于場地標識的哪種類別，如直線、拐角、T形、角弧等等[7-8].這些特征標記坐標在場地信息中都是已知的.如圖1所示，設定機器人的坐標為R(x,y)，觀察到的特征標識坐標分別為(x1,y1)、(x2,y2)，直接觀測數(shù)據(jù)為機器人與標識M1的距離D1和與機器人正方向成角度θ1，機器人與標識M2的距離D2和與機器人正方向成角度θ2.

圖1 全局坐標下機器人自定位及目標點定位Fig.1 The robot self-positioning and target positioning under global coordinate system

這樣可以得到機器人的全局坐標為

(1)

于是機器人就得到了自身在場地中的絕對坐標以及機器人正面朝向與世界坐標的夾角θ(0<θ≤2π).當機器人觀察到目標時，可以直接得到目標B在機器人坐標系中的坐標B(xr,yr).

(2)

1.2 多機器人協(xié)同定位及其改進的必要性

由于攝像頭的限制，機器人只能捕捉到距離自身中心一定半徑范圍的圖像信息，這也就意味著單機器人只能獲得局部的環(huán)境信息，并不能一次構(gòu)建全局的地圖信息.同時，單個機器人不能保證其獲取的信息的準確性，可能受到外部或內(nèi)部因素干擾而導致觀測誤差，而多機器人協(xié)同定位則能解決這些問題.由于單個機器人的局限性，為了能夠達到全局地圖的構(gòu)建，利用多個機器人對場地信息的獲取，并進行信息融合是一種提高定位精度的有效方法[9].關于信息融合有很多方法，有基于物理模型的，有基于參數(shù)分類的，還有基于認識識別模型的.其中的屬于基于參數(shù)分類方法的聚類分析算法是應用比較廣泛的一種[10].所謂聚類是將數(shù)據(jù)分類到不同的類或者簇中的一個過程，同一個簇中的對象有很大的相似性，而不同的簇間對象有很大的相異性.國內(nèi)外已經(jīng)有一些對多機器人協(xié)同定位的研究，利用基于密度的聚類方法來融合多機器人觀測信息.但是當應用在實際機器人平臺上的時候并沒有考慮其原始信息的準確性或可信度，于是在融合的預處理上就可能出現(xiàn)忽略有效信息或者融合錯誤信息的問題，導致融合信息精度的下降.所以平臺要在獲得觀測信息后，第一時間對觀測數(shù)據(jù)進行一次篩選，保留可信度高的數(shù)據(jù)，篩除噪聲.這里的引入機器人距離閾值的方法來改進基于密度的聚類分析算法(DBSCAN算法).

2 DBSCAN算法及其改進

2.1 DBSCAN算法原理

DBSCAN算法是一種基于密度的聚類方法.它的思想是：只要相鄰區(qū)域的密度(目標對象的數(shù)目)超過某個閾值，就繼續(xù)聚類，除此之外的則作為“噪聲”.這種聚類方法將密度足夠高的區(qū)域劃分為簇，使其能夠在帶有“噪聲”的空間內(nèi)發(fā)現(xiàn)任意形狀的類[11].

DBSCAN算法使用半徑閾值ε和MinPts來控制簇的生成.其中，給定對象半徑內(nèi)的區(qū)域為該對象的ε-領域，MinPts為該對象ε-領域中包含對象的最小數(shù)目.在實際的應用中根據(jù)需要融合的數(shù)據(jù)情況設定閾值ε.設定集合D中A1其領域下包含對象數(shù)目為N1，當ε-內(nèi)N1≤MinPts時，則將對象A1納入核心點集合C；當N1>MinPts時，將對象A1視為“噪聲”，不加入核心點集合C.以此對集合D中的所有元素進行判斷，得到完整的核心點集合C，即需要融合的數(shù)據(jù).

2.2 DBSCAN算法改進

由于全自主機器人定位是依靠全向視覺系統(tǒng)，所以其攝像頭的誤差以及定位計算的誤差是一直存在的.而提高機器人的定位精度也成了每個自主機器人系統(tǒng)需要去完善的.經(jīng)過多次實驗總結(jié)，發(fā)現(xiàn)由于反射鏡系統(tǒng)的誤差，機器人距離目標點越遠，定位的精確度也越差.不能改變設備的誤差，就只能在數(shù)據(jù)上進行處理，系統(tǒng)應該也將這些可信度不高的定位信息作為噪聲，不進行融合.

因此在算法中需要加入對機器人距離的信息的處理，及在獲取到目標點觀測坐標的同時，也需要獲得此觀測點到機器人自身的觀測距離值dist_R.設定距離閾值Dlimit，接上節(jié)算法，當N1>MinPts時，若dist_R≤Dlimit，則將目標點加入集合C；若dist_R>Dlimit，則不將其加入集合C.通過對距離閾值的比較來對觀測數(shù)據(jù)進行一次取舍處理，這樣一些誤判的噪聲點得以保留，進而增加了融合數(shù)據(jù)的基數(shù)，使精確度提高.

在全自主機器人平臺上得到的最直接的就是各個目標點相對于機器人坐標系的坐標，而通過1.1節(jié)中的轉(zhuǎn)換，能夠得到的是目標點相對于全局的坐標.在經(jīng)過大量的實驗之后，基本可以得出各機器人所觀測到同一個目標點的結(jié)果是呈現(xiàn)正態(tài)分布的，觀測點離實際位置越近的其分布密度越高.下面是算法流程：

(1)初始化參數(shù)，設定領域半徑EPS和領域內(nèi)最小對象數(shù)目MinPs.第i個觀測值的領域點個數(shù)為P[i]=0 (i∈[1,n])，其核心點數(shù)設為k=0，核心點的集合為D，觀測機器人數(shù)目為N.

(2)得到各個機器人觀測同一點目標A的值A1、A2……An(n≤N)，并計算出兩兩點之間的歐氏距離，設dij(i,j∈[1,N]，且i≠j)為點Ai到點Aj的距離，則有以下公式：

(3)

當dij≥EPS時，P[i]=P[i]+1.

(3)i從1到N循環(huán)判斷P[i]數(shù)值，若P[i]≥MinPs，則將Ai定義為核心點并添加到核心點集合D中，并令k=k+1，同時跳至第5步；若P[i]

(4)設定距離閾值為Dlimit，dist_R[i] (i∈[1,n])為機器人在獲取A坐標時測量到自身距A點的距離，若dist_R[i]≤Dlimit，則將Ai定義為核心點并添加到核心點集合D中，同時跳至第5步；若dist_R[i]>Dlimit，則將Ai視為噪聲點忽略，同時跳至第5步.

(4)

3 改進算法在ROBOCUP中的實際應用

以現(xiàn)有平臺為例，假設我方的5臺機器人對A目標點全部識別出其位置坐標，如圖2所示.分別為：A1(x1,y1)，A2(x2,y2)，A3(x3,y3)，A4(x4,y4)，A5(x5,y5)，機器人距離觀測點只有對A5的距離大于Dlimit.

圖2 在機器人平臺下基于DBSCAN算法 數(shù)據(jù)融合示意圖Fig.2 The schematic diagram of DBSCAN algorithm- based data integration on the robot platform

機器人將各自對A目標定位的信息上傳到場外的教練機，在那里進行數(shù)據(jù)融合.首先是要對每個點兩兩之間的距離進行運算，之后以每個坐標點為圓心，設定的EPS值為半徑做圓，這里EPS的設定與觀測數(shù)據(jù)相關，在ROBOCUP平臺下至少設定機器人直徑的2倍為閾值半徑，因為至少需要滿足兩機器人靠在一起的情況下能夠被分別定位到.比較每個圓當中的坐標數(shù)據(jù)點是否滿足MinPs，同時也對每個機器人到觀測點的距離與距離閾值Dlimit進行比較，大于Dlimit的且不滿足MinPs的則視為噪聲點剔除，剩下的坐標數(shù)值取平均值作為融合結(jié)果.對于本例中A1，A5并沒有滿足MinPs條件(設定MinPs=1)，但是A1觀測距離小于Dlimit所以只將A5點作為噪聲觀測點處理.故由A1、A2、A3、A4得出A點的融合結(jié)果為

具體實驗是在ROBOCUP中型組的標準平臺上進行，場地和場上隊員按照規(guī)定，我方機器人5臺，對方機器人5臺，場地上有橘紅色足球和場地線.每個機器人依靠自身的視覺系統(tǒng)得到自身周圍一定范圍的位置信息.通過1.3節(jié)中所闡述的機器人自定位方法和定位目標點方法，我方機器人能夠各自得到所觀察到的目標機器人或者小球以及自身位置坐標.如表1所示.

由表1得到機器人以及球在場地分布圖，如圖3所示.經(jīng)過實際測量，球在實際場地中的坐標(圖4中叉點)為(51,-15).在這里可以明顯的看出每個機器人對球坐標的獲取都帶有一定的誤差，這跟其具體位置和方向有關.下面給出通過DBSCAN聚類算法得到的經(jīng)過融合后的球坐標點.

表1 機器人自定位以及定位球的坐標數(shù)據(jù)Table 1 robot self-positioning and ball-positioning coordinate data

圖3 機器人和球在全局坐標系場地中的分布圖Fig.3 The distribution map of the robot and the ball in global coordinate field

在這一個試驗中，EPS領域值首先設置為6，MinPs設置為1，從圖4(a)中可見由于EPS大小的問題，只有2點成為核心點，于是坐標融合成(62,-5)，跟實際點(51,-15)有一定差別.當將EPS領域擴大為8時，如圖4(b)所示，可以發(fā)現(xiàn)融合相比前一次有很大的改善，融合坐標為(56,-12)，與實際坐標十分相近.通過對比可以發(fā)現(xiàn)傳統(tǒng)的DBSCAN聚類算法對EPS的選擇對融合結(jié)果影響很大，會影響其核心點的選擇，直至最后歸一時坐標的誤差很大.

在這里引入機器人與目標點的距離閾值就顯得尤為重要，因為觀測距離遠對觀測的準確度有很大的影響，為了不會錯誤的將某些點作為噪聲剔除，用距離作為一個閾值控制核心點是一個能夠提高融合精度的方法，如圖5所示，得到融合坐標為(55,-11).

圖4 EPS變化時運用DBSCAN算法得到 的小球融合坐標對比Fig.4 The comparison chart of ball fusion coordinate based on DBSCAN algorithm when EPS changes

圖5 EPS變化下DBSCAN聚類方法改 進后的小球融合坐標對比Fig.5 The comparison chart of ball fusion coordinate based on improved DBSCAN algorithm when EPS changes

圖5利用機器人得到的各自距小球距離，設定一個Dlimit=2作為距離閾值來重新判斷噪聲點.圖5(a)EPS設定為6，圖5(b)為8，不難看出領域值對其融合的影響不大，這樣使得融合準確度大大提高.

由于機器人觀測范圍限制，機器人可能不會觀測到場地中所有的目標，如圖3所示.方形表示我方機器人，三角形表示對方機器人.機器人R2對敵方機器人的觀測范圍為虛線所示，可知其只能觀測到敵方OR2和OR3號；同樣機器人R4能夠觀測到OR1、OR4和OR5號機器人，也不能觀測全部，這樣協(xié)同定位在構(gòu)建全局環(huán)境地圖的作用就得到了體現(xiàn)，R2，R3能夠協(xié)同定位到OR2，R4、R5、R3能夠協(xié)同定位到OR1、OR4和OR5，通過外部教練機系統(tǒng)進行融合就得到了完整的對方機器人位置信息及全局地圖信息，達到協(xié)同定位信息共享的功能.

4 結(jié) 語

通過對ROBOCUP全自主足球機器人平臺多機器人協(xié)同定位的研究以及對基于密度的聚類分析算法在信息融合方面的改進與應用，提高了全自主機器人平臺獲得融合信息的有效性以及協(xié)同定位的準確性和穩(wěn)定性，為多機器人通過局部信息獲取而構(gòu)建全局環(huán)境信息而提供了條件.實踐表明，通過引入機器人距離閾值而改進的DBSCAN信息融合算法讓機器人協(xié)同定位的精度、穩(wěn)定性有了顯著的提高.

致謝

論文在資料收集和實驗數(shù)據(jù)采集過程中，得到了閔鋒博士大力支持，在此謹向他表示衷心的感謝.

參考文獻：

[1] 賈建強,陳衛(wèi)東,席裕庚.全自主足球機器人系統(tǒng)關鍵技術綜述[J].上海交通大學學報.2003,37(z1):45-49.

[2] 門琳娜. 基于全向視覺的足球機器人定位的研究[D]. 長沙：長沙理工大學, 2010.

[3] 陳念, 李進, 王海暉. 雙目立體視覺測量系統(tǒng)的研究與實現(xiàn)[J]. 武漢工程大學學報,2011,33(5):101-104.

[4] 王衛(wèi)華, 陳衛(wèi)東, 席裕庚. 基于不確定信息的移動機器人地圖創(chuàng)建研究進展[J]. 機器人. 2001，23(6):563-568.

[5] 孔偉, 張彥鐸. 基于遺傳算法的自主機器人避障方法研究[J]. 武漢工程大學學報. 2008,30(3):110-113.

[6] 嚴勇杰. 多機器人系統(tǒng)協(xié)調(diào)與控制[D].哈爾濱：哈爾濱工程大學.2007.

[7] 毛慧珍,陳西平,浮紅霞,等.中型組足球機器人全向視覺定位技術[J]. 信息技術,2009(1):5-9.

[8] 初苗苗, 尹義龍. 面向RoboCup中型組比賽線元素檢測和分類[C]//中國人工智能學會第12屆全國學術年會論文匯編.中國人工智能學會.北京：北京郵電大學出版社，2007:413-417.

[9] 王遠, 徐華, 賈培發(fā). 多機器人系統(tǒng)中的信息融合技術綜述[J]. 微電子學與計算機, 2007,24(12):150-156.

[10] 石陸魁, 何丕廉. 一種基于密度的高效聚類算法[J].計算機應用,2005,25(8):1824-1826.

[11] 李杰, 賈瑞玉, 張璐璐. 一個改進的基于DBSCAN的空間聚類算法研究[J]. 計算機技術與發(fā)展, 2007,17(1):114-116.