机器人世界杯足球锦标赛中多机器人对目标协同定位算法的改进

2013-04-21张彦铎李哲靖鲁统伟

武汉工程大学学报 2013年2期

张彦铎，李哲靖，鲁统伟

(1.武汉工程大学计算机科学与工程学院，湖北武汉 430074； 2.智能机器人湖北省重点实验室，湖北武汉 430074)

0 引言

机器人世界杯足球锦标赛(ROBOCUP)中型组全自主机器人系统是由机器人子系统、视觉子系统、决策子系统以及通讯子系统组成.其中视觉子系统由工业摄像机、全向反射镜和图像处理软件构成[1-2]，是此平台获取外部环境信息的核心.机器人也必须对环境进行地图构建[3-4]，才能完成自主的移动过程，并通过各种路径规划的方法安全高效的达到目标点[5].文章中所用的是基于ROBOCUP中型组足球机器人的平台，其能够自主完成目标识别以及比赛的决策规划.

在多机器人系统中，多源信息的获取以及融合处理十分重要，它是以多个传感器信息融合为基础，通过机器人与机器人或者机器人与系统之间的联系，把分布在不同机器人上的多个同构或异构的传感器提供的局部不完整、不确定的信息加以融合，让此系统中的机器人个体对目标环境形成相对完整的认知[6].国内外有一些对机器人聚类信息融合的研究，其通过对DBSCAN算法的运用达到融合多机器人观测信息的目的，但是这种方法并没有考虑到观测信息的准确性，或者说在预处理阶段可能忽略有效信息，导致误差的出现.本文借助全自主足球机器人系统为平台，在研究单个机器人自定位的基础上，利用多机器人在空间分布和多传感器的优势，改进DBSCAN聚类算法对个体获得的信息进行信息融合，有效的实现协同定位.

1 ROBOCUP中的机器人定位

1.1 单个机器人的定位方法

对于机器人来说，能够进行定位也就意味着需要知道自身所处的环境信息，进而能够定位自身的坐标和角度以及目标点的相对场地坐标.当机器人对图像进行分割并形成有效的特征之后，就能得到场地中各种标识信息，如白色色块的长度、宽度、面积，通过这些特征来识别出是属于场地标识的哪种类别，如直线、拐角、T形、角弧等等[7-8].这些特征标记坐标在场地信息中都是已知的.如图1所示，设定机器人的坐标为R(x,y)，观察到的特征标识坐标分别为(x1,y1)、(x2,y2)，直接观测数据为机器人与标识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 多机器人协同定位及其改进的必要性

由于摄像头的限制，机器人只能捕捉到距离自身中心一定半径范围的图像信息，这也就意味着单机器人只能获得局部的环境信息，并不能一次构建全局的地图信息.同时，单个机器人不能保证其获取的信息的准确性，可能受到外部或内部因素干扰而导致观测误差，而多机器人协同定位则能解决这些问题.由于单个机器人的局限性，为了能够达到全局地图的构建，利用多个机器人对场地信息的获取，并进行信息融合是一种提高定位精度的有效方法[9].关于信息融合有很多方法，有基于物理模型的，有基于参数分类的，还有基于认识识别模型的.其中的属于基于参数分类方法的聚类分析算法是应用比较广泛的一种[10].所谓聚类是将数据分类到不同的类或者簇中的一个过程，同一个簇中的对象有很大的相似性，而不同的簇间对象有很大的相异性.国内外已经有一些对多机器人协同定位的研究，利用基于密度的聚类方法来融合多机器人观测信息.但是当应用在实际机器人平台上的时候并没有考虑其原始信息的准确性或可信度，于是在融合的预处理上就可能出现忽略有效信息或者融合错误信息的问题，导致融合信息精度的下降.所以平台要在获得观测信息后，第一时间对观测数据进行一次筛选，保留可信度高的数据，筛除噪声.这里的引入机器人距离阈值的方法来改进基于密度的聚类分析算法(DBSCAN算法).

