机器人同时定位与地图构建技术研究

收稿日期:2009-09-27;修回日期:2009-10-29 基金项目:广东高校优秀青年创新人才培育项目(201180);国家/8630计划资助项目

(2006AA04Z259);国家自然科学基金资助项目(60643005) 作者简介:柯文德(1976-),男,副教授,博士研究生,主要研究方向为计算机系统结构、机器人、人工智能等(wendeke@163.com);蔡则苏

(1966-),男,副教授,博士,主要研究方向为机器人、模式识别、人工智能等;李家兰(1977-),男,讲师,硕士,主要研究方向为计算机软件理论、机器人、人工智能等.机器人同时定位与地图构建技术研究*

柯文德1,2,蔡则苏2,李家兰1

(1.茂名学院计算机科学与技术系,广东茂名525000;2.哈尔滨工业大学计算机科学与技术学院,哈尔滨 150001)

摘 要:移动机器人同时定位与地图创建是实现未知环境下机器人自主导航的关键性技术,具有广泛的应用前

景,也是目前机器人研究的热门课题之一。针对国内外近年来关于移动机器人同时定位与地图创建的研究工作

进行了总结和分析,重点介绍了机器人的地图创建方法类别、基于概率理论的自主定位方法、同时定位与地图创

建的问题描述及研究方法等方面的发展现状及存在的不足。

关键词:机器人;地图;未知环境;同时定位与地图创建

中图分类号:TP24216 文献标志码:A 文章编号:1001-3695(2010)04-1216-04

do:i10.3969/.jissn.1001-3695.2010.04.004

Researchofsimultaneouslocalizationandmappinginrobot

KEWen-de1,2,CAIZe-su2,LIJia-lan1

(1.Dept.ofComputerScience,MaomingCollege,MaomingGuangdong525000,China;2.SchoolofComputerScience,HarbinInstituteofTechnology,Harbin150001,China)

Abstract:Smiultaneouslocalizationandmappingisthekeytechnologytorealizetheautonavigationforrobotintheunknownenvironment,whichhasbeenaparticularlyactivetopicofmobilerobotduetoitspotentia.lThispaperwasasurveyofthere-centresearchesonsuchareasofSLAMastypesofmapconstruction,selflocalizationbasedonprobability,descriptionofSLAManditsresearchingmethods,etc.RaisedsomeaspectsinSLAMneededtobemiprovedfinally.Keywords:robo;tmap;unknownenvironmen;tsmiultaneouslocalizationandmapping

0 引言

在未知的环境中,由机器人依靠其自身携带的传感器提供

的信息建立环境模型并实现定位是目前自主移动机器人研究

中的一个热点问题[1,2]。机器人需要以某种形式对环境进行

描述,构建环境地图模型,以便精确定位,而环境地图的建立又

取决于机器人各时刻观测点的位置。因此,机器人面临着两难

的情况:为了构建环境地图模型,机器人需要知道各个时刻的

位置;而机器人若要知道各个时刻的位置(即定位),则必须知道环境的地图模型。为了解决该问题,Smith与Self等人提出

了同时定位与地图创建(simultaneouslocalizationandmapping,

SLAM)的思想[3],将地图创建和定位联合起来考虑,机器人根

据已经创建的地图校正里程计的误差,其位姿误差不会随着运

动距离的增大而迅速增大,可以创建精度更高的地图;同时解

决了以往未知环境中由于机器人里程计误差的无上限性造成

的位姿不可靠问题。由于其重要的理论和应用价值,很多学者

认为SLAM是实现真正全自主移动机器人的关键。

1 地图创建方法

目前地图创建方法很多,大致可以归为四类:栅格表示法、几何信息表示法、拓扑图表示法和混合表示法。

1)基于栅格的地图表示法[4]

将整个环境分为若干相同大小的栅格{mx,y},仅仅决定每

个栅格是空(mx,y=0)还是存在障碍物(mx,y=1),对环境的其

他特征不感兴趣。栅格地图很容易创建和维护,机器人所了解

的每个栅格信息直接与环境中某区域对应,栅格地图的更新满

足贝叶斯规则:p(mx,yt+1=Gp(z|mx,yt+1)p(mx,yt)。

2)基于几何尺度的地图表示法[5]

指机器人收集对环境的感知,提取更为抽象的几何特征或

可以建模的对象来描述环境。该表示法较为紧凑,便于位置估

计和目标识别,能够将室内环境定义为面、角、边的集合或者

墙、走廊、门、房间等;对于室外的环境,可以用点特征来表示环

境中路标特征。

3)基于拓扑的地图表示法[6]

选用一些特定地点来描述环境空间信息,通常表示为一个

图表,图中节点表示一个特定地点,连接节点的弧表示特定地

点之间的路径信息。拓扑地图对于结构化环境是一个很有效

的表示方法,但不适合于非结构化环境。

4)混合表示法[7]

将拓扑图定义为一系列节点,节点间的连线表示机器人某第27卷第4期2010年4月 计算机应用研究ApplicationResearchofComputersVo.l27No.4Apr.2010个任务的完成,每个节点对应于一个几何地图;每个几何地图

都有自己的坐标系统,为局部导航、局部路径规划和避障提供

参数信息。这种表示方法既具有拓扑地图的高效性,又具有尺度地图的一致性和精确性。

2 机器人的自主定位方法

传统的自主定位方法主要有基于场景识别的定位方

法[8]、基于航标识别的三角定位方法[9]、基于几何特征匹配的方法[10,11],但这些方法都需要在环境中设定一些可以识别的

