Abstract Recent years have shown continuous progress in nanoscale assembly with the development of affordable large-scale manufacturing technologies. Modular robotics and, especially, the programmable matter is one of the emanations of this evolution, which consists of a set of identical modular robots capable of reconfiguring into any shape. However, the success of such a technology depends on the provided algorithmic solutions that allow shifting from the current configuration to the targeted shape. Major works concerning the modular robots self-reconfiguration problem (MRSR) are based on local and/or distributed heuristics that do not guarantee the optimality of the reconfiguration proposals in terms of energy and convergence time. Furthermore, centralized approaches employ constraint relaxation to reduce the combinatorial complexity of the problem. Therefore, obtained solutions are not practically usable in the physical world. In this paper, we provide the first modeling of the modular-robots self-reconfiguration problem into Mixed-Integer Quadratic Programming Model (MIQP). The model includes at the best of our knowledge all the physical, synchronization, and operational constraints of the horizontal 6-lattice MRSR problem. Modeling the MRSR problem as a MIQP problem allows to use exact optimization solvers to pre-calculate the best reconfiguration plan or to prove the problem’s unfeasibility. The obtained results show the relevance of the MIQP approach, especially for small and mid-size instances. Problems with 10 robots could be solved in a few seconds with sometimes the proof of optimality.
Mabed et al. (Mon,) studied this question.