IEEE Robotics & Automation Magazine - June 2014 - 72

Table 1. The processing time and efficiency of
three experiments.
Experiment

1

2

3

1

2

3

Method

Processing (s)

Verification (%)

PGVD based

12

10

13

95

91

92

Map segmentation [30]

105

83

106

95

92

94

ARW map merging [4]

168

150

152

93

88

92

1 : the Radish data set, 2 : the two CoroBots, and 3 : the three CoroBots.

grid map. The proposed method has been shown to preferentially fuse areas of the maps that have low uncertainty. Experiments and comparison with other established methods show
that it is effective and 9-14 times faster.
In future work, it would be interesting to use the structure
of the GVD to verify the accuracy of the map matching. If different pairs of edges are matched with high accuracy, then the
structure of the GVD could allow us to determine that both
sets of edges correspond to the same transformation, increasing the likelihood of correct matching.
Acknowledgment
This research is supported by the Natural Sciences and Engineering Research Council of Canada and the Canada Foundation for Innovation. We would also like to thank Jacqueline
Paull for her contributions.
References
[1] S. Saeedi, L. Paull, M. Trentini, M. Seto, and H. Li, "Efficient map merging
using a probabilistic generalized Voronoi diagram," in Proc. IEEE/RSJ Int.
Conf. Intelligent Robots Systems, 2012, pp. 4419-4424.
[2] H. Durrant-Whyte and T. Bailey, "Simultaneous localization and mapping
(SLAM): Part I the essential algorithms," IEEE Robot. Autom. Mag., vol. 13, no.
3, pp. 108-117, 2006.
[3] S. Thrun, W. Burgard, and D. Fox, Probabilistic Robotics. Cambridge, MA:
MIT Press, 2005.
[4] A. Birk and S. Carpin, "Merging occupancy grid maps from multiple robots,"
Proc. IEEE: Special Issue Multi-Robot Syst., vol. 94, no. 7, pp. 1384-1387, 2006.
[5] J. L. Gould, "Honey bee cognition," Cognition, vol. 37, pp. 83-103, Nov. 1990.
[6] T. Guilford, S. Roberts, D. Biro, and I. Rezek, "Positional entropy during
pigeon homing II: Navigational interpretation of Bayesian latent state models,"
J. Theor. Biol., vol. 227, no. 1, pp. 25-38, 2004.
[7] H. Bunke, "Graph matching: Theoretical foundations, algorithms, and
applications," in Proc. Int. Conf. Vision Interface, 2000, pp. 82-88.
[8] A. Howard, "Multi-robot simultaneous localization and mapping using
particle filters," Int. J. Robot. Res., vol. 25, no. 12, pp. 1243-1256, 2006.
[9] R. Smith, M. Self, and P. Cheeseman, "A stochastic map for uncertain spatial relationships," in Proc. 4th Int. Symp. Robotics Research, 1987, pp. 467-474.
[10] P. Dario and R. Chatila, Multi-Robot SLAM with Sparse Extended Information Filters (Springer Tracts in Advanced Robotics vol. 15). Berlin, Heidelberg, Germany: Springer, pp. 254-266, 2005.
[11] X. S. Zhou and S. I. Roumeliotis, "Multi-robot SLAM with unknown initial correspondence: The robot rendezvous case," in Proc. IEEE/RSJ Int. Conf.
Intelligent Robots Systems, 2006, pp. 1785-1792.
[12] A. Gil, O. Reinoso, M. Ballesta, and J. Miguel, "Multi-robot visual SLAM using a
Rao-Blackwellized particle filter," Robot. Auton. Syst., vol. 58, no. 1, pp. 68-80, 2010.
[13] D. Hahnel, W. Burgard, D. Fox, and S. Thrun, "An efficient FastSLAM
algorithm for generating maps of large-scale cyclic environments from raw
72

*

IEEE ROBOTICS & AUTOMATION MAGAZINE

*

June 2014

