移动机器人的同时定位和地图创建方法


第 36 卷

第 7期

2 0 0 4 年7 月

哈 尔 滨 工 业 大 学 学 报 JOURNAL OF HARBIN INSTITUTE OF TECHNOLOGY

Vol1 36 No17 July, 2004

移动机器人的同时定位和地图创建方法
厉茂海, 洪炳 , 罗荣华
( 哈尔滨工业大学 计 算机科学与技术学院, 黑龙江 哈尔滨 150001, E -mail: limaohai@ hit. edu. cn)

摘 要: 通过声纳传感器实时地创建 和修正 地图, 局部 地图 是基 于栅格 的概 率模型: 工 作环 境被划 分成 栅 格, 每一个栅格赋一个值, 标识栅格中有障碍物的概率. 地图应用哈夫变换创建, 定位通过对超声波数据应 用 滤波算法并结合地图创建实现. 使用 Pioneer 2 移动机器人在 实际的室 内环境 中的实 验, 验 证了该 方法的 可 行性. 关键词: 同时定位和地图创建; 声纳传感器; 基于栅格的 概率模型; 哈夫变换 中图分类号: TP24 文献标识码: A 文章编号: 0367- 6234( 2004) 07- 0874- 03

Simultaneous localization and map building for mobile robot
LI Mao hai, HONG Bing -rong, LUO Rong hua ( School of Computer Science and Technology , Harbin Institute of Technology, Harbin 150001, China, E -mail: limaohai@ hit. edu. cn)

Abstract: A map is built and updated immediately through sonar sensor. The local map is a grid based probabilist ic model: the work environment is decomposed into grids and every grid takes up a value, which indicates the proba bility of an obstacle in grids. The map is built through Hough transform. The map building combines with the sonar data obtained from a filter algorithm to realize the localization. Experimental results show the feasibility of this method. Key words: simultaneous localization and map building; sonar sensor; grid based probabilist ic model; Hough transform 移动机器人的同时定位和地图创建问题( Si multaneous Localization and Map Building: SLAM) 描 述如下: 移动机器人从初始位置, 经过一系列的位 置并且在每一个位置获得传感器对环境的感知信 息, 移动机器人的目标是处理这些传感器数据, 确 定机器人的位姿, 并且同时创建环境地图. 要想开 发一个有效的 SLAM 系统, 关键是选择好环境的 描述方法, 通常的地图描述方法有栅格法[ 1] 和特 征提 取法[ 2] , 还有拓扑方 法[ 3] 和 蒙特卡罗法 [ 4] . 为解决同时地图创建和定位问题, Thrun [ 5] 提出了 一种基于陆标的地图创建和定位的方法, 但定位 不是 实时 的 并 且要 求 陆 标是 人 工 设置 的. Ya 收稿日期: 2004- 04- 26. 基金项目: 国家高技术研究发展计划资助项目( 2002AA735041) . 作者简介: 厉茂海( 1980- ) , 男, 博士研究生; 洪炳 ( 1937- ) , 男, 博士, 教授, 博士生导师.

mauch [ 6] 提出了一种 连续定 位的地 图创建 算法. 本文采用基于栅格的概率模型, 地图应用哈夫变 换创建, 用来在声纳数据中的检测直线段.

1
111





机器人建模 本方法在 Pioneer 2 移动机器人上实现. 它是

一个三轮机器人, 前面是两个主动轮, 身体后面是 一个万向 从动轮, 在 身体 上方 装有 Pan- T ilt Zoom( PTZ) 视觉传感器, 里程计传感 器位于驱动 系统中, 提供对机器人位置估计 ( ax , a y , a th ) T . 系统的坐标系统分为全局坐标系 Ca = ( ax , ay , a th ) T 和机器人坐标系 C r = ( x , y , H T . 全局 ) 坐标系以机器人出发点为坐标原点( 0, 0, 0) , 通过 里程计的累积, 机器人在全局坐标系统中相对于 起始点的位姿定义为 X = ( ax , ay , a th ) T. 机器人

第7期

厉茂海, 等: 移动机器人的同时定位和地图创建方法

# 875 #

坐标系的 x 轴是机器人平移的速度向量, y 轴是 身体的左侧方向. 通过如下公式可以得到机器人 下一个位置的坐标: ax X next = ay = X + a th f ( X , u, t , X) . cos H 0 v sin H 0 # # t + X= w 0 1

位置即位置 4 为中心.

