Distributed and Efficient Algorithm for Self-reconfiguration of MEMS Microrobots

International audienceSelf-reconfiguration for moving MEMS microrobots currently needs a positioning system and a map of the target shape. Traditional positioning solutions like GPS or multilateration are not applicable in the micro-world and maps sharing does not scale. In this paper we present self-reconfiguration method where nodes are unaware of their positions, and where they do not have the final coordinates of each microrobots. In other words, nodes do not store the correct positions that build the target shape. Consequently memory usage for each node is reduced to O(1). This algorithm does not need message exchange to achieve the self reconfiguration from a chain to square configuration (microrobots are organized in square shape) that represents the optimal logical topology for messages sending and it ensures a Snap-connectivity. Obtained results show a rapid convergence of the algorithm. The worst-case time complexity is of n movement rounds, where n represents the number of microrobots. Our algorithm is implemented in the declarative language MELD and executed in the simulator DPRSim