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

第27卷第4期2010年4月

计算机应用研究ApplicationResearchofComputers

Vo.l27No.4

Apr.2010

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

柯文德,蔡则苏,李家兰

1,2

2

1

*

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

150001)

摘 要:移动机器人同时定位与地图创建是实现未知环境下机器人自主导航的关键性技术,具有广泛的应用前景,也是目前机器人研究的热门课题之一。针对国内外近年来关于移动机器人同时定位与地图创建的研究工作进行了总结和分析,重点介绍了机器人的地图创建方法类别、基于概率理论的自主定位方法、同时定位与地图创建的问题描述及研究方法等方面的发展现状及存在的不足。关键词:机器人;地图;未知环境;同时定位与地图创建中图分类号:TP24216 文献标志码:A 文章编号:do:i10.3969/.jissn.1001-3695.2010.04.004

1001-3695(2010)04-1216-04

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

几何信息表示法、拓扑图表示法和混合表示法。

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

将整个环境分为若干相同大小的栅格{mx,y},仅仅决定每个栅格是空(mx,y=0)还是存在障碍物(mx,y=1),对环境的其他特征不感兴趣。栅格地图很容易创建和维护,机器人所了解的每个栅格信息直接与环境中某区域对应,栅格地图的更新满足贝叶斯规则:p(mt+1=Gp(z|mt+1)p(mt)。

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

指机器人收集对环境的感知,提取更为抽象的几何特征或可以建模的对象来描述环境。该表示法较为紧凑,便于位置估计和目标识别,能够将室内环境定义为面、角、边的集合或者墙、走廊、门、房间等;对于室外的环境,可以用点特征来表示环境中路标特征。

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

选用一些特定地点来描述环境空间信息,通常表示为一个图表,图中节点表示一个特定地点,连接节点的弧表示特定地点之间的路径信息。拓扑地图对于结构化环境是一个很有效的表示方法,但不适合于非结构化环境。

4)混合表示法[7]

将拓扑图定义为一系列节点,节点间的连线表示机器人某

x,y

x,y

x,y

0 引言

在未知的环境中,由机器人依靠其自身携带的传感器提供的信息建立环境模型并实现定位是目前自主移动机器人研究中的一个热点问题[1,2]。机器人需要以某种形式对环境进行描述,构建环境地图模型,以便精确定位,而环境地图的建立又取决于机器人各时刻观测点的位置。因此,机器人面临着两难的情况:为了构建环境地图模型,机器人需要知道各个时刻的位置;而机器人若要知道各个时刻的位置(即定位),则必须知道环境的地图模型。为了解决该问题,Smith与Self等人提出了同时定位与地图创建(simultaneouslocalizationandmapping,SLAM)的思想

[3]

,将地图创建和定位联合起来考虑,机器人根

据已经创建的地图校正里程计的误差,其位姿误差不会随着运动距离的增大而迅速增大,可以创建精度更高的地图;同时解决了以往未知环境中由于机器人里程计误差的无上限性造成的位姿不可靠问题。由于其重要的理论和应用价值,很多学者认为SLAM是实现真正全自主移动机器人的关键。

1 地图创建方法

目前地图创建方法很多,大致可以归为四类:栅格表示法、

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

(2006AA04Z259);国家自然科学基金资助项目(60643005)

作者简介:柯文德(1976-),男,副教授,博士研究生,主要研究方向为计算机系统结构、机器人、人工智能等(wendeke@);蔡则苏(1966-),男,副教授,博士,主要研究方向为机器人、模式识别、人工智能等;李家兰(1977-),男,讲师,硕士,主要研究方向为计算机软件理论、机器人

第4期柯文德,等:机器人同时定位与地图构建技术研究 1217

个任务的完成,每个节点对应于一个几何地图;每个几何地图都有自己的坐标系统,为局部导航、局部路径规划和避障提供参数信息。这种表示方法既具有拓扑地图的高效性,又具有尺

度地图的一致性和精确性。

