Generalizing Metamodules to Simplify Planning in Modular Robotic 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{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{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{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{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{ashley-rollman-iclp09,
  author = {Ashley-Rollman, Michael P. and Lee, Peter and Goldstein,
     Seth Copen and Pillai, Padmanabhan and Campbell, Jason D.},
  booktitle = {Proceedings of the International Conference on Logic
     Programming (ICLP '09)},
  title = {A Language for Large Ensembles of Independently Executing
     Nodes},
  year = {2009},
  month = {Jul},
  keywords = {Distributed Systems, Meld, Programming Languages},
  url = {http://www.cs.cmu.edu/~claytronics/papers/ashley-rollman-iclp09.pdf},
  abstract = {We address how to write programs for distributed
     computing systems in which the network topology can change
     dynamically. Examples of such systems, which we call {\em
     ensembles}, include programmable sensor networks (where the
     network topology can change due to failures in the nodes or
     links) and modular robotics systems (whose physical configuration
     can be rearranged under program control). We extend Meld, a logic
     programming language that allows an ensemble to be viewed as a
     single computing system. In addition to proving some key
     properties of the language, we have also implemented a complete
     compiler for Meld. It generates code for TinyOS and for a
     Claytronics simulator. We have successfully written correct,
     efficient, and complex programs for ensembles containing over one
     million nodes.},
  booktitle = {Proceedings of the International Conference on Logic
     Programming (ICLP '09)},
}

@inproceedings{funiak-rss08,
  author = {Funiak, Stanislav and Pillai, Padmanabhan and
     Ashley-Rollman, Michael P. and Campbell, Jason D. and Goldstein,
     Seth Copen},
  title = {Distributed Localization of Modular Robot Ensembles},
  booktitle = {Proceedings of Robotics: Science and Systems},
  year = {2008},
  month = {Jun},
  abstract = {Internal localization, the problem of estimating
     relative pose for each module (part) of a modular robot is a
     prerequisite for many shape control, locomotion, and actuation
     algorithms. In this paper, we propose a robust hierarchical
     approach that uses normalized cut to identify dense subregions
     with small mutual localization error, then progressively merges
     those subregions to localize the entire ensemble. Our method
     works well in both 2D and 3D, and requires neither exact
     measurements nor rigid inter-module connectors. Most of the
     computations in our method can be effectively distributed. The
     result is a robust algorithm that scales to large,
     non-homogeneous ensembles. We evaluate our algorithm in accurate
     2D and 3D simulations of scenarios with up to 10,000 modules.},
  keywords = {Distributed Systems, Localization, Meld},
  url = {http://www.cs.cmu.edu/~claytronics/papers/funiak-rss2008.pdf},
  see = {funiak-ijrr09},
}

@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{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{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{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{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{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},
}

@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{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{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},
}