Graph-Based Optimal Reconfiguration Planning for Self-Reconfigurable Robots

Feili Hou and Wei-Min Shen. Graph-Based Optimal Reconfiguration Planning for Self-Reconfigurable Robots. Robotics and Autonomous Systems, 1(1-2):1–24, August 2013.

Download

[1.6MB pdf] 

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-typed robots based on graph representations and presents a series of theoretical results: (1) A formal proof that this is a NP- complete problem, (2) A reconfiguration planning algorithm called MDCOP which generates the optimal graph-based reconfiguration plan, (3) Another algorithm called GreedyCM which can find 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.

BibTeX Entry

@Article{	  houshen2013-graph-based-reconfiguration-plan,
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-typed robots based on graph representations and presents a series of theoretical results: (1) A formal proof that this is a NP- complete problem, (2) A reconfiguration planning algorithm called MDCOP which generates the optimal graph-based reconfiguration plan, (3) Another algorithm called GreedyCM which can find 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.},
  author	= {Feili Hou and Wei-Min Shen},
  journal	= ras,
  keyword       = {graph based, self reconfiguration, algorithm},
  month         = aug,
  number	= {1-2},
  pages		= {1-24},
  title		= {Graph-Based Optimal Reconfiguration Planning for Self-Reconfigurable Robots},
  volume	= {1},
  year		= {2013}
}