NP-completeness of optimal planning problem for modular robots

Self-reconfigurable modular robots (SRM-robots) can autonomously change their shape according to different tasks and work environments, and have received considerable attention recently. Many reshaping/reconfiguration algorithms have been proposed. In this paper, we present a theoretical analysis of computational complexity on a reshape planning for a kind of lattice-type 3D SRM-robots, whose modules are of cubic shape and can move by rotating on the surfaces of other modules. Different from previous NP-completeness study on general chain-type robots (i.e. the motion of any chains and the location of modules can be arbitrary), we consider more practical constraints on modules’ shape (i.e. cubic shape), position (lying in 2D/3D grids) and motion (using orthogonal rotations) in this paper. We formulate the reshape planning problem of SRM-robots with these practical constraints by a (p, q) optimization problem, where p and q characterize two widely used metrics, i.e. the number of disconnecting/reconnecting operations and the number of reshaping steps. Proofs are presented, showing that this optimization problem is NP-complete. Therefore, instead of finding global optimization results, most likely approximation solution can be obtained for the problem instead of seeking polynomial algorithm. We also present the upper and lower bounds for the 2-tuple (p, q), which is useful for evaluating the approximation algorithms in future research.