We consider the theoretical model of Crystalline robots, which have been introduced and prototyped by the robotics community. These robots consist of independently manipulable unit-square atoms that can extend contract arms on each side and attach detach from neighbors. These operations suffice to reconfigure between any two given (connected) shapes. The worstcase number of sequential moves required to transform one connected configuration to another is known to be ( n). However, in principle, atoms can all move simultaneously. We develop a parallel algorithm for reconfiguration that runs in only O(logn) parallel steps, although the total number of operations increases slightly to ( n logn). The result is the first (theoretically) almost-instantaneous universally reconfigurable robot built from simple units.
Self-reconfigurable robots are versatile systems consisting of large numbers of independent modules. Effective use of these systems requires parallel actuation and planning, both for efficiency and independence from a central controller. In this paper we present the PacMan algorithm, a technique for distributed actuation and planning for systems with two- or three-dimensional unit-compressible modules. We give two versions of the algorithm along with correctness analysis. We also analyze the parallel actuation capability of the algorithm, showing that it will not deadlock and will avoid disconnecting the robot. We have implemented PacMan on the Crystal robot, a hardware system developed in our lab, and we present experiments and discuss the feasibility of large-scale implementation. We discuss a robotic system composed of i>Crystalline modules. Crystalline modules can aggregate together to form distributed robot systems. Crystalline modules can move relative to each other by expanding and contracting. This actuation mechanism permits automated shape metamorphosis. We describe the Crystalline module concept and show the basic motions that enable a Crystalline robot system to self-reconfigure. We present an algorithm for general self-reconfiguration and describe simulation experiments. In this article we examine the problem of dynamic self-reconfiguration of a class of modular robotic systems referred to as metamorphic systems. A metamorphic robotic system is a collection of mechatronic modules, each of which has the ability to connect, disconnect, and climb over adjacent modules. A change in the macroscopic morphology results from the locomotion of each module over its neighbors. Metamorphic systems can therefore be viewed as a large swarm of physically connected robotic modules that collectively act as a single entity. What distinguishes metamorphic systems from other reconfigurable robots is that they possess all of the following properties: (1) a large number of homogeneous modules; (2) a geometry such that modules fit within a regular lattice; (3) self-reconfigurability without outside help; (4) physical constraints which ensure contact between modules. In this article, the kinematic constraints governing metamorphic robot self-reconfiguration are addressed, and lower and upper bounds are established for the minimal number of moves needed to change such systems from any initial to any final specified configuration. These bounds are functions of initial and final configuration geometry and can be computed very quickly, while it appears that solving for the precise number of minimal moves cannot be done in polynomial time. It is then shown how the bounds developed here are useful in evaluating the performance of heuristic motion planning reconfiguration algorithms for metamorphic systems. © 1996 John Wiley & Sons, Inc. We present a complete, local, and parallel reconfiguration algorithm for metamorphic robots made up of Telecubes, six degree of freedom cube shaped modules currently being developed at PARC. We show that by using 2 spl times 2 spl times 2 meta-modules we can achieve completeness of reconfiguration space using only local rules. Furthermore, this reconfiguration can be done in place and massively in parallel with many simultaneous module movements. Finally we present a loose quadratic upper bound on the total number of module movements required by the algorithm.