A metamorphic robotic system is an aggregate of homogeneous robot units which can individually and selectively locomote in such a way as to change the global shape of the system. We introduce a mathematical framework for defining and analyzing general metamorphic robots. With this formal structure, combined with ideas from geometric group theory, we define a new type of configuration space for metamorphic robots—the state complex—which is especially adapted to parallelization. We present an algorithm for optimizing an input reconfiguration sequence with respect to elapsed time. A universal geometric property of state complexes—non-positive curvature—is the key to proving convergence to the globally timeoptimal solution obtainable from the initial path.
Get full access to this article
View all access options for this article.
References
1.
Abrams, A. 2000. Configuration Spaces and Braid Groups of Graphs, PhD thesis, UC Berkeley.
2.
Abrams, A. 2002. Configuration spaces of colored graphs . Geometriae Dedicata92: 185–194 .
3.
Abrams, A. and Ghrist, R. 2002. Finding topology in a factory: configuration spaces . American Mathematics Monthly(109): 140–150 .
4.
Abrams, A. and Ghrist, R. 2004. The geometry and topology of reconfiguration, in press.
5.
Bridson, M. and Haefliger, A. 1999. Metric Spaces of Non- Positive Curvature, Springer-Verlag, Berlin .
6.
Butler, Z., Byrnes, S., and Rus, D. 2001. Distributed motion planning for modular robots with unit-compressible modules . Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Maui, Hawaii.
7.
Butler, Z., Kotay, K., Rus, D., and Tomita, K. 2001. Cellular automata for decentralized control of self-reconfigurable robots . Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Workshop on Modular Robots, Seoul, Korea, May 21–26.
8.
Castano, A., Shen, W.N., and Will, P. 2000. CONRO: towards deployable robots with inter-robots metamorphic capabilities . Autonomous Robots8(3): 309–324 .
9.
Chirikjian, G. 1994. Kinematics of a metamorphic robotic system . Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), San Diego, CA.
10.
Chirikjian, G. and Pamecha, A. 1996. Bounds for selfreconfiguration of metamorphic robots . Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Minneapolis, MN.
11.
Chirikjian, G., Pamecha, A., and Ebert-Uphoff, I. 1996. Evaluating efficiency of self-reconfiguration in a class of modular robots . Journal of Robotics Systems13(5): 317–338 .
12.
Ghrist, R.W. and Koditschek, D.E. 2002. Safe cooperative robot dynamics on graphs . SIAM Journal on Control and Optimization40(5): 1556–1575 .
13.
Gromov, M. 1987. Hyperbolic groups. Essays in Group Theory, MSRI Publication Vol. 8, Springer-Verlag, Berlin .
14.
Kotay, K. and Rus, D. 1998. The self-reconfiguring robotic molecule: design and control algorithms . Proceedings of theWorkshop on the Algorithmic Foundations of Robotics (WAFR), Houston, TX.
15.
McGray, C. and Rus, D. 2000. Self-reconfigurable molecule robots as 3D metamorphic robots . Proceedings of the International Conference on Intelligent Robots and Systems (IROS), Takamatsu, Japan, October 30–November 5.
16.
Murata, S., Kurokawa, H., and Kokaji, S. 1994. Selfassembling machine . Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), San Diego, CA.
17.
Murata, S., Kurokawa, H.,Yoshida, E., Tomita, K., and Kokaji, S. 1998. A 3D self-reconfigurable structure . Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Leuven, Belgium.
18.
Murata, S.,Yoshida, E., Kamikura, A., Kurokawa, H., Tomita, K., and Kokaji, S. 2002. M-TRAN: self-reconfigurable modular robotic system . IEEE ASME Transactions on Mechatronics7(4): 431–441 .
19.
Nguyen, A., Guibas, L., and Yim, M. 2000. Controlled module density helps reconfiguration planning . Proceedings of theWorkshop on the Algorithmic Foundations of Robotics (WAFR), Hanover, NH.
20.
Niblo, G.A. and Reeves, L.D. 1998. The geometry of cube complexes and the complexity of their fundamental groups . Topology37(3): 621–633 .
21.
Pamecha, A., Ebert-Uphoff, I., and Chirikjian, G.S. 1997. Useful metric for modular robot motion planning . IEEE Transactions on Robotics and Automation13(4): 531–545 .
22.
Pratt, V. 1991. Modelling concurrency with geometry . Proceedings of the 18th Symposium on Principles of Programming Languages, Orlando, FL.
23.
Rus, D. and Vona, M. 2001. Crystalline robots: selfreconfiguration with unit-compressible modules . Autonomous Robots10(1): 107–124 .
24.
Walter, J., Tsai, E., and Amato, N. 2002. Choosing good paths for fast distributed reconfiguration of hexagonal metamorphic robots . Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Washington, DC, May 11–15.
25.
Walter, J.E., Welch, J.L., and Amato, N.M. 1999. Concurrent metamorphosis of hexagonal robot chains into simple connected configurations . IEEE Transactions on Robotics and Automation15(6): 1035–1045 .
26.
Walter, J., Welch, J., and Amato, N. 2000. Distributed reconfiguration of metamorphic robot chains . Proceedings of the ACM Symposium on Distributed Computing, Portland, OR.
27.
Yim, M. 1993. A reconfigurable robot with many modes of locomotion . Proceedings of the International Conference on Advanced Mechatronics, Tokyo, Japan.
28.
Yim, M., Lamping, J., Mao, E., and Chase, J. 1997. Rhombic dodecahedron shape for self-assembling robots. Xerox PARC Technical Report P9710777.
29.
Yim, M., Zhang, Y., Lamping, J., and Mao, E. 2001. Distributed control for 3D metamorphosis . Autonomous Robots10(1): 41–56 .
30.
Yoshida, E., Murata, S., Tomita, K., Kurokawa, H., and Kokaji, S. 1997. Distributed formation control of a modular mechanical system . Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Grenoble, France.
