Abstract
A key capability for teams of mobile robots is to cooperatively explore and map an environment. Maps created by one robot must be merged with those from another robot — a difficult problem when the robots do not have a common reference frame. This problem is greatly simplified when topological maps are used because they provide a concise description of the navigability of a space. In this paper, we formulate an algorithm for merging two topological maps that uses aspects of maximal subgraph matching and image registration methods. Simulated and real-world experiments demonstrate the efficacy of our algorithm.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
K. R. Beevers. Topological mapping and map merging with sensing-limited robots. Master’s thesis, Rensselaer Polytechnic Institute, Troy, NY, April 2004.
P. Besl and N. McKay. A method for registration of 3-D shapes. IEEE Trans. on Pattern Analysis and Machine Intelligence, 14(2):239–256, February 1992.
H. Bunke. On a relation between graph edit distance and maximum common subgraph. Pattern Recognition Letters, 18(8):689–694, 1997.
G. Dedeoglu and G.S. Sukhatme. Landmark-based matching algorithm for cooperative mapping by autonomous robots. In L. E. Parker, G. W. Bekey, and J. Barhen, editors, Distributed Autonomous Robotic Systems 4, pages 251–260. Springer-Verlag, 2000.
T. Duckett, S. Marsland, and J. Shapiro. Learning globally consistent maps by relaxation. In IEEE Intl. Conf. on Robotics & Automation, pages 3841–3846, 2000.
G. Dudek, M. Jenkin, E. Milos, and D. Wilkes. Topological exploration with multiple robots. In 7th Intl. Symp. on Robotics with Applications, 1998.
J. Fenwick, P. Newman, and J. Leonard. Cooperative concurrent mapping and localization. In IEEE Intl. Conf. on Robotics & Automation, 2002.
J.M. Fitzpatrick, D.L. Hill, and C.R. Maurer, Jr. Image registration. In M. Sonka and J. M. Fitzpatrick, editors, Handbook of Medical Imaging, volume 2: Medical Image Processing and Analysis, chapter 8. SPIE, 2000.
M. Golfarelli, D. Maio, and S. Rizzi. Elastic correction of dead-reckoning errors in map building. In Intl. Conf. on Intelligent Robots and Systems, pages 905–911, 1998.
J. Ko, B. Stewart, D. Fox, K. Konolige, and B. Limketkai. A practical, decisiontheoretic approach to multi-robot mapping and exploration. In Intl. Conf. on Intelligent Robots and Systems, 2003.
K. Konolige, D. Fox, B. Limketkai, J. Ko, and B. Stewart. Map merging for distributed robot navigation. In Intl. Conf. on Intelligent Robots and Systems, pages 212–217, 2003.
F. Lu and E. Milios. Globally consistent range scan alignment for environment mapping. Autonomous Robots, 4(4):333–349, 1997.
S. Thrun. A probabilistic online mapping algorithm for teams of mobile robots. Intl. Journal of Robotics Research, 20(5):335–363, 2001.
R. Wilson and E. Hancock. Structural matching by discrete relaxation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 19(6), June 1997.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2007 Springer
About this paper
Cite this paper
Huang, W.H., Beevers, K.R. (2007). Topological Map Merging. In: Alami, R., Chatila, R., Asama, H. (eds) Distributed Autonomous Robotic Systems 6. Springer, Tokyo. https://doi.org/10.1007/978-4-431-35873-2_10
Download citation
DOI: https://doi.org/10.1007/978-4-431-35873-2_10
Publisher Name: Springer, Tokyo
Print ISBN: 978-4-431-35869-5
Online ISBN: 978-4-431-35873-2
eBook Packages: EngineeringEngineering (R0)