2 DBSCAN算法及其改进

2.1 DBSCAN算法原理

DBSCAN算法是一种基于密度的聚类方法.它的思想是：只要相邻区域的密度(目标对象的数目)超过某个阈值，就继续聚类，除此之外的则作为“噪声”.这种聚类方法将密度足够高的区域划分为簇，使其能够在带有“噪声”的空间内发现任意形状的类[11].

DBSCAN算法使用半径阈值ε和MinPts来控制簇的生成.其中，给定对象半径内的区域为该对象的ε-领域，MinPts为该对象ε-领域中包含对象的最小数目.在实际的应用中根据需要融合的数据情况设定阈值ε.设定集合D中A1其领域下包含对象数目为N1，当ε-内N1≤MinPts时，则将对象A1纳入核心点集合C；当N1>MinPts时，将对象A1视为“噪声”，不加入核心点集合C.以此对集合D中的所有元素进行判断，得到完整的核心点集合C，即需要融合的数据.

2.2 DBSCAN算法改进

由于全自主机器人定位是依靠全向视觉系统，所以其摄像头的误差以及定位计算的误差是一直存在的.而提高机器人的定位精度也成了每个自主机器人系统需要去完善的.经过多次实验总结，发现由于反射镜系统的误差，机器人距离目标点越远，定位的精确度也越差.不能改变设备的误差，就只能在数据上进行处理，系统应该也将这些可信度不高的定位信息作为噪声，不进行融合.

因此在算法中需要加入对机器人距离的信息的处理，及在获取到目标点观测坐标的同时，也需要获得此观测点到机器人自身的观测距离值dist_R.设定距离阈值Dlimit，接上节算法，当N1>MinPts时，若dist_R≤Dlimit，则将目标点加入集合C；若dist_R>Dlimit，则不将其加入集合C.通过对距离阈值的比较来对观测数据进行一次取舍处理，这样一些误判的噪声点得以保留，进而增加了融合数据的基数，使精确度提高.

在全自主机器人平台上得到的最直接的就是各个目标点相对于机器人坐标系的坐标，而通过1.1节中的转换，能够得到的是目标点相对于全局的坐标.在经过大量的实验之后，基本可以得出各机器人所观测到同一个目标点的结果是呈现正态分布的，观测点离实际位置越近的其分布密度越高.下面是算法流程：

(1)初始化参数，设定领域半径EPS和领域内最小对象数目MinPs.第i个观测值的领域点个数为P[i]=0 (i∈[1,n])，其核心点数设为k=0，核心点的集合为D，观测机器人数目为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循环判断P[i]数值，若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中的实际应用

以现有平台为例，假设我方的5台机器人对A目标点全部识别出其位置坐标，如图2所示.分别为：A1(x1,y1)，A2(x2,y2)，A3(x3,y3)，A4(x4,y4)，A5(x5,y5)，机器人距离观测点只有对A5的距离大于Dlimit.

图2 在机器人平台下基于DBSCAN算法数据融合示意图Fig.2 The schematic diagram of DBSCAN algorithm- based data integration on the robot platform

机器人将各自对A目标定位的信息上传到场外的教练机，在那里进行数据融合.首先是要对每个点两两之间的距离进行运算，之后以每个坐标点为圆心，设定的EPS值为半径做圆，这里EPS的设定与观测数据相关，在ROBOCUP平台下至少设定机器人直径的2倍为阈值半径，因为至少需要满足两机器人靠在一起的情况下能够被分别定位到.比较每个圆当中的坐标数据点是否满足MinPs，同时也对每个机器人到观测点的距离与距离阈值Dlimit进行比较，大于Dlimit的且不满足MinPs的则视为噪声点剔除，剩下的坐标数值取平均值作为融合结果.对于本例中A1，A5并没有满足MinPs条件(设定MinPs=1)，但是A1观测距离小于Dlimit所以只将A5点作为噪声观测点处理.故由A1、A2、A3、A4得出A点的融合结果为

