Issues in Motion Planning of Metamorphic Systems

Adrian Dumitrescu, University of Wisconsin--Milwaukee

We address a number of issues related to 
motion planning and analysis of both rectangular 
and hexagonal metamorphic robotic systems. 
We first present a distributed algorithm
for reconfiguration that applies to a relatively large subclass of
configurations, called horizontally convex configurations, 
of a rectangular system.
We then discuss several fundamental questions on 
the analysis of metamorphic systems.
In particular the following two questions are shown to be decidable:
(i) determining whether a given set of motion rules maintains
connectivity;
(ii) 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, determine whether there exists a 
certain type of configuration called a uniform straight-chain
configuration that yields a disconnected configuration.

This is joint work with Ichiro Suzuki and Masafumi Yamashita.