通过对机器人最有可能的几个状态进行跟踪,并采用高斯求和来表征后验分布,利用卡尔曼滤波器来更新各个假设的可能性,使用贝叶斯理论根据协方差估计值确定新高斯分布的产生、旧的高斯分布的删除。

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

这些方法可以分为两类:顺序扫描匹配和全局扫描匹配。顺序扫描匹配在获取里程计的基础上对相邻的扫描进行匹配比较,通过迭代搜索最优匹配,使得两个扫描之间的匹配误差最小,如迭代最近点(iterativeclosestpoint,ICP)[24]、迭代双对应算法(iterativedualcorrespondence,IDC)[25]等。属于全局扫描匹配的有CCF[26]法、LineMatch[27]算法、APR[28]法等。

2 机器人的自主定位方法

传统的自主定位方法主要有基于场景识别的定位方法、基于航标识别的三角定位方法、基于几何特征匹配的

[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]

[8]

[9]

3 SLAM的问题描述

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

TTT

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

(mtK)T)T。其中:mtk表示第k个特征的坐标;K表示t时刻已经观测到的特征数。系统的状态可以表示为

Xt=

xtm(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)

i)

y(=i(i)Ht

i)

xt-1+$t#vt-1cos(H(t-1+wt-1$t)+wxi)(i)y(#vt-1sin(Ht-1+$tt-1+wt-1$t)+wy

(i)

H#wt-1+wHt-1+$t

(i)

(2)

i)i)

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

人质心坐标和方向角;$t为t-1时刻到t时刻的时间间隔;v、X分别是机器人的速度和角速度;wx、wy、wH分别为相应的噪声项。

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

zirzi=

ciciwr

=

(yc-yi)

-H+wB

(xc-xi)

(3)

:(xcc;wr、

1218

wB分别是对应于测量距离和方向的噪声。

计算机应用研究

w(ti))|i=1,,,N}。

3)FastSLAM算法

第27卷

机器人从初始时刻到t时刻的所有观测信息的概率表示为

p(X1:t|z1:t,u1:t)=p(x1:t,mt|z1:t,u1:t)

(4)

该算法是rao-blackwellisedparticlefilter(RBPF)的一个实例,将SLAM分解成n+1个迭代估计器:一个机器人路径估计和n个与假定路径相关的独立航标状态估计。FastSLAM滤波器中的每个粒子独立地拥有自己的地图,每个地图可以采用n

p(X1:t|z1:t,u1:t)=p(x1:t,mt|z1:t,u1:t,n1:t)

(5)

如果特征之间的对应关系是已知的,那么式(4)可以表示为

其中:n1:t={n1,n2,,,nt},nt表示机器人在t时刻可以观测到的地图中的特征。

根据贝叶斯滤波器式(4)可以表示为

p(x1:t,mt|z1:t,u1:t)=A#p(zt|xt,mt)Qp(xt|xt-1,ut-1)p(x1:

t-1,

个卡尔曼滤波器分别估计地图中n个航标的位置。假设需要k个粒子实现SLAM,FastSLAM总共有kn个卡尔曼滤波,这样时刻t时第j个粒子可以写成:

jj

Sjt={Xjr,Lj1,t,2j1,t,,,Ln,t,2n,t}

k

mt-1|z1:t-1,u1:t-1)dx1:

(6)

t-1

其中:平均值Lji,t和协方差矩阵2ji,t分别代表每个航标的后验分布的高斯分布参数。因此,FastSLAM有机地将粒子滤波器与卡尔曼滤波器集成在一起,鲁棒性地解决数据关联和多目标跟踪问题,将时间复杂度减少到O(nlogk),并解决机器人非线性化运动问题。

4)扫描匹配算法

