Abstract-This paper presents a thorough analysis of the computational complexity of optimal reconfiguration planning problem for chain-type modular robots, i.e. finding the least number of reconfiguration steps to transform from the initial configuration into the goal configuration. It establishes a formal proof that this problem is NP-complete, even if the configurations are acyclic. This result gives a compelling reason that a polynomial algorithm for optimal reconfiguration plan is unlikely to exist. To facilitate future evaluation of reconfiguration algorithms, the paper also provides the lower and the upper bounds for the minimum number of reconfiguration steps for any given reconfiguration problem.
Optimal reconfiguration for chain-based robots was recently proven to be NP-complete REF .
On the complexity of optimal reconfiguration planning for modular reconfigurable robots
2010 IEEE International Conference on Robotics and Automation
2010 IEEE International Conference on Robotics and Automation
Computer Science Mathematics