Choosing good paths for fast distributed reconfiguration of hexagonal metamorphic robots

Jennifer E. Walter, Elizabeth M. Tsai, Nancy M. Amato

Research output: Contribution to journalArticlepeer-review


The problem addressed is the distributed reconfiguration of a metamorphic robot system composed of any number of two dimensional robots (modules) from 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 [12, 13, 14]. 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.

Original languageEnglish (US)
Pages (from-to)102-109
Number of pages8
JournalProceedings - IEEE International Conference on Robotics and Automation
StatePublished - May 2002
Externally publishedYes

ASJC Scopus subject areas

  • Software
  • Control and Systems Engineering
  • Artificial Intelligence
  • Electrical and Electronic Engineering


Dive into the research topics of 'Choosing good paths for fast distributed reconfiguration of hexagonal metamorphic robots'. Together they form a unique fingerprint.

Cite this