基于粒子滤波器的移动机器人定位和地图创建研究进展.pdf
《基于粒子滤波器的移动机器人定位和地图创建研究进展.pdf》由会员分享，可在线阅读，更多相关《基于粒子滤波器的移动机器人定位和地图创建研究进展.pdf（10页珍藏版）》请在冰点文库上搜索。
第29卷第3期2007年5月机器人ROBOTVo129No3May，2007文章编号：
12-0446（2007）03-0281-09基于粒子滤波器的移动机器人定位和地图创建研究进展余洪山，王耀南（湖南大学电气与信息工程学院，湖南长沙410082）摘要：
首先，对粒子滤波器的原理和研究进展进行了综述然后，介绍了基于粒子滤波器的移动机器人定位研究进展其次，给出了粒子滤波器在移动机器人地图创建领域的最新成果最后，对粒子滤波器在移动机器人研究领域的未来发展方向进行了展望关键词：
粒子滤波器；蒙特卡洛定位；移动机器人地图创建；移动机器人定位；移动机器人同步地图创建和定位中图分类号：
TP24文献标识码：
AAReviewonMobileRobotLocalizationandMapbuildingAlgorithmsBasedonParticleFiltersYUHong-shan，WANGYaonan（CollegeofElectricalandInformationEngineering，HunanUniversity，Changsha410082，China）Abstract：
Firstly，theresearchprogressandprincipleofparticlefiltersareoverviewedSecondly，theprogressofmobilerobotlocalizationbasedonparticlefiltersisdescribedThirdly，therecentworksofparticlefiltersinmapbuildingfornobilerobotsarepresentedFinally，thefuturedirectionsofparticlefiltersinmobilerobotaresummarizedKeywords：
particlefilter；MonteCarlolocalization；mobilerobotmapbuilding；mobilerobotlocalization；SLAM1引言（Introduction）粒子滤波器（particlefilter）是一种基本统计工具，其核心是基于贝叶斯采样估计的顺序重要采样（SequentialImportanceSampling，SIS）滤波思想，通常也称之为Bootstrap滤波器、蒙特卡洛滤波器、Condensation算法和SurvivaloftheFittest算法，开始成功应用于目标跟踪、语音识别、移动机器人定位、地图创建、故障诊断、统计分析等领域粒子滤波器具有可逼近任意概率分布的特性，并且计算简单方便，与传统卡尔曼滤波器方法、马尔可夫算法相比，具有其特定的优越性Dellaert等和Fox等。
分别独立提出将粒子滤波器应用于移动机器人定位研究中，即蒙特卡洛定位算法（MonteCarloLocalization，MCL）此后算法被研究人员广泛采用和扩展，迅速成为继EKF模型、马尔可夫模型后移动机器人定位领域的一个新的研究热点在此基础上，研究人员将粒子滤波器引入地图创建研究，提出了一系列移动机器人同步地图创建和定位方案，如FastSLAM算法，B、粒子滤波器和其他智能计算方法的复合地图创建方法等，得到了移动机器人地图创建研究人员的广泛认可本文拟对粒子滤波器在移动机器人定位、地图创建等应用领域的最新研究进行综述，分析和总结该类算法的优缺点和可能研究方向2粒子滤波器原理和研究进展（There-searchprogressandprincipleofparticlefilters）粒子滤波器的研究源于Hammersley等提出的基本SIS方法1993年Gordon等提出了一种新的基于SIS的Bootstrap非线性滤波方法，奠定了粒子滤基金项目：
国家自然科学基金资助项目（60375008）；教育部博士点基金资助项目（20030532004）；湖南大学优秀博士论文创新基金资助项目（521218006）收稿日期：
20060703维普资讯http:
/282机器人2007年5月波算法的基础，随后粒子滤波器的研究取得了迅速发展，代表性的如Liu等提出的连续重要性采样方法、Kitagawa等提出的蒙特卡洛滤波器和平滑器方法、Isard等提出的Condensation算法、Crisan等提出的连续时间滤波器方法等上述研究为粒子滤波器算法提供了坚实的理论基础和研究框架，并使粒子滤波器的研究逐步走向应用21粒子滤波器原理及关键技术如图1所示，粒子滤波器通过粒子集和粒子对应权值组成的随机采样数据集合S（k）表示相应的概率分布P（），以有限样本点的求和运算取代积分运算，从而获得状态最小方差估计用数学语言描述如下：
对平稳随机过程，假定七一1时刻系统的后验概率密度为P（一。
），依据一定原则选取n个随机样本点，k时刻获得测量信息后，经过状态和时间更新过程，n个粒子的后验概率密度可近似为P（J：
）随着粒子数目的增加，粒子的概率密度函数逐渐逼近状态的概率密度函数，粒子滤波估计即达到最优贝叶斯估计的效果粒子滤波算法摆脱了解决非线性滤波问题时随机量必须满足高斯分布的制约条件，并在一定程度上解决了粒子数匮乏问题，因此近年来该算法在许多领域得到成功应用图1粒子滤波器算法单次迭代处理对应的概率密度和粒子集Fig1Theprobabilitydensitiesandparticlesetsforoneiterationoftheparticlefiltersalgorithm假设通过次迭代处理，采样集合s（k）可精确逼近实际概率分布在每个时刻t，定义随机测量数据，：
。
，其中表示时刻n的第m个粒子，为相应粒子的权值，：
是信号的第m个采样轨迹如果这些粒子集均根据观测量和基于概率分布p（：
f。
：
）的采样轨迹而获取，则基于式
（1）近似相应的概率分布：
M|P（IZl：
n）一6（一：
）
（1）粒子滤波器包括三部分：
1）生成粒子集（采样步骤）；2）粒子权值计算（重要性步骤）；3）重采样211生成粒子集粒子集是根据如式
（2）所示的重要性概率密度函数7（）提取生成的，通过迭代处理可计算得到粒子的权值，如式（3）所示一仃（：
）=仃（。
）兀仃（。
：
一，。
：
）
（2）7（f，。
：
）（3）重要性概率分布7r（I，。
：
）在粒子滤波器设计中扮演着非常重要角色，因为它负责生成表示期望概率密度的粒子集如果提取的粒子集是在概率密度较小的区域内，则根据粒子集和相关权值获得的估计值也会很小，则对信号的后续跟踪处理可能会发散反之，如果在概率密度非常高的区域提取粒子集，则粒子滤波器的性能会大大增强有人提出p（。
，）是最优重要性函数，但缺陷在于难以采样和对粒子集权值进行更新，因为需要积分运算J，因此通常采用次优方案，如局部线性化、基于无先导变换的高斯近似法、基于辅助粒子滤波器的两步骤获取方法等212重要性步骤重要性步骤包括两步：
权值的计算和归一化令重要性函数如式
（2）所示，则权值更新方式如下：
（4）7丁xnI1：
n一1，01：
n，归一化处理如下：
，（m）：
=_（5）nL，JWn213重采样粒子滤波器的一个重要问题是粒子集权值的退化，即随着时间的增长，一部分权值变得非常大，而其余的部分则变得微不足道重采样就是要剔除较小权值的采样，从而集中于显著权值的采样进行处理采样过程中使用的标准算法有多种，如残差重采样、分支校正、系统重采样和带有拒绝控制的采样方法通常，基本的随机重采样算法步骤如下
（1）从中按照与标准归一化重采样函数成比例的概率分别独立提取x，其中m=1，和iJ1，与这些采样对应的新权值分别为：
W：
Of（m）（6）
（2）返回新的随机测量数据：
维普资讯http:
/第29卷第3期余洪山等：
基于粒子滤波器的移动机器人定位和地图创建研究进展283x，”M（7）这里i代表重采样后粒子集在内存中的索引号上述粒子滤波器算法的表示具有一定程度上的通用性例如，粒子滤波器常规直接采样方法是选择=当没有重采样处理时，对应的=1辅助粒子滤波器重采样方法是设置n：
州=：
驯P（+f：
）和7r（）=p（l：
），其中为平均值，即与概率密度P（：
）相关的数据变量某些重采样算法（例如RR），利用数组复制因子r替代数组索引i，复制因子表示在重采样处理中每个粒子被复制的次数然后重采样过程根据采样r，其对应的支持量由粒子集定义重采样通过集中粒子集到高后验概率分布的区域以提高对未来状态的估计，但是由于提高了估计的方差，所以降低了当前估计的精度因此，重采样的实施必须小心，可预先估计进行重采样的必要性22粒子滤波器算法存在的问题与研究热点最新的关于粒子滤波器算法的研究主要集中体现在重要性函数的设计、降低计算复杂度条件下的重采样策略、降低计算复杂度条件下的次优算法、粒子滤波器的收敛性结论等方面对于粒子滤波器而言，粒子数匮乏是其主要缺陷，即随着迭代次数增加，粒子丧失多样性的现象Doucet等加从理论上证明了SIS算法出现粒子数匮乏现象的必然性，而最有效的解决方法是选择重要性函数和采用重采样方法为解决粒子数匮乏问题，研究人员也提出了很多针对状态空间模型的改进算法，如辅助变量粒子滤波算法、局部线性化方法、拒绝采样方法等在重采样改进方法上，Higuchi等提出通过引入遗传算法和进化算法，增加重采样过程中粒子的多样性，Fox等则根据滤波性能动态调整粒子数3基于粒子滤波器的移动机器人定位（Mobilerobotlocalizationbasedonparticlefilters）Dellaert等和Fox等叫最初将粒子滤波器算法应用于移动机器人定位，形成了一个新的移动机器人定位研究方向蒙特卡洛定位算法在此基础上，研究人员针对算法的计算复杂度、实时性、可靠性等方面做了进一步研究，并开始广泛应用于基于声纳、激光和视觉传感器等类别传感器的移动机器人系统定位中，成为继EKF模型、HMM模型之后新的移动机器人定位模型31标准MCL算法原理和特性311MCL算法原理和步骤MCL定位算法集成了机器人感知模型和运动模型。
，利用个加权随机采样或粒子集合S=s，加l=1，N表示机器人位姿后验估计概率Bel（），算法基本原理可表示为：
Bel（）=P（ld。
）（8）Bel（X）S（9）这里为t时刻对应的状态，d表示从uf30到t的数据t时刻机器人位姿的概率分布如式（10）所示：
Bel（f）=P（l0f，Mf一1，0，Mf一2，0o）=（0）Jp（，M）ef（，）_lJ（10）其中o。
“。
分别对应移动机器人传感器测量数据和运动控制的测量数据，条件概率P（一，“）为机器人运动模型，P（O，）代表机器人感知模型，77为归一化常量方程（10）为MCL算法的基础机器人运动过程中，不断生成机器人位姿的采样集合，根据粒子滤波器实现对机器人状态的预测和更新，通过多次迭代处理来精确逼近位姿的后验分布估计利用MCL算法进行移动机器人全局定位，主要可以分为采样、预测、更新和权值归一化四个步骤，详细步骤见图2，其中初始位姿概率在机器人所在空间范围内呈均匀分布，加权值统一为1m拍
（1）根据Bel（一1）采集状态，按照由重要性因子P：
一。
规定的权值：
一，从表示Bel（一1）的采样集合S中随机抽取采样z：
（2）预测：
根据上次运算获取的状态集合s和机器人运动控制量的测量信息预测当前机器人的位姿状态P（，一，“，），对于状态集合s中的每个采样：
一，根据P（一，“），抽取一个采样z通过上述操作，获取一个新的集合s来近似预测分布P（ld），此时集合s并没有考虑t时刻任何传感器测量值（3）更新阶段：
在此阶段，我们考虑传感器测量值0，并对s冲的每个采样值进行加权处理，其权值为l-p（ol），即给定o时预测值的可信度（4）权值归一化：
对于个采样，分别对其权值进行归一化处理，获得t时刻的采样集合S=（：
，维普资讯http:
/机器人2007年5月）fi=1，2，从而获得关于Bel（x）的采样近似1，输入：
5=（，）Ji：
1，表示信任度
（一），控制测量变量一l，观测量Y2S：
=西，d=0初始化3Fori：
1，do生成个采样4重采样：
从先前的信任度中获取状态从离散分布中根据s的权值获取索引为的采样5采样：
预测下一状态基于和“，按p（一l一）获取采样：
6“=P（Y。
）计算重要性权值7Ot：
=Ot+”更新归一化因子8S：
=Su（，0）新采样插入采样集9endd010for：
1，do权值归一化处理11：
12enddol3etu71S图2MCL算法基本原理和步骤Fig2ThebasicprincipleandstepsofMCLalgorithm从而q：
=p（一。
，“）Bel（）对应重要性采样后的预测分布，用于近似期望后验概率分布：
P（of）P（f“一】，一1）Bel（一1），、厂上述更新和迭代处理步骤如图3所示，图中黑点表示机器人位姿的采样分布从图3（a）（e）可以看出，机器人位姿从随机分布逐渐收敛，最终收敛于实际机器人位姿，收敛速度与采样数目直接相关：
O（1-）312基本MCL算法的优点和特性MCL为在线算法，可作为Any-time算法应用，而定位精度与时间相关，采样集合的尺寸在计算精度和计算复杂度之间达到一种平衡相对于其他定位方法，基于采样表示MCL方法的优点如下，m：
1）与卡尔曼滤波器方法相比，可以表示多模分布，并可实现机器人的全局定位；2）与基于栅格的马尔可夫定位方法相比，能以相当高的频率集成测量数据；3）与固定尺寸栅格单元的马尔可夫定位方法相比，具有更高的定位精度，原因在于采样中对应的状态表示没有被离散化；4）易于实施（a）算法初始化（b）定位处理中（c）成功定位图3用于全局定位的MCL算法处理过程Fig3TheprocessofMCLalgorithmforgloballocalizationIo然而算法也存在不足，其原因在于估计的随机性例如，如果采样集的尺寸较小，机器人可能仅因为MCL没能够生成正确位置的一个采样而导致失去对其位置的跟踪算法也不适用于机器人绑架问题，因为一旦机器人处于绑架状态，则可能在机器人新位姿附近没有合适的采样因此，当传感器不足够准确时，上述基本的MCL算法性能会急速下降极端情况下，常规MCL算法在传感器信息无噪声干扰时也会失败32改进MCL算法为避免和减少常规MCL算法的缺陷，研究人员提出了多种改进方案Thrun等提出了混合MCL，算法综合了常规MCL和双MCL方法算法通过交换MCL算法中预测分布和重要性权值因子的角色，转换MCL的采样过程，其中常规MCL首先利用里程计估计新位姿，然后利用传感器测量数据评价这次采样的重要性；双MCL方法利用最近传感器测量数据估计位姿，然后利用里程计评价估计值与机器人先前概率值和里程计数据的符合程度上述每种方法均不是完美的，但是复合起来，效果非常好特别是，当采样集合尺寸较小时（例如50个采样），混合MCL算法效果良好，相比先前的MCL算法，可以更快地维普资讯http:
/第29卷第3期余洪山等：
基于粒子滤波器的移动机器人定位和地图创建研究进展285从机器人绑架问题中恢复出来然而粒子滤波器表示能力的提高，是以高计算复杂性为代价的如何实现粒子滤波器的在线、实时估计引来了新的研究课题Kwok等提出了一种实时粒子滤波器，解决由于计算资源的限制带来的局限性方法不再舍弃传感器测量数据，而是将滤波器更新过程中到来的所有采样放入不同的观测集合中这里，实时粒子滤波器利用混合采样集合代表状态空间分布，因此避免了由于独立采样数目的不足导致的滤波器分歧问题混合分量的权值通过采用蒙特卡洛近似梯度实现最优化处理，以减少混合表示引入的近似误差，最大程度上接近最优后验分布粒子滤波器算法执行每次更新的时间复杂度与估计所需的采样数目成线性关系因此人们对采样的有效使用进行了研究，以保持采样集合为合理尺寸Thrun等提出在后验估计中加入观测采样，从而动态控制采样集合数目，但是该方法需要可有效生成采样的传感器模型Gilks等提出引用MCMC（MarkovChainMonteCarlo）步骤提高基于采样表示的后验估计性能；Vlassis等提出采用辅助粒子滤波器，通过加入一个步骤减少预测分布和目标实际分布之问的误匹配，从而减少重要性权值变化，提高重要性采样的效率Fox等指出，在估计步骤中自适应选择采样集合数目可大大提高粒子滤波器的效率，并给出Kul1backLeibler距离（KullbackLeiblerdistance，KLD）采样解决方案ISKLD采样方法的主要思想在于限制粒子滤波器的采样表示引入的近似误差，如果采样概率集中于一小部分状态空间，则选择小数目采样，而如果状态不确定性较高，则选择大数目采样Kwok将KLD采样原理用于其提出的实时粒子滤波器算法中，形成了自适应实时粒子滤波器，进一步提高了算法的执行效率33其他MCL算法研究MCL定位方法不仅在测距类移动机器人系统中取得成功，在基于视觉传感器的机器人系统中也取得了成功，该类算法通常称之为Condensation算法Dellaert等_9将标准的MCL算法应用于装载有视觉传感器的移动机器人系统，解决了卡尔曼滤波器无法实现高不确定性环境下的定位的难题Vlassis等为解决图像的高维传感器观测和位置观测模型问题，使用基于NN（NearestNeighbour）条件概率估计的逆非参数观测模型，以解决图像遮挡和机器人绑架问题，方法成功应用于基于全景摄像机的室外移动机器人自主定位Jensfeh等_3。
通过TBF算法提取机器人环境中的有效路标特征，然后利用Condensation算法实现机器人的实时动态定位Lenser等_3提出当机器人丢失时，在MCL算法中加入传感器采样，即传感器重置定位算法，并成功应用于RoboCup99索尼行走机器人系统中，可在有限计算能力下实现机器人的鲁棒定位Wolf等提取环境图像不变特征作为路标，根据环境地图为数据库中的每个图像抽取可能视点集合，然后结合蒙特卡洛定位算法实现对机器人的可靠定位与跟踪Linaker等_3利用移动机器人装载全景摄像机执行基于外观的实时全局定位处理算法直接对全景摄像机图像进行处理，生成低维旋转恒定特征向量利用这些特征向量，粒子滤波器实现移动机器人位姿的精确连续估计4基于粒子滤波器的移动机器人地图创建（Mobilerobotmap-buildingbasedonparticlefilters）Montemerlo等12,13首先提出了FastSLAM方法，该方法将粒子滤波器和扩展卡尔曼滤
升级会员 