基于扩展卡尔曼滤波的同时定位与地图构建算法研究
|
摘要
移动机器人的研究涉及到智能控制技术、计算机技术、模式识别以及人工智能等许多学科,这些学科的飞速发展为移动机器人的研究带来新的动力。随着激光测距仪和其它先进传感器设备在移动机器人研究中的广泛应用,移动机器人的研究越来越受到国内外学者的普遍重视,取得了很多新的成果。
自主定位和地图构建是移动机器人研究中的两个核心问题,是移动机器人实现自主导航的基础。移动机器人的工作环境可分为室外环境和室内环境两种,本文主要针对移动机器人在室内环境下的同时定位与地图构建问题进行研究。文章首先指出了机器人同时定位与地图构建研究中存在的问题,包括制图复杂度、数据匹配难度以及定位制图关联度等,分析了常用的同时定位与地图构建方法。在此基础上引出了本研究的重点,基于卡尔曼滤波的移动机器人同时定位与地图构建(SLAM)算法,并对其算法构架、卡尔曼滤波定位等相关内容进行了介绍。本文提出了一种基于线特征的EKF-SLAM算法并对其进行了详细的阐述,给出了包括机器人运动模型、观测模型的建立、数据匹配、状态更新、地图建立、地图管理等方面的相关公式,最后以基于EKF的SLAM方案来解决移动机器人同时定位与地图构建,并进行了仿真试验和进一步的深入讨论。
The research of mobile robot involves a lot of knowledge such as intelligent control, computer science, pattern recognition and artificial intelligence.With the fast development of new technology and the wide use of advanced sensors, mobile robot has become the focus in the field of robotics and automation.
Map building and localization are two essential tasks for an autonomous mobile robot's navigation. They are important foundations to realize mobile robot navigation independently. According to working environment, it can be classified into indoor mobile robot and outdoor mobile robot.This paper aims to study simultaneous localization and mapping (SLAM) algorithm in indoor environment. The simultaneous localization and mapping (SLAM) problem is firstly introduced, based on the analysis of the localization problem and the map building problem which are two key points in the navigation techniques, including its structure, characteristics, categories and so on. It analyzes several commonly used methods of the simultaneous localization and mapping (SLAM) problem. The key point research of the paper is simultaneous localization and mapping Algorithm based on extentded Kalman filter and a line-feature based SLAM algorithm is well presented in this paper. All operations required for building and maintaining this map,such as model-setting,data association,and state-updating are described and formulated.Finally, the approach of SLAM based on EKF method has been programmed and successfully tested in the simulation work.And further experiment analysis show the Simultaneous Localization and Mapping algorithm's convergence, robustness and consistence.
自主定位和地图构建是移动机器人研究中的两个核心问题,是移动机器人实现自主导航的基础。移动机器人的工作环境可分为室外环境和室内环境两种,本文主要针对移动机器人在室内环境下的同时定位与地图构建问题进行研究。文章首先指出了机器人同时定位与地图构建研究中存在的问题,包括制图复杂度、数据匹配难度以及定位制图关联度等,分析了常用的同时定位与地图构建方法。在此基础上引出了本研究的重点,基于卡尔曼滤波的移动机器人同时定位与地图构建(SLAM)算法,并对其算法构架、卡尔曼滤波定位等相关内容进行了介绍。本文提出了一种基于线特征的EKF-SLAM算法并对其进行了详细的阐述,给出了包括机器人运动模型、观测模型的建立、数据匹配、状态更新、地图建立、地图管理等方面的相关公式,最后以基于EKF的SLAM方案来解决移动机器人同时定位与地图构建,并进行了仿真试验和进一步的深入讨论。
The research of mobile robot involves a lot of knowledge such as intelligent control, computer science, pattern recognition and artificial intelligence.With the fast development of new technology and the wide use of advanced sensors, mobile robot has become the focus in the field of robotics and automation.
Map building and localization are two essential tasks for an autonomous mobile robot's navigation. They are important foundations to realize mobile robot navigation independently. According to working environment, it can be classified into indoor mobile robot and outdoor mobile robot.This paper aims to study simultaneous localization and mapping (SLAM) algorithm in indoor environment. The simultaneous localization and mapping (SLAM) problem is firstly introduced, based on the analysis of the localization problem and the map building problem which are two key points in the navigation techniques, including its structure, characteristics, categories and so on. It analyzes several commonly used methods of the simultaneous localization and mapping (SLAM) problem. The key point research of the paper is simultaneous localization and mapping Algorithm based on extentded Kalman filter and a line-feature based SLAM algorithm is well presented in this paper. All operations required for building and maintaining this map,such as model-setting,data association,and state-updating are described and formulated.Finally, the approach of SLAM based on EKF method has been programmed and successfully tested in the simulation work.And further experiment analysis show the Simultaneous Localization and Mapping algorithm's convergence, robustness and consistence.
引文
[1] Smith R,Self M,Cheeseman P.Estimating uncertain spatial relationships in robotics[A].Proceedings of Conference on Uncertainty in Artificial Intelligence[C]. Amsterdam,North-Holland,1988,435-461
[2]徐国华,谭民.移动机器人的发展现状及其趋势.机器人技术与应用, 2001,3:7-8
[3] N Nilsson. An Application of Artificial Intelligence Techniques.In:Proc IJCAI,1969
[4] R S Mosher.Test and Evaluation of a Versatile Walking Truck. In:Proc of the off-road Mobility Res Symp Int Soc Terrain Vehicle Systems,Washington DC. 1968,359-379
[5]李磊,叶涛,谭民,陈细军.移动机器人技术研究现状与未来.机器人,2002,24(5):475-477
[6]蒋新松.未来移动机器人将是21世纪技术发展的热点.中国机械工程,2000,12(11):58-60
[7]蔡自兴,贺汉根,陈虹.未知环境中移动机器人导航控制研究的若干问题.决策与控制,2002,17(7):385-386
[8] Leonard.J,Durrant-Whyte.H F.Application of Muti-target Tracking to Sonar Based Mobile Robot Navigation,In International Conference on Decision and Control,1990
[9]马明山,朱绍文.室外移动机器人定位技术研究电工技术学报.1998,13(2):43-46
[10]Brain Yamauchi. Mobile Robots Localization in Dynamic Environments using Dead Reckoning and Evidence Grids. Proceedings of the 1996 IEEE International Conference on Robotics and Automation. 1996,1401-1406
[11]张军宇,何克忠.移动机器人THMR-V组合定位系统.计算机工程与应用.2001,37(15):68-71
[12]金妙.用于汽车导航系统的光纤陀螺.自动驾驶仪与红外技术.1999,4:27-28
[13]胡卫东.光纤陀螺发展评述.红外技术.2001, 23(5):29-33
[14]Barshan B, Durrant-Whyte.H F,An Inertial Navigation System for a Mobile Robot. Proceedings of the 1993 IEEE/RSJ International Conference on Intelligent Robotics and Systems. Yokohama, Japan, July 1993,2243-2248
[15]夏熙梅.差分GPS定位技术及应用.现代情报.2002, 22(3):99-100
[16]王军,于洪喜.差分GPS定位技术.空间电子技术.2001,1:107-110
[17]Wojtkowski. Automatic Lawn Mower Vehicle. US Patent,1992,5:163-273
[18]董再励,王光辉.自主移动机器人激光全局定位系统研究.机器人.2000,22(3):207-210
[19]崔茂源,董再励.移动机器人激光全局定位系统的算法研究.系统工程与电子技术.2001, 23(11):73-75
[20]Fukui I. TV Image Processing System. IEEE Spectrum. 1993
[21]董再励,赫颖明.一种新的基于主动路标的全方位移动机器人定位系统.机器人.2001,12(5):117-119
[22]魏芳,董再励.用于移动机器人的视觉全局定位系统研究.机器人.2000,23(5):400-403
[23]Rencken W.D. Concurrent Localization and Map Building for Mobile Robots Using Ultrasonic Sensors. Proceedings of the 1993 IEEE/RSJ International Conference on Intelligent Robotics and Systems. Yokohama,Japan,July 26-30,1993,2192-2197
[24]罗荣华,洪炳铬.移动机器人同时定位与地图创建研究进展.机器人,2004(26):183-186
[25]迟健男,徐心和.移动机器人即时定位与地图创建问题研究.机器人,2004(26):92-96
[26]N.Ayache,O.D.Faugeras. Maintaining a representation of the environment of a mobile robot. IEEE Transaction on Robotics and Automation,1989,5:804-819
[27]R.Smith,M.Self,P.Cheeseman. A stochastic map for uncertain spatial relation-ships in robotics. Autonomous Mobile Robots: Perception,Mapping and Navigation,1987,1:323-330
[28]Myung-JinJung,Hyun Myung,Sun-Gi Hong,Dong-ryeol Park,Hyoung-Ki Lee,Seok Won Bang.Structured light 2D range finder for simultaneous localization and map-building (SLAM) in home environments. Proceedings of the 2004 International Symposium in Nov. 2004,37371-37631
[29]Guivant J,Nebot E,Baiker S. Autonomous navigation and map building using laser range sensors in outdoor applications [J].Journal of Robotic Systems,2000,17 (10): 565-583
[30]Williams S.B,Newman.P,Dissanayak.C,Durrant-Whyte.H.Autonomous underwater simultaneous localisation and map building. Robotics and Automation,2000(2):1793-1798
[31]Davison A J,Nobuyuki K.3D simultaneous localization and map build in Using active vision for a robot moving on undulating terrain[A].Proceedings of the IEEE International Conference on Computer Vision an Recognization [C]. Hawail:2001(1):384-391
[32]Leonard.J,Durrant-Whyte H F. Dynamic map building for an autonomous mobile robot[J].Interna- tionl Journal of Robotics Research,1992,11(4):286-298
[33]Montemerlo,M,ThrunS. FastSLAM: a factored solution to the simultaneous localization and mapping problem[A].Proceedings of the Eighteen National Conference on Artificial Intelligence[C]. Edmonton:AAAI Press,2002,593-598
[34]Hu S,Hu D D,GuO. Landmark based navigation of mobile robots in manufacturing[A]. IEEE International Conferenceon Emerging Technologies & Factory Automatin[C].Spain:1999.18-21
[35]Newman P M. On the Structure and Solution of the Simultaneous Localization and Mapping Problem[D].Australian:The University of Sydney,1999
[36]Thrun S. Particle filters in robotics[A].Proceedings of Uncertainty in AI(UAI-2002) [C]. SanFrancisco:Morgan Kaufmann Publisher,2002,511-518
[37]Feder J S. Simultantous stochastic mapping and localization[D].USA:MIT,2001
[38]Tomatis N,Siegwart R.Combining topological and metric:A natural Integration for simultaneous localization and mapbuilding[A].Proceedings of the Fourth European Workshop on Advanced Mobile Robots[C].Sweden:2001,21-29
[39]Di Marco,M.Garulli,S.Lacroix. A set theoretic approach to the simultaneous localization and map building problem[A].Proceedings of The 39th IEEE conference on decision and control[C].Sidney: 2000,833-838
[40]Patric jensfelt,Henrik I,Christensen.Pose tracking using laser scanning and minimalistic environmental models. IEEE Transactions on Robotics and Automation,April 2001,17(2):138-147
[41]Chong K.S,Kleeman L.Accurate odometry and error modeling for a mobile robot.IEEE International Conf on Robotics and Automation, NM, USA. 2003,699-704
[42]J.A.Perez,J.A.Castellanos,J.M.M.Montiel,J.Neira,J.D.Tardos.Continuous mobile robot localization: vision vs. laser. IEEE International Conf. on Robotics and Automation,Michigan,USA, 1999,2917-2923
[43]Cang Ye,Johann Borenstein. 2-D laser scanner for mobile robot obstacle. Robotics and Automation. 2002,2512-2518
[44]Kalman R.E. A new approach to linearfiltering and prediction problems. Transaction of the ASME-journal of basic engineering,1960,35-45
[45]http://www.cs.unc.edu/
[46]R.西格沃特,I.R.诺巴克什(著),李人厚(译).自主移动机器人导论.西安交通大学出版社,2006
[47]T Bailey,E.Nebot,J.Rosenblatt,H.Durrant-Whyte.Robust Distinctive Place Recognition for Topological Maps. In Proceedings of InternationalConference on Field and Service Robotics,1999
[48]D.Sack,W.Burgard.A comparison of methods for line extraction from range data. IFAC Symposium Intelligent Autonomous Vehicles (IAV2004),2004
[49]http://www.robots.ox.ac.uk/~SSS06/Website/index.html
[50]http://www.cas.kth.se/SLAM/toc.html
[51]赵翊捷,陈卫东.基于地图的移动机器人定位技术新进展.上海交通大学学报.2002,36(10):1435-1438
[52]杨明等.基于激光雷达的移动机器人实时位姿估计方法研究.自动化学报.2004,30(5): 680-685
[53]孟凯,孙茂相,孙金根.基于主动路标的全方位移动机器人定位系统.沈阳工业大学学报.2000,22(2):148-151
[54]唐新蓬.基于图像信息处理的车辆自动驾驶控制方法.华中理工大学学报.1998,26(10):87-89
[55]李群明,熊蓉,褚健.室内自主移动机器人定位方法研究综述.机器人.2003,25(6):560-567
[56]贺伟,梁昔明.未知环境中移动机器人SLAM问题的研究进展.微计算机信息.2005,21(3):179-180
[57]王璐,蔡自兴.未知环境中移动机器人并发建图与定位(CML)的研究进展.机器人.2004,26(4):380-384
[58]苏丽颖,谭民.移动机器人构建地图的研究与发展.中国科学院研究生院学报.2002,19(2):157-161
[59]崔茂源,董再励,田彦涛,洪伟.移动机器人激光全局定位系统的算法研究.2001,24(11):73-75
[60]王磊.全区域覆盖移动机器人同时定位与地图创建技术的研究[硕士学位论文].南京理工大学,2005
[61]徐则中.移动机器人的同时定位和地图构建[博士学位论文].浙江大学,2004
[2]徐国华,谭民.移动机器人的发展现状及其趋势.机器人技术与应用, 2001,3:7-8
[3] N Nilsson. An Application of Artificial Intelligence Techniques.In:Proc IJCAI,1969
[4] R S Mosher.Test and Evaluation of a Versatile Walking Truck. In:Proc of the off-road Mobility Res Symp Int Soc Terrain Vehicle Systems,Washington DC. 1968,359-379
[5]李磊,叶涛,谭民,陈细军.移动机器人技术研究现状与未来.机器人,2002,24(5):475-477
[6]蒋新松.未来移动机器人将是21世纪技术发展的热点.中国机械工程,2000,12(11):58-60
[7]蔡自兴,贺汉根,陈虹.未知环境中移动机器人导航控制研究的若干问题.决策与控制,2002,17(7):385-386
[8] Leonard.J,Durrant-Whyte.H F.Application of Muti-target Tracking to Sonar Based Mobile Robot Navigation,In International Conference on Decision and Control,1990
[9]马明山,朱绍文.室外移动机器人定位技术研究电工技术学报.1998,13(2):43-46
[10]Brain Yamauchi. Mobile Robots Localization in Dynamic Environments using Dead Reckoning and Evidence Grids. Proceedings of the 1996 IEEE International Conference on Robotics and Automation. 1996,1401-1406
[11]张军宇,何克忠.移动机器人THMR-V组合定位系统.计算机工程与应用.2001,37(15):68-71
[12]金妙.用于汽车导航系统的光纤陀螺.自动驾驶仪与红外技术.1999,4:27-28
[13]胡卫东.光纤陀螺发展评述.红外技术.2001, 23(5):29-33
[14]Barshan B, Durrant-Whyte.H F,An Inertial Navigation System for a Mobile Robot. Proceedings of the 1993 IEEE/RSJ International Conference on Intelligent Robotics and Systems. Yokohama, Japan, July 1993,2243-2248
[15]夏熙梅.差分GPS定位技术及应用.现代情报.2002, 22(3):99-100
[16]王军,于洪喜.差分GPS定位技术.空间电子技术.2001,1:107-110
[17]Wojtkowski. Automatic Lawn Mower Vehicle. US Patent,1992,5:163-273
[18]董再励,王光辉.自主移动机器人激光全局定位系统研究.机器人.2000,22(3):207-210
[19]崔茂源,董再励.移动机器人激光全局定位系统的算法研究.系统工程与电子技术.2001, 23(11):73-75
[20]Fukui I. TV Image Processing System. IEEE Spectrum. 1993
[21]董再励,赫颖明.一种新的基于主动路标的全方位移动机器人定位系统.机器人.2001,12(5):117-119
[22]魏芳,董再励.用于移动机器人的视觉全局定位系统研究.机器人.2000,23(5):400-403
[23]Rencken W.D. Concurrent Localization and Map Building for Mobile Robots Using Ultrasonic Sensors. Proceedings of the 1993 IEEE/RSJ International Conference on Intelligent Robotics and Systems. Yokohama,Japan,July 26-30,1993,2192-2197
[24]罗荣华,洪炳铬.移动机器人同时定位与地图创建研究进展.机器人,2004(26):183-186
[25]迟健男,徐心和.移动机器人即时定位与地图创建问题研究.机器人,2004(26):92-96
[26]N.Ayache,O.D.Faugeras. Maintaining a representation of the environment of a mobile robot. IEEE Transaction on Robotics and Automation,1989,5:804-819
[27]R.Smith,M.Self,P.Cheeseman. A stochastic map for uncertain spatial relation-ships in robotics. Autonomous Mobile Robots: Perception,Mapping and Navigation,1987,1:323-330
[28]Myung-JinJung,Hyun Myung,Sun-Gi Hong,Dong-ryeol Park,Hyoung-Ki Lee,Seok Won Bang.Structured light 2D range finder for simultaneous localization and map-building (SLAM) in home environments. Proceedings of the 2004 International Symposium in Nov. 2004,37371-37631
[29]Guivant J,Nebot E,Baiker S. Autonomous navigation and map building using laser range sensors in outdoor applications [J].Journal of Robotic Systems,2000,17 (10): 565-583
[30]Williams S.B,Newman.P,Dissanayak.C,Durrant-Whyte.H.Autonomous underwater simultaneous localisation and map building. Robotics and Automation,2000(2):1793-1798
[31]Davison A J,Nobuyuki K.3D simultaneous localization and map build in Using active vision for a robot moving on undulating terrain[A].Proceedings of the IEEE International Conference on Computer Vision an Recognization [C]. Hawail:2001(1):384-391
[32]Leonard.J,Durrant-Whyte H F. Dynamic map building for an autonomous mobile robot[J].Interna- tionl Journal of Robotics Research,1992,11(4):286-298
[33]Montemerlo,M,ThrunS. FastSLAM: a factored solution to the simultaneous localization and mapping problem[A].Proceedings of the Eighteen National Conference on Artificial Intelligence[C]. Edmonton:AAAI Press,2002,593-598
[34]Hu S,Hu D D,GuO. Landmark based navigation of mobile robots in manufacturing[A]. IEEE International Conferenceon Emerging Technologies & Factory Automatin[C].Spain:1999.18-21
[35]Newman P M. On the Structure and Solution of the Simultaneous Localization and Mapping Problem[D].Australian:The University of Sydney,1999
[36]Thrun S. Particle filters in robotics[A].Proceedings of Uncertainty in AI(UAI-2002) [C]. SanFrancisco:Morgan Kaufmann Publisher,2002,511-518
[37]Feder J S. Simultantous stochastic mapping and localization[D].USA:MIT,2001
[38]Tomatis N,Siegwart R.Combining topological and metric:A natural Integration for simultaneous localization and mapbuilding[A].Proceedings of the Fourth European Workshop on Advanced Mobile Robots[C].Sweden:2001,21-29
[39]Di Marco,M.Garulli,S.Lacroix. A set theoretic approach to the simultaneous localization and map building problem[A].Proceedings of The 39th IEEE conference on decision and control[C].Sidney: 2000,833-838
[40]Patric jensfelt,Henrik I,Christensen.Pose tracking using laser scanning and minimalistic environmental models. IEEE Transactions on Robotics and Automation,April 2001,17(2):138-147
[41]Chong K.S,Kleeman L.Accurate odometry and error modeling for a mobile robot.IEEE International Conf on Robotics and Automation, NM, USA. 2003,699-704
[42]J.A.Perez,J.A.Castellanos,J.M.M.Montiel,J.Neira,J.D.Tardos.Continuous mobile robot localization: vision vs. laser. IEEE International Conf. on Robotics and Automation,Michigan,USA, 1999,2917-2923
[43]Cang Ye,Johann Borenstein. 2-D laser scanner for mobile robot obstacle. Robotics and Automation. 2002,2512-2518
[44]Kalman R.E. A new approach to linearfiltering and prediction problems. Transaction of the ASME-journal of basic engineering,1960,35-45
[45]http://www.cs.unc.edu/
[46]R.西格沃特,I.R.诺巴克什(著),李人厚(译).自主移动机器人导论.西安交通大学出版社,2006
[47]T Bailey,E.Nebot,J.Rosenblatt,H.Durrant-Whyte.Robust Distinctive Place Recognition for Topological Maps. In Proceedings of InternationalConference on Field and Service Robotics,1999
[48]D.Sack,W.Burgard.A comparison of methods for line extraction from range data. IFAC Symposium Intelligent Autonomous Vehicles (IAV2004),2004
[49]http://www.robots.ox.ac.uk/~SSS06/Website/index.html
[50]http://www.cas.kth.se/SLAM/toc.html
[51]赵翊捷,陈卫东.基于地图的移动机器人定位技术新进展.上海交通大学学报.2002,36(10):1435-1438
[52]杨明等.基于激光雷达的移动机器人实时位姿估计方法研究.自动化学报.2004,30(5): 680-685
[53]孟凯,孙茂相,孙金根.基于主动路标的全方位移动机器人定位系统.沈阳工业大学学报.2000,22(2):148-151
[54]唐新蓬.基于图像信息处理的车辆自动驾驶控制方法.华中理工大学学报.1998,26(10):87-89
[55]李群明,熊蓉,褚健.室内自主移动机器人定位方法研究综述.机器人.2003,25(6):560-567
[56]贺伟,梁昔明.未知环境中移动机器人SLAM问题的研究进展.微计算机信息.2005,21(3):179-180
[57]王璐,蔡自兴.未知环境中移动机器人并发建图与定位(CML)的研究进展.机器人.2004,26(4):380-384
[58]苏丽颖,谭民.移动机器人构建地图的研究与发展.中国科学院研究生院学报.2002,19(2):157-161
[59]崔茂源,董再励,田彦涛,洪伟.移动机器人激光全局定位系统的算法研究.2001,24(11):73-75
[60]王磊.全区域覆盖移动机器人同时定位与地图创建技术的研究[硕士学位论文].南京理工大学,2005
[61]徐则中.移动机器人的同时定位和地图构建[博士学位论文].浙江大学,2004