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 = {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{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{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},
  venue = {Revolutionary Aerospace Systems Concepts Academic Linkage
     {(RASC-AL)} Forum},
  author = {Karagozler, Mustafa Emre and Kirby, Brian and Lee, W.J.
     and Marinelli, Eugene and Ng, T.C. and Weller, Michael Philetus
     and Goldstein, Seth Copen},
  year = {2006},
  month = {May},
  address = {Cape Canaveral, FL},
  url = {http://www.cs.cmu.edu/~claytronics/papers/karagozler-rascal06.pdf},
  keywords = {Applications of Claytronics, Robotics},
}

@inproceedings{goldstein-robosphere04,
  author = {Goldstein, Seth Copen and Mowry, Todd C.},
  title = {Claytronics: A scalable basis for future robots},
  booktitle = {RoboSphere 2004},
  venue = {RoboSphere 2004},
  address = {Moffett Field, CA},
  month = {November},
  year = {2004},
  keywords = {Robotics},
  url = {http://www.cs.cmu.edu/~claytronics/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 = {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{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},
}

@article{campbell-ijrr-srmr,
  author = {Campbell, Jason D. and Pillai, Padmanabhan},
  title = {Collective Actuation},
  journal = {International Journal of Robotics Research},
  volume = {27},
  number = {3-4},
  year = {2008},
  pages = {299-314},
  keywords = {Actuation, Controlling Ensembles},
  abstract = {Modular robot designers confront an inherent tradeoff
     between size and power: Smaller, more numerous modules increase
     the adaptability of a given volume or mass of robot---allowing
     the aggregate robot to take on a wider variety of
     configurations---but do so at a cost of reducing the power and
     complexity budget of each module. Fewer, larger modules can
     incorporate more powerful actuators and stronger hinges but at a
     cost of overspecializing the resulting robot in favor of
     corresponding uses. In the paper we describe a technique for
     coordinating the efforts of many tiny modules to achieve forces
     and movements larger than those possible for individual modules.
     In a broad sense, the question of actuator capacity and range
     thus may become one of software coding and ensemble topology as
     well as of hardware design. An important aspect of this technique
     is its ability to bend complex and large-scale structures and to
     realize the equivalent of large scale joints. Although our
     results do not suggest that modular robots will replace high
     power purpose-built robots, they do offer an increase in the
     plausible scalability of modular robot self-reconfiguration and
     facilitate a corresponding increase in adaptability.},
}

@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{Christensen-icra07,
  author = {Christensen, David Johan and Campbell, Jason D.},
  title = {Locomotion of Miniature Catom Chains: Scale Effects on Gait
     and Velocity},
  booktitle = {Proceedings of the IEEE International Conference on
     Robotics and Automation ({ICRA '07})},
  venue = {IEEE International Conference on Robotics and Automation
     (ICRA)},
  month = {April},
  pages = {2254-2260},
  keywords = {Biologically Inspired, Actuation, Controlling
     Ensembles},
  year = {2007},
}

@inproceedings{campbell-rss06,
  author = {Campbell, Jason D. and Pillai, Padmanabhan},
  title = {Collective Actuation},
  booktitle = {RSS 2006 Workshop on Self-Reconfigurable Modular
     Robots},
  venue = {Robotics: Science and Systems Workshop on
     Self-Reconfigurable Modular Robots},
  year = {2006},
  month = {August},
  keywords = {Actuation, Controlling Ensembles},
  url = {http://www.cs.cmu.edu/~claytronics/papers/campbell-rss06.pdf},
  abstract = {Modular robot designers confront an inherent tradeoff
     between size and power: Smaller, more numerous modules increase
     the adaptability of a given volume or mass of modules---allowing
     the aggregate robot to take on a wider variety of configurations
     – but do so at the expense of the power and complexity of each
     module. Fewer, larger modules can incorporate more powerful
     actuators, more powerful bonds, and stronger hinges but at a cost
     of overspecializing the resulting robot in favor of
     correspond-ing uses. We describe a technique for coordinating the
     efforts of many tiny modules to achieve forces and movements
     be-yond those possible for individual modules. Our approach is
     predominantly applicable to spherical and cylindrical modules and
     their faceted counterparts, but may apply to some chain-style
     modular robot systems. Thus actuator capacity and range becomes a
     function of software and dynamic topology as well as of hardware.
     An important aspect of this technique is its ability to bend
     complex and large-scale structures and to realize the equivalent
     of large scale joints.},
}

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

@article{Lakhlef-SUPE14,
  author = {Lakhlef, Hicham and Mabed, Hakim and Bourgeois, Julien},
  title = {An Energy and Memory-Efficient Distributed
     Self-reconfiguration for Modular Sensor/Robot Networks},
  journal = {Journal of Supercomputing},
  pages = {***--***},
  volume = {*},
  number = {*},
  publisher = {Springer},
  year = {2014},
  keywords = {Multi-Robot Formations},
}

@article{Lakhlef-JNCA14,
  author = {Lakhlef, Hicham and Mabed, Hakim and Bourgeois, Julien},
  title = {Optimization of the Logical Topology for Mobile {MEMS}
     Networks},
  journal = {JNCA, Journal of Network and Computer Applications},
  pages = {***--***},
  volume = {*},
  number = {*},
  publisher = {Elsevier},
  year = {2014},
  keywords = {Multi-Robot Formations},
}

@inproceedings{Lakhlef-AINA14,
  author = {Lakhlef, Hicham and Bourgeois, Julien and Mabed, Hakim},
  title = {Robust Parallel Redeployment Algorithm for {MEMS}
     Microrobots.},
  booktitle = {AINA 2014, 28th IEEE Int. Conf. on Advanced Information
     Networking and Applications},
  pages = {1--8},
  address = {Victoria, Canada},
  publisher = {IEEE},
  month = {May},
  year = {2014},
  keywords = {Multi-Robot Formations},
}

@inproceedings{lakhlef-sac13,
  author = {Lakhlef, Hicham and Mabed, Hakim and Bourgeois, Julien},
  title = {Distributed and Efficient Algorithm for
     Self-reconfiguration of {MEMS} Microrobots},
  booktitle = {SAC 2013, 28-th ACM Symposium On Applied Computing},
  pages = {1--6},
  address = {Coimbra, Portugal},
  month = {March},
  year = {2013},
  keywords = {Multi-Robot Formations},
}

@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{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}},
  venue = {IEEE/RSJ International Conference on Intelligent Robots and
     Systems (IROS)},
  year = {2007},
  month = {October},
  keywords = {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},
}