doi:

DOI: 10.3724/SP.J.1218.2013.00500

Robot (机器人) 2013/35:4 PP.500-512

Graph-based SLAM: A Survey


Abstract:
Graph-based simultaneous localization and mapping (SLAM) is currently a hot research topic in the field of robotics. Frame-to-frame alignment, loop closure detection and graph optimization are three main aspects in graph-based SLAM. For each aspect, the key techniques and current progress are discussed, and the difficult problems and the possible solutions are also analyzed. Finally, the potential future issues and research trends are explored.

Key words:simultaneous localization and mapping,registration,loop closure detection,graph optimization

ReleaseDate:2016-08-31 09:31:47



[1] Durrant-Whyte H, Bailey T. Simultaneous localization andmapping: Part I. The essential algorithms[J]. IEEE Robotics andAutomation Magazine, 2006, 13(2): 99-108.

[2] Smith R C, Cheeseman P. On the representation and estimationof spatial uncertainty[J]. International Journal of Robotics Research,1986, 5(4): 56-68.

[3] Thrun S, Liu Y F, Koller D, et al. Simultaneous localizationand mapping with sparse extended information filters[J]. InternationalJournal of Robotics Research, 2004, 23(7/8): 693-716.

[4] Montemerlo M, Thrun S, Koller D, et al. FastSLAM: A factoredsolution to the simultaneous localization and mapping problem[C]//Proceedings of the National Conference on ArtificialIntelligence. Menlo Park, USA: AAAI, 2002: 593-598.

[5] Thrun S. Robotic mapping: A survey[M]// Exploring ArtificialIntelligence in the New Millennium. San Francisco, USA: MorganKaufmann, 2002: 1-35.

[6] Huang S D, Dissanayake G. Convergence and consistency analysisfor extended Kalman filter based SLAM[J]. IEEE Transactionson Robotics, 2007, 23(5): 1036-1049.

[7] Thrun S, Burgard W, Fox D. Probabilistic robotics[M]. Cambridge,USA: MIT Press, 2005.

[8] Thrun S, Montemerlo M. The graph SLAM algorithm with applicationsto large-scale mapping of urban structures[J]. InternationalJournal of Robotics Research, 2006, 25(5/6): 403-429.

[9] Frese U, Larsson P, Duckett T. A multilevel relaxation algorithmfor simultaneous localization and mapping[J]. IEEE Transactionson Robotics, 2005, 21(2): 196-207.

[10] Olson E, Leonard J, Teller S. Fast iterative alignment of posegraphs with poor initial estimates[C]//IEEE International Conferenceon Robotics and Automation. Piscataway, USA: IEEE,2006: 2262-2269.

[11] Grisetti G, Stachniss C, Grzonka S, et al. A tree parameterizationfor efficiently computing maximum likelihood maps usinggradient descent[M]//Robotics: Science and Systems III. Cambridge,USA: MIT Press, 2008: 65-72.

[12] Kaess M, Ranganathan A, Dellaert F. iSAM: Incrementalsmoothing and mapping[J]. IEEE Transactions on Robotics,2008, 24(6): 1365-1378.

[13] Konolige K, Agrawal M. FrameSLAM: From bundle adjustmentto real-time visual mapping[J]. IEEE Transactions onRobotics, 2008, 24(5): 1066-1077.

[14] Kummerle R, Grisetti G, Strasdat H, et al. g2o: A general frameworkfor graph optimization[C]//IEEE International Conferenceon Robotics and Automation. Piscataway, USA: IEEE, 2011:3607-3613.

[15] Sünderhauf N, Protzel P. Towards a robust back-end for posegraph SLAM[C]//IEEE International Conference on Roboticsand Automation. Piscataway, USA: IEEE, 2012: 1254-1261.

[16] Johannsson H, Kaess M, Fallon M, et al. Temporally scalable visualSLAM using a reduced pose graph[R]. Cambridge, USA:Computer Science and Artificial Intelligent Laboratory, MIT,2012.

[17] Grisetti G, Grzonka S, Stachniss C, et al. Efficient estimation ofaccurate maximum likelihood maps in 3D[C]//IEEE/RSJ InternationalConference on Intelligent Robots and Systems. Piscataway,USA: IEEE, 2007: 3472-3478.

