基于动态阈值启发式图搜索SLAM算法.doc

基于动态阈值启发式图搜索的SLAM算法
基于动态阈值启发式图搜索的SLAM算法 第37卷
,
第17期

计算机工程
ComputerEngineering
20I1年9月
September2011
?
人工智能及识别技术?文章编号:1ooo_3428(2011)17—185—3文献标识码;A中田分类号:TP301?6
基于动态阈值启发式图搜索的SLAM算法
冯林,柴红霞,孙焘,殷志远
(大连理工大学创新实验学院,辽宁大连116023)
摘要:针对当前多数SLAM数据关联算法存在不能在线修正的问题,
回溯机制实现对错误数据的修正,在搜索过程中使用动态闽值进行门限过滤,减少可能的数据关联的数目,在不降低数据关联正确率的情
况下,,该算法可有效地降低运算时间. 关健词:数据关联;启发式图搜索;动态阈值;在线修正;回溯
SLAMAlgorithmBased0nHeuristicGraphSearch withDynamicThreshold
FENGLin,CHAIHong-xia,SUNTao,YINZhi-yuan (SchoolofInnovationExperiment,DalianUniversityofTechnology,Dalian116023,China)
[Abstract]Aimingattheproblemthatmostofdataassociationalgorithmcan'tamendpasterro
rassociationsonline,thispaperpresentsflheuristic

ndpasterrorassociationsandusesdynamicthreshold 'tlowertheaccuracyof
dataassociationbutraisetheefficiencyofdata .
[Keywordsldataassociation;heuristicgraphsearch;dynamicthreshold;correctiononline;r
ecall
DOI:.1000—
1概述
在完全未知环境中移动机器人依靠自身所携带的传感器
获取环境的感知信息,创建周围环境的地图,同时利用所创
建的地图实现自身定位,即同时定位和地图创建(Simultaneous
LocalizationandMappingBuilding,SLAM)问题是移动机器人
[1】中,提出了
基于扩展的卡尔曼滤波(ExtendedKalmanFiltering,EKF)的统
计地图,其中数据关联是它的一个难点.
数据关联是建立在不同时间,不同地点的传感器测量之
间,传感器测量与地图特征之间或者地图特征之间的对应关
系,以确定它们是否源于环境中同一物理实体的过程..不
同于一般简单的定位,SLAM算法对数据关联非常敏感,错
误的数据关联不仅影响机器人的定位,还会影响地图的建立,
直接导致算法的不一致性及发散J.
当前大多数数据关联算法确定关联假设后就不能修改,
如最近邻算法,
性数据关联的算法是一种启发式搜索算法,通过回溯方法
实现了修正过去错误的数据关联,但是因为该方法需要计算
维数较大矩阵的逆,[8】提出
的基于一种关联树回溯算法(FullSLAMwithBacktracking SearchDataAssociation,BTK—
SLAM)是在惰性数据关联上的
一
种改进,将对数据关联树的搜索和最小二乘的SLAM状态 估计的算法相结合,实现了修正过去错误的数据关联,通过 相应的剪枝,有效减小了运算量,这种算法是一种启发式搜 , 进行了一些不必要的运算和存储.