Parallel self-reconfiguration for MEMS microrobots

MEMS microrobots are low-power and low-memory capacity devices that can sense and act. One of the most difficult challenges in MEMS microrobot applications is the self-reconfiguration, especially when the efficiency, parallelism and the scalability of the algorithm are required. Self-reconfiguration with shared map does not scale. Because the map (predefined position of the target shape) consists of P positions, and each node must have a memory capacity, at least, of P positions. Therefore, if P is very high, the self-reconfiguration will be not feasible. In this paper, we present an efficient reconfiguration algorithm, without predefined positions of the target shape, which reduces memory usage to O(1). This algorithm ensures the networks connectivity throughout all its execution time. This solution improves the execution time and the number of movements by using movement of different microrobots at the same time that we call parallelism of movement. Our algorithm is implemented in Meld, a declarative language, and executed in a real environment simulator called DPRSim.