D-SLAM: A Decoupled Solution to Simultaneous Localization and Mapping

Abstract

The main contribution of this paper is the reformulation of the simultaneous localization and mapping (SLAM) problem for mobile robots such that the mapping and localization can be treated as two concurrent yet separated processes: D-SLAM (decoupled SLAM). It is shown that SLAM with a range and bearing sensor in an environment populated with point features can be decoupled into solving a nonlinear static estimation problem for mapping and a low-dimensional dynamic estimation problem for localization. This is achieved by transforming the measurement vector into two parts: one containing information relating features in the map and another with information relating the map and robot. It is shown that the new formulation results in an exactly sparse information matrix for mapping when it is solved using an Extended Information Filter (EIF).Thus a significant saving in the computational effort can be achieved for large-scale problems by exploiting the special properties of sparse matrices. An important feature of D-SLAM is that the correlation among features in the map are still kept and it is demonstrated that the uncertainty of the feature estimates monotonically decreases. The algorithm is illustrated and evaluated through computer simulations and experiments.

Keywords

decoupled SLAM extended information filter sparse matrix computational complexity

Get full access to this article

View all access options for this article.

References

Bailey, T. (2002). Mobile robot localization and mapping in extensive outdoor environment. PhD Thesis. Australian Centre of Field Robotics, University of Sydney.

Castellanos, J. A. , Neira. J. , and Tardos, J. D. (2004). Limits to the consistency of EKF-based SLAM. Proceedings of 2004 IFAC Symposium on Intelligent Autonomous Vehicles, Lisbon, Portugal .

Chen, L. , Arambel, P. O. , and Mehra, R. K. (2002). Estimation under unknown correlation: covariance intersection revisited . IEEE Transactions on Automatic Control, 47(11): 1879–1882 .

Csorba, M. , Uhlmann, J. K. , and Durrant-Whyte, H. (1997). A suboptimal algorithm for automatic map building . Proceedings of the American Control Conference, pp. 537–541 .

Deans, M. C. and Hebert, M. (2000). Invariant filtering for simultaneous localization and map building . Proceedings of the IEEE International Conference on Robotics and Automation, pp. 1042–1047 .

Dellaert, F. (2005). Square root SAM . Proceedings of Robotics: Science and Systems. See webpage: http://www.roboticsproceedings.org/rss01/index.html.

Dissanayake, G. , Newman, P. , Clark, S. , Durrant-Whyte, H. , and Csobra, M. (2001). A solution to the simultaneous localization and map building (SLAM) problem . IEEE Transactions on Robotics and Automation, 17(3): 229–241 .

Eustice, R. M. , Singh, H. , and Leonard, J. (2005a). Exactly sparse delayed-state filters . Proceedings of IEEE International Conference on Robotics and Automation, pp. 2428-2435 .

Eustice, R. M. , Walter, M. , and Leonard, J. (2005b). Sparse extended information filters: insights into sparsification . Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 641–648 .

10.

Frese, U. (2005). A proof for the approximate sparsity of SLAM information matrices . Proceedings of IEEE International Conference on Robotics and Automation, pp. 331–337 .

11.

Frese, U. , Larsson, P. , and Duckett, T. (2005). A multilevel relaxation algorithm for simultaneous localization and mapping . IEEE Transactions on Robotics, 21(2): 196–207 .

12.

Frese, U. (2006). A discussion of simultaneous localization and mapping . Autonomous Robots, 20 (1): 25–42 .

13.

Gerkey, B. P. , Vaughan, R. T. , and Howard, A. (2003). The player/stage project: Tools for multirobot and distributed sensor systems . Proceedings of International Conference on Advanced Robotics, pp. 317–323 .

14.

Guivant, J. E. , and Nebot, E. M. (2001). Optimization of the simultaneous localization and map building algorithm for real time implementation , IEEE Transactions of Robotics and Automation, 17(3): 242–257 .

15.

Huang, S. , Wang, Z. , and Dissanayake, G. (2006). Mapping large scale environments using relative position information among landmarks . Proceedings of International Conference on Robotics and Automation, pp. 2297–2302 .

16.

Julier, S. J. and Uhlmann, J. K. (2001). Simultaneous localization and map building using split covariance intersection . Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 1257–1262 .

17.

Martinelli, A. , Tomatics, N. , and Siegwart, R. (2004). Open challenges in SLAM: An optimal solution based on shift and rotation invariants . Proceedings of IEEE International Conference on Robotics and Automation, pp. 1327–1332 .

18.

Maybeck, P. (1979). Stochastic Models, Estimation, and Control, Vol. 1. Academic Press, New York .

19.

Neira, J. and Tardos, J. D. (2001). Data association in stochastic mapping using the joint compatibility test . IEEE Transactions on Robotics and Automation, 17(6): 890–897 .

20.

Newman, P. (2000). On the structure and solution of the simultaneous localization and map building problem. PhD thesis. Australian Centre of Field Robotics, University of Sydney.

21.

Pradalier, C. and Sekhavat, S. (2003). Simultaneous localization and mapping using the Geometric Projection Filter and correspondence graph matching . Advanced Robotics, 17(7): 675–690 .

22.

Shewchuk, J. (1994). An Introduction to the Conjugate Gradient Method without the Agonizing Pain. Technical Report. CMU-CS-94-125, Carnegie Mellon Univerisity, Pittsburgh, PA, USA .

23.

Tardos, J. D. , Neira, J. , Newman, P. , and Leonard, J. (2002). Robust mapping and localization in indoor environments using sonar data . International Journal of Robotics Research, 21(4): 311–330 .

24.

Thrun, S. , Liu, Y. , Koller, D. , Ng, A. Y. , Ghahramani, Z. , and Durrant-Whyte, H. (2004). Simultaneous localization and mapping with sparse extended information filters . International Journal of Robotics Research, 23(7-8): 693–716 .

25.

Walter, M. , Eustice, R. , and Leonard, J. (2005). A provably consistent method for imposing exact sparsity in featurebased SLAM information filters . Proceedings of International Symposium on Robotics Research. See webpage: http://robot.cc/program.html.

26.

Williams, S. B. (2001). Efficient solutions to autonomous mapping and navigation problems. PhD thesis. Australian Centre of Field Robotics, University of Sydney.