Abstract
We present a new algorithm for merging occupancy grid maps produced by multiple robots exploring the same environment. The algorithm produces a set of possible transformations needed to merge two maps, i.e translations and rotations. Each transformation is weighted, thus allowing to distinguish uncertain situations, and enabling to track multiple cases when ambiguities arise. Transformations are produced extracting some spectral information from the maps. The approach is deterministic, non-iterative, and fast. The algorithm has been tested on public available datasets, as well as on maps produced by two robots concurrently exploring both indoor and outdoor environments. Throughout the experimental validation stage the technique we propose consistently merged maps exhibiting very different characteristics.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Birk, A., & Carpin, S. (2006). Merging occupancy grids from multiple robots. Proceedings of the IEEE, 94(7), 1384–1397.
Carpin, S., Birk, A., & Jucikas, V. (2005). On map merging. Robotics and Autonomous Systems, 53(1), 1–14.
Censi, A., Iocchi, L., & Grisetti, G. (2005). Scan matching in the Hough domain. In Proceedings of the IEEE international conference on robotics and automation (pp. 2739–2744).
Craig, J. J. (2005). Introduction to robotics – mechanics and control. New York: Prentice Hall.
Dedeoglu, G., & Sukhatme, G. S. (2000). Landmark-based matching algorithm for cooperative mapping by autonomous robots. In Distributed autonomous robotic systems 4 (pp. 251–260). Berlin: Springer.
Duda, R., & Hart, P. (1972). Use of the hough transform to detect lines and curves in the pictures. Communications of the ACM, 15(1), 11–15.
Fox, D., Ko, J., Konolige, K., Limketai, B., Schulz, D., & Stewart, B. (2006). Distributed multirobot exploration and mapping. Proceedings of the IEEE, 94(7), 1325–1339.
Garey, M. R., & Johnson, D. S. (1979). Computers and intractability. A guide to the theory of NP-completeness. New York: Freeman.
Grisetti, S., Stachniss, C., & Burgard, W. (2005). Improving grid-based slam with rao-blackwellized particle filters by adaptive proposals and selective resampling. In Proceedings of the IEEE international conference on robotics and automation (pp. 2432–2437).
Howard, A., Parker, L. E., & Sukhatme, G. S. (2006). Experiments with a large heterogeneous mobile robot team: exploration, mapping, deployment and detection. International Journal of Robotics Research, 25(5–6), 431–447.
Huang, W. H., & Beevers, K. R. (2005). Topological map merging. International Journal of Robotics Research, 24(8), 601–613.
Konolige, K., Fox, D., Limketkai, B., Ko, J., & Steward, B. (2003). Map merging for distributed robot navigation. In Proceedings of the IEEE/RSJ international conference on intelligent robots and systems (pp. 212–217).
Kuipers, B. (1978). Modeling spatial knowledge. Cognitive Science, 2, 129–153.
Open Computer Vision Library (2008). http://sourceforge.net/projects/opencvlibrary/.
Openslam. (2007). http://www.openslam.org.
Oppenheim, A. V., & Willsky, A. S. (1997). Signal and systems. New York: Prentice Hall.
Parker, L. E. (2000). Current state of the art in distributed autonomous mobile robots. In L. E. Parker, G. Bekey & J. Barhen (Eds.), Distributed autonomous robotic systems 4 (pp. 3–12). Berlin: Springer.
Radish. (2007). The robotics data set repository. http://radish.sourceforge.net.
Thrun, S. (2001). A probabilistic online mapping algorithm for teams of mobile robots. International Journal of Robotics Research, 20(5), 335–363.
Thrun, S., Burgard, W., & Fox, D. (2006). Probabilistic robotics. Cambridge: MIT.
Williams, S. B., Dissanyake, G., & Durrant-Whyte, H. (2002). Towards multi-wehicle simultaneous localisation and mapping. In Proceedings of the IEEE international conference on robotics and automation (pp. 2743–2748).
Zitová, B., & Flusser, J. (2003). Image registration methods: a survey. Image and Vision Computing, 21, 977–1000.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Carpin, S. Fast and accurate map merging for multi-robot systems. Auton Robot 25, 305–316 (2008). https://doi.org/10.1007/s10514-008-9097-4
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10514-008-9097-4