Internal localization, the problem of estimating relative pose for each module of a modular robot, is a prerequisite for many shape control, locomotion, and actuation algorithms. In this paper, we propose a robust hierarchical approach that uses normalized cut to identify dense sub-regions with small mutual localization error, then progressively merges those sub-regions to localize the entire ensemble. Our method works well in both two and three dimensions, and requires neither exact measurements nor rigid inter-module connectors. Most of the computations in our method can be distributed effectively. The result is a robust algorithm that scales to large ensembles. We evaluate our algorithm in two- and three-dimensional simulations of scenarios with up to 10,000 modules.
Ashley-Rollman, M.P., Goldstein, S.C., Lee, P., Mowry, T.C. and Pillai, P. (2007). Meld: a declarative approach to programming ensembles . IEEE/RSJ International Conference on Intelligent Robots and Systems, 2007 (IROS 2007), pp. 2794-2800.
2.
Biswas, P., Lian, T.C., Wang, T.C. and Ye, Y. (2006). Semi-definite programming based algorithms for sensor network localization. ACM Transactions on Sensor Networks , 2(2): 188-220.
3.
Blanco, J.L., Gonzalez, J. and Fernandez-Madrigal, J.A. (2006). Consistent observation grouping for generating metric-topological maps that improves robot localization . Proceedings of IEEE International Conference on Robotics and Automation (ICRA2006), pp. 818-823.
4.
Brunskill, E., Kollar, T. and Roy, N. (2007). Topological mapping using spectral clustering and classification. IEEE/RSJ International Conference on Intelligent Robots and Systems, 2007 (IROS 2007), pp. 3491-3496.
5.
Ceri, S., Gottlob, G. and Tanca, L. (1989). What you always wanted to know about Datalog (and never dared to ask). IEEE Transactions on Knowledge and Data Engineering, 1(1): 146-166.
6.
Crick, C. and Pfeffer, A. (2003). Loopy belief propagation as a basis for communication in sensor networks. Proceedings of the Nineteenth Conference on Uncertainty in Artificial Intelligence (UAI-2003), Meek, C. and Kjærulff, U. (eds). San Francisco, CA, Morgan Kaufmann.
7.
Duckett, T., Marsland, S. and Shapiro, J. (2002). Fast, on-line learning of globally consistent maps. Autonomous Robots, 12(3): 287-300.
8.
Frese, U., Larsson, P. and Duckett, T. (2005). A multilevel relaxation algorithm for simultaneous localisation and mapping. IEEE Transactions on Robotics, 21(2): 1-12.
9.
Gilpin, K., Kotay, K., Rus, D. and Vasilescu, I. (2008). Miche: modular shape formation by self-disassembly . The International Journal of Robotics Research, 27(3-4): 345-372.
10.
Goldstein, S.C. and Mowry, T. (2004). Claytronics: A scalable basis for future robots . Robosphere.
11.
Grisetti, G., Grzonka, S., Stachniss, C., Pfaff, P. and Burgard, W. (2007a). Efficient estimation of accurate maximum likelihood maps in 3D. IEEE/RSJ International Conference on Intelligent Robots and Systems, 2007 (IROS 2007), pp. 3472-3478.
12.
Grisetti, G., Stachniss, C., Grzonka, S. and Burgard, W. (2007b). A tree parameterization for efficiently computing maximum likelihood maps using gradient descent. Proceedings of Robotics: Science and Systems. Atlanta, GA.
13.
Loo, B.T., Condie, T., Garofalakis, M., Gay, D.E., Hellerstein, J.M., Maniatis, P., Ramakrishnan, R., Roscoe, T. and Stoica, I. (2006). Declarative networking: language, execution and optimization. Proceedings of the 2006 ACM SIG-MOD International Conference on Management of Data. New York , ACM Press, pp. 97-108.
14.
Lu, F. and Milios, E. (1997). Globally consistent range scan alignment for environment mapping. Autonomous Robots, 4(4): 333-349.
15.
Olson, E., Leonard, J. and Teller, S. (2006). Fast iterative alignment of pose graphs with poor initial estimates. Proceedings 2006 IEEE International Conference on Robotics and Automation, 2006 (ICRA 2006), pp. 2262-2269.
16.
Pillai, P., Campbell, J., Kedia, G., Moudgal, S. and Sheth, K. (2006). A 3D fax machine based on claytronics. IEEE/RSJ International Conference on Intelligent Robots and Systems , pp. 4728-4735.
17.
Reshko, G. (2004). Localization techniques for synthetic reality . Master's Thesis, Carnegie Mellon University.
18.
Roufas, K., Zhang, Y., Duff, D. and Yim, M. (2001). Six degree of freedom sensing for docking using IR LED emitters and receivers. ISER '00: Experimental Robotics VII. London, Springer, pp. 91-100.
19.
Shang, Y., Ruml, W., Zhang, Y. and Fromherz, M.P.J. (2003). Localization from mere connectivity. Proceedings of the 4th ACM International Symposium on Mobile Ad Hoc Networking and Computing. New York, ACM Press, pp. 201- 212.
20.
Shi, J. and Malik, J. (2000). Normalized cuts and image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 22(8): 888-905.
21.
Støy, K. (2003). Emergent control of self-reconfigurable robots . PhD Thesis, University of Southern Denmark.
22.
Umeyama, S. (1991). Least-squares estimation of transformation parameters between two point patterns. IEEE Transactions on Pattern Analysis and Machine Intelligence, 13(4): 376-380.
23.
Wang, Z., Zheng, S., Boyd, S. and Yez, Y. (2006). Further relaxations of the SDP approach to sensor network localization. Technical Report, Stanford University .
24.
Yang, P., Freeman, R.A., Gordon, G., Lynch, K., Srinivasa, S. and Sukthankar, R. (2008). Decentralized estimation and control of graph connectivity in mobile sensor networks. American Control Conference .
25.
Yim, M., Duff, D.G. and Roufas, K.D. (2000). Polybot: a modular reconfigurable robot. Proceedings IEEE International Conference on Robotics and Automation, 2000 (ICRA '00), Volume 1, pp. 514-520.
26.
Yim, M., Shen, W.M., Salemi, B., Rus, D., Moll, M., Lipson, H., Klavins, E. and Chirikjian, G.S. (2007). Modular self-reconfigurable robot systems: challenges and opportunities for the future. IEEE Robotics and Automation Magazine, 14: 43-52.
27.
Zivkovic, Z., Bakker, B. and Krose, B. (2005). Hierarchical map building using visual landmarks and geometric constraints. IEEE/RSJ International Conference on Intelligent Robots and Systems, 2005 (IROS 2005), pp. 2480- 2485.
28.
Zivkovic, Z., Booij, O. and Kröse, B. (2007). From images to rooms. Robotics and Autonomous Systems, 55(5): 411- 418.
