Transformation of modular robots by rotation: 3 + 1 musketeers for all orthogonally convex shapes

摘要

We study programmable matter systems consisting of modules that perform the minimal mechanical operation of rotating by 90° around each other. We represent the modules as nodes lying on the cells of a two-dimensional square grid. We are interested in characterising families whose shapes can be transformed into each other by a sequence of rotation moves that maintains global connectivity. Shapes can only be transformed into each other by rotation if they are colour-consistent , meaning that their nodes have identical colour cardinalities on a checkered colouring of the grid. We develop a generic centralised transformation and prove that, for any pair A , B of connected, colour-consistent, orthogonally convex shapes, it can transform A into B , using a seed of 3 or 4 nodes to trigger the transformation. The running time of our transformation is an optimal O ( n 2 ) sequential moves, where n = | A | = | B | .