Motion planning for metamorphic systems: Feasibility, decidability, and distributed reconfiguration

Adrian Dumitrescu, Ichiro Suzuki, Masafumi Yamashita

Research output: Contribution to journalArticlepeer-review

30 Citations (Scopus)


In this paper, we address a number of issues related to motion planning and analysis of rectangular metamorphic robotic systems. We first present a distributed algorithm for reconfiguration that applies to a relatively large subclass of configurations, called horizontally convex configurations. We then discuss several fundamental questions in the analysis of metamorphic systems. In particular, the following two questions are shown to be decidable: 1) whether a given set of motion rules maintains connectivity; 2) whether a goal configuration is reachable from a given initial configuration (at specified locations). In the general case in which each module has an internal state, the following is shown to be undecidable: given a set of motion rules, whether there exists a certain type of configuration called a uniform straight-chain configuration that yields a disconnected configuration.

Original languageEnglish
Pages (from-to)409-418
Number of pages10
JournalIEEE Transactions on Robotics and Automation
Issue number3
Publication statusPublished - Jun 2004

All Science Journal Classification (ASJC) codes

  • Control and Systems Engineering
  • Electrical and Electronic Engineering


Dive into the research topics of 'Motion planning for metamorphic systems: Feasibility, decidability, and distributed reconfiguration'. Together they form a unique fingerprint.

Cite this