Using a pocket-filling strategy for distributed reconfiguration of a system of hexagonal metamorphic robots in an obstacle-cluttered environment

We address the problem of reconfiguration planning for a metamorphic robotic system composed of a large number of hexagonal mobile robots. Our objective is to develop an algorithm to plan the concurrent movement of individual robots over a lattice composed of identical robots, from an initial configuration I to a goal configuration G, when G contains one or more obstacles. The contribution of this paper is a deterministic motion planning algorithm to envelop multiple obstacles in an admissible set of goal configurations while eliminating the risk of module collision or deadlock. We developed a discrete event simulator to test our algorithms, and every admissible G tested was filled successfully. We include a full proof of correctness and analysis of our algorithm.