移动机器人在SLAM中数据关联方法的研究
|
摘要
同步定位与地图创建(SLAM)问题是移动机器人解决在未知环境中实现自主的关键问题。然而,在未知的环境中,移动机器人系统缺乏先验的地图信息和定位信息,它只能通过对环境特征的感知与估计来进行定位,同时利用定位信息来进行地图创建。数据关联的问题是SLAM研究重点,本文的工作重点就是对SLAM中数据关联技术的相关方法进行研究与探讨。
本文根据数据关联树模型和贝叶斯图模型,提出了一种解决同时定位与地图创建中数据关联问题算法,即基于动态阈值的启发式搜索SLAM算法(DHBS_SLAM);该方法通过对数据关联树有限深度的回溯实现对错误数据的修正,在搜索的过程中使用动态阈值进行门限过滤,减少可能的数据关联的数目,在不降低数据关联正确率的情况下,提高数据关联效率,最终实现算法的在线修正过去错误数据关联。
本文对机器人相关的模型进行了研究,结合了SLAM的问题中的一般模型创建了简化的仿真平台。借助这个平台,对FastSLAM的方法,HBS_SLAM方法和DHBS_SLAM方法进行了实验,并对实验结果从关联正确率和关联时间两方面上进行了比较、分析。实验结果表明DHBS_SLAM算法是一种有效的机器人同时定位与地图创建方法。
The simultaneous localization and mapping (SLAM) problem is one of the key problems for a mobile robot to be truly autonomous in an unknown environment. However, in an unknown environment, for lack of priori map information and location information the mobile robot locates by the perception of environmental characteristics and estimate and at the same time to create map. Data association is a important part of SLAM. In this paper, we research and discuss the data association in SLAM.
In this paper, by analyzing data association tree model and Bayesian model, there is a method to resolve data association problem for SLAM which is called as an SLAM algorithm based on heuristic graph search with dynamic threshold. This method uses back-searching to revise past error data associations and uses dynamic threshold to reduce possible associations. The algorithm doesn't lower the accuracy of data association and doesn't take more time to revise the past error data associations on line.
The paper has done a lot of researches on robot's model. At the end, A simulation platform is created using the models to do experiments. Using the platform, we do experiments using FastSLAM, HBS_SLAM and DHBS_SLAM to test algorithm's performance. And do some analysises on the experiment's results. The accuracy of data association and time of data association improve that the DHBS_SLAM is a efficient algorithm for SLAM.
本文根据数据关联树模型和贝叶斯图模型,提出了一种解决同时定位与地图创建中数据关联问题算法,即基于动态阈值的启发式搜索SLAM算法(DHBS_SLAM);该方法通过对数据关联树有限深度的回溯实现对错误数据的修正,在搜索的过程中使用动态阈值进行门限过滤,减少可能的数据关联的数目,在不降低数据关联正确率的情况下,提高数据关联效率,最终实现算法的在线修正过去错误数据关联。
本文对机器人相关的模型进行了研究,结合了SLAM的问题中的一般模型创建了简化的仿真平台。借助这个平台,对FastSLAM的方法,HBS_SLAM方法和DHBS_SLAM方法进行了实验,并对实验结果从关联正确率和关联时间两方面上进行了比较、分析。实验结果表明DHBS_SLAM算法是一种有效的机器人同时定位与地图创建方法。
The simultaneous localization and mapping (SLAM) problem is one of the key problems for a mobile robot to be truly autonomous in an unknown environment. However, in an unknown environment, for lack of priori map information and location information the mobile robot locates by the perception of environmental characteristics and estimate and at the same time to create map. Data association is a important part of SLAM. In this paper, we research and discuss the data association in SLAM.
In this paper, by analyzing data association tree model and Bayesian model, there is a method to resolve data association problem for SLAM which is called as an SLAM algorithm based on heuristic graph search with dynamic threshold. This method uses back-searching to revise past error data associations and uses dynamic threshold to reduce possible associations. The algorithm doesn't lower the accuracy of data association and doesn't take more time to revise the past error data associations on line.
The paper has done a lot of researches on robot's model. At the end, A simulation platform is created using the models to do experiments. Using the platform, we do experiments using FastSLAM, HBS_SLAM and DHBS_SLAM to test algorithm's performance. And do some analysises on the experiment's results. The accuracy of data association and time of data association improve that the DHBS_SLAM is a efficient algorithm for SLAM.
引文
[1][日]白井良明.机器人工程[M].科学出版社,OHM社.2001
[2]罗荣华,洪炳铭.移动机器人同时定位与地图创建研究进展.机器人,26(2)：1892-186.
[3]李群明,熊蓉,褚健.室内自主移动机器人定位方法研究综述[J].机器人,2003,25(6)560-567.
[4]赵翊捷,陈卫东.基于地图的移动机器人定位技术新进展[J].上海交通大学学报,2002,36(10)：1435-1447.
[5]高明.基于全景视觉的弹幕SLAM系统[D].合肥工业大学,2009.
[6]Thrun S. Robotic mapping:a survey. Exploring artificial intelligence in the new millennium, Morgan Kaufmann Publishers Inc,2003,1-35.
[7]Elefes A, Moravec H. High resolution maps from wide angle sonar. Proc of the IEEE Int Conf on Robotics and Automation. St. Louis MO:IEEE Press,1985.
[8]蔡自兴,贺汉根,陈虹.未知环境中移动机器人导航控制研究的若干问题[J].控制与决策,2002,17(4)：385-390.
[9]郑宏.移动机器人导航和SLAM系统研究[D].上海：上海交通大学,2007.
[10]Randall Smith, Matthew Self, Peter Cheeseman. A stochastic map for uncertain spatial relationships[C]. Proc of the 4th Int Symposium on Robotic Research. Cambridge MA:MIT Press,1987:467-474.
[11]韩崇昭,朱洪艳,段战胜,etal.多源信息融合[M].北京：清华大学出版社,2006.
[12]王永清.同时定位与地图创建中的数据关联技术研究[D].中国海洋大学,2007.
[13]ZHANG S, XIE L H, ADAMS M. An efficient data association approach to simultaneous localization and map building[C]. IEEE International Conference 011 Robotics and Automation,2004(1):854-859.
[14]WUESOMA WS, PERERA L DL, ADAMS MD. Toward multidimensional assignment data association in robot localization and mapping[J]. IEEE Transactions on Robotics. 2006,22(2):350-365.
[15]SMITH R, SELF M, CHEESEMAN P. Extimating uncertain spatial relationships in robotics[C]. Proceedings of Conference on Uncertainty in Artificial intelligence, Amsterdam:North-Holland,1988:435-461.
[16]Houles A. Multisensor tracking of a maneuvering target in clutter[J]. IEEE Trans On Aerospace and Electronic Systems.1989,25(2):176-188.
[18]J. A. Castellanos, J. M. M Montiel, J. Neira and J. D. Tartdos. The SPmap:a probabilistic framework for simultaneous localization and map building[J]. IEEE Transactions on Robotics and Automation,1999,15(5):948-952.
[17]Samuel B. Colegrove, Samuel J. Davey. On using nearest neighbours with the probabilistic data association filter[C]. Proceedings of International Radar Conference.2000(5):53-58.
[19]B. Zhou, N K BOSE. Multitarget tracking in clutter:Fast Algorithms for data Assocation[J]. IEEE Trans On Aerospace and Electronic Systems.1993,29(2):352-353.
[20]M S Lee, Y H Kim. New data association method for automotive radar tracking[C]. In:Radar, Sonar and Navigation, IEE Proceedings,2001-10.
[21]Jose Neira, Juan D. Tardos. Data association in stochastic mapping using the joint compatibility test[C]. IEEE Transactions on Robotics and Automation.2001,17(6): 890-897.
[22]林尧瑞,马少平.人工智能导论[M].北京：清华大学出版社,1989.
[24]Hahnel D, Thnm S, Wegbreit B, et al. Towards Lazy Data Association in SLAM[M]. Robotics Research.2005:421-431.
[23]Feature Extraction and Data Association for AUVConcurrent Mapping and Localisation[C]. Proceedings of the 2001 IEEE Conference on Robotics and Automation. Seoul, Korea:2001,2785-2790.
[25]Julier S J. A sparse weight Kalman filter approach to simultaneous localization and map building[A]. Proceedings of the IEEE International Conference on Intelligent Robots and Systems.2001:1251-1256.
[26]Tomatis N, Nourbakhah I, Siegwart R. Hybrid Simultaneous Localization and Map Building closing the loop with multi-hypotheses tracking[C]. Proceedings of the IEEE International Conference on Robotics and Automation.2000:2749-2754.
[27]Tomatis N, Nourbakhah I, Siegwart R. Hybrid Simultaneous Localization and Map Building:Building:a natural integration of topological and metric[J]. Robotics and Autonomous Systems,2003:44(1):3-14.
[28]Andrew J. Davison and David W. Murray. Simultaneous Localization and Map Building using active vision[J]. IEEE Transactions On Partern Analysis And Machine Intelltgece,2002,24(7):865-880.
[29]Hans Jacob S. Federal, John J. Lenard and Christopher M. Simith. Adaptive mobile robot navigation and mapping[J]. International Journal of Robotics Research,1999,18(6):650-668.
[30]P. Hebert and S. Betge Brezetz and R. Chatila. Decoupling Odometry and exteroceptive Perception in Building a World Map of a Mobile Robot[C]. Proceedings of IEEE International Conference On Robotics and Automation,1996:757-764.
[31]Hanna Bulata and Michel Devy. Incremental Construction of a Landmark Based and Topological Model of Indoor Environments by a Mobile Robot [C]. Proceedings of IEEE International Conference On Robotics and Automation,1996:1054-1060.
[32]Nicola Tomatis, Illah Nourbakhsh and Roland Siegwart. Hybrid Simultaneous Localization and Map Building closing the loop with multi—hypotheses tracking[C]. Proceedings of the IEEE International Conference On Robotics and Automation, 2000:2449-2754.
[33]Nicola Tomatis, Illah Nourbakhsh and Roland Siegwart. Hybrid Simultaneous Localization and Map Building:a natural integration of topological and metric[J]. Robotics and Autonomous Systems,2003,44(1).
[34]蔡自兴,徐光佑.人工智能机器应用[M].北京：清华念大学出版社,2003.
[35]Wijesoma WS, Perera LD L, Adams M D. Toward multidimensional assignment data association in robot localization and mapping. IEEE Transactions on Robotics and Automation.2006,22(2).
[36]季秀才.机器人同步定位与建图中数据关联问题的研究[D].湖北：国防科技大学,2008.
[37]王磊.全区域覆盖移动机器人同时定位与地图创建SLAM技术的研究[D].江苏：南京理工大学,2005.
[38]王璐,蔡自兴,未知环境中移动机器人并发建图与定位(CML)的研究进展[J],机器人,200426(4)：380-384.
[39]Kalman R. E. A New Approach to Linear Filtering and Prediction Problems [J]. Basic Engineerine,1960:35-45.
[40]郭剑辉.移动机器人同步定位与地图创建建方法研究[D].江苏：南京理工大学,2008.
[41]邓翔.移动机器人同时定位与地图创建算法研究[D].江苏：南京理工大学,2008.
[42]S. Xhmn, D. Koller, Z. Ghahmarani, and H. Durrant-Whyte. SLAM updates require constant time School of Computer Science, Carnegie MeHonUniversity, Pittsburgh, Technical Report,2002.
[43]S. Xhmn,D. Koller,Z. Ghahmarani, and H. Durrant-Whyte. Simultaneous localization and mapping with sparse extended information filters. International Journal of Robotics Research, July-August 2004,23(7-8):693-716.
[44]Dellaert F, Fox D, Burgard W, etal. Montecarlo localization for mobile robots[C]. Proceedings of the IEEE International Conference on Robotics and Automation, Detroit,1999:1322-1328.
[45]程娅荔.基于扩展卡尔曼滤波的同时定位与地图构建算法研究.山东：中国海洋大学,2007.
[46]Arnaud Doucet, Nando De Freitas, Kevin Murphy, etal. Rao-Blackwellizedparticle filtering for dynamic Bayesian networks[C]. Proc. Of the Conf. on Uncertainty in Artificial Intelligence, UAI, Standord, CA, USA,2000:176-183.
[47]Dellaert F, Kaess M. Square Root SAM:Simultaneous Localization and Mapping via Square Root Information Smoothing[J]. Intemational Journal of Robotics Research. 2006,25(12):1181-1203.
[48]Borenstein J, Everett H. R, Feng L. Mobile robot positioning:sensors and techniques. Journal of robotic Systems. Special Issue on Mobile Robots.1997,14(4): 231-249.
[2]罗荣华,洪炳铭.移动机器人同时定位与地图创建研究进展.机器人,26(2)：1892-186.
[3]李群明,熊蓉,褚健.室内自主移动机器人定位方法研究综述[J].机器人,2003,25(6)560-567.
[4]赵翊捷,陈卫东.基于地图的移动机器人定位技术新进展[J].上海交通大学学报,2002,36(10)：1435-1447.
[5]高明.基于全景视觉的弹幕SLAM系统[D].合肥工业大学,2009.
[6]Thrun S. Robotic mapping:a survey. Exploring artificial intelligence in the new millennium, Morgan Kaufmann Publishers Inc,2003,1-35.
[7]Elefes A, Moravec H. High resolution maps from wide angle sonar. Proc of the IEEE Int Conf on Robotics and Automation. St. Louis MO:IEEE Press,1985.
[8]蔡自兴,贺汉根,陈虹.未知环境中移动机器人导航控制研究的若干问题[J].控制与决策,2002,17(4)：385-390.
[9]郑宏.移动机器人导航和SLAM系统研究[D].上海：上海交通大学,2007.
[10]Randall Smith, Matthew Self, Peter Cheeseman. A stochastic map for uncertain spatial relationships[C]. Proc of the 4th Int Symposium on Robotic Research. Cambridge MA:MIT Press,1987:467-474.
[11]韩崇昭,朱洪艳,段战胜,etal.多源信息融合[M].北京：清华大学出版社,2006.
[12]王永清.同时定位与地图创建中的数据关联技术研究[D].中国海洋大学,2007.
[13]ZHANG S, XIE L H, ADAMS M. An efficient data association approach to simultaneous localization and map building[C]. IEEE International Conference 011 Robotics and Automation,2004(1):854-859.
[14]WUESOMA WS, PERERA L DL, ADAMS MD. Toward multidimensional assignment data association in robot localization and mapping[J]. IEEE Transactions on Robotics. 2006,22(2):350-365.
[15]SMITH R, SELF M, CHEESEMAN P. Extimating uncertain spatial relationships in robotics[C]. Proceedings of Conference on Uncertainty in Artificial intelligence, Amsterdam:North-Holland,1988:435-461.
[16]Houles A. Multisensor tracking of a maneuvering target in clutter[J]. IEEE Trans On Aerospace and Electronic Systems.1989,25(2):176-188.
[18]J. A. Castellanos, J. M. M Montiel, J. Neira and J. D. Tartdos. The SPmap:a probabilistic framework for simultaneous localization and map building[J]. IEEE Transactions on Robotics and Automation,1999,15(5):948-952.
[17]Samuel B. Colegrove, Samuel J. Davey. On using nearest neighbours with the probabilistic data association filter[C]. Proceedings of International Radar Conference.2000(5):53-58.
[19]B. Zhou, N K BOSE. Multitarget tracking in clutter:Fast Algorithms for data Assocation[J]. IEEE Trans On Aerospace and Electronic Systems.1993,29(2):352-353.
[20]M S Lee, Y H Kim. New data association method for automotive radar tracking[C]. In:Radar, Sonar and Navigation, IEE Proceedings,2001-10.
[21]Jose Neira, Juan D. Tardos. Data association in stochastic mapping using the joint compatibility test[C]. IEEE Transactions on Robotics and Automation.2001,17(6): 890-897.
[22]林尧瑞,马少平.人工智能导论[M].北京：清华大学出版社,1989.
[24]Hahnel D, Thnm S, Wegbreit B, et al. Towards Lazy Data Association in SLAM[M]. Robotics Research.2005:421-431.
[23]Feature Extraction and Data Association for AUVConcurrent Mapping and Localisation[C]. Proceedings of the 2001 IEEE Conference on Robotics and Automation. Seoul, Korea:2001,2785-2790.
[25]Julier S J. A sparse weight Kalman filter approach to simultaneous localization and map building[A]. Proceedings of the IEEE International Conference on Intelligent Robots and Systems.2001:1251-1256.
[26]Tomatis N, Nourbakhah I, Siegwart R. Hybrid Simultaneous Localization and Map Building closing the loop with multi-hypotheses tracking[C]. Proceedings of the IEEE International Conference on Robotics and Automation.2000:2749-2754.
[27]Tomatis N, Nourbakhah I, Siegwart R. Hybrid Simultaneous Localization and Map Building:Building:a natural integration of topological and metric[J]. Robotics and Autonomous Systems,2003:44(1):3-14.
[28]Andrew J. Davison and David W. Murray. Simultaneous Localization and Map Building using active vision[J]. IEEE Transactions On Partern Analysis And Machine Intelltgece,2002,24(7):865-880.
[29]Hans Jacob S. Federal, John J. Lenard and Christopher M. Simith. Adaptive mobile robot navigation and mapping[J]. International Journal of Robotics Research,1999,18(6):650-668.
[30]P. Hebert and S. Betge Brezetz and R. Chatila. Decoupling Odometry and exteroceptive Perception in Building a World Map of a Mobile Robot[C]. Proceedings of IEEE International Conference On Robotics and Automation,1996:757-764.
[31]Hanna Bulata and Michel Devy. Incremental Construction of a Landmark Based and Topological Model of Indoor Environments by a Mobile Robot [C]. Proceedings of IEEE International Conference On Robotics and Automation,1996:1054-1060.
[32]Nicola Tomatis, Illah Nourbakhsh and Roland Siegwart. Hybrid Simultaneous Localization and Map Building closing the loop with multi—hypotheses tracking[C]. Proceedings of the IEEE International Conference On Robotics and Automation, 2000:2449-2754.
[33]Nicola Tomatis, Illah Nourbakhsh and Roland Siegwart. Hybrid Simultaneous Localization and Map Building:a natural integration of topological and metric[J]. Robotics and Autonomous Systems,2003,44(1).
[34]蔡自兴,徐光佑.人工智能机器应用[M].北京：清华念大学出版社,2003.
[35]Wijesoma WS, Perera LD L, Adams M D. Toward multidimensional assignment data association in robot localization and mapping. IEEE Transactions on Robotics and Automation.2006,22(2).
[36]季秀才.机器人同步定位与建图中数据关联问题的研究[D].湖北：国防科技大学,2008.
[37]王磊.全区域覆盖移动机器人同时定位与地图创建SLAM技术的研究[D].江苏：南京理工大学,2005.
[38]王璐,蔡自兴,未知环境中移动机器人并发建图与定位(CML)的研究进展[J],机器人,200426(4)：380-384.
[39]Kalman R. E. A New Approach to Linear Filtering and Prediction Problems [J]. Basic Engineerine,1960:35-45.
[40]郭剑辉.移动机器人同步定位与地图创建建方法研究[D].江苏：南京理工大学,2008.
[41]邓翔.移动机器人同时定位与地图创建算法研究[D].江苏：南京理工大学,2008.
[42]S. Xhmn, D. Koller, Z. Ghahmarani, and H. Durrant-Whyte. SLAM updates require constant time School of Computer Science, Carnegie MeHonUniversity, Pittsburgh, Technical Report,2002.
[43]S. Xhmn,D. Koller,Z. Ghahmarani, and H. Durrant-Whyte. Simultaneous localization and mapping with sparse extended information filters. International Journal of Robotics Research, July-August 2004,23(7-8):693-716.
[44]Dellaert F, Fox D, Burgard W, etal. Montecarlo localization for mobile robots[C]. Proceedings of the IEEE International Conference on Robotics and Automation, Detroit,1999:1322-1328.
[45]程娅荔.基于扩展卡尔曼滤波的同时定位与地图构建算法研究.山东：中国海洋大学,2007.
[46]Arnaud Doucet, Nando De Freitas, Kevin Murphy, etal. Rao-Blackwellizedparticle filtering for dynamic Bayesian networks[C]. Proc. Of the Conf. on Uncertainty in Artificial Intelligence, UAI, Standord, CA, USA,2000:176-183.
[47]Dellaert F, Kaess M. Square Root SAM:Simultaneous Localization and Mapping via Square Root Information Smoothing[J]. Intemational Journal of Robotics Research. 2006,25(12):1181-1203.
[48]Borenstein J, Everett H. R, Feng L. Mobile robot positioning:sensors and techniques. Journal of robotic Systems. Special Issue on Mobile Robots.1997,14(4): 231-249.