A Scalable Distributed Algorithm for Shape Transformation in Multi-Robot Systems

@inproceedings{dewey-iros08,
  author = {Dewey, Daniel and Srinivasa, Siddhartha S. and
     Ashley-Rollman, Michael P. and De~Rosa, Michael and Pillai,
     Padmanabhan and Mowry, Todd C. and Campbell, Jason D. and
     Goldstein, Seth Copen},
  title = {Generalizing Metamodules to Simplify Planning in Modular
     Robotic Systems},
  booktitle = {Proceedings of IEEE/RSJ 2008 International Conference
     on Intelligent Robots and Systems {IROS '08}},
  year = {2008},
  address = {Nice, France},
  month = {Sep},
  abstract = {In this paper we develop a theory of metamodules and an
     associated distributed asynchronous planner which generalizes
     previous work on metamodules for lattice-based modular robotic
     systems. All extant modular robotic systems have some form of
     non-holonomic motion constraints. This has prompted many
     researchers to look to metamodules, i.e., groups of modules that
     act as a unit, as a way to reduce motion constraints and the
     complexity of planning. However, previous metamodule designs have
     been specific to a particular modular robot. 
By analyzing the
     constraints found in modular robotic systems we develop a
     holonomic metamodule which has two important properties: (1) it
     can be used as the basic unit of an efficient planner and (2) it
     can be instantiated by a wide variety of different underlying
     modular robots, e.g., modular robot arms, expanding cubes,
     hex-packed spheres, etc. Using a series of transformations we
     show that our practical metamodule system has a provably complete
     planner. Finally, our approach allows the task of shape
     transformation to be separated into a planning task and a
     resource allocation task. We implement our planner for two
     different metamodule systems and show that the time to completion
     scales linearly with the diameter of the ensemble.},
  url = {http://www.cs.cmu.edu/~claytronics/papers/dewey-iros08.pdf},
  keywords = {Meld, Planning, Multi-Robot Formations, Controlling
     Ensembles, Robotics},
}

@inproceedings{ravichandran-iros07,
  author = {Ravichandran, Ramprasad and Gordon, Geoffrey and
     Goldstein, Seth Copen},
  title = {A Scalable Distributed Algorithm for Shape Transformation
     in Multi-Robot Systems},
  booktitle = {Proceedings of the IEEE International Conference on
     Intelligent Robots and Systems {IROS '07}},
  year = {2007},
  month = {Oct},
  keywords = {Claytronics, Multi-Robot Formations},
  abstract = {Distributed reconfiguration is an important problem in
     multi-robot systems such as mobile sensor nets and metamorphic
     robot systems. In this work, we present a scalable distributed
     reconfiguration algorithm, Hierarchical Median Decomposition, to
     achieve arbitrary target configurations. Our algorithm is built
     on top of a novel distributed median consensus estimator. The
     algorithms presented are fully distributed and do not require
     global communication. We show results from simulations in an open
     source multi-robot simulator.},
  url = {http://www.cs.cmu.edu/~claytronics/papers/ravichandran-iros07.pdf},
}

@inproceedings{bg11,
  author = {Bourgeois, Julien and Goldstein, Seth Copen},
  title = {Distributed Intelligent {MEMS}: Progresses and
     Perspectives},
  booktitle = {ICT Innovations 2011},
  pages = {15--25},
  series = {Advances in Intelligent and Soft Computing},
  volume = {150},
  isbn = {978-3-642-28663-6},
  editor = {Kocarev, Ljupco},
  address = {Ohrid, Macedonia},
  publisher = {Springer Berlin / Heidelberg},
  year = {2012},
  note = {Keynote talk at the ICT Innovations 2011 conference},
  keywords = {Claytronics},
}

@article{goldstein09,
  author = {Goldstein, Seth Copen and Mowry, Todd C. and Campbell,
     Jason D. and Ashley-Rollman, Michael P. and De~Rosa, Michael and
     Funiak, Stanislav and Hoburg, James F. and Karagozler, Mustafa
     Emre and Kirby, Brian and Lee, Peter and Pillai, Padmanabhan and
     Reid, J. Robert and Stancil, Daniel D. and Weller, Michael
     Philetus},
  title = {Beyond Audio and Video: Using Claytronics to Enable Pario},
  journal = {AI Magazine},
  year = {2009},
  volume = {30},
  number = {2},
  month = {Jul},
  keywords = {Claytronics},
  abstract = {In this article, we describe the hardware and software
     challenges involved in realizing Claytronics, a form of
     programmable matter made out of very large numbers-potentially
     millions-of submillimeter sized spherical robots. The goal of the
     claytronics project is to create ensembles of cooperating
     submillimeter robots, which work together to form dynamic 3D
     physical objects. For example, claytronics might be used in
     telepresense to mimic, with high-fidelity and in 3-dimensional
     solid form, the look, feel, and motion of the person at the other
     end of the telephone call. To achieve this long-range vision we
     are investigating hardware mechanisms for constructing
     submillimeter robots, which can be manufactured en masse using
     photolithography. We also propose the creation of a new media
     type, which we call pario. The idea behind pario is to render
     arbitrary moving, physical 3-dimensional objects that you can
     see, touch, and even hold in your hands. In parallel with our
     hardware effort, we are developing novel distributed programming
     languages and algorithms to control the ensembles, LDP and Meld.
     Pario may fundamentally change how we communicate with others and
     interact with the world around us. Our research results to date
     suggest that there is a viable path to implementing both the
     hardware and software necessary for claytronics, which is a form
     of programmable matter that can be used to implement pario. While
     we have made significant progress, there is still much research
     ahead in order to turn this vision into reality.},
}

@inproceedings{derosa-icra08,
  author = {De~Rosa, Michael and Goldstein, Seth Copen and Lee, Peter
     and Campbell, Jason D. and Pillai, Padmanabhan},
  booktitle = {Proceedings of the IEEE International Conference on
     Robotics and Automation {ICRA '08}},
  venue = {IEEE International Conference on Robotics and Automation
     (ICRA)},
  keywords = {Claytronics, Modular Robotics, Programming, LDP},
  title = {Programming Modular Robots with Locally Distributed
     Predicates},
  year = {2008},
  abstract = {We present a high-level language for programming modular
     robotic systems, based on locally distributed predicates (LDP),
     which are distributed conditions that hold for a connected
     subensemble of the robotic system. An LDP program is a collection
     of LDPs with associated actions which are triggered on any
     subensemble that matches the predicate. The result is a reactive
     programming language which efficiently and concisely supports
     ensemble-level programming. We demonstrate the utility of LDP by
     implementing three common, but diverse, modular robotic tasks.},
  url = {http://www.cs.cmu.edu/~claytronics/papers/derosa-icra08.pdf},
}

@inproceedings{bkirby-iros07,
  author = {Kirby, Brian and Aksak, Burak and Goldstein, Seth Copen
     and Hoburg, James F. and Mowry, Todd C. and Pillai, Padmanabhan},
  title = {A Modular Robotic System Using Magnetic Force Effectors},
  booktitle = {Proceedings of the IEEE International Conference on
     Intelligent Robots and Systems ({IROS '07})},
  year = {2007},
  month = {Oct},
  abstract = {One of the primary impediments to building ensembles
     with many modular robots is the complexity and number of
     mechanical mechanisms used to construct the individual modules.
     As part of the Claytronics project---which aims to build very
     large ensembles of modular robots---we investigate how to
     simplify each module by eliminating moving parts and reducing the
     number of mechanical mechanisms on each robot by using
     force-at-a-distance actuators. Additionally, we are also
     investigating the feasibility of using these unary actuators to
     improve docking performance, implement intermodule adhesion,
     power transfer, communication, and sensing.},
  keywords = {Claytronics, Actuation, Adhesion},
  url = {http://www.cs.cmu.edu/~claytronics/papers/bkirby-iros07.pdf},
}

@inproceedings{ravichandran-iros07,
  author = {Ravichandran, Ramprasad and Gordon, Geoffrey and
     Goldstein, Seth Copen},
  title = {A Scalable Distributed Algorithm for Shape Transformation
     in Multi-Robot Systems},
  booktitle = {Proceedings of the IEEE International Conference on
     Intelligent Robots and Systems {IROS '07}},
  year = {2007},
  month = {Oct},
  keywords = {Claytronics, Multi-Robot Formations},
  abstract = {Distributed reconfiguration is an important problem in
     multi-robot systems such as mobile sensor nets and metamorphic
     robot systems. In this work, we present a scalable distributed
     reconfiguration algorithm, Hierarchical Median Decomposition, to
     achieve arbitrary target configurations. Our algorithm is built
     on top of a novel distributed median consensus estimator. The
     algorithms presented are fully distributed and do not require
     global communication. We show results from simulations in an open
     source multi-robot simulator.},
  url = {http://www.cs.cmu.edu/~claytronics/papers/ravichandran-iros07.pdf},
}

@inproceedings{ashley-rollman-derosa-iros07wksp,
  author = {Ashley-Rollman, Michael P. and De~Rosa, Michael and
     Srinivasa, Siddhartha S. and Pillai, Padmanabhan and Goldstein,
     Seth Copen and Campbell, Jason D.},
  title = {Declarative Programming for Modular Robots},
  booktitle = {Workshop on Self-Reconfigurable Robots/Systems and
     Applications at {IROS '07}},
  year = {2007},
  month = {Oct},
  keywords = {Claytronics, Programming Models, Planning, LDP, Meld},
  abstract = {Because of the timing, complexity, and asynchronicity
     challenges common in modular robot software we have recently
     begun to explore new programming models for modular robot
     ensembles. In this paper we apply two of those models to a
     metamodule-based shape planning algorithm and comment on the
     differences between the two approaches. Our results suggest that
     declarative programming can provide several advantages over more
     traditional imperative approaches, and that the differences
     between declarative programming styles can themselves contribute
     leverage to different parts of the problem domain.},
  url = {http://www.cs.cmu.edu/~claytronics/papers/ashley-rollman-derosa-iros07wksp.pdf},
}

@inproceedings{karagozler-iros07,
  author = {Karagozler, Mustafa Emre and Campbell, Jason D. and
     Fedder, Gary K. and Goldstein, Seth Copen and Weller, Michael
     Philetus and Yoon, Byung W.},
  title = {Electrostatic Latching for Inter-module Adhesion, Power
     Transfer, and Communication in Modular Robots},
  booktitle = {Proceedings of the IEEE International Conference on
     Intelligent Robots and Systems ({IROS '07})},
  year = {2007},
  month = {Oct},
  abstract = {A simple and robust inter-module latch is possibly the
     most important component of a modular robotic system. This paper
     describes a latch based on capacitive coupling which not only
     provides significant adhesion forces, but can also be used for
     inter-module power transmission and communication. The key
     insight that enables electrostatic adhesion to be effective at
     the macroscale is to combine flexible electrodes with a geometery
     that uses shear forces to provide adhesion. To measure the
     effectiveness of our latch we incorporated it into a 28cm x 28cm
     x 28cm modular robot. The result is a latch which requires almost
     zero static power and yet can hold over 0.6N/cm^2 of latch
     area.},
  keywords = {Actuation, Adhesion, Claytronics},
  url = {http://www.cs.cmu.edu/~claytronics/papers/karagozler-iros07.pdf},
}

@inproceedings{funiak-iros07,
  author = {Funiak, Stanislav and Pillai, Padmanabhan and Campbell,
     Jason D. and Goldstein, Seth Copen},
  title = {Internal Localization of Modular Robot Ensembles},
  booktitle = {Workshop on Self-Reconfiguring Modular Robotics at the
     IEEE International Conference on Intelligent Robots and Systems
     (IROS) '07},
  year = {2007},
  month = {Oct},
  abstract = {The determination of the relative position and pose of
     every robot in a modular robotic ensemble is a necessary
     preliminary step for most modular robotic tasks. Localization is
     particularly important when the modules make local noisy
     observations and are not significantly constrained by inter-robot
     latches. In this paper, we propose a robust hierarchical approach
     to the {\em internal localization} problem that uses normalized
     cut to identify subproblems with small localization error. A key
     component of our solution is a simple method to reduce the cost
     of normalized cut computations. The result is a robust algorithm
     that scales to large, non-homogeneous ensembles. We evaluate our
     algorithm in simulation on ensembles of up to 10,000 modules,
     demonstrating substantial improvements over prior work.},
  keywords = {Claytronics, Probabilistic Inference, Sensing,
     Localization, Distributed Algorithms},
  url = {http://www.cs.cmu.edu/~claytronics/papers/funiak-iros07.pdf},
}

@inproceedings{ashley-rollman-iros07,
  author = {Ashley-Rollman, Michael P. and Goldstein, Seth Copen and
     Lee, Peter and Mowry, Todd C. and Pillai, Padmanabhan},
  title = {Meld: A Declarative Approach to Programming Ensembles},
  booktitle = {Proceedings of the IEEE International Conference on
     Intelligent Robots and Systems ({IROS '07})},
  year = {2007},
  month = {Oct},
  keywords = {Claytronics, Programming Languages, Meld},
  abstract = {This paper presents Meld, a programming language for
     modular robots, i.e., for independently executing robots where
     inter-robot communication is limited to immediate neighbors. Meld
     is a declarative language, based on P2, a logic-programming
     language originally designed for programming overlay networks. By
     using logic programming, the code for an ensemble of robots can
     be written from a global perspective, as opposed to a large
     collection of independent robot views. This greatly simplifies
     the thought process needed for programming large ensembles.
     Initial experience shows that this also leads to a considerable
     reduction in code size and complexity. An initial implementation
     of Meld has been completed and has been used to demonstrate its
     effectiveness in the Claytronics simulator. Early results
     indicate that Meld programs are considerably more concise (more
     than 20x shorter) than programs written in C++, while running
     nearly as efficiently.},
  url = {http://www.cs.cmu.edu/~claytronics/papers/ashley-rollman-iros07.pdf},
}

@inproceedings{weller-iros07,
  author = {Weller, Michael Philetus and Karagozler, Mustafa Emre and
     Kirby, Brian and Campbell, Jason D. and Goldstein, Seth Copen},
  title = {Movement Primitives for an Orthogonal Prismatic
     Closed-Lattice-Constrained Self-Reconfiguring Module},
  booktitle = {Workshop on Self-Reconfiguring Modular Robotics at the
     IEEE International Conference on Intelligent Robots and Systems
     (IROS) '07},
  year = {2007},
  month = {Oct},
  keywords = {Claytronics, Adhesion, Robotics, Planning},
  abstract = {We describe a new set of prismatic movement primitives
     for cubic modular robots. Our approach appears more practical
     than previous metamodule-based approaches. We also describe
     recent hardware developments in our cubic robot modules that have
     sufficient stiffness and actuator strength so that when they work
     together they can realize, in earth's gravity, all of the motion
     primitives we describe here.},
  url = {http://www.cs.cmu.edu/~claytronics/papers/weller-iros07.pdf},
}

@inproceedings{derosa-rss06,
  author = {De~Rosa, Michael and Goldstein, Seth Copen and Lee, Peter
     and Campbell, Jason D. and Pillai, Padmanabhan},
  booktitle = {Robotics: Science and Systems Workshop on
     Self-Reconfigurable Modular Robots},
  title = {Distributed Watchpoints: Debugging Very Large Ensembles of
     Robots},
  month = {Aug},
  year = {2006},
  keywords = {Claytronics, Modular Robotics, Debugging, Distributed
     Systems},
  address = {Philadelphia, PA},
  talk = {http://www.cs.cmu.edu/~seth/papers/derosa-rss06.pdf},
  url = {http://www.cs.cmu.edu/~seth/papers/derosa-rss06.pdf},
  abstract = {We describe a debugging tool for modular robotics that
     introduces the concept of distributed watchpoint triggers. This
     technique can initiate debugging actions (system halt, global
     snapshot, logging, etc.) in an ensemble of robots based on
     temporal, physical, and logical conditions distributed over
     multiple robots. Our technique is specifically designed to be
     effective in debugging modular robotic ensembles, where many
     important types of failure conditions can be detected within
     small, physically connected subsets of the total ensemble.},
}

@inproceedings{bhat06,
  author = {Bhat, Preethi Srinivas and Kuffner, James and Goldstein,
     Seth Copen and Srinivasa, Siddhartha},
  title = {Hierarchical Motion Planning for Self-reconfigurable
     Modular Robots},
  booktitle = {2006 IEEE/RSJ International Confernce on Intelligent
     Robots and Systems (IROS)},
  year = {2006},
  month = {Oct},
  keywords = {Claytronics, Planning, Modular Robotics},
  url = {http://www.cs.cmu.edu/~seth/papers/bhat06.pdf},
}

@inproceedings{derosa-icra06,
  author = {De~Rosa, Michael and Goldstein, Seth Copen and Lee, Peter
     and Campbell, Jason D. and Pillai, Padmanabhan},
  title = {Scalable Shape Sculpting via Hole Motion: Motion Planning
     in Lattice-Constrained Module Robots},
  month = {May},
  booktitle = {Proceedings of the 2006 {IEEE} International Conference
     on Robotics and Automation (ICRA '06)},
  year = {2006},
  keywords = {Claytronics, Programmable Matter, Planning, Modular
     Robotics},
  url = {http://www.cs.cmu.edu/~seth/papers/derosa-icra06.pdf},
  abstract = {We describe a novel shape formation algorithm for
     ensembles of 2-dimensional lattice-arrayed modular robots, based
     on the manipulation of regularly shaped voids within the lattice
     (``holes''). The algorithm is massively parallel and fully
     distributed. Constructing a goal shape requires time propor-
     tional only to the complexity of the desired target geometry.
     Construction of the shape by the modules requires no global
     communication nor broadcast floods after distribution of the
     target shape. Results in simulation show 97.3\% shape compliance
     in ensembles of approximately 60,000 modules, and we believe that
     the algorithm will generalize to 3D and scale to handle millions
     of modules.},
}

@inproceedings{karagozler-rascal06,
  title = {Ultralight Modular Robotic Building blocks for the Rapid
     Deployment of Planetary Outposts},
  booktitle = {Revolutionary Aerospace Systems Concepts Academic
     Linkage (RASC-AL) Forum 2006},
  author = {Karagozler, Mustafa Emre and Kirby, Brian and Lee, W.J.
     and Marinelli, Eugene and Ng, T.C. and Weller, Michael and
     Goldstein, Seth Copen},
  year = {2006},
  month = {May},
  address = {Cape Canaveral, FL},
  url = {http://www.cs.cmu.edu/~seth/papers/karagozler-rascal06.pdf},
  keywords = {Claytronics,Modular Robotics,Robotics},
}

@misc{goldstein-popsci05,
  title = {2029 The 3-D Fax Machine Brings Back the House Call},
  howpublished = {Headline from the Future, Popular Science Magazine},
  author = {Goldstein, Seth Copen},
  year = {2005},
  url = {http://www.cs.cmu.edu/~seth/papers/goldstein-popsci05.pdf},
  month = {Mar},
  pages = {34},
  keywords = {Claytronics},
}

@inproceedings{kirby-aaai05,
  author = {Kirby, Brian and Campbell, Jason D. and Aksak, Burak and
     Pillai, Padmanabhan and Hoburg, James F. and Mowry, Todd C. and
     Goldstein, Seth Copen},
  title = {Catoms: Moving Robots Without Moving Parts},
  url = {http://www.cs.cmu.edu/~seth/papers/kirby-aaai05.pdf},
  booktitle = {AAAI (Robot Exhibition)},
  pages = {1730--1},
  year = {2005},
  month = {Jul},
  address = {Pittsburgh, PA},
  keywords = {Claytronics, Robotics},
}

@inproceedings{aksak-sensys05,
  author = {Aksak, Burak and Bhat, Preethi Srinivas and Campbell,
     Jason D. and De~Rosa, Michael and Funiak, Stanislav and Gibbons,
     Phillip B. and Goldstein, Seth Copen and Guestrin, Carlos and
     Gupta, Ashish and Helfrich, Casey and Hoburg, James F. and Kirby,
     Brian and Kuffner, James and Lee, Peter and Mowry, Todd C. and
     Pillai, Padmanabhan and Ravichandran, Ram and Rister, Benjamin D.
     and Seshan, Srinivasan and Sitti, Metin and Yu, Haifeng},
  title = {Demo Abstract: Claytronics---highly scalable
     communications, sensing, and actuation networks.},
  booktitle = {Proceedings of the 3rd international conference on
     Embedded networked sensor systems (SenSys)},
  year = {2005},
  pages = {299},
  url = {http://www.cs.cmu.edu/~seth/papers/aksak-sensys05.pdf},
  doi = {http://doi.acm.org/10.1145/1098918.1098964},
  keywords = {Claytronics, Programmable Matter},
}

@article{goldstein-computer05,
  author = {Goldstein, Seth Copen and Campbell, Jason D. and Mowry,
     Todd C.},
  title = {Programmable Matter},
  journal = {IEEE Computer},
  volume = {38},
  number = {6},
  pages = {99--101},
  year = {2005},
  month = {Jun},
  keywords = {Claytronics, Programmable Matter},
  url = {http://www.cs.cmu.edu/~seth/papers/goldstein-computer05.pdf},
}

@inproceedings{goldstein05,
  author = {Goldstein, Seth Copen and Mowry, Todd C. and Campbell,
     Jason D. and Lee, Peter and Pillai, Padmanabhan and Hoburg, James
     F. and Gibbons, Phillip B. and Guestrin, Carlos and Kuffner,
     James and Kirby, Brian and Rister, Benjamin D. and De~Rosa,
     Michael and Funiak, Stanislav and Aksak, Burak and Sukthankar,
     Rahul},
  title = {The Ensemble Principle},
  booktitle = {13th Foresight Conference of Advanced Nanotechnogy},
  url = {http://www.cs.cmu.edu/~seth/papers/goldstein05.pdf},
  year = {2005},
  month = {Oct},
  address = {San Francisco, CA},
  keywords = {Claytronics, Robotics},
}

@inproceedings{campbell05,
  author = {Campbell, Jason D. and Pillai, Padmanabhan and Goldstein,
     Seth Copen},
  title = {The Robot is the Tether: Active, Adaptive Power Routing for
     Modular Robots With Unary Inter-robot Connectors},
  booktitle = {IEEE/RSJ International Conference on Intelligent Robots
     and Systems (IROS 2005)},
  pages = {4108--15},
  year = {2005},
  address = {Edmonton, Alberta Canada},
  month = {Aug},
  keywords = {Claytronics, Robotics},
  url = {http://www.cs.cmu.edu/~seth/papers/campbell05.pdf},
}

@inproceedings{goldstein-robosphere04,
  author = {Goldstein, Seth Copen and Mowry, Todd C.},
  title = {Claytronics: A scalable basis for future robots},
  booktitle = {RoboSphere 2004},
  address = {Moffett Field, CA},
  month = {Nov},
  year = {2004},
  keywords = {Claytronics, Robotics},
  url = {http://www.cs.cmu.edu/~seth/papers/goldstein-robosphere04.pdf},
}

@inproceedings{goldstein-waci04,
  author = {Goldstein, Seth Copen and Mowry, Todd C.},
  title = {Claytronics: An Instance of Programmable Matter},
  booktitle = {Wild and Crazy Ideas Session of ASPLOS},
  year = {2004},
  month = {Oct},
  address = {Boston, MA},
  keywords = {Claytronics},
  url = {http://www.cs.cmu.edu/~seth/papers/goldstein-waci04.pdf},
  abstract = {Programmable matter refers to a technology that will
     allow one to control and manipulate three-dimensional physical
     artifacts (similar to how we already control and manipulate
     two-dimensional images with computer graphics). In other words,
     programmable matter will allow us to take a (big) step beyond
     virtual reality, to synthetic reality, an environment in which
     all the objects in a user's environment (including the ones
     inserted by the computer) are physically realized. Note that the
     idea is not to transport objects nor is it to recreate an objects
     chemical composition, but rather to create a physical artifact
     that will mimic the shape, movement, visual appearance, sound,
     and tactile qualities of the original object.},
}