其基本思想是将扫描特征或原始数据之间的一些度量距离最小化来对齐扫描集的重叠部分,通过搜索带有噪声的数据集之间的一致性来进行比较。不同的扫描匹配算法的区别主要在于:(a)所选择和匹配的原始数据不同;(b)所使用的度量距离类型不同;(c)对应点之间的加权不同;(d)出格点的拒绝范围不同。例如,Cox将扫描点与手绘图的线段进行匹配[29]。Lu等人[24]将扫描点与先验未知的、任意结构环境中的点进行匹配。Gutmann等人[30]利用Cox算法的计算有效性和Lu算法的通用性,以维持大闭环环境下的相容性。Jensen等人[31]基于融合了传感噪声和机器人位姿不确定的概率度量距离,建立了扫描点之间的对应性。Weiss等人[32]使用角度直方图、x直方图和y直方图间的关联来匹配扫描数据。Biber[33]提出了一种基于正态分布转换方法来解决激光扫描匹配问题等。

5)混合方法

一些混合方法可以将SLAM算法与扫描匹配算法集成在一起,如Hahnel等人[34]将FastSLAM与扫描匹配算法合并,使得里程计的读数最小,因此减少了创建大规模地图所需的粒子数。文献[35]在Hahnel等人的基础上提出了一种基于栅格的改进快速同时定位与地图生成(FastSLAM)算法,通过自适应提议分布和选择重取样减少了RBPF中的粒子数,从而减轻了粒子耗散问题。Pradalizer等人[36]使用扫描匹配算法改进了EKF的数据关联的鲁棒性。

A是保证式(6)代表概率分布的归一化因子。式(6)给出了SLAM问题的迭代形式,是SLAM问题的核心。

4 SLAM的常用方法

SLAM中所存在的方法之间的区别表现在一些基本属性上,如地图的表征(航标的笛卡尔坐标、占据栅格和多边形)、地图中的不确定性表征(高斯分布/混合高斯分布、最大似然性、粒子集合)、传感器噪声的限制、收敛的最优化、计算的复杂度、精度、广义性和鲁棒性、地图的相容性和增量性等。常用的SLAM方法有五种。

1)扩展卡尔曼滤波器(extendedKalmanfilter,EKF)方法系统状态矢量Xk定义为Xk=[Xrk,X1,,Xn]T。其中Xrk

