Graph-based optimal reconfiguration planning for self-reconfigurable robots |
| |
Affiliation: | 1. Department of Aerospace Engineering, Ryerson University, Toronto, ON M5B 2K3, Canada;2. Robotic Research Center, Shanghai University, Shanghai 200072, China |
| |
Abstract: | 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. |
| |
Keywords: | Modular robots Optimal reconfiguration planning Computational complexity |
本文献已被 ScienceDirect 等数据库收录! |
|