式中: u = [ v w ] t , v 和t 分别为平移和转动速度; X 为里程计的累积误差; t 是移动的时间; X 为机 器人的当前位姿; H为机器人当前的方向. 实验发 现在短距离范围内, 里程计的测量值还是较为准 确的, 误差约为 X = 10- 3. 112 环境建模 本试验在 一个相对结构化 的室内环 境中完 成, 结构化环境可以用一组在全局坐标系中的直 线段表示出来, 直线段可以用来表示物体的表面. 每一条直线段表示环境的第 i 个/ 墙0, 定义为 w i = [ aT ax c ay c al ] , 其中, 全局坐标系 Ca = ( ax , ay , a th ) T, av 表示全局坐 标系中墙的方向, ax c , ay c 表 示全局坐标系中墙的中心, a 1 表示墙的长度. 因 此提出的 环境表示 是一个 线段集 合: W = [ w 1T w 2 ,] .
T T T

图1

移动栅格

211

坐标转换

坐标转换实现的是: 把在机器人坐标系中测 得物体的位置转换到全局坐标系统中的位置. 当 机器人在栅格 i 中时, 它的位置按照全局坐标系 统表示为( ax , ay , a th ) , 声纳在机器人坐标系统 C r 中得到的测距数据 s r , j = 0, ,, 15, 描述为 x r = ( sr + r) cos( ar ) , y r = ( s r + r ) sin( ar ) , ajr = 2215 # j . 其中, r 是机器人半径, ajr 是第j 个声纳相对于正 前声纳的相对角. 此时, 假设机器人在全局坐标 系中的坐标为( aR , aR , a R ) T, 声纳所 测到的物体 x y th 在机器人坐标系统中的坐标为( x jr , y jr , ajr ) T , 则经 过坐标变换, 该物体在全局坐标系中的坐标( ax , ay , a th ) T 表示为 ax ay 212 = cos aR - sinaR th th sinaR cosaR th th # xr j yr j + aR x aR y ,
j j j j j j j r r r T

2

地图创建算法
采用基于栅格的概率模型. 该方法仅基于由

超声波传感器获得的数据, 应用移动局部栅格的 概念, 算法描述如下. Step1: 机器人从初始姿态 X 0 = ( ax , ay , ath ) T = ( 0, 0, 0) T 开始探测周围环境, 这时, 声纳传感 器涉及的区域形成静态的方形栅格, 栅格以当前 机器人位置为中心. Step2: 当机器人移动时, 如果机器人在该栅 格的安全距离范围内, 转 Step3, 否则转 Step4. Step3: 声纳传感器不断获得周围环境信息, 对声纳数据应用滤波算法, 尽量减小噪声的影响, 应用哈夫变换创建地图, 直到机器人超过该栅格 的安全距离为止, 转 Step1. Step4: 老的栅格消失, 同时, 又创建了一个新 的栅格, 新形成的栅格以机器人走出的前一个栅 格安全距离边界点为中心, 也就是当它超过了安 全区域的界限时就以当前机器人的位置为中心形 成一个新的栅格, 转 Step1. 如图 1 所示, 位置 1、 3 都在安全边界之内, 2、 栅格不需要新的创建, 当机器人超过安全区域时, 下一个新的栅格就会形成, 并且以机器人的当前

a th = aR + ajr . th 栅格安全边界的确定 当机器人在栅格 i 的安全区域内时, 它通过 声纳传感器不断对周围环境探测, 获得足够多的 声纳信息, 以保证哈夫变换的实现. 每次当机器人 离开局部栅格 i 确定的安全边界时, 就会以机器 人的当前位置作为中心, 就会形成新的栅格 i + 1, 但是, 当机器人即将穿过栅格 i 时, 必须知道在 机器人的前面是什么. 由于这个原因, 定义了一 个内部的安全边界, 如图 1 所示的点划线, 当机器 人过点划线时, 就会产生一个新的局部栅格. 为了确定安全边界, 需要从栅格中心进行测 量, 根据超声波传感器的测量范围, 在这个范围内 进行实验寻找错误迅速递增的边界点. 试验发现 当距离大于 4 m 后错误迅速增加, 因此, 栅格的内 部安全边界确定为距离栅格中心 315 m.

# 876 #



















第 36 卷

213

地图创建的哈夫变换 哈夫变换( Hough Transform: HT ) 是对灰度图

Step3: 结合 t - 1 时刻对机器人的位姿估计 p t- 1 与 t 时刻传感器得到的测量值m t 提供新的对 ? 机器人的位姿估计 p t , 转 Step1. ? Step4: 由于传感器的错误读数导致了不一致 性的存在, 并且需要抛弃机器人位置感知错误的 部分, 转 Step1. 应用本方法用 Pioneer2 移动机器人在结构化 的室内环境中实现了地图创建和定位的同时性, 取得了很好的效果, 实验结果略.

