基于Voronoi地图表示方法的同步定位与地图创建

郭帅; 马书根; 李斌; 王明辉; 王越超

doi:10.3724/SP.J.1004.2011.01095

基于Voronoi地图表示方法的同步定位与地图创建

doi: 10.3724/SP.J.1004.2011.01095

郭帅^1,2, ,,
马书根^1,3,
李斌¹,
王明辉¹,
王越超¹

1.
中国科学院沈阳自动化研究所机器人学国家重点实验室沈阳 110016;
2.
中国科学院研究生院北京 100039;
3.
日本立命馆大学机器人系草津 525-8577

详细信息

通讯作者:
郭帅中国科学院沈阳自动化研究所博士研究生. 主要研究方向为移动机器人及机器人同步定位与地图创建. E-mail: guoshuai@sia.cn

计量
- 文章访问数: 2480
- HTML全文浏览量: 58
- PDF下载量: 1533
- 被引次数: 0
出版历程
- 收稿日期: 2010-12-29
- 修回日期: 2011-02-18
- 刊出日期: 2011-09-20

Simultaneous Localization and Mapping Through a Voronoi-diagram-based Map Representation

1.
State Key Laboratory of Robotics, Shenyang Institute of Automation, Chinese Academy of Sciences, Shenyang 110016, P.R. China;
2.
Graduate University, Chinese Academy of Sciences, Beijing 100039, P.R. China;
3.
Department of Robotics, Ritsumeikan University, Kusatsu-Shi 525-8577, Japan

摘要

摘要: 针对基于混合米制地图机器人同步定位与地图创建 (Simultaneous localization and mapping, SLAM)中地图划分方法不完善的问题, 提出了基于Voronoi地图表示方法的同步定位与地图创建算法VorSLAM. 该算法在全局坐标系下创建特征地图, 并根据此特征地图使用Voronoi图唯一地划分地图空间, 在每一个划分内部创建一个相对于特征的局部稠密地图. 特征地图与各个局部地图最终一起连续稠密地描述了环境. Voronoi地图表示方法解决了地图划分的唯一性问题, 理论证明局部地图可以完整描述该划分所对应的环境轮廓. 该地图表示方法一个基本特点是特征与局部地图一一对应, 每个特征都关联一个定义在该特征上的局部地图. 基于该特点, 提出了一个基于形状匹配的数据关联算法, 用以解决传统数据关联算法出现的多重关联问题. 一个公寓弧形走廊的实验验证了VorSLAM算法和基于形状匹配的数据关联方法的有效性.
- 同步定位与地图创建 /
- Voronoi图 /
- 数据关联 /
- 移动机器人
Abstract: To solve the problem that the current map division methods in the hybrid metric map based simultaneous localization and mapping (SLAM) are not complete, this paper proposes an algorithm "VorSLAM", which uses a new map representation based on Voronoi diagram. The VorSLAM builds a feature based map in the global reference frame firstly. By operating Voronoi diagram on the feature map, it then divides the whole environment space uniquely into a series of local regions, in which dense local maps are built. The feature map together with the local maps gives the environment a continuous and dense description. The map representation based on Voronoi diagram ensures that the map division is unique. In each region, the local environment coutour is proven to be described completely by the corresponding local map. A basic character of the proposed map representation is that each global feature associates with a local dense map, which is defined relative to this feature. Utilizing this character, a data association (DA) approach based on shape matching is presented to solve the ambiguity problem of traditional DA algorithms. An experiment carried out in a long arched corridor illustrates the effectiveness of VorSLAM algorithm and the shape matching data association method.
- Simultaneous localization and mapping (SLAM) /
- Voronoi diagram /
- data association (DA) /
- mobile robot

HTML全文

参考文献(1)

[1]

