Towards Programmable Material: flexible distributed algorithm for modular robots shape-shifting

The programmable material is one of the most challenging problem in micro-robotic field. In addition to the problems raised by manufacturing 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. Programmable materials have many applications in field of paintable displays, prototyping, locomotion, ... We propose in this paper an original flexible distributed algorithm allowing to reorganize a set of modular micro-robot into a desired target shape. The efficiency of such algorithm is assessed on the basis of the memory requirements, communication load and the amount of performed movements to reach the final shapes. The proposed algorithm shows a great flexibility concerning the range of target shapes, partly thanks to the no need for an explicit description of the final shape. To assess the computational performances of the algorithm, we proposed a linear programming model of the shape-shifting problem giving the lower bounds of optimized criteria. The comparison of our results with those given by the relaxed linear programming proves the efficiency of our approach.