像检测直线和其他参数曲线的一种方法. 在 x y 坐标平面( 输入空间) 中的一条直线可以用方程 Q= x cos H+ ysin H来描述, 在 H Q参数空间( 哈 夫空间) 中, 直线被映射成为单个点. 如果给定在 输入空间中的一个点, 在哈夫空间中就会有无数 的直线通过该点. 在输入空间中通过点 ( x i , y i ) 的 所有直线的参数在( H Q 哈夫空间中形成了一条 , ) 正弦曲线: x i sin H+ y i cos H= Q. ( 1) 哈夫变换( HT) 的实现是基于参数离散化的. 如果 H和 Q的值被离散化, 可以形成一个累加矩 阵 A( H Q . 参数 H被离散化成值 H , k = 1, ,, n, , ) k H - H 1 = $ . 特征点( x i , y i ) 的哈夫变换按照 k kH 式( 1) 可以对 n 个H 值计算 Q Q值可以被离散化 . k 成 m 个离散的值 Q, k = 1, ,, m 满足Q - Q 1 = k k k$ , 并且相应的累加矩阵 A( H , Q) 是递增的. 该 Q k k 过程对所有的特征点重复. 哈夫变换( HT) 有许多要注意的问题: 1) 尽管认为对 H和 Q量子化越小越能增加准 确性, 但是实际情况, 量子化程度过小会增加算法 复杂度, 影响效率, 因此合适的选择 $H和 $Q是有 必要的, 这可以通过多做几次实验来确定累加矩 阵最好的可能结果. 2) 实验表明往往由于累加矩阵的量子化错 误使哈夫变换提取的线段数远远超过要求的线段 数, 这样会使输出结果非常复杂, 为了保留最主要 的线段, 需要应用相关的算法对结果进一步处理, 如聚类算法和滤波算法.

4





1) 提出了一个可靠的方法来处理地图创建和 定位的同时性问题. 对世界模型的估计提供给定 位算法. 反过来, 定位算法给出了机器人的准确 位置和方向估计, 这些估计又应用到地图创建算 法中去更新世界模型. 2) 用移动的局部栅格理论上可以无限地创建 地图. 这个结果模型需要很少的存储量并且简单 准确, 整个应用程序可以实时执行.

参考文献:
[ 1] SCHULTZ A C, ADAMS W. Continuous localization using evidence grids[ J] . Proceedings of the 1998 IEEE Interna tional Conference on Robotics and Automation. 1998, 4: 2833 - 2839. [ 2] AYACHE N, FAUGERAS O D. Maintaining representations of the environment of a mobile robot[ J] . IEEE Trans Robot Automat, 1989, 5( 6) : 804- 819. [ 3] KYUOERS B J. The spatial semantic hierarchy[ J] . Artificial Intelligence, 2000, 119: 191- 233. [4] DOUCET A, FREITAS N, GORDAN N. Sequential Monte Carlo Methods in Practice[ M] . Springer- Verlag, 2001. [ 5] THRUN S, FOX D, BURGARD W. Probabilistic mapping of an environment by a mobile robot [ J] . Proceedings of the 1998 IEEE International Conference on Robotics and Au tomation, 1998, 4: 1546- 1551. [ 6] YAMAUCHI B, SCHULTZ A , ADAMS W. Mobile robot ex ploration and map building with continuous localization[ J] . Proceedings of the 1998 IEEE International Conference on Robotics and Automation. 1998, 4: 3715- 3720.

3

定位算法
Step1: 在 t 时刻通过传感器获得了机器人位

姿测量值 mt , 该值同时应用到地图创建和定位两 个算法. Step2: 假设在前一个 t - 1 瞬时地图创建已 经产生了局部地图模型, 否则调用地图创建算法 进行地图创建. 该模型提供对机器人的位姿估计 参数用 p t- 1 表示, 判断 m t 中的信息与 p t- 1 是否一 ? ? 致, 如果一致转 Step3, 否则转 Step4.

( 编辑

王小唯)


相关文档

移动机器人同时定位与地图创建自适应算法研究
移动机器人同时定位与地图创建算法研究
仪的移动机器人同时定位和地图创建
移动机器人同时定位和地图创建的一种新方法
移动机器人的同时定位和地图创建方法(200407)
基于SIFT算法的移动机器人同时定位与地图创建
面向智能移动机器人的同时定位与地图创建研究
移动机器人同时定位与地图创建研究进展
基于 SIFT 算法的移动机器人同时定位与地图创建
移动机器人即时定位与地图创建问题研究
电脑版