Durrant-Whyte H, Bailey T. Simultaneous localization and mapping: part I. IEEE Robotics and Automation Magazine, 2006, 13(2): 99-110[2] Bailey T, Durrant-Whyte H. Simultaneous localization and mapping (SLAM): part II. IEEE Robotics Automation Magazine, 2006, 13(3): 108-117[3] Smith R, Self M, Cheeseman P. A stochastic map for uncertain spatial relationships. In: Proceedings of the 4th International Symposium on Robotics Research. Massachusetts, USA: The MIT Press, 1988. 467-474[4] Thrun S, Liu Y F, Koller D, Ng A Y, Ghahramani Z, Durrant-Whyte H. Simultaneous localization and mapping with sparse extended information filters. The International Journal of Robotics Research, 2004, 23(7-8): 693-716[5] Guivant J E, Nebot E M. Optimization of the simultaneous localization and map-building algorithm for real-time implementation. IEEE Transactions on Robotics and Automation, 2001, 17(3): 242-257[6] Montemerlo M, Thrun S, Koller D, Wegbreit B. FastSLAM: a factored solution to the simultaneous localization and mapping problem. In: Proceedings of the 18th National Conference on Artificial Intelligence. Edmonton, Canada: AAAI, 2002. 593-598[7] Montemerlo M, Thrun S, Koller D, Wegbreit B. FastSLAM 2.0: an improved particle filtering algorithm for simultaneous localization and mapping that provably converges. In: Proceedings of the International Joint Conference on Artificial Intelligence. Acapulco, Mexico: Morgan Kaufmann, 2003. 1151-1156[8] Zhu Ji-Hua, Zheng Nan-Ning, Yuan Ze-Jian, Zhang Qiang. A SLAM algorithm based on central difference particle filter. Acta Automatica Sinica, 2010, 36(2): 249-257(祝继华, 郑南宁, 袁泽剑, 张强. 基于中心差分粒子滤波的SLAM算法. 自动化学报, 2010, 36(2): 249-257)[9] Hahnel D, Burgard W, Fox D, Thrun S. A highly efficient FastSLAM algorithm for generating cyclic maps of large-scale environments from raw laser range measurements. In: Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems. Washington D. C., USA: IEEE, 2003. 206-211[10] Eliazar A I, Parr R M. DP-SLAM: fast, robust simultaneous localization and mapping without predetermined land-marks. In: Proceedings of the International Joint Conference on Artificial Intelligence. Acapulco, Mexico: Morgan Kaufmann, 2003. 1135-1142[11] Eliazar A I, Parr R. DP-SLAM 2.0. In: Proceedings of the IEEE International Conference on Robotics and Automation. Washington D. C., USA: IEEE, 2004. 1314-1320[12] Nieto J, Bailey T, Nebot E. Scan-SLAM: combining EKF-SLAM and scan correlation. In: Proceedings of the 5th International Conference on Field Robotics. Port Douglas, Australia: Springer, 2005. 167-178[13] Sun R C, Ma S G, Li B, Wang Y C. Simultaneous localization and sampled environment mapping. In: Proceedings of the 48th IEEE Conference on Decision and Control and Held Jointly with the 28th Chinese Control Conference. Shanghai, China: IEEE, 2009. 6484-6489[14] Sun Rong-Chuan, Ma Shu-Gen, Li-Bin, Wang Ming-Hui, Wang Yue-Chao. Simultaneous localization and sampled environment mapping based on a divide-and-conquer ideology. Acta Automatica Sinica, 2010, 36(12): 1697-1705(孙荣川, 马书根, 李斌, 王明辉, 王越超. 基于分治法的同步定位与环境采样地图创建. 自动化学报, 2010, 36(12): 1697-1705)[15] Nieto J I, Guivant J E, Nebot E M. The hybrid metric maps (HYMMs): a novel map representation for DenseSLAM. In: Proceedings of the IEEE International Conference on Robotics and Automation. Washington D. C., USA: IEEE, 2004. 391-396[16] Nieto J I, Guivant J E, Nebot E M. DenseSLAM: simultaneous localization and dense mapping. The International Journal of Robotics Research, 2006, 25(8): 711-744[17] Neira J I, Tardos J D. Data association in stochastic mapping using the joint compatibility test. IEEE Transactions on Robotics and Automation, 2001, 17(6): 890-897[18] Barber C B, Dobkin D P, Huhdanpaa H. The quickhull algorithm for convex hulls. ACM Transactions on Mathematical Software, 1996, 22(4): 469-483[19] Aurenhammer F. Voronoi diagrams —— a survey of a fundamental geometric data structure. ACM Computing Surveys, 1991, 23(3): 345-405[20] Doh N L, Chung W K, Lee S, Oh S, You B. A robust general Voronoi graph based SLAM for a hyper symmetric environment. In: Proceeding of the IEEE/RSJ International Conference on Intelligent Robots and Systems. Washington D. C., USA: IEEE, 2003. 218-223[21] Choset H, Nagatani K. Topological simultaneous localization and mapping (SLAM): toward exact localization without explicit localization. IEEE Transactions on Robotics and Automation, 2001, 17(2): 125-137[22] Duda R O, Hart P E. Pattern Classification and Scene Analysis. New York: John Wiley and Sons, 1973. 11-15[23] Borges G A, Aldon M J. Line extraction in 2D range images for mobile robotics. Journal of Intelligent and Robotic Systems, 2004, 40(3): 267-297[24] Haralick R M. Propagating covariance in computer vision. In: Proceedings of the 12th IAPR International Conference on Pattern Recognition. Washington D. C., USA: IEEE, 1994. 493-498[25] Besl P J, McKay H D. A method for registration of 3-D shapes. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1992, 14(2): 239-256[26] Guo R, Sun F C, Yuan L. ICP based on polar point matching with application to graph-SLAM. In: Proceedings of the International Conference on Mechatronics and Automation. Changchun, China: IEEE, 2009. 1122-1127[27] Zhang Z Y. Iterative point matching for registration of free-form curves and surfaces. International Journal of Computer Vision, 1994, 13(2): 119-152[28] Lu F. Shape Registration Using Optimization for Mobile Robot Navigation [Ph.D. dissertation], University of Toronto, Canada, 1995

施引文献

资源附件(0)

访问统计