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.

This paper presents an algorithm that deterministically plans the simultaneous, collision-free movement of n hexagonal metamorphic robots (modules) over any contiguous surface composed of modules in a hexagonal grid. A planning stage algorithm identifies narrow passages between surface cells where moving modules will come into contact. After identifying all narrow passages on a surface, our algorithm identifies the cells that can be used to build temporary structures across the entrance to each narrow passage using 1, 2, or 3 modules. The algorithm does not use intermodule message passing at any stage of the traversal, making it suitable for modules with limited communication capabilities. The algorithm maintains optimal spacing between moving modules throughout the traversal. Our current algorithm is an improvement over previous bridging algorithms because the bridging cells are situated such that when they are filled with modules, they do not form narrow passages (pockets) on the surface. In this paper, we also propose a multi-layered technique for finding longer bridges. We discuss the complexity and performance of our algorithms and give an example of the results of simulating them using a discrete event simulator.