是机器人的状态,集合M={Xi|1[i[n}表征了可观测航标的地图。机器人的运动模型主要是用来获取机器人从前一个状态Xk-1到下一个状态Xk的变化Xk=f(Xk-1,uk)+vk。其中:uk表征在时间段(tk-1,tk)所给定的控制输入信号;vk标记时变非相关的高斯噪声,其平均值为0;协方差为Qk,f(,)是在给定uk时从Xk-1映射到Xk的非线性函数。在时间k时观测到的航标的状态值可通过观测模型zk=h(Xk)+wk来描述。其中:wk是时变非相关测量噪声的随机矢量,其平均值为0;协方差矩阵为Rk;h(.)是对系统状态的观测值和状态本身之间的关系进行建模的非线性函数。基于机器人的系统模型和观测模型,EKF使用最小平均方差融合所有可以使用的状态信息,通过预测、观测和更新三步迭代法计算系统状态估计值。

2)粒子滤波器(particlefilter)算法

采用一个带权重的离散粒子的集合St={s

(i)

t

|i=1,,,

N},s(ti)=(X(ti),w(ti))表示系统的后验概率p(X0:t|z0:t)。其中:X(ti)是一个采样,表示在t时刻系统的一个可能状态;w(ti)被称为采样(粒子)的权重,且w

(i)t

5 结束语

本文对国内外近年来移动机器人同时定位与地图创建的研究工作进行了总结和分析,介绍了常用的地图创建方法与基于概率理论的机器人自主定位方法的特征及类别,描述了同时定位与地图创建的基本思想,列举并指出了同时定位与地图创建的各种研究方法的特点、现状及不足。参考文献:

[1]贺锋,秦晓丽,方勇纯.一种基于遗传算法的移动机器人自定位

方法[J].模式识别与人工智能,2009,22(1):142-147.潘薇,,>0,E

N

i=1

w

(i)t

=1;N表示粒子的

个数。与传统的扩展卡尔曼滤波器相比,粒子滤波器不需要假设系统模型服从高斯分布,可以表示任何形式的系统模型。但粒子耗散情况严重影响粒子滤波器的性能,最简单地减少粒子耗散问题的方法就是采用较大的粒子数,但该方法在实际应用上并不现实。为了减少粒子耗散问题,一些研究者采用重取样方法,从{(X(0:t)t,w(tt))|i=1,,,N}中按照由采样的权重定义的,重相等子集{(X

^(i)

0:t

,

第4期柯文德,等:机器人同时定位与地图构建技术研究 1219

定位与建图方法[J].模式识别与人工智能,2008,21(6):843-848.[3]

LEONARDJJ,DURRANT-WHYTEHF.Directedsonarsensingformobilerobotnavigation[J].AdvancedRobotics,1992,10(6):547-578.

[4]MORAVECH,ELFESAE.Highresolutionmapsfromwideangle

sonar[C]//ProcofIEEEInternationalConferenceonRoboticsandAutomation.1985:116-121.[5]

CHONGKS,KLEEMANL.Mobile-robotmapbuildingfromanad-vancedsonararrayandaccurateodometry[J].InternationalJournalofRoboticsResearch,1999,18(1):20-36.[6]

KORTENKAMPD,WEYNOUTHT.Topologicalmappingformobilerobotsusingacombinationofsonarandvisionsensing[C]//Procofthe12thNCAI.1994:979-984.

[7]MANUELA,VALEM.Mobilerobotnavigationinoutdoorenviron-ments:atopologicalapproach[D].[S..l]:UniversityofTecnicaDeLisboa,InstitutoSuperiorTecnico,2005.

[8]HASHIMOTOM,OBAF,TOMIIET.Mobilerobotlocalizationusing

colorsignboard[J].Mechatronics,1999,9(6):633-656.[9]

BERKEM,GURVITSL.Mobilerobotlocalizationusinglandmarks[J].

IEEETransonRoboticsandAutomation,1997,13(2):

wellizedparticlefilteringfordynamicBayesiannetworks[C]//ProcofConferenceonUncertaintyinArtificalIntelligence.2000:176-183.[21]MARCHETTI,GRISETTIG,LOCCHIL.Acomparativeanalysisof

particlefilterbasedlocalizationmethods[C]//ProcofRoboCupSym-posium.2006:1-12.

[22]JENSFELTP,KRISTENSENS.Activegloballocalizationforamo-bilerobotusingmultiplehypothesistracking[J].RoboticsAutomation,2001,17(5):748-760.

[23]TOMONOM,SCANA.MatchingmethodusingEuclideaninvariant

signatureforgloballocalizationandmapbuilding[C]//ProcofIEEEInternationalConferenceonRobotics&Automation.2004:866-871.[24]LUFeng,MILIOSE.E.Robotposeestimationinunknownenviron-mentsbymatching2Drangescans[J].JournalofIntelligentandRoboticSystems,1997,18(3):249-275.

[25]张鸿宾,唐积尧.多视点距离图像的对准算法[J].自动化学报,

2001,27(1):39-46.

[26]PFISTERST,ROUMELIOTISSI,BURDICKJW.Weightedline

fittingalgorithmsformobilerobotmapbuildingandefficientdatarep-resentation[C]//ProcofIEEEInternationalConferenceonRoboticsandAutomation.2003:1304-1311.

[27]WEBERJ,FRANKENL,J;RGKW,etal.Referencescanmatc-hingforglobalsel-flocalization[J].Systems,2002,40(2-3):99-110.

[28]WEBERJ,WERNERK,PUTTKAMERE.APR-globalscanmatc-hingusinganchorpointrelationships[C]//Procofthe6thInterna-tionalConferenceonIntelligentAutonomousSystems.2000:471-478.[29]COXIJ.Blanche-anexperimentinguidanceandnavigationofanau-tonomousrobotvehicle[J].IEEETransonRoboticsandAutoma-tion,1991,7(2):193-204.

[30]GUTMANNJS,KONOLIGEK.Incrementalmappingoflargecyclic

environments[C]//ProcofIEEEInternationalSymposiumonCompu-tationalIntelligenceinRoboticsandAutomation.1999:318-325.[31]JENSENB,SIEGWARTR.Scanalignmentwithprobabilisticdis-tancemetric[C]//ProcofIEEE/RSJInternationalConferenceonIn-telligentRobotsandSystems.2004:2191-2196.

[32]WEISSG,PUTTKAMEREV.Amapbasedonlaserscanswithout

geometricinterpretation[C]//ProcofInternationalConferenceonIn-telligentAutonomousSystems.1995:403-407.

[33]BIBERP.Thenormaldistributionstransform:anewapproachtola-serscanmatching[C]//ProcofIEEE/RSJInternationalConferenceonIntelligentRobotsandSystems.2003:2743-2748.

[34]HAHNELD,SCHULZD,BURGARDW.Mobilerobotmappingin

populatedenvironments[J].

JournaloftheRoboticsSocietyof

RoboticsandAutonomous

IEEETranson

251-263.

[10]MOUADDIBEM,MARHICB.Geometricalmatchingformobilero-botlocalization[J].

IEEETransonRoboticsandAutomation,

2000,16(5):542-552.

[11]HOLENSTEINAA,MULLERMA,BADREDDINE.Mobilerobot

localizationinastructuredenvironmentclutteredwithobstacles[C]//ProcofIEEEInternationalConferenceonRoboticsandAutomation.1992:2576-2581.

[12]FRESEU.AprooffortheapproximatesparsityofSLAMinformation

matrices[C]//ProcofIEEEInternationalConferenceonRoboticsandAutomation.2005:331-337.

[13]DURRANT-WHYTEH,BAILEYT.Simultaneouslocalizationand

mapping:partÑ[J].IEEERoboticsandAutomationMagazine,2006,13(3):99-108.

[14]HANRu,iLIWen-feng.Line-feature-basedSLAMalgorithm[J].

ActaAutomaticaSinica,2006,32(1):43-46.

[15]庄严,王伟.移动机器入基于激光测距和单目视觉的室内同时定

位和地图构建[J].自动化学报,2005,32(1):925-933.

[16]REKLEITISIM.Aparticlefiltertutorialformobilerobotlocaliza-tion,TechnicalReportTR-CIM-04-02[R].[S..l]:CentreforIn-telligentMachines,McGillUniversity,2004.

[17]LEONARDJJ,DURRANT-WHYTEFH.Mobilerobotlocalization

bytrackinggeometricbeacons[J].Automation,1991,7(3):376-382.

[18]BURGARDW,FOXD,HENNINGD,etal.Estimatingtheabsolute

positionofamobilerobotusingpositionprobabilitygrids[C]//ProcofNationalConferenceonArtificialIntelligence.1996:896-901.[19]DELLAERTF,FOXD,BURGARDW,etal.MonteCarlolocaliza-tionformobilerobots[C]//ProcofIEEEInternationalConferenceonRoboticsandAutomation.1999:1322-1328.

[20]DOUCETA,DeFREITASJFG,MURPHYK,etal.Rao-black-IEEETransonRoboticsand

Japan,2003,7(17):579-598.

[35]STACHNISSC,GRISETTIG,BURGARDW.Recoveringparticle

diversityinarao-blackwellizedparticlefilterforSLAMafteractivelyclosingloops[C]//ProcofIEEEInternationalConferenceonRoboticsandAutomation.2005:667-672.

[36]PRADALIZERC,SEKHAVATS.Concurrentmatching,localization

andmapbuildingusinginvariantfeatures[C]//ProcofIEEE/RSJIn-ternationalConferenceonIntelligentRobotsandSystems.2002:514-520.

本文来源：https://www.bwwdw.com/article/8m01.html