Declarative Programming for Modular Robots

@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{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{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},
  venue = {Workshop on Self-Reconfigurable Robots/Systems and
     Applications at IROS},
  year = {2007},
  month = {October},
  keywords = {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 S.},
  title = {Hierarchical Motion Planning for Self-reconfigurable
     Modular Robots},
  booktitle = {2006 IEEE/RSJ International Conference on Intelligent
     Robots and Systems (IROS)},
  venue = {IEEE/RSJ International Conference on Intelligent Robots and
     Systems (IROS)},
  year = {2006},
  month = {October},
  keywords = {Planning, Controlling Ensembles, Hierarchical
     Algorithms},
  url = {http://www.cs.cmu.edu/~claytronics/papers/bhat06.pdf},
  abstract = {Motion planning for a self-reconfigurable robot involves
     coordinating the movement and connectivity of each of its
     homogeneous modules. Reconfiguration occurs when the shape of the
     robot changes from some initial configuration to a target
     configuration. Finding an optimal solution to reconfiguration
     problems involves searching the space of possible robot
     configurations. As this space grows exponentially with the number
     of modules, optimal planning becomes intractable. We propose a
     hierarchical planning approach that computes heuristic global
     reconfiguration strategies efficiently. Our approach consists of
     a base planner that computes an optimal solution for a few
     modules and a hierarchical planner that calls this base planner
     or reuses pre-computed plans at each level of the hierarchy to
     ultimately compute a global suboptimal solution. We present
     results from a prototype implementation of the method that
     efficiently plans for self-reconfigurable robots with several
     thousand modules.We also discuss tradeoffs and performance issues
     including scalability, heuristics and plan optimality.},
}

@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)},
  venue = {IEEE International Conference on Robotics and Automation
     (ICRA)},
  year = {2006},
  keywords = {Planning, Controlling Ensembles, Stochastic Algorithms},
  url = {http://www.cs.cmu.edu/~claytronics/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 proportional
     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{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{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{beckman-sdir07,
  author = {Beckman, Nels and Aldrich, Jonathan},
  title = {A Programming Model for Failure-Prone, Collaborative
     Robots},
  booktitle = {Workshop on Software Development and Integration in
     Robotics (SDIR)},
  venue = {Workshop on Software Development and Integration in
     Robotics (SDIR)},
  year = {2007},
  month = {April},
  keywords = {Programming Models},
  url = {http://www.cs.cmu.edu/~claytronics/papers/beckman-sdir07.pdf},
  talk = {http://www.cs.cmu.edu/~nbeckman/presentations/failure_prone_collaborative_robots.pdf},
  abstract = {A major problem in programming failure-prone
     collaborative robots is liveness. How do we ensure that the
     failure of one robot does not cause other robots to be
     permanently unavailable if, for example, that robot was a leader
     of others? In this paper, we propose a general mechanism which
     could be added to existing RPC libraries that allows applications
     to detect failure and execute programmer-specified recovery
     code.},
}

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