Deterministic distributed algorithm for self-reconfiguration of modular robots from arbitrary to straight chain configurations

Abstract

The problem addressed is the reconfiguration of a system of hexagonal metamorphic robots from an initial arbitrary shape configuration I, to a straight chain goal configuration, G. This is the first time a fully distributed deterministic algorithm has been written to achieve the parallel reconfiguration of a system of homogeneous modules from an initial arbitrary shape to a straight chain goal configuration. The contribution of this paper is an algorithm that uses no pre-processing or message passing to accomplish reconfiguration. The algorithm eliminates the possibility of module collision by assuming modules have the capability to detect another module at a distance of one cell away on each of their six sides. The algorithm is successful as long as: the system starts in an initial configuration that satisfies admissibility requirements, the goal cells are known to all modules, and if every module is equipped with sensors to determine if the cell adjacent to and in the same direction as a neighboring empty cell is occupied. A discrete-event simulator tests the algorithm.