Algorithms for fast concurrent reconfiguration of hexagonal metamorphic robots Academic Article

abstract

• 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. 2005 IEEE.

authors

• Amato, Nancy

published proceedings

• IEEE TRANSACTIONS ON ROBOTICS

author list (cited authors)

• Walter, J. E., Tsai, E. M., & Amato, N. M.

citation count

• 26

complete list of authors

• Walter, JE||Tsai, EM||Amato, NM

publication date

• August 2005

publisher

• Institute of Electrical and Electronics Engineers (IEEE)  Publisher

published in

• IEEE Transactions on Robotics  Journal

keywords

• Distributed Reconfiguration
• Metamorphic Robots

Digital Object Identifier (DOI)

• 10.1109/TRO.2004.842325

start page

• 621

end page

• 631

volume

• 21

issue

• 4

URL

• http://dx.doi.org/10.1109/tro.2004.842325