A multilevel relaxation algorithm for simultaneous localization and mapping

被引:185
作者
Frese, U [1 ]
Larsson, P
Duckett, T
机构
[1] Univ Bremen, FB3, TZI, BISS,Bremen Inst Safe Syst, D-28334 Bremen, Germany
[2] NamaTec AB, SE-69127 Karlskoga, Sweden
[3] Univ Orebro, Dept Technol, AASS, S-70182 Orebro, Sweden
关键词
Galerkin multigrid; Gauss-Seidel relaxation; metric-topological maps; mobile robot navigation; simultaneous localization and mapping (SLAM);
D O I
10.1109/TRO.2004.839220
中图分类号
TP24 [机器人技术];
学科分类号
080202 ; 1405 ;
摘要
This paper addresses the problem of simultaneous localization and mapping (SLAM) by a mobile robot. An incremental SLAM algorithm is introduced that is derived from multigrid methods used for solving partial differential equations. The approach improves on the performance of previous relaxation methods for robot mapping, because it optimizes the map at multiple levels of resolution. The resulting algorithm has an update time that is linear in the number of estimated features for typical indoor environments, even when closing very large loops, and offers advantages in handling nonlinearities compared with other SLAM algorithms. Experimental comparisons with alternative algorithms using two well-known data sets and mapping results on a real robot are also presented.
引用
收藏
页码:196 / 207
页数:12
相关论文
共 36 条
[1]  
[Anonymous], 2002, 7 INT C SIM AD BEH
[2]  
BEESON P, 2003, P IJCAI WORKSH REAS, P15
[3]  
Bengtsson O, 2001, IROS 2001: PROCEEDINGS OF THE 2001 IEEE/RJS INTERNATIONAL CONFERENCE ON INTELLIGENT ROBOTS AND SYSTEMS, VOLS 1-4, P1931, DOI 10.1109/IROS.2001.976356
[4]  
BOSSE M, IN PRESS INT J ROBOT
[5]  
BRANDT A, 1977, MATH COMPUT, V31, P333, DOI 10.1090/S0025-5718-1977-0431719-X
[6]  
Briggs W. L., 1987, MULTIGRID TUTORIAL
[7]   BLANCHE - AN EXPERIMENT IN GUIDANCE AND NAVIGATION OF AN AUTONOMOUS ROBOT VEHICLE [J].
COX, IJ .
IEEE TRANSACTIONS ON ROBOTICS AND AUTOMATION, 1991, 7 (02) :193-204
[8]  
Doucet A., 2001, SEQUENTIAL MONTE CAR
[9]  
Duckett T, 2003, IEEE INT CONF ROBOT, P434
[10]  
Duckett T., 2000, Proceedings 2000 ICRA. Millennium Conference. IEEE International Conference on Robotics and Automation. Symposia Proceedings (Cat. No.00CH37065), P3841, DOI 10.1109/ROBOT.2000.845330