[18] Borrmann D, Elseberg J, Lingemann K, et al. Globally consistent3D mapping with scan matching[J]. Robotics and AutonomousSystems, 2008, 56(2): 130-142.

[19] Wurm K M, Hornung A, Bennewitz M, et al. OctoMap: Aprobabilistic, flexible, and compact 3D map representation forrobotic systems[C]//ICRA 2010Workshop: Best Practice in 3DPerception and Modeling for Mobile Manipulation. 2010.

[20] McDonald J, Kaess M, Cadena C, et al. Real-time 6-DOFmulti-session visual SLAM over large-scale environments[J].Robotics and Autonomous Systems, 2012.

[21] Kretzschmar H, Grisetti G, Stachniss C. Lifelong map learningfor graph-based SLAM in static environments[J]. Künstliche Intelligenz,2010, 24(3): 199-206.

[22] Cruz L, Lucio D, Velho L. Kinect and RGBD images: Challengesand applications[C]//SIBGRAPI - Conference on Graphics,Patterns and Images Tutorials. Washington, USA: IEEEComputer Society, 2012: 36-49.

[23] Henry P, Krainin M, Herbst E, et al. RGB-D mapping: UsingKinect-style depth cameras for dense 3D modeling of indoorenvironments[J]. International Journal of Robotics Research,2012, 31(5): 647-663.

[24] Huang A S, Bachrach A, Henry P, et al. Visual odometryand mapping for autonomous flight using an RGB-D camera[C]//International Symposium on Robotics Research. 2011.

[25] Endres F, Hess J, Engelhard N, et al. An evaluation of theRGB-D SLAM system[C]//IEEE International Conference onRobotics and Automation. Piscataway, USA: IEEE, 2012:1691-1696.

[26] Izadi S, Kim D, Hilliges O, et al. KinectFusion: Real-time3D reconstruction and interaction using a moving depth camera[C]//24th Annual ACM Symposium on User Interface Softwareand Technology. New York, USA: ACM, 2011: 559-568.

[27] Whelan T, Kaess M, Fallon M, et al. Kintinuous: Spatially extendedKinectFusion[M]//Robotics: Science and Systems VII.Cambridge, USA: MIT Press, 2012.

[28] Lu F, Milios E. Globally consistent range scan alignment forenvironment mapping[J]. Autonomous robots, 1997, 4(4): 333-349.

[29] Gutmann J S, Konolige K. Incremental mapping of large cyclicenvironments[C]//IEEE International Symposium on ComputationalIntelligence in Robotics and Automation. Piscataway,USA: IEEE, 1999: 318-325.

[30] Scaramuzza D, Fraundorfer F. Visual odometry. Part I: The first30 years and fundamentals[J]. IEEE Robotics and AutomationMagazine, 2011, 18(4): 80-92.

[31] Nister D, Naroditsky O, Bergen J. Visual odometry for groundvehicle applications[J]. Journal of Field Robotics, 2006, 23(1):3-20.

[32] Konolige K, Agrawal M, Sola J. Large-scale visual odometryfor rough terrain[C]//13th International Symposium on RoboticsResearch. Berlin, Germany: Springer, 2011: 201-212.

[33] Saez J M, Hogue A, Escolano F, et al. Underwater 3D SLAMthrough entropy minimization[C]//IEEE International Conferenceon Robotics and Automation. Piscataway, USA: IEEE,2006: 3562-3567.

[34] Steder B, Grisetti G, Stachniss C, et al. Visual SLAM for flyingvehicles[J]. IEEE Transactions on Robotics, 2008, 24(5): 1088-1093.

[35] Maimone M, Cheng Y, Matthies L. Two years of visual odometryon the mars exploration rovers[J]. Journal of Field Robotics,2007, 24(3): 169-186.

