Self-reconfiguration of shape-shifting modular robots with triangular structure

In this paper, we present a reconfiguration algorithm for shape-shifting modular robots with a triangular structure. The algorithm is derived from a novel description of the configuration space based on extended binary trees. Extended binary trees representing the same configuration are grouped into equivalence classes, which allows for a one-to-one correspondence between a configuration and its mathematical representation. Reconfiguration is then accomplished by a successive construction of the goal configuration, realized by moving individual modules along the surface of the robot and building up the binary tree of the goal configuration by populating unoccupied binary tree indices in ascending order with new modules. The algorithm is capable of solving the self-reconfiguration problem for modular robots with a triangular structure in O(n2) reconfiguration steps and is demonstrated on two reconfiguration examples. We then discuss the limits of the proposed methods, regarding constraints on the implementation and the lack of efficient collision avoidance, and outline possible resolutions.