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

(1.武漢工程大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，湖北 武漢 430074； 2.智能機(jī)器人湖北省重點(diǎn)實(shí)驗(yàn)室，湖北 武漢 430074)

0 引 言

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

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

1 ROBOCUP中的機(jī)器人定位

1.1 單個(gè)機(jī)器人的定位方法

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

圖1 全局坐標(biāo)下機(jī)器人自定位及目標(biāo)點(diǎn)定位Fig.1 The robot self-positioning and target positioning under global coordinate system

這樣可以得到機(jī)器人的全局坐標(biāo)為

(1)

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

(2)

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

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

2 DBSCAN算法及其改進(jìn)

2.1 DBSCAN算法原理

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

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

2.2 DBSCAN算法改進(jìn)

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

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

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

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

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

(3)

當(dāng)dij≥EPS時(shí)，P[i]=P[i]+1.

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

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

(4)

3 改進(jìn)算法在ROBOCUP中的實(shí)際應(yīng)用

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

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

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

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

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

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

圖3 機(jī)器人和球在全局坐標(biāo)系場(chǎng)地中的分布圖Fig.3 The distribution map of the robot and the ball in global coordinate field

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

在這里引入機(jī)器人與目標(biāo)點(diǎn)的距離閾值就顯得尤為重要，因?yàn)橛^測(cè)距離遠(yuǎn)對(duì)觀測(cè)的準(zhǔn)確度有很大的影響，為了不會(huì)錯(cuò)誤的將某些點(diǎn)作為噪聲剔除，用距離作為一個(gè)閾值控制核心點(diǎn)是一個(gè)能夠提高融合精度的方法，如圖5所示，得到融合坐標(biāo)為(55,-11).

圖4 EPS變化時(shí)運(yùn)用DBSCAN算法得到 的小球融合坐標(biāo)對(duì)比Fig.4 The comparison chart of ball fusion coordinate based on DBSCAN algorithm when EPS changes

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

圖5利用機(jī)器人得到的各自距小球距離，設(shè)定一個(gè)Dlimit=2作為距離閾值來(lái)重新判斷噪聲點(diǎn).圖5(a)EPS設(shè)定為6，圖5(b)為8，不難看出領(lǐng)域值對(duì)其融合的影響不大，這樣使得融合準(zhǔn)確度大大提高.

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

4 結(jié) 語(yǔ)

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

致謝

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

參考文獻(xiàn)：

[1] 賈建強(qiáng),陳衛(wèi)東,席裕庚.全自主足球機(jī)器人系統(tǒng)關(guān)鍵技術(shù)綜述[J].上海交通大學(xué)學(xué)報(bào).2003,37(z1):45-49.

[2] 門琳娜. 基于全向視覺(jué)的足球機(jī)器人定位的研究[D]. 長(zhǎng)沙：長(zhǎng)沙理工大學(xué), 2010.

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

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

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

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

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

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

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

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

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