Abstract
Graph signature is a fast isomorphism test that is used in self reconfiguration planning of modular robots. In case of dealing with homomorphic modules, the required time to calculate the signature grows exponentially with the number of symmetry lines. We tackle this problem by introducing an isomorphism- invariant signature calculation method, which is based on the power centrality of nodes. We also introduce a new sample-based search method. Simulation results show the new method finds better solutions in a significantly shorter time.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Rus, D., Vona, M.: Crystalline robots: Self-reconfiguration with compressible unit modules. Autonomous Robots 10, 107–124 (2001)
Jørgensen, M., Østergaard, E., Lund, H.: Modular ATRON: Modules for a self-reconfigurable robot. In: 2004 IEEE/RSJ Int. Conf. on Intelligent. Robots & Systems (IROS), pp. 2068–2073 (2004)
Vassilvitskii, S., Kubica, J., Rieffel, E., Suh, J., Yim, M.: On the general reconfiguration problem for expanding cube style modular robots. In: Proceedings - IEEE International Conference on Robotics and Automation, pp. 801–808 (2002)
Kotay, K., Rus, D., Vona, M., McGray, C.: Self-reconfiguring robotic molecule. In: Proceedings - IEEE International Conference on Robotics and Automation, pp. 424–431 (1998)
Murata, S., Yoshida, E., Kamimura, A., Kurokawa, H., Tomita, K., Kokaji, S.: M-TRAN: Self-reconfigurable modular robotic system. IEEE/ASME Trans. on Mechatronics 7, 431–441 (2002)
Castano, A., Shen, W., Will, P.: CONRO: towards deployable robots with inter-robot metamorphic capabilities. Autonomous Robots 8, 309–324 (2000)
Sproewitz, E., Billard, A., Dillenbourg, P., Ijspeert, A.J.: Roombots—Mechanical Design of Self-Reconfiguring Modular Robots for Adaptive Furniture. In: IEEE International Conference on Robotics and Automation, pp. 4259–4264 (2009)
Yim, M., Duff, D.G., Roufas, K.D.: PolyBot: a modular reconfigurable robot. In: Proceedings - IEEE International Conference on Robotics and Automation, pp. 514–520 (2000)
Moeckel, R., Jaquier, C., Drapel, K., Dittrich, E., Upegui, A., Ijspeert, A.: Exploring adaptive locomotion with YaMoR, a novel autonomous modular robot with Bluetooth interface. Industrial Robot 33, 285–290 (2006)
Salemi, B., Moll, M., Shen, W.: Superbot: A deployable, multi-functional, and modular self-reconfigurable robotic system. In: IEEE International Conference on Intelligent Robots and Systems, pp. 3636–3641 (2006)
Asadpour, M., Sproewitz, A., Billard, A., Dillenbourg, P., Ijspeert, A.: Graph signature for self-reconfiguration planning. In: 2008 IEEE/RSJ International Conference on Intelligent Robots and Systems, IROS, pp. 863–869 (2008)
Asadpour, M., Ashtiani, M., Sproewitz, A., Ijspeert, A.: Graph signature for self-reconfiguration planning of modules with symmetry. In: 2009 IEEE/RSJ International Conference on Intelligent Robots and Systems, IROS, pp. 5295–5300 (2009)
Bonacich, P.: Power and Centrality: A Family of Measures. The American Journal of Sociology 92, 1170–1182 (1987)
Yim, M., Goldberg, D., Casal, A.: Connectivity planning for closed-chain reconfiguration. In: Proceedings of SPIE - The Int. Society for Optical Engineering, pp. 402–412 (2000)
Casal, A., Yim, M.: Self-reconfiguration planning for a class of modular robots. In: Proceedings of SPIE - The International Society for Optical Engineering, pp. 246–257 (1999)
Hou, F., Shen, W.: Distributed, dynamic, and autonomous reconfiguration planning for chain-type self-reconfigurable robots. In: Proceedings - IEEE International Conference on Robotics and Automation, pp. 3135–3140 (2008)
Garey, M., Johnson, D.: Computers and Intractability: A Guide to the Theory of NP-Completeness (Series of Books in the Mathematical Sciences). W.H. Freeman (1979)
Luks, E.: Isomorphism of graphs of bounded valence can be tested in polynomial time. Journal of Computer and System Sciences 25, 42–65 (1982)
Jiang, X., Bunke, H.: Optimal quadratic-time isomorphism of ordered graphs. Pattern Recognition 32, 1273–1283 (1999)
Lavalle, S.M.: Rapidly-Exploring Random Trees: A New Tool for Path Planning (1998)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Golestan, K., Asadpour, M., Moradi, H. (2013). A New Graph Signature Calculation Method Based on Power Centrality for Modular Robots. In: Martinoli, A., et al. Distributed Autonomous Robotic Systems. Springer Tracts in Advanced Robotics, vol 83. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-32723-0_36
Download citation
DOI: https://doi.org/10.1007/978-3-642-32723-0_36
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-32722-3
Online ISBN: 978-3-642-32723-0
eBook Packages: EngineeringEngineering (R0)