laser range measurements," in Proc. IEEE/RSJ Int. Conf. Intelligent Robots Systems, 2003, pp. 206-211.
[14] S. Thrun, "A probabilistic on-line mapping algorithm for teams of mobile
robots," Int. J. Robot. Res., vol. 20, no. 5, pp. 335-363, 2001.
[15] S. Carpin, "Fast and accurate map merging for multi-robot systems,"
Auton. Robot., vol. 25, no. 3, pp. 305-316, 2008.
[16] S. Carpin, A. Birk, and V. Jucikas, "On map merging," Robot. Auton. Syst.,
vol. 53, no. 1, pp. 1-14, Oct. 31, 2005.
[17] H. Choset, K. M. Lynch, S. Hutchinson, G. Kantor, W. Burgard, L. E. Kavraki,
and S. Thrun, Principles of Robot Motion: Theory, Algorithms, and Implementations
(Intelligent Robotics and Autonomous Agents). Cambridge, MA: MIT Press, 2005.
[18] E. R. Davies, Machine Vision, Theory, Algorithms, Practicalities, 3rd ed.
San Francisco, CA: Morgan Kaufmann, 2005.
[19] H. Blum, "A transformation for extracting new descriptors of shape," in
Models for the Perception of Speech and Visual Form. Cambridge, MA: MIT
Press, 1967, pp. 362-381.
[20] B. Lau, C. Sprunk, and W. Burgard, "Improved updating of Euclidean distance maps and Voronoi diagrams," in Proc. IEEE/RSJ Int. Conf. Intelligent
Robots Systems, 2010, pp. 281-286.
[21] P. Beeson, N. K. Jong, and B. Kuipers, "Towards autonomous topological
place detection using the extended Voronoi graph," in Proc. IEEE/RSJ Int.
Conf. Robotics Automation, 2004, pp. 4373-4379.
[22] H. Choset and K. Nagatani, "Topological simultaneous localization and
mapping (SLAM): Toward exact localization without explicit localization,"
IEEE Trans. Robot. Autom., vol. 17, no. 2, pp. 125-137, 2001.
[23] H. Choset, S. Walker, K. Eiamsa-Ard, and J. Burdick, "Sensor-based
exploration: Incremental construction of the hierarchical generalized Voronoi
graph," Int. J. Robot. Res., vol. 19, no. 2, pp. 125-148, 2000.
[24] J. O. Wallgrum, "Voronoi graph matching for robot localization and mapping," Trans. Comput. Sci. IX, 2010, vol. 6290, pp. 76-108.
[25] P. Beeson, J. Modayil, and B. Kuipers, "Factoring the mapping problem:
Mobile robot map-building in the hybrid spatial semantic hierarchy," Int. J.
Robot. Res., vol. 29, no. 4, pp. 428-459, 2010.
[26] A. Ranganathan, E. Menegatti, and F. Dellaert, "Bayesian inference in the
space of topological maps," IEEE Trans. Robot., vol. 22, no. 1, pp. 92-107, 2006.
[27] S. Friedman, H. Pasula, and D. Fox, "Voronoi random fields: Extracting
the topological structure of indoor environments via place labeling," in Proc.
Int. Joint Conf. Artificial Intelligence, 2007, pp. 2109-2114.
[28] D. Silver, D. Ferguson, A. Moms, and S. Thayer, "Feature extraction for
topological mine maps," in Proc. IEEE/RSJ Int. Conf. Intelligent Robots Systems, 2004, pp. 773-779.
[29] W. H. Huang and K. R. Beevers, "Topological map merging," Int. J. Robot.
Res., vol. 24, no. 8, pp. 601-613, 2005.
[30] S. Saeedi, L. Paull, M. Trentini, and H. Li, "Multiple robot simultaneous
localization and mapping," in Proc. IEEE/RSJ Int. Conf. Intelligent Robots Systems, 2011, pp. 853-858.
[31] D. Fox, W. Burgard, S. Thrun, and A. B. Cremers, "Position estimation for
mobile robots in dynamic environments," in Proc. American Association for
Artificial Intelligence, 1998, pp. 983-988.
[32] A. Howard and N. Roy. (2003). The robotics data set repository (Radish).
[Online]. Available: http://cres.usc.edu/radishrepository/

Sajad Saeedi, COBRA Group, University of New Brunswick,
Fredericton, Canada. E-mail: sajad.saeedi.g@unb.ca.
Liam Paull, CSAIL Lab, Massachusetts Institute of Technology,
Cambridge. E-mail: lpaull@csail.mit.edu.
Michael Trentini, Defence Research and Development CanadaSuffield, Alberta, Canada. E-mail: Mike.Trentini@drdc-rddc.gc.ca.
Mae Seto, Defence Research and Development Canada-Atlantic, Nova Scotia, Canada. E-mail: mae.seto@drdc-rddc.gc.ca.
Howard Li, COBRA Group, University of New Brunswick,
Fredericton, Canada. E-mail: howard@unb.ca.
http://cres.usc.edu/radishrepository/
Table of Contents for the Digital Edition of IEEE Robotics & Automation Magazine - June 2014
