上海理工大学学报 第 38 卷 第 3 期 犑. 犝狀犻狏犲狉狊犻狋狔狅犳犛犺犪狀犵犺犪犻犳狅狉犛犮犻犲狀犮犲犪狀犱犜犲犮犺狀狅犾狅犵狔 犞狅犾.38 犖狅.3 2016 文章编号 :1007-6735(2016)03-0281-06 犇犗犐 :10.13255/ 犼. 犮狀犽犻. 犼狌狊狊狋.2016.03.012 一种自适应搜索的足球机器人定位方法 彭为微 1, 赵逢禹 2 (1. 上海理工大学医疗器械与食品学院, 上海 200093;2. 上海理工大学光电信息与计算机工程学院, 上海 200093) 摘要 : 基于目前结构环境下的机器人定位问题, 将机器人定位的概率问题转换为有限空间范围内的极小值搜索问题, 实现了一种新的基于机器自学习的搜索方法. 为了保证定位的实时性与定位精度, 提出了一个能自动调整搜索步长的自适应搜索算法, 解决了犚狅犫狅犆狌狆中型组足球机器人的自定位问题, 并在实际环境中完成了算法有效性测试. 关键词 : 自定位 ; 全向移动机器人 ; 全景成像 ; 扩展卡尔曼滤波器 ; 自适应搜索 中图分类号 : 犜犘 181 文献标志码 : 犃 犛犲犾犳 犾狅犮犪犾犻狕犪狋犻狅狀犃狆狆狉狅犪犮犺犳狅狉犛狅犮犮犲狉犚狅犫狅狋犅犪狊犲犱狅狀犛犲犾犳 犪犱犪狆狋犻狏犲犛犲犪狉犮犺犻狀犵 犘犈犖犌犠犲犻狑犲犻 1 2, 犣犎犃犗犉犲狀犵狔狌 (1. 犛犮犺狅狅犾狅犳犕犲犱犻犮犪犾犐狀狊狋狉狌犿犲狀狋犪狀犱犉狅狅犱犈狀犵犻狀犲犲狉犻狀犵, 犝狀犻狏犲狉狊犻狋狔狅犳犛犺犪狀犵犺犪犻犳狅狉犛犮犻犲狀犮犲犪狀犱犜犲犮犺狀狅犾狅犵狔, 犛犺犪狀犵犺犪犻 200093, 犆犺犻狀犪 ;2. 犛犮犺狅狅犾狅犳犗狆狋犻犮犪犾 犈犾犲犮狋狉犻犮犪犾犪狀犱犆狅犿狆狌狋犲狉犈狀犵犻狀犲犲狉犻狀犵, 犝狀犻狏犲狉狊犻狋狔狅犳犛犺犪狀犵犺犪犻犳狅狉犛犮犻犲狀犮犲犪狀犱犜犲犮犺狀狅犾狅犵狔, 犛犺犪狀犵犺犪犻 200093, 犆犺犻狀犪 ) 犃犫狊狋狉犪犮狋 : 犐狀狅狉犱犲狉狋狅狊狅犾狏犲狋犺犲狆狉狅犫犾犲犿狅犳狉狅犫狅狋狊犲犾犳 犾狅犮犪犾犻狕犪狋犻狅狀犻狀狊狋狉狌犮狋狌狉犲犲狀狏犻狉狅狀犿犲狀狋, 犪犳犪狊狋犪狀犱狉狅犫狌狊狋犪狆狆狉狅犪犮犺犳狅狉狊犲犾犳 犾狅犮犪犾犻狕犪狋犻狅狀犻犿狆犾犲犿犲狀狋犲犱犻狀狉狅犫狅狋犻犮狊狅犮犮犲狉狑犪狊狆狉犲狊犲狀狋犲犱. 犐狀狋犺犲犪狆狆狉狅犪犮犺, 狋犺犲狆狉狅犫犪犫犻犾犻狋狔狅犳狉狅犫狅狋犾狅犮犪犾犻狕犪狋犻狅狀狆狉狅犫犾犲犿狑犪狊犮狅狀狏犲狉狋犲犱狋狅犪犿犻狀犻犿狌犿狏犪犾狌犲犻狀狋犺犲狉犪狀犵犲狅犳犪犾犻犿犻狋犲犱狊犲犪狉犮犺犻狀犵狊狆犪犮犲. 犜狅犪犮犺犻犲狏犲犺犻犵犺狊犲犪狉犮犺犻狀犵犲犳犻犮犻犲狀犮狔犪狀犱犪狏狅犻犱狋犺犲犾狅犮犪犾狅狆狋犻犿狌犿狅犳狆犪狉狋犻犮犾犲犳犻犾狋犲狉犿犲狋犺狅犱, 犪狊犲犾犳 犪犱犪狆狋犻狏犲狊犲犪狉犮犺犪犾犵狅狉犻狋犺犿狑犪狊狆狉狅狏犻犱犲犱. 犜犺犲犲狓狆犲狉犻犿犲狀狋狉犲狊狌犾狋狊狊犺狅狑狋犺犪狋狋犺犲犾狅犮犪犾犻狕犪狋犻狅狀犿犲狋犺狅犱狆狉狅狆狅狊犲犱犺犪狊狋犺犲犪犱狏犪狀狋犪犵犲狊狅犳狉犲犪犾狋犻犿犲犪狀犱狆狉犲犮犻狊犻狅狀犪狀犱犻狊狊狌狆犲狉犻狅狉狋狅狅狋犺犲狉犮狌狉狉犲狀狋狉狅犫狅狋犾狅犮犪犾犻狕犪狋犻狅狀犿犲狋犺狅犱狊. 犓犲狔狑狅狉犱狊 : 狊犲犾犳 犾狅犮犪犾犻狕犪狋犻狅狀 ; 狅犿狀犻 犱犻狉犲犮狋犻狅狀犪犾犿狅犫犻犾犲狉狅犫狅狋 ; 狅犿狀犻 犱犻狉犲犮狋犻狅狀犪犾狏犻狊犻狅狀 ; 犲狓狋犲狀犱犲犱犓犪犾犿犪狀犳犻犾狋犲狉 ; 犪犱犪狆狋犻狏犲狊犲犪狉犮犺 机器人自定位问题作为移动机器人自主化 智能化研究中最为基础的问题, 由于受到外界环境的 复杂性 计算机资源的有限性, 以及噪声和干扰的影响, 一直是智能移动机器人领域研究的一个重点. 收稿日期 :2015-01-26 基金项目 : 国家自然科学基金资助项目 (61202376) 第一作者 : 彭为微 (1981-), 女, 硕士研究生. 研究方向 : 人工智能. 犈 犿犪犻犾 : 狆犲狀犵狑狑 314@163. 犮狅犿通信作者 : 赵逢禹 (1963-), 男, 教授. 研究方向 : 人工智能 软件工程 智能信息处理. 犈 犿犪犻犾 : 狕犺犪狅犳犲狀犵狔狏 @ 狌狊狊狋. 犲犱狌. 犮狀
282 机器人自定位技术作为新的研究热门领域, 自提出以来涌现了许多种方法. 例如, 纯粹利用编码器 [1] 和陀螺仪的航迹推断算法, 利用图像识别的几何定位方法 [2]. 但是, 由于基于航迹推断的方法存在无法避免的累积误差, 而图像的几何定位方法对外界环境的适应性较差, 且存在难以满足精度和实时性要求的问题, 所以, 这些方法在实际中未能得到广泛的应用. 目前, 基于贝叶斯滤波理论的概率方法是解决机器人自定位问题的主流方法, 在具体的实际应用中可采用多种不同的实现方式, 其中, 最有代表性的方法为基于贝叶斯估值理论的卡尔曼滤波器. 卡尔曼滤波器提供了一种以最小均方差来估计机器人位姿信息的有效的递归计算方法, 但是, 由于其数学模型自身的局限性, 卡尔曼滤波器也存在诸多不足. 例如 : 犪. 起始姿态必须是已知且满足高斯分布 ; 犫. 不能从跟踪失败中恢复过来, 无法避免机器人定位的 绑架问题 ; 犮. 不能处理多峰分布时的定位问题. 由于卡尔曼滤波器模型本身的局限性, 近几年, 一种基于粒子滤波的方法被应用于足球机器人的定 [3-4] 位, 该方法又称为蒙特卡洛算法, 其基本思想是采用带有权重的粒子的集合来表示对系统状态的估计, 并通过序贯权重采样法来更新粒子集合. 传统的粒子滤波的定位方法也存在其局限性, 其中的粒子点数量直接影响了定位算法的复杂度和效果, 因此, 其定位精度和计算效率是相互矛盾的. 自定位算法作为足球机器人研究中最为重要和基础的组成部分, 不仅估算出当前机器人在场地中实时的位置和朝向, 同时也为移动物体的速度估计提供了计算基础, 以便决策模块能对下一步动作作合理的规划, 所以, 自定位算法的实时性和定位精度显得尤为重要. 传统的粒子滤波算法的大量时间用于计算权重已经较低的粒子, 而这些粒子对最终的定位效果的贡献其实已经非常小, 为了避免这种多余的计算, 很多学者提出了不同的解决办法. 例如, 文献 [5] 提出的对粒子群进行速度与位置变更的方法. 本文提出了一种新的基于机器自学习的搜索方法, 其基本思想是根据前几次搜索计算的结果自动修正搜索步长, 在保证实时性的同时又保证了搜索精度. 其本质可看作一个可以 移动 的粒子, 其移动的步长来源于前几次学习的结果. 由于不需要对粒子数量的约束, 且当误差较大时, 自适应算法会自动增加搜索步长, 避免了粒子滤波器中粒子数量过少导致的 粒子 贫乏 现象. 另外, 由于只采用了一个可移动的粒子, 极大地降低了对计算机内存容量的要求, 同时也避免了粒子数量过多而造成的计算量大 无法保证实时性的问题. 此方法在解决了 粒子贫乏 的基础上, 还避免了估算精度和算法效率难以兼顾的情况. 为了提高整体系统的计算频率, 本文进一步提出了一种适合结构环境中的观测模型的计算方法, 通过对相互独立的特征点进行聚合, 将弱特征聚合为强特征点, 从而在提高计算效率的同时, 最大程度地避免了外界环境及图像处理中产生的误差对整体系统的影响. 1 观测模型的计算方法 1.1 成像系统机器人的图像传感器大都基于小孔成像原理, 成像效果好, 但往往视野较窄, 即使是鱼眼镜头, 也存在图像扭曲程度过大且成像的角度只能在 180 左右的问题. 由于机器人运动速度较快 (2~3 犿 / 狊 ), 且运动过程中常伴有自转, 即使采用云台的方式, 也难免会有拖影现象, 且无法避免图像拼接难以匹配的问题. 而对于中型组的足球机器人, 如果视野被其他机器人遮挡, 不能在比赛过程中实时 360 观察周围情况, 机器人就无法确定自己的位姿. 所以, 在本实验机器人上采用了一种全景图像采集装置, 相机并不直接对外成像, 而是通过采集双曲反光镜反射的信息来获得外界 360 的环境信息, 如图 1 所示, 其主要结构分为三部分 : 短焦相机 双曲反光镜和支撑装置. 现介绍全景视觉系统的设计参数 ( 安装位置为机器人顶部, 距离地面高度为 1 犿 ). 犪. 视距范围 : 机器人周围 5 犿以内清晰成像 ; 犫. 视野范围 : 水平方向 360, 垂直方向 5~ 80. 在实验场地的成像效果如图 2 所示. 摄像头的实际成像平面的图像来自场景的光线经过反射镜反射后在犆犆犇 ( 图像控制器 ) 平面内的成像, 并非双曲面反射全景成像系统的透视像. 为了求取成像中的像点对应水平方向上的真实物体的位置 ( 物点 ), 根据设计的双曲镜面, 可以用参数方程表示二次曲线. 狉 = ( 犲 2-1) 狋 2 2 槡 +2 狆狋 - 狆式中 : 犲为离心率 ; 狆为二次曲线的焦距 ; 狋为变量 ; 狉 为二次曲线.
第 3 期彭为微, 等 : 一种自适应搜索的足球机器人定位方法 283 图 1 全景成像装置 犉犻犵.1 犗犿狀犻 犱犻狉犲犮狋犻狅狀犪犾狏犻狊犻狅狀犱犲狏犻犮犲 图 2 全景成像图 犉犻犵.2 犗犿狀犻 犱犻狉犲犮狋犻狅狀犪犾狏犻狊犻狅狀狆犻犮狋狌狉犲 当犲 >1 时, 该方程表示双曲线, 双曲面反射镜上点的坐标 狊 2= [ 狕, 狉 ] 式中 : 狕 为径向坐标 ; 狉 为镜像坐标. 由图 3 可知, 反射光线的方向向量 狏 2= [ 狋, 槡 ( 犲 2-1) 狋 2 +2 狆狋 - 狆设镜面的法向向量为犖, 根据反射定律, 得出入射光线的方向向量 2 ] 狏 1= 狏 2-2 犖 [ 犖, 狏 2] 虽然单目全景视觉系统无法得到深度信息, 但在已知反射镜头的安装高度和入射光线的方向向量的情况下, 即可求出在同一水平面上物点相对机器人的水平距离犱. 犱 = 狏 1- 犣式中 : 犣为双曲镜面距离地面的安装高度. 1.2 特征点选取近年来, 针对犚狅犫狅犆狌狆中型组足球机器人的定位问题, 在定位时采用的特征点主要有以下 3 种 : 犪. 提取黄球门 蓝球门 立柱等特殊物体作为特征点, 从而实现几何三角定位 [6]. 犫. 通过犎狅狌犵犺变换等方法来提取场地白色标志线组成的特殊几何形状, 从而实现集合定位 [7]. 犮. 提取场地白线上的白点作为特征点 [8]. 早期采用黄球门 蓝球门 立柱等特殊的地标点 图 3 双曲反射镜成像光路图 犉犻犵.3 犗狆狋犻犮犪犾狆犪狋犺狅犳犺狔狆犲狉犫狅犾犻犮犿犻狉狉狅狉 [9] 作为特征点的定位方法, 其定位精度差, 容易受到障碍物遮挡, 加上现阶段中型组的比赛场地已经取消了类似的标志物, 所以, 此类方法已经不再适用, 而且由于比赛场地的扩大, 基于主动型传感器 ( 激光测距 [10-11] 仪和声纳等传感器 ) 的定位方法也不再适用. 中型组比赛场地的简化, 加上场地周围观众干扰等不确定性, 使机器人定位非常容易受到外界因素的干扰 ; 针对这种结构环境下的定位问题, 依靠场地的尺寸和白线是唯一相对固定的条件. 本文在图像处理过程中, 选取白线作为参考点. 在以往采用白线作为特征点识别的方法中, 往往倾向于利用图像内容中容易确定的强特征点, 如角点 直线交叉点 中场的圆形等 [12]. 这类特征点的优点是比较直观和方便理解, 但针对这类区域特征点的计算方法往往需要借助图像分割算法, 如犎狅狌犵犺变换等. 而这类算法的计算效率偏低, 加上实际图像中经常因为遮挡导致数据缺失且包含噪声, 所以, 在实际的应用中很难保证识别的稳定性和实时性. 为了避免强特征点在识别过程中计算效率低 关键点被遮挡时无法正确识别的问题, 本文提出将直线上的点作为观测模型计算的特征点. 不同于角点 直线交叉点等强特征点, 边线上单独的每个点虽然相互独立, 但将相互独立的弱特征通过投票的机制聚合在一起时, 便构成了强特征点, 即使局部被遮挡或存在外部噪声时, 也不会对整体的识别效果造成太大的影响. 为了提取边线上的白色特征点, 如果对图像中的每个点都进行分析, 则计算量太大 (640 480= 307200 个像素 ), 且会提取出很多重复的特征点. 在实际的计算中, 结合全景成像的特点, 采用扫描线的 [13] 方式提取特征点, 扫描线采用自机器人中心放射
284 状的射线, 如图 4 所示. 图 4 放射状扫描线犉犻犵.4 犚犪犱犻犪犾狊犮犪狀狀犻狀犵犾犻狀犲特征点提取的方式为在扫描线上白色区域的中间点, 且白色区域的两端都为绿色区域, 如图 5 所示. 图 6 给出了图 5 中特征点的局部放大图. 图 5 扫描线示意图犉犻犵.5 犛犮犺犲犿犪狋犻犮犱犻犪犵狉犪犿狅犳狊犮犪狀狀犻狀犵犾犻狀犲 犫. 以 10 犮犿的间距遍历场地中的所有位置, 假设该特征点的质量为 1, 所有白线的质量为 1, 通过万有引力公式计算两物体之间的引力 2 犉 = 犌犿犕 / 狉式中 : 犌为引力常量 ; 犿, 犕分别为两物体的质量 ; 狉为两物体距离. 场地上所有线段对该特征点的引力的作用结果为一个合力, 其结果用矢量表示. 犉的值越小, 表示该点的误差值越大 ; 反之越小. 因为, 这部分的计算量比较大且不会发生变化, 所以, 在实际的运用中, 将它作为标定数据存放在内存中供查表使用, 以提高计算速度. 为了提高定位精度, 场地边线外 1 犿也进行计算, 实际遍历区间为 (18+2) (12+2) 犿. 1.4 观测模型的计算在地图模型已知的情况下, 每当捕获到新的图像信息后, 首先提取白线上的特征点 ( 参见图 6), 然后将识别到的每个特征点代入公式中进行计算, 将特征点从机器人的相对坐标系转换到世界地图模型中的全局坐标系下, 其转换式为犮狅狊 θ - 狊犻狀 θ 犚 = 狆 + ( 狊犻狀 θ 犮狅狊 θ ) 狊犻 (1) 式中 : 狊犻代表特征点在在机器人相对坐标系下的位置 ( 犡, 犢 ); 犘点代表机器人在全局坐标系下的位置 ( 犡, 犢 ); 角度 θ 代表机器人当前的姿态 ; 犚为机器人在全局坐标下的位置. 从而可以将特征点在机器人相对坐标系下的 ( 犡, 犢 ), 通过坐标系旋转式, 转换为特征点在全局坐标下的坐标 ( 犡, 犢 ), 其计算式即为 犡 ( ) = 犢 犡 犮狅狊 θ - 狊犻狀 θ + 狊犻狀 θ 犮狅狊 θ 犢 ( ) 犡 ( )( 犢 ) 图 6 扫描线与特征点的局部放大图犉犻犵 6 犈狀犾犪狉犵犲犱狆犻犮狋狌狉犲狅犳狊犮犪狀狀犻狀犵犾犻狀犲犪狀犱犮犺犪狉犪犮狋犲狉犻狊狋犻犮狆狅犻狀狋狊 1.3 地图模型的建立作为结构环境下的机器人定位方法, 首先需要建立场地的地图数据. 在移动机器人定位中采用的地图的表示方法主要有 4 种 : 拓扑图 特征图 网格图和直接表征法. 由于中型组足球机器人比赛的场地尺寸已知, 且观测模型的特征点已明确, 故在直接表征法的基础上对其进行改进, 地图的建立方法如下 : 犪. 以犚狅犫狅犆狌狆中型组机器人真实比赛的场地尺寸建立模型, 以场地上的白线作为标记物. 图 7 机器人坐标特征点向全局坐标变换犉犻犵 7 犚狅犫狅狋 狊犮狅狅狉犱犻狀犪狋犲犮狅狀狏犲狉狊犻狅狀当特征点转换到全局坐标系后, 理论上所有的特征点都应该位于白线上且完全吻合, 但是, 由于机
第 3 期彭为微, 等 : 一种自适应搜索的足球机器人定位方法 285 器人在运动过程中可能受到碰撞, 其真实位置与姿态同理论值存在差异, 将图像识别的特征点转换到全局坐标系后, 都会存在一定的偏差. 所以, 将特征点到地图模型上最近白线的最小距离值 ( 标量 ), 作为该特征点的观测误差值. 图 8 中的黑点表示特征点, 黑线表示特征点到白线的距离, 即特征点观测模型和世界模型间的误差值. 图 8 计算出的特征点坐标 犉犻犵 8 犆犪犾犮狌犾犪狋犲犱犮狅狅狉犱犻狀犪狋犲狊狅犳犮犺犪狉犪犮狋犲狉犻狊狋犻犮狆狅犻狀狋狊 为了尽量减少识别错误点对定位效果的影响, 在计算时, 对距离白线越远的特征点犚犻, 采用的可信度越低 ; 反之, 越近的特征点, 其可信度越高. 误差值 ε 的计算公式为 ε( 犚犻 )=1- 犆 2 /( 犆 2 2 + 犱犻 ) (2) 式中 : 犆取常数 250; 犱犻为特征点犚犻在地图模型中距离白线最短的距离. 误差值可看作是该特征点对当前机器人位置的一次投票. 综合考虑所有的特征点投票, 将其所有的误差值进行累加计算. 犈 = ε ( 犚犻 ) (3) 犈可作为当前机器人位姿相对观测模型的一个评估值. 该误差值越小, 说明机器人在该位置的可能性越大 ; 反之则可能性越小. 相对于采用强特征进 [14-15] 行识别并定位的方法, 此方法将多个相互独立的弱特征聚合为强特征, 在图像被遮挡或局部特征提取错误的情况下, 不会导致整体系统计算失效, 极大地提高了容错性, 其计算量相对于特征点的数量也仅仅成线性比例关系, 该方法在数量计算及速度上有非常大的提升. 2 自适应搜索算法 机器人自定位的问题, 可以转换为假设机器人在场地上的不同位置, 计算在该位置的误差值, 通过计算找到误差最小的位置, 即为机器人当前所在概率最高的位置. 从而将机器人自定位问题转换为计 算图中误差最小位置的问题. 该问题最简单的方法就是直接对场地上所有机器人的位置遍历计算后寻找最小值, 但是, 在实际操作中, 由于机器人姿态由位置 ( 犡, 犢 ) 和姿态 θ( 因为机器人在平面上移动, 所以这里的姿态代表机器人的转动角度信息 )3 个参数组成, 如果在三维的环境下进行搜索, 计算量会以几何倍数递增, 例如 : 以犡, 犢 最小搜索步长 10 犮犿,θ 最小搜索步长 1 为例, 每次定位所需要的计算次数为 (1800/10)(1200/10)(360/1), 共 7776000 次, 这么大的计算量很难达到实时性的要求. 在实际应用中, 为了平衡精度和实时性的矛盾, 通常采用扩展卡尔曼滤波粒子滤波等方法来减少计算量, 但都有不可避免的局限性. 本文提出另一种求解方法, 即将机器人自定位的问题转换为数值计算中求极大极小值的问题, 从而避免了以往方法的局限性, 其计算方法为 狀犿犻狀犈 = 犿犻狀 ( ) ε( 犚犻犻 =1 ) (4) 式中, 狀为特征点的数量. 在数学模型中, 求解这类极大极小值问题的方法有很多, 如爬山 模拟退火等方法, 但在计算速度和精度上很难有一个很好的取舍. 例如, 当搜索范围小时, 虽能很好地保证定位精度和实时性, 但计算的结果容易陷入局部极小位置, 导致出现粒子滤波中 粒子贫乏 问题. 如果增大搜索的范围, 又不能保证实时性. 如果增加搜索步长, 又会导致定位精度不能满足要求. 为了解决采用固定步长无法同时满足精度和计算效率的问题, 本文提出了一种基于机器自适应搜索的机器人定位算法. 将第狋步搜索的步长定义为狑, 为了达到步长自适应调整的目的, 下次搜索的步长不仅依靠学习率, 而且还结合了前几次的计算结果来进行调整, 这样就可以达到当目标偏离较远时, 搜索步长会快速增加以期最快速度接近目标, 当较接近搜索目标时, 会在目标区域附近震荡, 逐渐减小步长, 以期最大程度接近目标. 为了达到搜索步长学习的目的, 引入一个可变 ( 狋 +1) 因子 Δ 来计算下一次的步长狑, 其更新的规则不仅仅依赖全局学习率 η, 而且还和前次学习的偏导数 Δ 有关, 计算公式为 烄 η + Δ, 犈 犈 >0 Δ =烅 η - Δ, 犈 犈 <0 Δ 烆, 其他
286 全局学习率 η 的取值不依赖于前次搜索的结果, 而取决于上次定位的偏差值. 若前次定位的偏差越小, 则 η 的取值越小, 反之则越大, 其计算方法为 η = 犈犓式中 : 犓为设定参数, 用以满足 0<η - <1<η + 的约束条件 ;η + 为误差变小时的正向学习率 ;η + - 为误差变大时的逆向学习率. 当可变因子计算完成后, 则可以计算步长的调 ( 狋节率 ) Δ 狑, 计算公式为 ( 狋 Δ 狑 ) =烅 +Δ, 犈 <0 烆 0, 其他 ( 狋 +1) 最后即可得到下次采用的步长狑, 更新规则为 烄 -Δ, 犈 >0 ( 狋狑 +1) ( 狋 = 狑 ) +Δ 狑 但是, 会有一种意外情况, 如果偏导数狑为负值时, 及前次步长过大, 则有可能会 冲过 目标点, 从而错失最佳的匹配位置, 所以, 下次搜索的步长必须具有方向性, 从而能够进行反向的调节, 其计算方法为 ( 狋 Δ 狑 ) =-Δ 狑, 犈 3 测试效果 犈 <0 针对自适应搜索算法和粒子滤波算法, 在实际场地进行测试 (18 犿 12 犿 ), 直径为 50 犮犿的机器人, 计算平台为犘 2.4 双核犆犘犝,1 犌内存, 机器人从点犃以 1.5 犿 / 狊的速度移动到点犅, 然后移动到点 犆, 再回到点犃作为一次测试样本. 同时在运行过程中以激光测距设备实时保存机器人的位姿信息, 作为算法定位效果对比的标准数据信息. 图 9 表示机器人测试时的移动轨迹. 图 9 机器人移动路径图 犉犻犵 9 犚狅犫狅狋 狊犿狅狏犻狀犵狆犪狋犺 在同样的计算耗时 (5 犿狊 ) 的情况下, 粒子滤波方法中, 粒子的数量不能大于 50 个, 表 1 以 50 个粒子 数量及 150 个粒的粒子滤波方法同自适应搜索算法的定位效果 ( 平均误差 ) 进行了对比, 误差单位为犿狊. 表 1 定位精度和耗时对比 犜犪犫.1 犆狅狀狋狉犪狊狋狅犳狊犲狋犻狀犵犪犮犮狌狉犪犮狔犪狀犱狋犻犿犲犮狅狀狊狌犿犿犻狀犵 3 种计算方法犡方向 / 犮犿犢方向 / 犮犿 θ 方向 /( ) 平均耗时 / 犿狊 自适应搜索算法 粒子滤波 (50 粒子 ) 粒子滤波 (150 粒子 ) 34.2 28.4 1.1 4.87 111.3 86.7 6.2 5.12 33.1 27.9 1.1 19.09 从表 1 看出, 当粒子数量较少时 (50 个 ) 时, 计算的平均耗时都在 5 犿狊左右时, 粒子滤波算法的定位精度远远低于自适应搜索算法的定位精度, 其最大误差值可达 111.3 犮犿及 6.2, 远大于自适应搜索算法的 34.2 犮犿和 1.1. 当增加粒子数量到 150 个时, 定位精度接近自适应搜索算法的定位精度, 但计算时间却大幅增加, 平均耗时达到 19.09 犿狊, 远大于自适应搜索算法的 4.87 犿狊. 4 结束语 基于粒子滤波的机器人自定位方法中, 候选粒子的个数是个关键问题, 它影响到机器人自定位的精度和算法消耗的时间, 并且无法调和. 相对于采用粒子滤波的定位方法, 自适应搜索的定位方法在保证满足犚狅犫狅犆狌狆中型组足球机器人定位精度要求的同时, 极大地提高了计算效率. 参考文献 : [1] 董晓杰, 陈启军. 卡尔曼滤波在足球机器人定位中的应用 [ 犑 ]. 装备制造技术,2008(2):45-48. [2] 杨洋, 罗亚辉, 康江, 等. 基于航迹推算的移动式机器人定位系统设计 [ 犑 ]. 山西电子技术,2012(2):24-27. [3] 犜犎犚犝犖犛, 犉犗犡犇, 犅犝犚犌犃犚犇犠, 犲狋犪犾. 犚狅犫狌狊狋犿狅狀狋犲犮犪狉犾狅犾狅犮犪犾犻狕犪狋犻狅狀犳狅狉犿狅犫犻犾犲狉狅犫狅狋狊 [ 犑 ]. 犃狉狋犻犳犻犮犻犪犾犐狀狋犲犾犻犵犲狀犮犲,2001,128(1/2):99-141. [4] 犕犈犖犈犌犃犜犜犐犈, 犘犚犈犜犜犗犃, 犘犃犌犈犔犔犗犈. 犃狀犲狑狅犿狀犻犱犻狉犲犮狋犻狅狀犪犾狏犻狊犻狅狀狊犲狀狊狅狉犳狅狉犿狅狀狋犲 犮犪狉犾狅犾狅犮犪犾犻狕犪狋犻狅狀 [ 犕 ] 犖犃犚犇犐犇, 犚犐犈犇犕犐犔犔犈犚犕, 犛犃犕犕犝犜犆, 犲狋犪犾. 犚狅犫狅犆狌狆 2004: 犚狅犫狅狋犛狅犮犮犲狉犠狅狉犾犱犆狌狆犞犐. 犅犲狉犾犻狀 : 犛狆狉犻狀犵犲狉 犞犲狉犾犪犵,2005:97-109. [5] 袁光辉, 樊重俊, 张惠珍, 等. 一种新的粒子群算法与人工鱼群算法的混合算法 [ 犑 ]. 上海理工大学学报, 2014,36(3):223-226,238. ( 下转第 292 页 )
292 [4] 犆犎犈犖犔犖, 犔犐犅犎, 犣犎犃犗犓, 犲狋犪犾. 犃狀犻犿狆狉狅狏犲犱犪犾犵狅狉犻狋犺犿狋狅犵犲狀犲狉犪狋犲犪犠犻犉犻犳犻狀犵犲狉狆狉犻狀狋犱犪狋犪犫犪狊犲犳狅狉犻狀犱狅狅狉狆狅狊犻狋犻狅狀犻狀犵 [ 犑 ]. 犛犲狀狊狅狉狊,2013,13 (8): 11085-11096. [5] 犚犈犎犐犕犕. 犎狅狉狌狊 : 犪犠犔犃犖 犫犪狊犲犱犻狀犱狅狅狉犾狅犮犪狋犻狅狀犱犲狋犲狉犿犻狀犪狋犻狅狀狊狔狊狋犲犿 [ 犕 ]. 犕犪狉狔犾犪狀犱 : 犝狀犻狏犲狉狊犻狋狔狅犳犕犪狉狔犾犪狀犱犪狋犆狅犾犲犵犲犘犪狉犽,2004. [6] 犉犃犖犌犛犎, 犔犐犖犜犖. 犐狀犱狅狅狉犾狅犮犪狋犻狅狀狊狔狊狋犲犿犫犪狊犲犱狅狀 犕狅犫犻犾犲犆狅犿狆狌狋犻狀犵,2012,11(1):100-110. [11] 犗犝犜犈犕犣犃犅犈犜犛, 犖犈犚犌犝犐犣犐犃犖犆. 犃犮犮狌狉犪犮狔犲狀犺犪狀犮犲 犿犲狀狋狅犳犪狀犻狀犱狅狅狉犃犖犖 犫犪狊犲犱犳犻狀犵犲狉狆狉犻狀狋犻狀犵犾狅犮犪狋犻狅狀狊狔狊狋犲犿狌狊犻狀犵犓犪犾犿犪狀犳犻犾狋犲狉犻狀犵 [ 犆 ] 犘狉狅犮犲犲犱犻狀犵狊狅犳狋犺犲犐犈犈犈 19 狋犺犐狀狋犲狉狀犪狋犻狅狀犪犾犛狔犿狆狅狊犻狌犿狅狀犘犲狉狊狅狀犪犾, 犐狀犱狅狅狉犪狀犱犕狅犫犻犾犲犚犪犱犻狅犆狅犿犿狌狀犻犮犪狋犻狅狀狊. 犆犪狀狀犲狊 : 犐犈犈犈,2008:1-5. [12] 犆犎犐犑犖, 犙犐犃犖犆犉, 犣犎犃犖犌犘犢, 犲狋犪犾. 犃狀狅狏犲犾犈犔犕 犱犻狊犮狉犻犿犻狀犪狀狋 犪犱犪狆狋犻狏犲狀犲狌狉犪犾狀犲狋狑狅狉犽犻狀犐犈犈犈 802.11 犫犪狊犲犱犪犱犪狆狋犻狏犲犓犪犾犿犪狀犳犻犾狋犲狉狋狉犪犮犽犻狀犵犪犾犵狅狉犻狋犺犿 [ 犑 ]. 犲狀狏犻狉狅狀犿犲狀狋狊 [ 犑 ]. 犐犈犈犈犜狉犪狀狊犪犮狋犻狅狀狊狅狀犖犲狌狉犪犾犖犲狌狉狅犮狅犿狆狌狋犻狀犵,2014,128:42-49. 犖犲狋狑狅狉犽狊,2008,19(11):1973-1978. [13] 犖犌犝犢犈犖犎犖, 犣犎犗犝犑, 犓犃犖犌犎犑. 犃犮犪犾犻犫狉犪狋犻狅狀 [7] 犠犝犣犔, 犔犐犆犎, 犖犌犑犓犢, 犲狋犪犾. 犔狅犮犪狋犻狅狀犲狊狋犻犿犪狋犻狅狀犿犲狋犺狅犱犳狅狉犲狀犺犪狀犮犻狀犵狉狅犫狅狋犪犮犮狌狉犪犮狔狋犺狉狅狌犵犺狏犻犪狊狌狆狆狅狉狋狏犲犮狋狅狉狉犲犵狉犲狊狊犻狅狀 [ 犑 ]. 犐犈犈犈犜狉犪狀狊犪犮狋犻狅狀狊犻狀狋犲犵狉犪狋犻狅狀狅犳犪狀犲狓狋犲狀犱犲犱犓犪犾犿犪狀犳犻犾狋犲狉犪犾犵狅狉犻狋犺犿犪狀犱狅狀犕狅犫犻犾犲犆狅犿狆狌狋犻狀犵,2007,6(3):311-321. 犪狀犪狉狋犻犳犻犮犻犪犾狀犲狌狉犪犾狀犲狋狑狅狉犽 [ 犑 ]. 犖犲狌狉狅犮狅犿狆狌狋犻狀犵, [8] 犓犝犛犎犓犐犃, 犘犔犃犜犃犖犐犗犜犐犛犓犖, 犞犈犖犈犜犛犃犖犗犘犗犝犔犗犛犃 2015,151:996-1005. 犖. 犓犲狉狀犲犾 犫犪狊犲犱狆狅狊犻狋犻狅狀犻狀犵犻狀狑犻狉犲犾犲狊犾狅犮犪犾犪狉犲犪 [14] 犆犎犈犖犣, 犣犗犝犎, 犑犐犃犖犌犎, 犲狋犪犾. 犉狌狊犻狅狀狅犳犠犻犉犻, 狀犲狋狑狅狉犽狊 [ 犑 ]. 犐犈犈犈犜狉犪狀狊犪犮狋犻狅狀狊狅狀犕狅犫犻犾犲犆狅犿狆狌狋犻狀犵, 狊犿犪狉狋狆犺狅狀犲狊犲狀狊狅狉狊犪狀犱犾犪狀犱犿犪狉犽狊狌狊犻狀犵狋犺犲犓犪犾犿犪狀 2007,6(6):689-705. 犳犻犾狋犲狉犳狅狉犻狀犱狅狅狉犾狅犮犪犾犻狕犪狋犻狅狀 [ 犑 ]. 犛犲狀狊狅狉狊,2015,15(1): [9] 赵永翔, 周怀北, 陈淼, 等. 卡尔曼滤波在室内定位系 715-732. 统实时跟踪中的应用 [ 犑 ]. 武汉大学学报 ( 理学版 ), [15] 张明华, 张申生, 曹健. 基于无线局域网定位的误差关 2009,55(6):696-700. 键因素分析与仿真 [ 犑 ]. 系统仿真学报,2009,21(15): [10] 犉犃犖犌犛犎, 犔犐犖犜. 犘狉犻狀犮犻狆犪犾犮狅犿狆狅狀犲狀狋犾狅犮犪犾犻狕犪狋犻狅狀犻狀 4866-4869. 犻狀犱狅狅狉犠犔犃犖犲狀狏犻狉狅狀犿犲狀狋狊 [ 犑 ]. 犐犈犈犈犜狉犪狀狊犪犮狋犻狅狀狊狅狀 ( 编辑 : 丁红艺 ) 櫅櫅櫅櫅櫅櫅櫅櫅櫅櫅櫅櫅櫅櫅櫅櫅櫅櫅櫅櫅櫅櫅櫅櫅櫅櫅櫅櫅櫅櫅櫅櫅櫅櫅櫅櫅櫅櫅櫅櫅櫅櫅櫅櫅櫅櫅 ( 上接第 286 页 ) [6] 刘伟. 犚狅犫狅犆狌狆中型组机器人全景视觉系统设计与实现 [ 犇 ]. 长沙 : 国防科学技术大学,2004. [7] 卢惠民, 刘斐, 郑志强. 一种新的用于足球机器人的全向视觉系统 [ 犑 ]. 中国图象图形学报,2007,12(7): 1243-1248. [8] 犕犈犖犈犌犃犜犜犐犈, 犘犚犈犜犜犗犃, 犛犆犃犚犘犃犃, 犲狋犪犾. 犗犿狀犻犱犻狉犲犮狋犻狅狀犪犾狏犻狊犻狅狀狊犮犪狀犿犪狋犮犺犻狀犵犳狅狉狉狅犫狅狋犾狅犮犪犾犻狕犪狋犻狅狀犻狀犱狔狀犪犿犻犮犲狀狏犻狉狅狀犿犲狀狋狊 [ 犑 ]. 犐犈犈犈犜狉犪狀狊犪犮狋犻狅狀狊狅狀犚狅犫狅狋犻犮狊,2006,22(3):523-535. [9] 犢犃犛犝犇犃犌, 犅犐犖犌. 犗犫犼犲犮狋狉犲犮狅犵狀犻狋犻狅狀犪狀犱狊犲犾犳 犾狅犮犪犾犻狕犪狋犻狅狀犳狅狉犻狀狋犲狉犪犮狋犻狏犲狊狅犮犮犲狉狉狅犫狅狋狊 [ 犆 ] 犘狉狅犮犲犲犱犻狀犵狊狅犳狋犺犲犐犈犈犈犐狀狋犲狉狀犪狋犻狅狀犪犾犆狅狀犳犲狉犲狀犮犲狅狀犚狅犫狅狋犻犮狊犪狀犱犅犻狅犿犻犿犲狋犻犮狊. 犛犺犲狀狔犪狀犵 : 犐犈犈犈,2004: 407-412. [10] 方正, 佟国峰, 徐心和. 一种鲁棒高效的移动机器人定位方法 [ 犑 ]. 自动化学报,2007,33(1):48-53. [11] 徐则中, 庄燕滨. 移动机器人定位方法对比研究 [ 犑 ]. 系统仿真学报,2009,21(7):1891-1896. [12] 犅犃犐犛犜犃, 犛犃犅犔犃犜犖犐犌犚, 犖犗犞犃犓犌. 犔犻狀犲 犫犪狊犲犱犾犪狀犱犿犪狉犽狉犲犮狅犵狀犻狋犻狅狀犳狅狉狊犲犾犳 犾狅犮犪犾犻狕犪狋犻狅狀狅犳狊狅犮犮犲狉狉狅犫狅狋狊 [ 犆 ] 犘狉狅犮犲犲犱犻狀犵狊狅犳狋犺犲犐犈犈犈犛狔犿狆狅狊犻狌犿狅狀犈犿犲狉犵犻狀犵犜犲犮犺狀狅犾狅犵犻犲狊. 犐狊犾犪犿犪犺犪犱 : 犐犈犈犈,2005: 132-137. [13] 犖犈犞犈犛犃犑犚, 犕犃犚犜犐犖犛犇犃, 犘犐犖犎犗犃犑. 犃犺狔犫狉犻犱狏犻狊犻狅狀狊狔狊狋犲犿犳狅狉狊狅犮犮犲狉狉狅犫狅狋狊狌狊犻狀犵狉犪犱犻犪犾狊犲犪狉犮犺犾犻狀犲狊 [ 犆 ] 犘狉狅犮犲犲犱犻狀犵狊狅犳狋犺犲 8 狋犺犆狅狀犳犲狉犲狀犮犲狅狀犃狌狋狅狀狅犿狅狌狊犚狅犫狅狋犛狔狊狋犲犿狊犪狀犱犆狅犿狆犲狋犻狋犻狅狀狊,2008: 51-55. [14] 丘柳东, 王牛, 李祖枢. 一种中型自主足球机器人自定位方法 [ 犑 ]. 计算机工程与应用,2011,47(22): 21-25. [15] 犔犝犗犚犎, 犕犐犖犎犙. 犃狀犲狑狅犿狀犻 狏犻狊犻狅狀犫犪狊犲犱狊犲犾犳 犾狅犮犪犾犻狕犪狋犻狅狀犿犲狋犺狅犱犳狅狉狊狅犮犮犲狉狉狅犫狅狋狊 [ 犆 ] 犘狉狅犮犲犲犱犻狀犵狊狅犳犠犚犐犠狅狉犾犱犆狅狀犵狉犲狊狊狅狀犛狅犳狋狑犪狉犲犈狀犵犻狀犲犲狉犻狀犵. 犡犻犪犿犲狀 : 犐犈犈犈,2009:126-130. ( 编辑 : 石瑛 )