A Language for Large Ensembles of Independently Executing Nodes

@inproceedings{ashley-rollman-iclp09,
  author = {Ashley-Rollman, Michael P. and Lee, Peter and Goldstein,
     Seth Copen and Pillai, Padmanabhan and Campbell, Jason D.},
  title = {A Language for Large Ensembles of Independently Executing
     Nodes},
  year = {2009},
  month = {July},
  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 = {June},
  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},
}

@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 = {September},
  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}},
  venue = {Workshop on Self-Reconfigurable Robots/Systems and
     Applications at IROS},
  year = {2007},
  month = {October},
  keywords = {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})},
  venue = {IEEE/RSJ International Conference on Intelligent Robots and
     Systems (IROS)},
  year = {2007},
  month = {October},
  keywords = {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{ashley-rollman-iclp09,
  author = {Ashley-Rollman, Michael P. and Lee, Peter and Goldstein,
     Seth Copen and Pillai, Padmanabhan and Campbell, Jason D.},
  title = {A Language for Large Ensembles of Independently Executing
     Nodes},
  year = {2009},
  month = {July},
  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 = {June},
  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},
}

@article{mderosa-ijrr-2008,
  author = {De~Rosa, Michael and Goldstein, Seth Copen and Lee, Peter
     and Campbell, Jason D. and Pillai, Padmanabhan},
  journal = {International Journal of Robotics Research},
  keywords = {Debugging, Distributed Systems},
  month = {March},
  note = {Special Issue on Modular Robotics},
  url = {http://www.cs.cmu.edu/~claytronics/papers/mderosa-ijrr-2008.pdf},
  venue = {International Journal of Robotics Research},
  number = {3},
  title = {Distributed Watchpoints: Debugging Large Modular Robotic
     Systems},
  abstract = {Distributed systems frequently exhibit properties of
     interest which span multiple entities. These properties cannot
     easily be detected from any single entity, but can be readily be
     detected by combining the knowledge of multiple entities. Testing
     for distributed properties is especially important in debugging
     or verifying software for modular robots. We have developed a
     technique we call distributed watchpoint triggers which can
     efficiently recognize distributed conditions. Our watchpoint
     description language can handle a variety of temporal, spatial,
     and logical properties spanning multiple robots. This paper
     presents the specification language, describes the distributed
     online mechanism for detecting distributed conditions in a
     running system, and evaluates the performance of our
     implementation.},
  volume = {27},
  also = {Distributed Watchpoints: Debugging Large Multi-Robot
     Systems, (icra07)},
  year = {2008},
}

@inproceedings{rister-icra07,
  author = {Rister, Benjamin D. and Campbell, Jason D. and Pillai,
     Padmanabhan and Mowry, Todd C.},
  title = {Integrated Debugging of Large Modular Robot Ensembles},
  booktitle = {Proceedings of the IEEE International Conference on
     Robotics and Automation {ICRA '07}},
  venue = {IEEE International Conference on Robotics and Automation
     (ICRA)},
  keywords = {Debugging, Distributed Systems},
  month = {April},
  abstract = {Creatively misquoting Thomas Hobbes, the process of
     software debugging is nasty, brutish, and all too long. This
     holds all the more true in robotics, which frequently involves
     concurrency, extensive nondeterminisism, event-driven components,
     complex state machines, and difficult platform limitations.
     Inspired by the challenges we have encountered while attempting
     to debug software on simulated ensembles of tens of thousands of
     modular robots, we have developed a new debugging tool
     particularly suited to the characteristics of highly parallel,
     event- and state-driven robotics software. Our state capture and
     introspection system also provides data that may be used in
     higher-level debugging tools as well. We report on the design of
     this promising debugging system, and on our experiences with it
     so far.},
  year = {2007},
  url = {http://www.cs.cmu.edu/~claytronics/papers/rister-icra07.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},
  venue = {Robotics: Science and Systems Workshop on
     Self-Reconfigurable Modular Robots},
  title = {Distributed Watchpoints: Debugging Very Large Ensembles of
     Robots},
  month = {August},
  year = {2006},
  keywords = {Debugging, Distributed Systems},
  address = {Philadelphia, PA},
  talk = {http://www.cs.cmu.edu/~seth/papers/derosa-talk-rss06.pdf},
  url = {http://www.cs.cmu.edu/~claytronics/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{ashley-rollman-iclp09,
  author = {Ashley-Rollman, Michael P. and Lee, Peter and Goldstein,
     Seth Copen and Pillai, Padmanabhan and Campbell, Jason D.},
  title = {A Language for Large Ensembles of Independently Executing
     Nodes},
  year = {2009},
  month = {July},
  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{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})},
  venue = {IEEE/RSJ International Conference on Intelligent Robots and
     Systems (IROS)},
  year = {2007},
  month = {October},
  keywords = {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},
}