The Self-Reconfiguring Crystal Robot
Contents for This Page
Self-reconfiguring robots change their shape without human intervention, and are typically designed with the goal of making arbitrary shapes. A general way to achieve this is to build a robot composed of many individual modules: if the modules can attach together into a structure, and if individual units can relocate within and about the structure, then self-reconfiguration is possible.
Since the early 1990s, several research groups have proposed a variety of ways to implement the modules. One concept our group has explored is a system composed of cubes (or squares in 2D) with expanding and contracting faces. We call this the crystalline robot concept because motion in this system in some ways resembles models of plastic deformation in solid materials with crystalline atomic structure. Continuing with this analogy, we call the modules in a crystalline robot atoms.
History and Research Context
We first developed and popularized the basic concept of crystalline robots in the late 1990s. As is often the case, we found that we were not the absolute first to consider the idea: a Japanese research group had previously described lattice modules with expanding faces in a patent document , but it appears this was their only publication on the subject.
Marsette Vona developed a theory and a 2D implementation of the crystalline system in his undergraduate honors thesis at Dartmouth College in 1999 , and Robert Fitch explored algorithms for the heterogeneous case—where the modules have unique types—in his dissertation in 2005 . Many other past and present members of our group have also worked on aspects of crystalline robots, our publications are listed below.
Several other research groups have also contributed new developments. Suh, Yim, and their collaborators at Xerox Parc developed a 3D module implementation  and new reconfiguration algorithms . Aloupis and collaborators from 8 other institutions recently published a planning algorithm for arbitrary reconfiguration in systems made of 2x2x2 meta-modules which requires only a linear number of parallel expansions and contractions  (previous algorithms were quadratic). While much of the work in reconfiguration planning for crystalline robots has considered only kinematics, Reif and Slee at Duke University have recently developed a model with relevant energetic constraints and reconfiguration planning algorithms which are proven optimal in that model .
 K. Tanie and H. Maekawa. Self-reconfigurable cellular robotic system. US Patent 5361186, 1993.
 Marsette Arthur Vona, III. A Two-Dimensional Crystalline Atomic Unit Modular Self-Reconfigurable Robot. Undergraduate Honors Thesis, Dartmouth College, 1999.
 Robert Charles Fitch. Heterogeneous self-reconfiguring robotics. Ph.D. Thesis, Dartmouth College, 2005.
 Suh, J.W., Homans, S.B., and Yim,M. Telecubes: Mechanical Design of a Module for Self-Reconfigurable Robotics. Proc. of the IEEE Intl. Conf. on Robotics and Automation, (ICRA), Washington D.C., May 11-15, 2002.
 Vassilvitskii, S., Suh, J.W. and Yim, M. A Complete, Local and Parallel Reconfiguration Algorithm for Cube Style Modular Robots. Proc. of the IEEE Intl. Conf. on Robotics and Automation, (ICRA), Washington D.C., May 11-15, 2002.
 Greg Aloupis, Sébastien Collette, Mirela Damian, Erik D. Demaine, Robin Flatland, Stefan Langerman, Joseph O'Rourke, Suneeta Ramaswami, Vera Sacristán, and Stefanie Wuhrer. Linear Reconfiguration of Cube-Style Modular Robots. Proceedings of the 18th Annual International Symposium on Algorithms and Computation, December 17–19, 2007, pages 208–219.
 John H. Reif and Sam Slee, Asymptotically Optimal Kinodynamic Motion Planning for Self-Reconfigurable Robots, Seventh International Workshop on the Algorithmic Foundations of Robotics (WAFR2006), NYC, New York, July 16-18, 2006.
Much of our work has focused on algorithm development for crystal systems. One fundamental problem is reconfiguration planning: given a start shape and a goal shape, find a short sequence of expand/contract and connect/disconnect operations which achieves the reconfiguration without self-collision. Often we also assume that the total structure must remain globally connected throughout the reconfiguration, and sometimes we also consider other constraints, such as environmental obstacles.
An early result was that any 2D crystal composed of 4x4 meta-modules could be reconfigured from one shape to another in quadratic time by melting the start shape into an intermediate linear configuration and then growing the goal shape. For example, a 2D table can change into a chair as follows (each square represents a 4x4 meta-module):
This result was complete, in the sense that it would work for any start and goal shape made of 4x4 meta-modules, but not optimal.
As noted above, other groups have also developed interesting and fast reconfiguration algorithms for crystalline robots.
We have developed various simulators for crystalline robots, including Vona's XSim. The following animations, produced with an earlier simulator, demonstrate some simple reconfigurations.
We built two generations of 2D crystal modules and performed experiments with groups of up to 16 modules. The first generation of modules had only one actuator which simultaneously controlled all four faces:
Since atoms never rotate, only half the faces require active connection mechanisms. Our first-generation crystal atom, with only three total actuators, was thus an interesting demonstration of minimality. However, we found that while one expansion actuator is theoretically sufficient, in practice it is more useful to have independent control of at least each axis. The second hardware generation thus includes independent axis control as well as stronger expansion motors, a more powerful microprocessor, and IR communication between adjacent atoms.
Both generations carried batteries and were able to operate untethered. We found that the complexity of reconfigurations we could demonstrate was severely limited by connection failures and un-modeled collisions due to misalignment and play in the expansion mechanisms.
- Zack Butler, Daniela Rus. Distributed Planning and Control for Modular Robots with Unit-Compressible Modules. The International Journal of Robotics Research 22(9):699-715, 2003.
- Daniela Rus, Zack Butler, Keith Kotay, Marsette Vona. Self-reconfiguring robots. Communications of the ACM 45(3):39-45, 2002.
- Zack Butler, Robert Fitch, Daniela Rus. Distributed Control for Unit-compressible Robots: Goal-recognition, Locomotion and Splitting. IEEE/ASME Trans. on Mechatronics 7(4):418-430, 2002.
- Daniela Rus, Marsette Vona. Crystalline Robots: Self-Reconfiguration with Compressible Unit Modules. Autonomous Robots 10(1):107-124, 2001.
- Robert Fitch, Zack Butler, Daniela Rus. 3D Rectilinear Motion Planning with Minimum Bends. Proceedings of IROS , 2001.
- Zack Butler, Sean Byrnes, Daniela Rus. Distributed Motion Planning for Modular Robots with Unit-Compressible Modules. Proceedings of IROS , 2001.
- Daniela Rus, Marsette Vona. A Physical Implementation of the Self-reconfiguring Cyristalline Robot. Proceedings of the IEEE Intl. Conference on Robotics and Automation pp. 1726--1733, 2000.
- Daniela Rus, Marsette Vona. A basis for self-reconfiguring robots using crystal modules. IEEE/RSJ International Conference on Intelligent Robots and Systems, 2000. (IROS 2000) 3:2194--2202, Takamatsu, Japan, 2000.
- Robert Fitch, Daniela Rus, Marsette Vona. A Basis for Self-Repair Robots Using Self-Reconfiguring Crystal Modules. Proceedings of Intelligent Autonomous Systems 2000 , 2000.
- Daniela Rus, Marsette Vona. Self-reconfiguration Planning with Compressible Unit Modules. Proceedings of the IEEE Intl. Conference on Robotics and Automation 4:2513--2520, Detroit, MI, USA, 1999.