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.
When @math strength is required but velocities are allowed to grow arbitrarily over time, reconfiguration takes @math steps @cite_11 . Note that this is for 2D robots and the third dimension is used as an intermediate.
@cite_11
1534588514
A self-reconfigurable (SR) robot is one composed of many small modules that autonomously act to change the shape and structure of the robot. In this paper we consider a general class of SR robot modules that have rectilinear shape that can be adjusted between fixed dimensions, can transmit forces to their neighbors, and can apply additional forces of unit maximum magnitude to their neighbors. We present a kinodynamically optimal algorithm for general reconfiguration between any two distinct, 2D connected configurations of n SR robot modules. The algorithm uses a third dimension as workspace during reconfiguration. This entire movement is achieved within O( √ n) movement time in the worst case, which is the asymptotically optimal time bound. The only prior reconfiguration algorithm achieving this time bound was restricted to linearly arrayed start and finish configurations (known as the “x-axis to y-axis problem”). All other prior work on SR robots assumed a constant velocity bound on module movement and so required at least time linear in n to do the reconfiguration.