Distributed Watchpoints: Debugging Very Large Ensembles of 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},
}

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

@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{derosa-icra07,
 abstract = {Tightly-coupled multi-agent systems such as modular
 robots frequently exhibit properties of interest that span
 multiple modules. These properties cannot easily be detected from
 any single module, though they might readily be detected by
 combining the knowledge of multiple modules. Testing for
 distributed conditions is especially important in debugging or
 verifying the correctness of software for modular robots. We have
 developed a technique we call distributed watchpoint triggers
 which can efficiently recognize such distributed conditions. Our
 watchpoint description language can handle a variety of temporal,
 spatial, and logical properties spanning multiple robots. This
 paper presents that language, describes our fully-distributed,
 online mechanism for detecting distributed conditions in a
 running system, and evaluates the performance of our
 implementation. We found that the performance of the system is
 highly dependent on the program being debugged, scales linearly
 with ensemble size, and is small enough to make the system
 practical in all but the worst case scenarios.},
 author = {De~Rosa, Michael and Goldstein, Seth Copen and Lee, Peter
 and Campbell, Jason D. and Pillai, Padmanabhan and Mowry, Todd
 C.},
 booktitle = {Proceedings of the IEEE International Conference on
 Robotics and Automation {ICRA '07}},
 venue = {IEEE International Conference on Robotics and Automation
 (ICRA)},
 title = {Distributed Watchpoints: Debugging Large Multi-Robot
 Systems},
 year = {2007},
 month = {April},
 keywords = {Debugging, Distributed Algorithms},
 url = {http://www.cs.cmu.edu/~claytronics/papers/derosa-icra07.pdf},
}

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