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

第 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 probability 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

移动机器人的同时定位和地图创建问题( S-i 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, ay, ath )T .
系统的坐标系统分为全局坐标系 Ca = ( ax, ay, ath )T 和机器人坐标系 Cr = ( x , y , H)T . 全局 坐标系以机器人出发点为坐标原点( 0, 0, 0) , 通过 里程计的累积, 机器人在全局坐标系统中相对于 起始点的位姿定义为 X = ( ax , ay, ath) T. 机器人

第7期

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

# 875 #

坐标系的 x 轴是机器人平移的速度向量, y 轴是

身体的左侧方向. 通过如下公式可以得到机器人

下一个位置的坐标:

X next =

ax ay = X + a th

cos H 0 sin H 0 # v # t + X =
w 01

f ( X , u, t , X) .

式中: u = [ v w ] t , v 和t 分别为平移和转动速度;

X 为里程计的累积误差; t 是移动的时间; X 为机

器人的当前位姿; H为机器人当前的方向. 实验发

现在短距离范围内, 里程计的测量值还是较为准 确的, 误差约为 X = 10- 3.

112 环境建模

本试验在 一个相对结构化 的室内环 境中完

成, 结构化环境可以用一组在全局坐标系中的直

线段表示出来, 直线段可以用来表示物体的表面.

每一条直线段表示环境的第 i 个/ 墙0, 定义为 w i

= [ aTax ay al ] T, 其中, 全局坐标系 Ca = ( ax , ay, cc
ath) T, av 表示全局坐 标系中墙的方向, axc , ayc 表 示全局坐标系中墙的中心, a1 表示墙的长度. 因

此提出的 环境表示 是一个 线段集 合: W =

[

w

T 1

w

T 2

,] T

.

2 地图创建算法

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

位置即位置 4 为中心.

图 1 移动栅格

211 坐标转换

坐标转换实现的是: 把在机器人坐标系中测

得物体的位置转换到全局坐标系统中的位置. 当

机器人在栅格 i 中时, 它的位置按照全局坐标系

统表示为( axr , ayr , athr )T , 声纳在机器人坐标系统

Cr

中得

到的

测距

数据

s

j r

,

j=

0, ,, 15, 描述为

xjr = ( sjr + r) cos( ajr ) , yjr = ( sjr + r ) sin( ajr ) ,

ajr = 2215 # j .

其中, r 是机器人半径, ajr 是第j 个声纳相对于正

前声纳的相对角. 此时, 假设机器人在全局坐标

系中的坐标为( aRx ,

aRy ,

a

R th

)

T,

声纳所 测到的物体

在机器人坐标系统中的坐标为( xjr , yjr , ajr )T , 则经

过坐标变换, 该物体在全局坐标系中的坐标( ax,

ay, ath )T 表示为

ax =
ay

cos aRth - sinaRth

xrj

sinaRth cos aRth

# yrj +

aRx aRy ,

ath = aRth + ajr .

212 栅格安全边界的确定

当机器人在栅格 i 的安全区域内时, 它通过

声纳传感器不断对周围环境探测, 获得足够多的

声纳信息, 以保证哈夫变换的实现. 每次当机器人

离开局部栅格 i 确定的安全边界时, 就会以机器

人的当前位置作为中心, 就会形成新的栅格 i +

1, 但是, 当机器人即将穿过栅格 i 时, 必须知道在

机器人的前面是什么. 由于这个原因, 定义了一

个内部的安全边界, 如图 1 所示的点划线, 当机器

人过点划线时, 就会产生一个新的局部栅格.

为了确定安全边界, 需要从栅格中心进行测

量, 根据超声波传感器的测量范围, 在这个范围内

进行实验寻找错误迅速递增的边界点. 试验发现

当距离大于 4 m 后错误迅速增加, 因此, 栅格的内

部安全边界确定为距离栅格中心 315 m.

# 876 #

哈尔滨工业大学学报

第 36 卷

213 地图创建的哈夫变换

哈夫变换( Hough Transform: HT ) 是对灰度图

像检测直线和其他参数曲线的一种方法. 在 x -

y 坐标平面( 输入空间) 中的一条直线可以用方程

Q= x cos H+ ysin H来描述, 在 H- Q参数空间( 哈

夫空间) 中, 直线被映射成为单个点. 如果给定在

输入空间中的一个点, 在哈夫空间中就会有无数

的直线通过该点. 在输入空间中通过点 ( xi , yi ) 的 所有直线的参数在( H, Q) 哈夫空间中形成了一条

正弦曲线:

xi sin H+ y i cos H= Q.

( 1)

哈夫变换( HT) 的实现是基于参数离散化的.

如果 H和 Q的值被离散化, 可以形成一个累加矩

阵 A( H, Q) . 参数 H被离散化成值 Hk, k = 1, ,, n, Hk - Hk- 1 = $H. 特征点( x i , y i ) 的哈夫变换按照

式( 1) 可以对 n 个Hk 值计算 Q. Q值可以被离散化 成 m 个离散的值 Qk, k = 1, ,, m 满足Qk - Qk- 1 =

$Q, 并且相应的累加矩阵 A( Hk, Qk) 是递增的. 该

过程对所有的特征点重复.

哈夫变换( HT) 有许多要注意的问题:

1) 尽管认为对 H和 Q量子化越小越能增加准

确性, 但是实际情况, 量子化程度过小会增加算法

复杂度, 影响效率, 因此合适的选择 $H和 $Q是有

必要的, 这可以通过多做几次实验来确定累加矩

阵最好的可能结果.

2) 实验表明往往由于累加矩阵的量子化错

误使哈夫变换提取的线段数远远超过要求的线段

数, 这样会使输出结果非常复杂, 为了保留最主要

的线段, 需要应用相关的算法对结果进一步处理,

如聚类算法和滤波算法.

3 定位算法

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

Step3: 结合 t - 1 时刻对机器人的位姿估计 p?t- 1 与 t 时刻传感器得到的测量值mt 提供新的对 机器人的位姿估计 p?t , 转 Step1.
Step4: 由于传感器的错误读数导致了不一致 性的存在, 并且需要抛弃机器人位置感知错误的 部分, 转 Step1.
应用本方法用 Pioneer2 移动机器人在结构化 的室内环境中实现了地图创建和定位的同时性, 取得了很好的效果, 实验结果略.
4结论
1) 提出了一个可靠的方法来处理地图创建和 定位的同时性问题. 对世界模型的估计提供给定 位算法. 反过来, 定位算法给出了机器人的准确 位置和方向估计, 这些估计又应用到地图创建算 法中去更新世界模型.
2) 用移动的局部栅格理论上可以无限地创建 地图. 这个结果模型需要很少的存储量并且简单 准确, 整个应用程序可以实时执行.
参考文献:
[ 1] SCHULTZ A C, ADAMS W. Continuous localization using evidence grids[ J] . Proceedings of the 1998 IEEE International 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 Automation, 1998, 4: 1546- 1551.
[ 6] YAMAUCHI B, SCHULTZ A , ADAMS W. Mobile robot exploration and map- building with continuous localization[ J] . Proceedings of the 1998 IEEE International Conference on Robotics and Automation. 1998, 4: 3715- 3720.
( 编辑 王小唯)


相关文档

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