The Self-Reconfiguring Crystal Robot

From DRLWiki

Jump to: navigation, search

Contents for This Page

Introduction

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.

Simulation of a "dog" reconfiguring into a "couch".

Our group has also considered several other self-reconfiguring systems: 1, 2, 3, 4.

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 [1], 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 [2], and Robert Fitch explored algorithms for the heterogeneous case—where the modules have unique types—in his dissertation in 2005 [3]. 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 [4] and new reconfiguration algorithms [5]. 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 [6] (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 [7].

[1] K. Tanie and H. Maekawa. Self-reconfigurable cellular robotic system. US Patent 5361186, 1993.
[2] Marsette Arthur Vona, III. A Two-Dimensional Crystalline Atomic Unit Modular Self-Reconfigurable Robot. Undergraduate Honors Thesis, Dartmouth College, 1999.
[3] Robert Charles Fitch. Heterogeneous self-reconfiguring robotics. Ph.D. Thesis, Dartmouth College, 2005.
[4] 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.
[5] 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.
[6] 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.
[7] 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.

Algorithms

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):

Image:t2c.gif

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.

In later work, we explored self-repair techniques and distributed reconfiguration, goal-recognition, locomotion, and splitting.

As noted above, other groups have also developed interesting and fast reconfiguration algorithms for crystalline robots.

Simulation

We have developed various simulators for crystalline robots, including Vona's XSim. The following animations, produced with an earlier simulator, demonstrate some simple reconfigurations.

Corner (29 KB Animated GIF)
Popper (73 KB Animated GIF)
Popperclose (53 KB Animated GIF)
Inchworm (54 KB Animated GIF)
Pentacube-popper (26 KB Animated GIF)
Translate (185 KB Animated GIF)

Hardware

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:

File:middle row async.avi

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.

File:InchTenSteps3x.avi File:InchTwoColumn3x.avi File:Blob1DivX.avi
File:Blob2DivX.avi File:StAloneInchWithSplit.avi File:RecursiveSplitDivX.avi

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.

Publications

Personal tools