On the Complexity of Optimal Reconfiguration Planning for Modular Reconfigurable Robots
Feili Hou and Wei-Min Shen. On the Complexity of Optimal Reconfiguration Planning for Modular Reconfigurable Robots. In Proc. 2010 IEEE Intl. Conf. on Robotics and Automation, Anchorage, Alaska, USA, May 2010.
Download
Abstract
This paper presents a thorough analysis of thecomputational complexity of optimal reconfiguration planningproblem for chain-type modular robots, i.e. finding the leastnumber of reconfiguration steps to transform from the initialconfiguration into the goal configuration. It establishes a formalproof that this problem is NP-complete, even if theconfigurations are acyclic. This result gives a compelling reasonthat a polynomial algorithm for optimal reconfiguration plan isunlikely to exist. To facilitate future evaluation ofreconfiguration algorithms, the paper also provides the lowerand the upper bounds for the minimum number ofreconfiguration steps for any given reconfiguration problem.
BibTeX Entry
@InProceedings{hou2010complexity-optimal-reconfiguration-planning,
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.},
address = {Anchorage, Alaska, USA},
author = {Feili Hou and Wei-Min Shen},
booktitle = icra-10,
month = may,
title = {On the Complexity of Optimal Reconfiguration Planning for Modular Reconfigurable Robots},
year = {2010}
}
