{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,1]],"date-time":"2026-07-01T20:21:31Z","timestamp":1782937291135,"version":"3.54.5"},"reference-count":64,"publisher":"SAGE Publications","issue":"7-8","license":[{"start":{"date-parts":[[2004,8,1]],"date-time":"2004-08-01T00:00:00Z","timestamp":1091318400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["The International Journal of Robotics Research"],"published-print":{"date-parts":[[2004,8]]},"abstract":"<jats:p>In this paper we describe a scalable algorithm for the simultaneous mapping and localization (SLAM) problem. SLAM is the problem of acquiring a map of a static environment with a mobile robot. The vast majority of SLAM algorithms are based on the extended Kalman filter (EKF). In this paper we advocate an algorithm that relies on the dual of the EKF, the extended information filter (EIF). We show that when represented in the information form, map posteriors are dominated by a small number of links that tie together nearby features in the map. This insight is developed into a sparse variant of the EIF, called the sparse extended information filter (SEIF). SEIFs represent maps by graphical networks of features that are locally interconnected, where links represent relative information between pairs of nearby features, as well as information about the robot\u2019s pose relative to the map. We show that all essential update equations in SEIFs can be executed in constant time, irrespective of the size of the map. We also provide empirical results obtained for a benchmark data set collected in an outdoor environment, and using a multi-robot mapping simulation.<\/jats:p>","DOI":"10.1177\/0278364904045479","type":"journal-article","created":{"date-parts":[[2004,9,13]],"date-time":"2004-09-13T20:12:22Z","timestamp":1095106342000},"page":"693-716","source":"Crossref","is-referenced-by-count":449,"title":["Simultaneous Localization and Mapping with Sparse Extended Information Filters"],"prefix":"10.1177","volume":"23","author":[{"given":"Sebastian","family":"Thrun","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yufeng","family":"Liu","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Daphne","family":"Koller","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Andrew Y.","family":"Ng","sequence":"additional","affiliation":[{"name":"Stanford University, Stanford, CA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Zoubin","family":"Ghahramani","sequence":"additional","affiliation":[{"name":"Gatsby Computational Neuroscience Unit, University College London, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hugh","family":"Durrant-Whyte","sequence":"additional","affiliation":[{"name":"University of Sydney, Sydney, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"179","published-online":{"date-parts":[[2004,8,1]]},"reference":[{"key":"atypb1","unstructured":"Bailey, T. 2002.\n                      Mobile Robot Localization and Mapping in Extensive Outdoor Environments\n                      . PhD thesis, University of Sydney, Sydney, NSW, Australia."},{"key":"atypb2","unstructured":"Bosse, M., Leonard, J., and Teller, S. 2002. Large-scale CML using a network of multiple local maps . Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Workshop Notes of the ICRA Workshop on Concurrent Mapping and Localization for Autonomous Mobile Robots (W4), Washington, DC, May 11\u201315."},{"key":"atypb3","unstructured":"Bosse, M., Newman, P., Soika, M., Feiten, W., Leonard, J., and Teller, S. 2003. An atlas framework for scalable mapping . Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Taipei, Taiwan."},{"key":"atypb4","unstructured":"Burgard, W., Fox, D., Jans, H., Matenar, C., and Thrun, S. 1999. Sonar-based mapping of large-scale mobile robot environments using EM . Proceedings of the International Conference on Machine Learning, Bled, Slovenia."},{"key":"atypb5","unstructured":"Burgard, W., Fox, D., Moors, M., Simmons, R., and Thrun, S. 2000. Collaborative multi-robot exploration . Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), San Francisco, CA, April 24\u201328."},{"key":"atypb6","unstructured":"Choset, H. 1996.\n                      Sensor Based Motion Planning: The Hierarchical Generalized Voronoi Graph\n                      . PhD thesis, California Institute of Technology."},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1207\/s15516709cog1901_1"},{"key":"atypb8","unstructured":"Cover, T. M. and Thomas, J. A. 1991. Elements of Information Theory. Wiley, NewYork ."},{"key":"atypb9","unstructured":"Csorba, M. 1997.\n                      Simultaneous Localization and Map Building\n                      . PhD thesis, Department of Engineering Science, University of Oxford, Oxford, UK."},{"key":"atypb10","doi-asserted-by":"crossref","unstructured":"Deans, M. and Hebert, M. 2000. Invariant filtering for simultaneous localization and mapping . Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), San Francisco, CA, April 24\u201328, pp. 1042\u20131047 .","DOI":"10.1109\/ROBOT.2000.844737"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1109\/70.938381"},{"key":"atypb12","doi-asserted-by":"crossref","unstructured":"Doucet,A., de Freitas, J. F. G., and Gordon, N. J. editors. 2001. Sequential Monte Carlo Methods In Practice. Springer Verlag, NewYork .","DOI":"10.1007\/978-1-4757-3437-9"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1109\/70.938382"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1109\/71.598277"},{"key":"atypb15","unstructured":"Gutmann, J.S., and Konolige, K. 1999. Incremental mapping of large cyclic environments . Proceedings of the IEEE International Symposium on Computational Intelligence in Robotics and Automation (CIRA), Monterey, CA."},{"key":"atypb16","doi-asserted-by":"crossref","unstructured":"Gutmann, J.S., and Nebel, B. 1997. Navigation mobiler roboter mit laserscans. Autonome Mobile Systeme. Springer Verlag, Berlin .","DOI":"10.1007\/978-3-642-60904-6_4"},{"key":"atypb17","unstructured":"H\u00e4hnel, D., Burgard, W., Wegbreit, B., and Thrun, S. 2003a. Towards lazy data association in SLAM . Proceedings of the 11th International Symposium of Robotics Research (ISRR\u201903), Sienna, Italy."},{"key":"atypb18","unstructured":"H\u00e4hnel, D., Fox, D., Burgard, W., and Thrun, S. 2003b. A highly efficient FastSLAM algorithm for generating cyclic maps of large-scale environments from raw laser range measurements . Proceedings of the Conference on Intelligent Robots and Systems (IROS), Las Vegas, NV, October 27\u201331."},{"key":"atypb19","unstructured":"H\u00e4hnel, D., Triebel, R., Burgard, W., and Thrun, S. 2003c. Map building with mobile robots in dynamic environments . Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Taipei, Taiwan."},{"key":"atypb20","doi-asserted-by":"crossref","unstructured":"Julier, S. J., and Uhlmann, J. K. 2000. Building a million beacon map. Sensor Fusion and Decentralized Control in Robotic Systems IV, Bellingham, WA , Proceedings of the SPIE 4571.","DOI":"10.1117\/12.444158"},{"key":"atypb21","unstructured":"Kuipers, B., and Byun,Y.T. 1988. Arobust qualitative method for spatial learning in unknown environments . Proceeding of the 8th National Conference on Artificial Intelligence AAAI-88, Menlo Park, Cambridge."},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1016\/0921-8890(91)90014-C"},{"key":"atypb23","doi-asserted-by":"crossref","unstructured":"Leonard, J. J. and Durrant-Whyte, H. F. 1992. Directed Sonar Sensing for Mobile Robot Navigation. Kluwer Academic, Boston, MA .","DOI":"10.1007\/978-1-4615-3652-9"},{"key":"atypb24","doi-asserted-by":"crossref","unstructured":"Leonard, J. J. and Feder, H. J. S. 1999. A computationally efficient method for large-scale concurrent mapping and localization . Proceedings of the 9th International Symposium on Robotics Research, Salt Lake City, Utah.","DOI":"10.1007\/978-1-4471-0765-1_21"},{"key":"atypb25","unstructured":"Leonard, J., Tard\u00f3s, J. D., Thrun, S., and Choset, H. editors. Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Workshop Notes of the ICRA Workshop on Concurrent Mapping and Localization for Autonomous Mobile Robots (W4), Washington, DC, May 11\u201315."},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1145\/99935.99949"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008854305733"},{"key":"atypb28","unstructured":"Matar\u00edc, M. J. 1990.\n                      A Distributed Model for Mobile Robot Environment-Learning and Navigation\n                      . Master\u2019s thesis, MIT, Cambridge, MA. Also available as MIT Artificial Intelligence Laboratory Tech Report AITR-1228."},{"key":"atypb29","unstructured":"Maybeck, P. 1979. Stochastic Models, Estimation, and Control, Vol. 1. Academic, NewYork ."},{"key":"atypb30","unstructured":"Montemerlo, M., and Thrun, S. 2003. Simultaneous localization and mapping with unknown data association using FastSLAM . Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Taipei, Taiwan."},{"key":"atypb31","unstructured":"Montemerlo, M., Thrun, S., Koller, D., and Wegbreit, B. 2002. FastSLAM: a factored solution to the simultaneous localization and mapping problem . Proceedings of the AAAI National Conference on Artificial Intelligence, Edmonton, Canada."},{"key":"atypb32","unstructured":"Montemerlo, M., Thrun, S., Koller, D., and Wegbreit, B. 2003. FastSLAM 2.0: An improved particle filtering algorithm for simultaneous localization and mapping that provably converges . Proceedings of the 16th International Joint Conference on Artificial Intelligence (IJCAI), Acapulco, Mexico."},{"key":"atypb33","unstructured":"Moravec, H. P. 1988. Sensor fusion in certainty grids for mobile robots . AI Magazine 9(2): 61\u201374 ."},{"key":"atypb34","unstructured":"Moutarlier, P., and Chatila, R. 1989. An experimental system for incremental environment modeling by an autonomous mobile robot . Proceedings of the 1st International Symposium on Experimental Robotics, Montreal, Canada, June."},{"key":"atypb35","unstructured":"Murphy, K. 2000. Bayesian map learning in dynamic environments. Advances in Neural Information Processing Systems (NIPS). MIT Press, Cambridge, MA ."},{"key":"atypb36","unstructured":"Murphy, K. P., Weiss, Y., and Jordan, M. I. 1999. Loopy belief propagation for approximate inference: an empirical study . Proceedings of the Conference on Uncertainty in AI (UAI), Stockholm, Sweden, pp. 467\u2013475 ."},{"key":"atypb37","unstructured":"Neira, J., Tard\u00f3s, J. D., and Castellanos, J. A. 2003. Linear time vehicle relocation in SLAM . Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Taipei, Taiwan."},{"key":"atypb38","doi-asserted-by":"crossref","unstructured":"Nettleton, E. W., Gibbens, P. W., and Durrant-Whyte, H. F. 2000. Closed form solutions to the multiple platform simultaneous localization and map building (slam) problem. Sensor Fusion: Architectures, Algorithms, and Applications IV, Bellingham, WA , Vol. 4051, Bulur V. Dasarathy, editor. pp. 428\u2013437.","DOI":"10.1117\/12.381658"},{"key":"atypb39","doi-asserted-by":"crossref","unstructured":"Nettleton, E., Durrant-Whyte, H., Gibbens, P., and Gokto.gan, A. 2000. Multiple platform localization and map building. Sensor Fusion and Decentralized Control in Robotic Systems III, Bellingham, WA , Vol. 4196, G.T. McKee and P.S. Schenker, editors, pp. 337\u2013347.","DOI":"10.1117\/12.403733"},{"key":"atypb40","unstructured":"Nettleton, E., Thrun, S., and Durrant-Whyte, H. 2002. A constant time communications algorithm for decentralized SLAM. Submitted for publication."},{"key":"atypb41","unstructured":"Nettleton, E., Thrun, S., and Durrant-Whyte, H. 2003. Decentralized SLAM with low-bandwidth communication for teams of airborne vehicles . Proceedings of the International Conference on Field and Service Robotics, Lake Yamanaka, Japan."},{"key":"atypb42","unstructured":"Newman, P. 2000.\n                      On the Structure and Solution of the Simultaneous Localization and Map Building Problem\n                      . PhD thesis, Australian Centre for Field Robotics, University of Sydney, Sydney, Australia."},{"key":"atypb43","unstructured":"Paskin, M. A. 2002. Thin junction tree filters for simultaneous localization and mapping. Technical Report UCB\/CSD-02-1198, University of California, Berkeley, CA ."},{"key":"atypb44","doi-asserted-by":"crossref","unstructured":"Pearl, J. 1988. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann, San Mateo, CA .","DOI":"10.1016\/B978-0-08-051489-5.50008-4"},{"key":"atypb45","doi-asserted-by":"crossref","unstructured":"Procopiuc, O., Agarwal, P. K., Arge, L., and Vitter, J. S. 2003. Bkd-tree: a dynamic scalable kd-tree. Advances in spatial and temporal awareness, T. Hadzilacos, Y. Manolopoulos, J. F. Roddick and Y. Theodoridis, editors. Springer-Verlag, Santorini Island, Greece .","DOI":"10.1007\/978-3-540-45072-6_4"},{"key":"atypb46","unstructured":"Shatkay, H., and Kaelbling, L. 1997. Learning topological maps with weak local odometric information . Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI)."},{"key":"atypb47","unstructured":"Simmons, R.,Apfelbaum, D., Burgard, W., Fox, M., and Moors, D., Thrun, S., and Younes, H. 2000. Coordination for multirobot exploration and mapping . Proceedings of the AAAI National Conference on Artificial Intelligence, Austin, TX."},{"key":"atypb48","unstructured":"Smith, R. C. and Cheeseman, P. 1985. On the representation and estimation of spatial uncertainty. Technical Report 4760 and 7239, SRI International, Menlo Park, CA ."},{"key":"atypb49","doi-asserted-by":"publisher","DOI":"10.1177\/027836498600500404"},{"key":"atypb50","doi-asserted-by":"crossref","unstructured":"Smith, R., Self, M., and Cheeseman, P. 1990. Estimating uncertain spatial relationships in robotics. Autonomous Robot Vehicles, I.J. Cox and G.T. Wilfong, editors. Springer-Verlag, Berlin , pp. 167\u2013193.","DOI":"10.1007\/978-1-4613-8997-2_14"},{"key":"atypb51","unstructured":"Stewart, B., Ko, J., Fox, D., and Konolige, K. 2003. A hierarchical bayesian approach to mobile robot map structure estimation . Proceedings of the Conference on Uncertainty in AI (UAI), Acapulco, Mexico."},{"key":"atypb52","doi-asserted-by":"publisher","DOI":"10.1177\/027836402320556340"},{"key":"atypb53","unstructured":"Thorpe, C. and Durrant-Whyte, H. 2001. Field robots . Proceedings of the 10th International Symposium of Robotics Research (ISRR\u201901), Lorne, Australia."},{"key":"atypb54","unstructured":"Thrun, S. 2000. Towards programming tools for robots that integrate probabilistic computation and learning . Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), San Francisco, CA, April 24\u201328."},{"key":"atypb55","doi-asserted-by":"publisher","DOI":"10.1177\/02783640122067435"},{"key":"atypb56","unstructured":"Thrun, S. 2002. Robotic mapping: a survey. Exploring Artificial Intelligence in the New Millennium, G. Lakemeyer and B. Nebel, editors. Morgan Kaufmann, San Mateo, CA ."},{"key":"atypb57","unstructured":"Thrun, S., and Liu, Y. 2003. Multi-robot SLAM with sparse extended information filers . Proceedings of the 11th International Symposium of Robotics Research (ISRR\u201903), Sienna, Italy."},{"key":"atypb58","doi-asserted-by":"publisher","DOI":"10.1023\/A:1007436523611"},{"key":"atypb59","unstructured":"Thrun, S., H\u00e4hnel, D., Ferguson, D., Montemerlo, M., Triebel, R., Burgard, W., Baker, C., Omohundro, Z., Thayer, S., and Whittaker, W. 2003. A system for volumetric robotic mapping of abandoned mines . Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Taipei, Taiwan."},{"key":"atypb60","unstructured":"Wainwright, M. J. 2002.\n                      Stochastic Processes on Graphs With Cycles: Geometric and Variational Approaches\n                      . PhD thesis, Department of Electrical Engineering and Computer Science, MIT, Cambridge, MA."},{"key":"atypb61","unstructured":"Wang, C.C., Thorpe, C., and Thrun, S. 2003. On-line simultaneous localization and mapping with detection and tracking of moving objects: theory and results from a ground vehicle in crowded urban areas . Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Taipei, Taiwan."},{"key":"atypb62","doi-asserted-by":"publisher","DOI":"10.1162\/089976601750541769"},{"key":"atypb63","unstructured":"Williams, S., and Dissanayake, G. 2002. Efficient simultaneous localisation and mapping using local submaps . Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Workshop Notes of the ICRA Workshop on Concurrent Mapping and Localization for Autonomous Mobile Robots (W4), Washington, DC, May 11\u201315."},{"key":"atypb64","doi-asserted-by":"crossref","unstructured":"Williams, S. B., Dissanayake, G., and Durrant-Whyte, H. 2002. An efficient approach to the simultaneous localization and mapping problem . Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Washington, DC, May 11\u201315, pp. 406\u2013411 .","DOI":"10.1109\/ROBOT.2002.1013394"}],"container-title":["The International Journal of Robotics Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/0278364904045479","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/0278364904045479","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T10:17:10Z","timestamp":1777457830000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/0278364904045479"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,8]]},"references-count":64,"journal-issue":{"issue":"7-8","published-print":{"date-parts":[[2004,8]]}},"alternative-id":["10.1177\/0278364904045479"],"URL":"https:\/\/doi.org\/10.1177\/0278364904045479","relation":{},"ISSN":["0278-3649","1741-3176"],"issn-type":[{"value":"0278-3649","type":"print"},{"value":"1741-3176","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004,8]]}}}