When multiple robots cooperatively explore an environment, maps from individual robots must be merged to produce a single globally consistent map. This is a challenging problem when the robots do not have a common reference frame or global positioning. In this paper, we describe an algorithm for merging embedded topological maps. Topological maps provide a concise description of the navigability of an environment, and, with measurements easily collected during exploration, the vertices of the map can be embedded in a metric space. Our algorithm uses both the structure and the geometry of topological maps to determine the best correspondence between maps with single or multiple overlapping regions. Experiments with simulated and real-world data demonstrate the efficacy of our algorithm.
Get full access to this article
View all access options for this article.
References
1.
Beevers, K. R. and Huang, W. H. 2005. Loop closing in topological maps . Proceedings of the International Conference on Robotics and Automation (ICRA 2005), Barcelona, Spain, pp. 4378-4383 .
2.
Besl, P. and McKay, N. 1992. A method for registration of 3-D shapes . IEEE Transactions on Pattern Analysis and Machine Intelligence14(2): 239-256 .
3.
Brown, L. 1992. A survey of image registration techniques . ACM Computing Surveys24(4): 325-376 .
4.
Bunke, H. 1997. On a relation between graph edit distance and maximum common subgraph . Pattern Recognition Letters18(8): 689-694 .
5.
Bunke, H. 2000. Graph matching: Theoretical foundations, algorithms, and applications . International Conference on Vision Interface, Montreal, Quebec, Canada, May, pp. 82-88 .
6.
Bunke, H. and Allermann, G. 1983. Inexact graph matching for structural pattern recognition . Pattern Recognition Letters1(4): 245-253 .
7.
Chen, Y. and Medioni, G. 1992. Object modelling by registration of multiple range images . Image and Vision Computing10(3): 145-155 .
8.
Conte, D., Foggia, P., Sansone, C., and Vento, M. 2004. Thirty years of graph matching in pattern recognition . International Journal of Pattern Recognition and Artificial Intelligence18(3): 265-298 .
9.
Day, W. and Edelsbrunner, H. 1984. Efficient algorithms for agglomerative hierarchical clustering methods . Journal of Classification1(7): 1-24 .
10.
Dedeoglu, G. and Sukhatme, G. 2000. Landmark-based matching algorithm for cooperative mapping by autonomous robots . Proceedings of the 2000 International Symposium on Distributed Autonomous Robotic Systems (DARS), Knoxville, TN, October 4-6, pp. 251-260 .
11.
Duckett, T., Marsland, S., and Shapiro, J. 2000. Learning globally consistent maps by relaxation . Proceedings of the 2000 IEEE International Conference on Robotics and Automation, San Francisco, CA, April 24-28, pp. 3841-3846 .
12.
Dudek, G., Jenkin, M., Milos, E., and Wilkes, D. 1998. Topological exploration with multiple robots . Proceedings of the 7th International Symposium on Robotics with Applications (ISORA’98), Anchorage, Alaska, May 10-14
13.
Durand, P., Pasari, R., Baker, J., and Tsai, C. 1999. An efficient algorithm for similarity analysis of molecules . Internet Journal of Chemistry2, article 17 .
14.
Fenwick, J., Newman, P., and Leonard, J. 2002. Cooperative concurrent mapping and localization . Proceedings of the 2002 IEEE International Conference on Robotics and Automation, Washington, DC, May 11-15, pp. 1810-1817 .
15.
Fitzpatrick, J., Hill, D., and Maurer, C Jr. 2000. Image registration. Handbook of Medical Imaging. Volume 2: Medical Image Processing and Analysis, M. Sonka and J. Fitzpatrick, editors, SPIE, Bellingham, WA , chapter 8.
16.
Golfarelli, M., Maio, D., and Rizzi, S. 1998. Elastic correction of dead-reckoning errors in map building . Proceedings of the 1998 IEEE/RSJ International Conference on Intelligent Robots and Systems, Victoria, BC, Canada, pp. 905-911 .
17.
Grabowski, R., Navarro-Serment, L., Paredis, C., and Khosla, P. 1999. Heterogeneous teams of modular robots for mapping and exploration . Autonomous Robots8(3): 293-308 .
18.
Huang, W. H. and Beevers, K. R. 2004a. Topological map merging . Proceedings of the 7th International Symposium on Distributed Autonomous Robotic Systems (DARS 2004), Toulouse, France, June 23-25, pp. 91-100 .
19.
Huang, W. H. and Beevers, K. R. 2004b. Topological mapping with sensing-limited robots . Proceedings of the 6th International Workshop on the Algorithmic Foundations of Robotics (WAFR 2004), Utrecht, the Netherlands, July 11-13, pp. 367-382 .
20.
Jennings, J., Kirkwood-Watts, C., and Tanis, C. 1998. Distributed map-making and navigation in dynamic environments . Proceedings of the 1998 IEEE/RSJ International Conference on Intelligent Robots and Systems, Victoria, BC, Canada, pp. 1695-1701 .
21.
Ko, J., Stewart, B., Fox, D., Konolige, K., and Limketkai, B. 2003. A practical, decision-theoretic approach to multi-robot mapping and exploration . Proceedings of the 2003 IEEE/RSJ International Conference on Intelligent Robots and Systems, Las Vegas, NV, October 27-31, pp. 212-217 .
22.
Konolige, K., Fox, D., Limketkai, B., Ko, J., and Stewart, B. 2003. Map merging for distributed robot navigation . Proceedings of the 2003 IEEE/RSJ International Conference on Intelligent Robots and Systems, Las Vegas, NV, October 27-31, pp. 212-217 .
Lu, F. and Milios, E. 1997. Globally consistent range scan alignment for environment mapping . Autonomous Robots4(4): 333-349 .
25.
McGregor, J. 1982. Backtrack search algorithms and the maximal common subgraph problem . Software Practice and Experience12(1): 23-34 .
26.
Stroupe, A., Martin, M., and Balch, T. 2001. Distributed sensor fusion for object position estimation by multirobot systems . Proceedings of the 2001 IEEE International Conference on Robotics and Automation, Seoul, Korea, May 21-26, pp. 1092-1098 .
27.
Thrun, S. 2001. A probabilistic online mapping algorithm for teams of mobile robots . International Journal of Robotics Research20(5): 335-363 .