[36] Besl P J, McKay N D. A method for registration of 3-D shapes[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence,1992, 14(2): 239-256.

[37] Yang C, Medioni G. Object modeling by registration of multiplerange images[J]. Image and Vision Computing, 1992, 10(3):145-155.

[38] Zhang Z Y. Iterative point matching for registration of free-formcurves and surfaces[J]. International Journal of Computer Vision,1994, 13(2): 119-152.

[39] Arun K S, Huang T S, Blostein S D. Least-squares fitting oftwo 3-D point sets[J]. IEEE Transactions on Pattern Analysisand Machine Intelligence, 1987, 9(5): 698-700.

[40] Eggert DW, Lorusso A, Fischer R B. Estimating 3-D rigid bodytransformations: A comparison of four major algorithms[J].Machine Vision and Applications, 1997, 9(5/6): 272-290.

[41] Segal A, Haehnel D, Thrun S. Generalized-ICP[M]//Robotics:Science and Systems V. Cambridge, USA: MIT Press, 2009.

[42] Salvi J, Matabosch C, Fofi D, et al. A review of recent rangeimage registration methods with accuracy evaluation[J]. Imageand Vision Computing, 2007, 25(5): 578-596.

[43] Turk G, Levoy M. Zippered polygon meshes from range images[C]//21st Annual Conference on Computer Graphics andInteractive Techniques. New York, USA: ACM, 1994: 311-318.

[44] Godin G, Rioux M, Baribeau R. Three-dimensional registrationusing range and intensity information[C]//Proceedings ofthe SPIE, vol.2350. Bellingham, USA: SPIE, 1994: 279-290.

[45] Fitzgibbon AW. Robust registration of 2D and 3D point sets[J].Image and Vision Computing, 2003, 21(13/14): 1145-1153.

[46] Rusinkiewicz S, Levoy M. Efficient variants of the ICP algorithm[C]//Third International Conference on 3-D Digital Imagingand Modeling. Los Alamitos, USA: IEEE Computer Society,2001: 145-152.

[47] Nister D, Naroditsky O, Bergen J. Visual odometry[C]//IEEEComputer Society Conference on Computer Vision and PatternRecognition. Los Alamitos, USA: IEEE Computer Society,2004: 652-659.

[48] Lowe D G. Distinctive image features from scale-invariantkeypoints[J]. International Journal of Computer Vision, 2004,60(2): 91-110.

[49] Bay H, Ess A, Tuytelaars T, et al. Speeded-up robust features(SURF)[J]. Computer Vision and Image Understanding, 2008,110(3): 346-359.

[50] Agrawal M, Konolige K, Blas M R. CenSurE: Center surroundextremas for realtime feature detection and matching[C]//European Conference on Computer Vision. Berlin, Germany:Springer, 2008: 102-115.

[51] Shi J B, Tomasi C. Good features to track[C]//IEEE ComputerSociety Conference on Computer Vision and Pattern Recognition.Los Alamitos, USA: IEEE Computer Society, 1994: 593-600.

[52] Fischler M A, Bolles R C. Random sample consensus: Aparadigm for model fitting with applications to image analysisand automated cartography[J]. Communications of the ACM,1981, 24(6): 381-395.

[53] Nister D. An efficient solution to the five-point relative poseproblem[C]//IEEE Computer Society Conference on ComputerVision and Pattern Recognition. Los Alamitos, USA: IEEEComputer Society, 2003: 195-202.

[54] Moreno-Noguer F, Lepetit V, Fua P. Accurate non-iterative O(n)solution to the PnP problem[C]//IEEE International Conferenceon Computer Vision. Piscataway, USA: IEEE, 2007: 2168-2175.

[55] Kneip L, Scaramuzza D, Siegwart R. A novel parametrizationof the perspective-three-point problem for a direct computationof absolute camera position and orientation[C]//IEEE Conferenceon Computer Vision and Pattern Recognition. Piscataway,USA: IEEE, 2011: 2969-2976.

[56] Newman P, Ho K. SLAM – Loop closing with visually salientfeatures[C]//IEEE International Conference on Robotics andAutomation. Piscataway, USA: IEEE, 2005: 635-642.

[57] Cummins M, Newman P. Probabilistic appearance based navigationand loop closing[C]//IEEE International Conferenceon Robotics and Automation. Piscataway, USA: IEEE, 2007:2042-2048.

[58] Zhang H. BoRF: Loop-closure detection with scale invariantvisual features[C]//IEEE International Conference on Roboticsand Automation. Piscataway, USA: IEEE, 2011: 3125-3130.

[59] Cummins M, Newman P. Appearance-only SLAM at large scalewith FAB-MAP 2.0[J]. International Journal of Robotics Research,2011, 30(9): 1100-1123.

[60] Sünderhauf N, Protzel P. Brief-gist-closing the loop by simplemeans[C]//IEEE/RSJ International Conference on IntelligentRobots and Systems. Piscataway, USA: IEEE, 2011: 1234-1241.

[61] Liu Y, Zhang H. Visual loop closure detection with a compactimage descriptor[C]//IEEE/RSJ International Conference on IntelligentRobots and Systems. Piscataway, USA: IEEE, 2012:1051-1056.

[62] Matas J, Chum O, Urban M, et al. Robust wide-baseline stereofrom maximally stable extremal regions[J]. Image and VisionComputing, 2004, 22(10): 761-767.

[63] Steder B, Grisetti G, Burgard W. Robust place recognition for3D range data based on point features[C]//IEEE InternationalConference on Robotics and Automation. Piscataway, USA:IEEE, 2010: 1400-1405.

[64] Hartigan J A, Wong M A. A k-means clustering algorithm[J].Applied Statistics, 1979, 28(1): 100-108.

[65] Sivic J, Zisserman A. Video Google: A text retrieval approachto object matching in videos[C]//IEEE International Conferenceon Computer Vision. Los Alamitos, USA: IEEE Computer Society,2003: 1470-1477.

[66] Baeza-Yates R, Ribeiro-Neto B. Modern information retrieval[M]. New York, USA: ACM Press, 1999.

[67] Nister D, Stewenius H. Scalable recognition with a vocabularytree[C]//IEEE Computer Society Conference on Computer Visionand Pattern Recognition. Los Alamitos, USA: IEEE ComputerSociety, 2006: 2161-2168.

[68] Schindler G, Brown M, Szeliski R. City-scale location recognition[C]//IEEE Computer Society Conference on Computer Visionand Pattern Recognition. Los Alamitos, USA: IEEE ComputerSociety, 2007: 1-7.

[69] Angeli A, Filliat D, Doncieux S, et al. Fast and incrementalmethod for loop-closure detection using bags of visual words[J].IEEE Transactions on Robotics, 2008, 24(5): 1027-1037.

[70] Williams B, Cummins M, Neira J, et al. An image-to-map loopclosing method for monocular SLAM[C]//IEEE/RSJ InternationalConference on Intelligent Robots and Systems. Piscataway,USA: IEEE, 2008: 2053-2059.

[71] Clemente L A, Davison A J, Reid I, et al. Mapping large loopswith a single hand-held camera[C]//Robotics: Science and Systems.Cambridge, USA: MIT Press, 2007: 297-304.

[72] Bosse M, Newman P, Leonard J, et al. An Atlas frameworkfor scalable mapping[C]//IEEE International Conferenceon Robotics and Automation. Piscataway, USA: IEEE, 2003:1899-1906.

[73] Olson E B. Robust and efficient robotic mapping[D]. Cambridge,USA: Department of Electrical Engineering and ComputerScience, MIT, 2008.

[74] Ho K L, Newman P. Detecting loop closure with scene sequences[J]. International Journal of Computer Vision, 2007,74(3): 261-286.

[75] Konolige K, Bowman J, Chen J D, et al. View-based maps[J].International Journal of Robotics Research, 2010, 29(8): 941-957.

[76] Hartley R, Zisserman A. Multiple view geometry in computervision[M]. Cambridge, UK: Cambridge University Press, 2000.

[77] Galvez-Lopez D, Tardos J D. Real-time loop detection withbags of binary words[C]//IEEE/RSJ International Conferenceon Intelligent Robots and Systems. Piscataway, USA: IEEE,2011: 51-58.

[78] Cadena C, Gálvez-López D, Ramos F, et al. Robust place recognitionwith stereo cameras[C]//IEEE/RSJ International Conferenceon Intelligent Robots and Systems. Piscataway, USA:IEEE, 2010: 5182-5189.

[79] Olson E. Recognizing places using spectrally clustered localmatches[J]. Robotics and Autonomous Systems, 2009, 57(12):1157-1172.

[80] Golfarelli M, Maio D, Rizzi S. Elastic correction of deadreckoningerrors in map building[C]//IEEE/RSJ InternationalConference on Intelligent Robots and Systems. Piscataway,USA: IEEE, 1998: 905-911.

[81] Duckett T, Marsland S, Shapiro J. Learning globally consistentmaps by relaxation[C]//IEEE International Conferenceon Robotics and Automation. Piscataway, USA: IEEE, 2000:3841-3846.

[82] Konolige K, Grisetti G, Kummerle R, et al. Efficient sparse poseadjustment for 2D mapping[C]//IEEE/RSJ International Conferenceon Intelligent Robots and Systems. Piscataway, USA:IEEE, 2010: 22-29.

[83] Strasdat H, Montiel J M M, Davison A J. Real-time monocularSLAM: Why filter?[C]//IEEE International Conferenceon Robotics and Automation. Piscataway, USA: IEEE, 2010:2657-2664.

[84] Dellaert F, Kaess M. Square root SAM: Simultaneous localizationand mapping via square root information smoothing[J]. InternationalJournal of Robotics Research, 2006, 25(12): 1181-1203.

[85] Grisetti G, Kummerle R, Stachniss C, et al. Hierarchical optimizationon manifolds for online 2D and 3D mapping[C]//IEEEInternational Conference on Robotics and Automation. Piscataway,USA: IEEE, 2010: 273-278.

[86] Wagner R, Birbach O, Frese U. Rapid development of manifoldbasedgraph optimization systems for multi-sensor calibrationand SLAM[C]//IEEE/RSJ International Conference on IntelligentRobots and Systems. Piscataway, USA: IEEE, 2011: 3305-3312.

[87] Nocedal J, Wright S J. Numerical optimization[M]. Berlin, Germany:Springer Verlag, 1999.

[88] Carlone L, Aragues R, Castellanos J A, et al. A linear approximationfor graph-based simultaneous localization and mapping[J]. Robotics: Science and Systems VII. Cambridge, USA:MIT Press, 2012: 41-48.

[89] Sünderhauf N. Robust optimization for simultaneous localizationand mapping[D]. Chemnitz, Germany: Department of ElectricalEngineering and Information, Chemnitz University ofTechnology, 2012.

[90] Kretzschmar H, Stachniss C, Grisetti G. Efficient informationtheoreticgraph pruning for graph-based SLAM with laser rangefinders[C]//IEEE/RSJ International Conference on IntelligentRobots and Systems. Piscataway, USA: IEEE, 2011: 865-871.

[91] Konolige K, Garage W. Sparse sparse bundle adjustment[C]//Proceedings of the British Machine Vision Conference. 2010.

[92] Huang S D, Lai Y W, Frese U, et al. How far is SLAM from alinear least squares problem?[C]//IEEE/RSJ International Conferenceon Intelligent Robots and Systems. Piscataway, USA:IEEE, 2010: 3011-3016.

[93] Huang S D,Wang H, Frese U, et al. On the number of local minimato the point feature based SLAM problem[C]//IEEE InternationalConference on Robotics and Automation. Piscataway,USA: IEEE, 2012: 2074-2079.

[94] Sünderhauf N, Protzel P. Switchable constraints for robust posegraph SLAM[C]//IEEE/RSJ International Conference on IntelligentRobots and Systems. Piscataway, USA: 2012: 1879-1884.

[95] Olson E, Agarwal P. Inference on networks of mixtures forrobust robot mapping[M]//Robotics: Science and Systems 12.Cambridge, USA: MIT Press, 2012.

[96] Konolige K, Bowman J. Towards lifelong visual maps[C]//IEEE/RSJ International Conference on Intelligent Robots andSystems. Piscataway, USA: IEEE, 2009: 1156-1163.

[97] Walcott-Bryant A, Kaess M, Johannsson H, et al. Dynamicpose graph SLAM: Long-term mapping in low dynamic environments[C]//IEEE/RSJ International Conference on IntelligentRobots and Systems. Piscataway, USA: IEEE, 2012: 1871-1878.

[98] Koppula H S, Anand A, Joachims T, et al. Semantic labeling of3D point clouds for indoor scenes[C]//25th Annual Conferenceon Neural Information Processing Systems. New York, USA:Curran Associates Inc., 2011.

[99] Bao S Y, Savarese S. Semantic structure from motion[C]//IEEEComputer Society Conference on Computer Vision and PatternRecognition. Los Alamitos, USA: IEEE Computer Society,2011: 2025-2032.