Graph-based optimal reconfiguration planning for self-reconfigurable robots

•On finding the least (dis)connect actions to reconfigure between arbitrary shapes.•A proof that the optimal reconfiguration planning problem is NP-complete.•An algorithm which can generate the optimal reconfiguration sequence.•An algorithm that finds the near-optimal reconfiguration sequence in polynomial time.

The goal of optimal reconfiguration planning (ORP) is to find a shortest reconfiguration sequence to transform a modular and reconfigurable robot from an arbitrary configuration into another. This paper investigates this challenging problem for chain-type robots based on graph representations and presents a series of theoretical results: (1) a formal proof that this is an NP-complete problem, (2) a reconfiguration planning algorithm called MDCOP which generates the optimal graph-based reconfiguration plan, and (3) another algorithm called GreedyCM which can find a near-optimal solution in polynomial time. Experimental and statistical results demonstrate that the solutions found by GreedyCM are indeed near-optimal and the approach is computationally feasible for large-scale robots.