Paper by Erik D. Demaine

Reference:

Greg Aloupis, Nadia Benbernou, Mirela Damian, Erik D. Demaine, Robin Flatland, John Iacono, and Stefanie Wuhrer, “Efficient Reconfiguration of Lattice-Based Modular Robots”, Computational Geometry: Theory and Applications, volume 46, number 8, October 2013, pages 917–928.

Abstract:

Modular robots consist of many identical units (or atoms) that can attach together and perform local motions. By combining such motions, one can achieve a reconfiguration of the global shape of a robot. The term modular comes from the idea of grouping together a fixed number of atoms into a metamodule, which behaves as a larger individual component. Recently, a fair amount of research has focused on algorithms for universal reconfiguration using Crystalline and Telecube metamodules, which use expanding/contracting cubical atoms.

From an algorithmic perspective, this work has achieved some of the best asymptotic reconfiguration times under a variety of different physical models. In this paper we show that these results extend to other types of modular robots, thus establishing improved upper bounds on their reconfiguration times. We describe a generic class of modular robots, and we prove that any robot meeting the generic class requirements can simulate the operation of a Crystalline atom by forming a six-arm structure. Previous reconfiguration bounds thus transfer automatically by substituting the six-arm structures for the Crystalline atoms. We also discuss four prototyped robots that satisfy the generic class requirements: M-TRAN, SuperBot, Molecube, and RoomBot.

Comments:

See also animations of the 6-arm module.

Availability:

The paper is available in PDF (7545k).

See information on file formats.

[Google Scholar search]

Related papers:

MTRAN_Molecube_ECMR2009 (Efficient Reconfiguration of Lattice-Based Modular Robots)

Crystalline_WAFR2008 (Realistic Reconfiguration of Crystalline (and Telecube) Robots)

Crystalline_ISAAC2008 (Reconfiguration of Cube-Style Modular Robots Using O(log n) Parallel Moves)

Crystalline_CGTA (Linear Reconfiguration of Cube-Style Modular Robots)