路标,人为地改变了环境,不能很好地表示机器人定位的不确

定性。

最近一些研究者提出了利用概率理论来描述机器人的状

态并实现定位的方法[12~16],受到了广泛的重视。在机器人和

其所处环境组成的动态系统中,根据所有的观测数据{z0:t,

(u0:t)}估计系统的当前状态xt,即计算后验概率分布p(xt|

z0:t,u0:t,m)。其中:u0:t与z0:t分别表示0~t时刻机器人的控制

信息与外部传感器的观测信息;m是已知的环境地图;xt是机

器人位姿。由于后验概率分布往往是不可计算的,需要采取某

种近似的方法来表示后验概率p(xt|z0:t,u0:t,m),决定了定位

方法的功能及其所适用的环境。

定位方法分为位姿跟踪与全局定位。位姿跟踪通常采用

扩展卡尔曼滤波器(extendedKalmanfilter)来实现[17]。该方法

采用高斯分布来近似表示机器人位姿的后验概率分布,其计算

过程主要包括三步:a)根据机器人的运动信息预测机器人的

位姿;b)将观测信息与地图进行匹配;c)将预测后的机器人位

姿以及匹配的特征计算机器人应该观测到的信息,并利用该信

息与实际观测到的信息之间的差距来更新机器人的位姿。

机器人的全局定位方法主要有五种。

1)马尔可夫定位[18]

马尔可夫定位是将机器人的状态空间离散化,计算机器人

在每一个可能状态的概率。其过程分为预测(即机器人运动

时预测其在各个可能状态的概率)和更新(即根据最新的观测

信息调整各个状态的概率)两个步骤。马尔可夫定位通过离

散化方法对后验概率分布进行p(xt|z0:t,u0:t,m)求解,从而实

现机器人的定位。

2)基于粒子滤波器的方法

Dellaert等人[19]在马尔可夫定位的基础上将粒子滤波器

用于机器人的定位,提出蒙特卡罗定位(MonteCarlolocaliza-

tion,MCL)。其主要思想是采用状态空间中一个带权重的离

散采样集来表示机器人位姿的后验概率分布,使用里程计运动

模型p(xt+1|xt,u)作为粒子滤波器提议分布。

3)基于Rao-Blackwellization滤波器的方法[20]

当系统的状态空间是高维时,由于表征概率密度分布所需

的粒子样本很大,上述的粒子滤波器方法往往难于应用。Rao-

Blackwellization滤波器的根本思想就是使用解析法评估滤波

器的一部分,使用粒子取样评估另一部分。文献[21]提出了

一种改进的Rao-Blackwellization滤波器,通过自适应提议分布

和选择重取样减少了RBPF中的粒子数,减轻了粒子耗散

问题。4)基于多假设跟踪的方法[22]通过对机器人最有可能的几个状态进行跟踪,并采用高斯

求和来表征后验分布,利用卡尔曼滤波器来更新各个假设的可

能性,使用贝叶斯理论根据协方差估计值确定新高斯分布的产

生、旧的高斯分布的删除。

5)基于激光扫描匹配技术的方法[23]

这些方法可以分为两类:顺序扫描匹配和全局扫描匹

配。顺序扫描匹配在获取里程计的基础上对相邻的扫描进

行匹配比较,通过迭代搜索最优匹配,使得两个扫描之间的

匹配误差最小,如迭代最近点(iterativeclosestpoint,

ICP)[24]、迭代双对应算法(iterativedualcorrespondence,

IDC)[25]等。属于全局扫描匹配的有CCF[26]法、LineMatch[27]

算法、APR[28]法等。

3 SLAM的问题描述

如图1所示,假设机器人在t时刻观测到了特征m1,xt=

(xt,yt,Ht)T,观测到的地图为mt=((mt1)T,(mt2)T,,,

(mtK)T)T。其中:mtk表示第k个特征的坐标;K表示t时刻已

经观测到的特征数。系统的状态可以表示为

Xt=xtmt(1)

在SLAM中有两个系统模型:观测模型和运动模型。观测

模型用p(zt|xt)表示,描述了当机器人的位姿为xt时,观测到

的信息为zt的概率。机器人的运动模型表示为p(xt|xt-1,

ut-1)。其中:ut-1=(vt-1,Xt-1)为t-1时刻里程计给出的控

制信息。vt-1和Xt-1分别表示t-1时刻机器人的速度和角速

度。运动模型描述了t时刻机器人位姿的概率分布。通常采

用式(2)所示模型来预测机器人运动:

x(i)

y(i)iH(i)t=x(i)t-1+$t#vt-1cos(H(i)t-1+wt-1$t)+wxy(i)t-1+$t#vt-1sin(H(i)t-1+wt-1$t)+wyH(i)t-1+$t#wt-1+wH(2)

其中:x(i)t-1、y(i)t-1、H(i)t-1分别为t-1时刻第i个粒子所表征的机器

人质心坐标和方向角;$t为t-1时刻到t时刻的时间间隔;v、

X分别是机器人的速度和角速度;wx、wy、wH分别为相应的噪

声项。

机器人状态与观测值之间的关系为

zirziB=RB=(xc-xi)2+(yc-yi)2+wr

arctan(yc-yi)(xc-xi)-H+wB(3)

其中:(xc,yc)分别是机器人的位置;H是机器人的方向角;wr、1217第4期柯文德,等:机器人同时定位与地图构建技术研究