Scalable Shape Sculpting via Hole Motion: Motion Planning in Lattice-Constrained Module Robots

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

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