A characterization of the reconfiguration space of self-reconfiguring robotic systems

Tom Larkworthy, Subramanian Ramamoorthy

Research output: Contribution to journalArticlepeer-review


Motion planning for self-reconfiguring robots can be made efficient by exploiting potential reductions to suitably large subspaces. However, there are no general techniques for identifying suitable restrictions that have a positive effect on planning efficiency. We present two approaches to understanding the structure that is required of the subspaces, which leads to improvement in efficiency of motion planning. This work is presented in the context of a specific motion planning procedure for a hexagonal metamorphic robot. First, we use ideas from spectral graph theory -- empirically estimating the algebraic connectivity of the state space -- to show that the HMR model is better structured than many alternative motion catalogs. Secondly, using ideas from graph minor theory, we show that the infinite sequence of subspaces generated by configurations containing increasing numbers of subunits is well ordered, indicative of regularity of the space as complexity increases. We hope that these principles could inform future algorithm design for many different types of self-reconfiguring robotics problems.
Original languageEnglish
Pages (from-to)73-85
Number of pages13
Issue numberSpecial Issue 1
Publication statusPublished - Jan 2011


  • Self-reconfiguring robotics
  • Motion planning
  • Graph theory

Fingerprint Dive into the research topics of 'A characterization of the reconfiguration space of self-reconfiguring robotic systems'. Together they form a unique fingerprint.

Cite this