Distributed and Dynamic Map-less Self-reconfiguration for Microrobot Networks

MEMS micro robots are low-power and low memory capacity devices that can sense and act. One of the most challenges in MEMS micro robot applications is the self-reconfiguration, especially when the efficiency and the scalability of the algorithm are required. In the literature, if we want a self-reconfiguration of micro robots to a target shape consisting of P positions, each micro robot should have a memory capacity of P positions. Therefore, if P equals to millions, each node should have a memory capacity of millions of positions. Therefore, this is not scalable. In this paper, nodes do not record any position, we present a self-reconfiguration method where a set of micro robots are unaware of their current position and do not have the map of the target shape. In other words, nodes do not store the positions that build the target shape. Consequently, memory usage for each node is reduced to O(1). An algorithm of self-reconfiguration to optimize the communication is deeply studied showing how to manage the dynamicity (wake up and sleep of micro robots) of the network to save energy. Our algorithm is implemented in Meld, a declarative language, and executed in a real environment simulator called DPRSim.