具体实验是在ROBOCUP中型组的标准平台上进行，场地和场上队员按照规定，我方机器人5台，对方机器人5台，场地上有橘红色足球和场地线.每个机器人依靠自身的视觉系统得到自身周围一定范围的位置信息.通过1.3节中所阐述的机器人自定位方法和定位目标点方法，我方机器人能够各自得到所观察到的目标机器人或者小球以及自身位置坐标.如表1所示.

由表1得到机器人以及球在场地分布图，如图3所示.经过实际测量，球在实际场地中的坐标(图4中叉点)为(51,-15).在这里可以明显的看出每个机器人对球坐标的获取都带有一定的误差，这跟其具体位置和方向有关.下面给出通过DBSCAN聚类算法得到的经过融合后的球坐标点.

表1 机器人自定位以及定位球的坐标数据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)所示，可以发现融合相比前一次有很大的改善，融合坐标为(56,-12)，与实际坐标十分相近.通过对比可以发现传统的DBSCAN聚类算法对EPS的选择对融合结果影响很大，会影响其核心点的选择，直至最后归一时坐标的误差很大.

在这里引入机器人与目标点的距离阈值就显得尤为重要，因为观测距离远对观测的准确度有很大的影响，为了不会错误的将某些点作为噪声剔除，用距离作为一个阈值控制核心点是一个能够提高融合精度的方法，如图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号机器人，也不能观测全部，这样协同定位在构建全局环境地图的作用就得到了体现，R2，R3能够协同定位到OR2，R4、R5、R3能够协同定位到OR1、OR4和OR5，通过外部教练机系统进行融合就得到了完整的对方机器人位置信息及全局地图信息，达到协同定位信息共享的功能.

4 结语

通过对ROBOCUP全自主足球机器人平台多机器人协同定位的研究以及对基于密度的聚类分析算法在信息融合方面的改进与应用，提高了全自主机器人平台获得融合信息的有效性以及协同定位的准确性和稳定性，为多机器人通过局部信息获取而构建全局环境信息而提供了条件.实践表明，通过引入机器人距离阈值而改进的DBSCAN信息融合算法让机器人协同定位的精度、稳定性有了显著的提高.

致谢

论文在资料收集和实验数据采集过程中，得到了闵锋博士大力支持，在此谨向他表示衷心的感谢.

参考文献：

[1] 贾建强,陈卫东,席裕庚.全自主足球机器人系统关键技术综述[J].上海交通大学学报.2003,37(z1):45-49.

[2] 门琳娜. 基于全向视觉的足球机器人定位的研究[D]. 长沙：长沙理工大学, 2010.

[3] 陈念, 李进, 王海晖. 双目立体视觉测量系统的研究与实现[J]. 武汉工程大学学报,2011,33(5):101-104.

[4] 王卫华, 陈卫东, 席裕庚. 基于不确定信息的移动机器人地图创建研究进展[J]. 机器人. 2001，23(6):563-568.

[5] 孔伟, 张彦铎. 基于遗传算法的自主机器人避障方法研究[J]. 武汉工程大学学报. 2008,30(3):110-113.

[6] 严勇杰. 多机器人系统协调与控制[D].哈尔滨：哈尔滨工程大学.2007.

[7] 毛慧珍,陈西平,浮红霞,等.中型组足球机器人全向视觉定位技术[J]. 信息技术,2009(1):5-9.

[8] 初苗苗, 尹义龙. 面向RoboCup中型组比赛线元素检测和分类[C]//中国人工智能学会第12届全国学术年会论文汇编.中国人工智能学会.北京：北京邮电大学出版社，2007:413-417.

[9] 王远, 徐华, 贾培发. 多机器人系统中的信息融合技术综述[J]. 微电子学与计算机, 2007,24(12):150-156.