Distributed Localization of Modular Robot Ensembles

@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{funiak-ijrr08,
 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},
 journal = {International Journal of Robotics Research},
 keywords = {Localization, Modular Robotics},
 volume = {28},
 number = {8},
 year = {2009},
 pages = {946-961},
}

@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{funiak-iros07,
 author = {Funiak, Stanislav and Pillai, Padmanabhan and Campbell,
 Jason D. and Goldstein, Seth Copen},
 title = {Internal Localization of Modular Robot Ensembles},
 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},
 abstract = {The determination of the relative position and pose of
 every robot in a modular robotic ensemble is a necessary
 preliminary step for most modular robotic tasks. Localization is
 particularly important when the modules make local noisy
 observations and are not significantly constrained by inter-robot
 latches. In this paper, we propose a robust hierarchical approach
 to the {\em internal localization} problem that uses normalized
 cut to identify subproblems with small localization error. A key
 component of our solution is a simple method to reduce the cost
 of normalized cut computations. The result is a robust algorithm
 that scales to large, non-homogeneous ensembles. We evaluate our
 algorithm in simulation on ensembles of up to 10,000 modules,
 demonstrating substantial improvements over prior work.},
 keywords = {Probabilistic Inference, Sensing, Localization,
 Distributed Algorithms},
 url = {http://www.cs.cmu.edu/~claytronics/papers/funiak-iros07.pdf},
}

@inproceedings{funiak-ipsn06,
 author = {Funiak, Stanislav and Guestrin, Carlos and Sukthankar,
 Rahul and Paskin, Mark},
 title = {Distributed Localization of Networked Cameras},
 booktitle = {Fifth International Conference on Information
 Processing in Sensor Networks (IPSN'06)},
 venue = {International Conference on Information Processing in
 Sensor Networks (IPSN'06)},
 month = {April},
 pages = {34--42},
 year = {2006},
 keywords = {Probabilistic Inference, Sensing, Distributed
 Algorithms, Graphical Models, Localization},
 url = {http://www.cs.cmu.edu/~claytronics/papers/funiak-ipsn06.pdf},
 abstract = {Camera networks are perhaps the most common type of
 sensor network and are deployed in a variety of real-world
 applications including surveillance, intelligent environments and
 scientific remote monitoring. A key problem in deploying a
 network of cameras is calibration, i.e., determining the location
 and orientation of each sensor so that observations in an image
 can be mapped to locations in the real world. This paper proposes
 a fully distributed approach for camera network calibration. The
 cameras collaborate to track an object that moves through the
 environment and reason probabilistically about which camera poses
 are consistent with the observed images. This reasoning employs
 sophisticated techniques for handling the difficult
 nonlinearities imposed by projective transformations, as well as
 the dense correlations that arise between distant cameras. Our
 method requires minimal overlap of the cameras' fields of view
 and makes very few assumptions about the motion of the object. In
 contrast to existing approaches, which are centralized, our
 distributed algorithm scales easily to very large camera
 networks. We evaluate the system on a real camera network with 25
 nodes as well as simulated camera networks of up to 50 cameras
 and demonstrate that our approach performs well even when
 communication is lossy.},
}

@mastersthesis{reshko04,
 author = {Reshko, Greg},
 venue = {Masters Thesis},
 title = {Localization Techniques for Synthetic Reality},
 school = {Carnegie Mellon University},
 keywords = {Localization},
 year = {2004},
}

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