This Article Full Text (PDF) Multimedia References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Add to Saved Citations Download to citation manager Request Permissions Request Reprints Add to My Marked Citations Citing Articles Citing Articles via Google Scholar Citing Articles via Scopus Google Scholar Articles by Werfel, J. Articles by Nagpal, R. Search for Related Content Social Bookmarking                         What's this?

Three-Dimensional Construction with Mobile Robots and Modular Blocks

Department of Electrical Engineering and Computer Science, Harvard University, Cambridge, MA 02138, USA, jkwerfel{at}eecs.harvard.edu

Radhika Nagpal

Department of Electrical Engineering and Computer Science, Harvard University, Cambridge, MA 02138, USA, rad{at}eecs.harvard.edu

We present a decentralized algorithmic approach to automatically building user-specified three-dimensional structures from modular units. Our bipartite system comprises passive units (blocks), responsible for embodying the structure and determining where further units can legally be attached, and active units (robots), responsible for transporting passive units. The algorithmic issues are correspondingly decomposed into two parts: (1) deciding where passive units may be attached; and (2) getting them to those locations. For the first part, we give simple, scalable rules for attachment and prove that they will reliably lead to the construction of any desired structure from a large class of three-dimensional shapes. For the second part, we compare three approaches: random movement, systematic search and gradient-following; each approach is successively faster but requires more communication overhead and/or unit capabilities. The system we describe enables guaranteed construction of desired structures using very simple agent algorithms, taking a high-level specification as the only required input. The topic of collective construction is related to the problems of programmed self-assembly and self-reconfiguration in modular robots, and the rules governing block attachment presented here may be usefully applied to such systems.

Key Words: Robotics in Construction • Cellular and Modular Robots • Distributed Robot Systems • Autonomous Agents • Path Planning for Multiple Mobile Robot Systems

The International Journal of Robotics Research, Vol. 27, No. 3-4, 463-479 (2008)
DOI: 10.1177/0278364907084984


CiteULike    Complore    Connotea    Del.icio.us    Digg    Reddit    Technorati    Twitter    What's this?