The problem addressed is the distributed reconfiguration of a system of hexagonal metamorphic robots (modules) from an initial straight chain to a goal configuration that satisfies a simple admissibility condition. Our reconfiguration strategy depends on finding a contiguous path of cells that spans the goal configuration and over which modules can move concurrently without collision or deadlock, called an admissible substrate path. A subset of modules first occupy the admissible substrate path, which is then traversed by other modules to fill in the remainder of the goal. We present a two-phase reconfiguration strategy, beginning with a centralized preprocessing phase that finds and heuristically ranks all admissible substrate paths in the goal configuration, according to which path is likely to result in fast parallel reconfiguration. We prove the correctness of our path-finding algorithm and demonstrate its effectiveness through simulation. The second phase of reconfiguration is accomplished by a deterministic, distributed algorithm that uses little or no intermodule message passing.

The problem addressed is the distributed reconfiguration of the metamorphic robot system composed of any number of two dimensional robots (modules). The initial configuration we consider is a straight chain of modules, while the goal configuration satisfies a simple admissibility condition. Our reconfiguration strategy depends on finding a contiguous path of cells, called a substrate path that spans the goal configuration. Modules fill in this substrate path and then move along the path to fill in the remainder of the goal without collision or deadlock. In this paper, we address the problem of reconfiguration when a single obstacle is embedded in the goal environment. We introduce a classification for traversable surfaces, which allows for coherence in defining admissibility characteristics for various objects in the hexagonal grid. We present algorithms to 1) determine if an obstacle embedded in the goal fulfills a simple admissibility requirement, 2) include an admissible obstacle in a substrate path, and 3) accomplish distributed reconfiguration.

The problem addressed is the distributed reconfiguration of a metamorphic robot system composed of any number of two dimensional robots (modules) front specific initial to specific goal configurations. The initial configuration we consider is a straight chain of modules, while the goal configuration satisfies a simple admissibility condition. Reconfiguration of the modules depends on finding a contiguous path of cells, called a substrate path, that spans the goal configuration. Modules fill in this substrate path and then move along the path to fill in the remainder of the goal without collision or deadlock. In this paper, we examine the problem of finding the substrate path most likely to result in fast parallel reconfiguration, drawing on results from our previous papers (2000, 2001). Admissible goal configurations are represented as directed acyclic graphs (DAGs). We present a combination graph traversal-weighting algorithm that traverses all paths in the rooted DAG and use this algorithm to determine the best substrate path. We extend our definition of admissible substrate paths to consider admissible obstacle surfaces for reconfiguration when obstacles are present in the environment.