基于Voronoi图的移动机器人SLAM算法

第42卷增刊1 中南大学学报(自然科学版) Vol.42 Suppl. 1 2011年9月 Journal of Central South University (Science and Technology) Sep. 2011

基于Voronoi图的移动机器人SLAM算法

李羚1，张奇志1，周亚丽1

(1. 北京信息科技大学 自动化学院，北京，100192)

摘要：针对移动机器人同步自定位与地图创建(SLAM)过程中最近邻点匹配耗费时间长问题，将一种基于Voronoi图的最近邻点算法应用到SLAM中，该算法根据Voronoi图原理对栅格地图进行2次横向扫描来获得地图上所有栅格的最近邻点，提高了机器人建图的效率，仿真结果验证了该方法的可行性和适用性。 关键词：Voronoi图；SLAM；扫描匹配；最近邻点

中图分类号：TP24 文献标志码：A 文章编号：1672 7207(2011)S1

SLAM approach with Voronoi diagram

LI Ling1, ZHANG Qi-zhi1, ZHOU Ya-li1

(1. School of Automation, Beijing Information Science & Technology University, Beijing 100192, China)

Abstract: For the time-consuming of scan matching in the SLAM, a closest point algorithm based on Voronoi diagram is applied in SLAM. It gets the closest point with two transverse scans to improve the efficiency of mapping for robot. The simulation results prove the exactness and applicability of the algorithm. Key words: Voronoi diagram; SLAM; scan matching; closest point

近年来，随着计算机技术、微电子技术、网络技术的快速发展，移动机器人的应用领域越来越广泛，从制造领域开始向非制造领域发展，海洋开发、宇宙探测、采掘、建筑、医疗、农林业、服务、娱乐等行业都提出自动化和机器人化的要求。同时，移动机器人在军事侦察、扫雷排险、防止核污染和化学污染等危险与恶劣环境中的物料搬运，特别是在一些具有危险性的操作中也具有广泛的应用。为了获得更大的独立性，人们也对机器人的灵活性及智能提出更高的要求,要求机器人能够在一定范围内自主移动且在移动中能自主完成特定的任务，增强对环境的适应能力，因而移动机器人在陌生环境下实现同步自定位与地图创建(SLAM)问题已成为众多研究人员所关注的一个焦点[1]。

1 基于粒子滤波的SLAM算法

基于Rao-Blackwellized粒子滤波的SLAM算法[2]

如图1所示，其具体算法如下：

(1) 根据初始坐标，随机生成由N个粒子位姿s0i、粒子权值为1/N组成的粒子集；

(2) 根据k 1时刻粒子集中的每个粒子位姿sk 1i

及运动模型计算k时刻粒子位姿ski；

(3) 根据由运动模型运算所得粒子位姿、机器人观测数据及观测模型对粒子集进行匹配；

(4) 根据匹配结果对粒子权值进行更新； (5) 根据粒子权值对粒子集进行重采样，去除权值小的粒子，复制权值大的粒子；