Choosing good paths for fast distributed reconfiguration of hexagonal metamorphic robots

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.