Scalable Distributed Protocol for Modular Micro-Robots Network Reorganization

The programmable material is one of the most challenging problems in micro-robot networking. In addition to the problems that arise by the miniaturization of millimeter-scale mobile devices, the conception of the distributed asynchronous algorithms allowing the coordination of large number of robots remains a very complex task. Micro-robot network represents one of the implementations of the Internet of things, where a set of micro-robots react to an order submitted on a wireless down-link channel specifying a global goal. This goal corresponds to a target shape in the case of shape-shifting problem. Programmable materials have many applications in the field of paintable displays, prototyping, locomotion, etc. We propose in this paper an original flexible distributed algorithm allowing to reorganize a modular micro-robot network into a desired target shape (physical topology). The efficiency of such an algorithm is assessed on the basis of the memory requirements, the communication load, and the number of performed movements to reach the final shape. The proposed algorithm shows a great flexibility concerning the range of target shapes that can be achieved, in part because there is no need for an explicit description of the final shape. To assess the computational performances of the presented algorithm, we proposed a linear programming model of the shape-shifting problem that provides a lower bound of optimized criteria. The comparison of our results with those given by the relaxed linear programming proves the efficiency of our approach.