## Distributed Computing by Oblivious Mobile RobotsThe study of what can be computed by a team of autonomous mobile robots, originally started in robotics and AI, has become increasingly popular in theoretical computer science (especially in distributed computing), where it is now an integral part of the investigations on computability by mobile entities. The robots are identical computational entities located and able to move in a spatial universe; they operate without explicit communication and are usually unable to remember the past; they are extremely simple, with limited resources, and individually quite weak. However, collectively the robots are capable of performing complex tasks, and form a system with desirable fault-tolerant and self-stabilizing properties. The research has been concerned with the computational aspects of such systems. In particular, the focus has been on the minimal capabilities that the robots should have in order to solve a problem. This book focuses on the recent algorithmic results in the field of distributed computing by oblivious mobile robots (unable to remember the past). After introducing the computational model with its nuances, we focus on basic coordination problems: pattern formation, gathering, scattering, leader election, as well as on dynamic tasks such as flocking. For each of these problems, we provide a snapshot of the state of the art, reviewing the existing algorithmic results. In doing so, we outline solution techniques, and we analyze the impact of the different assumptions on the robots' computability power. Table of Contents: Introduction / Computational Models / Gathering and Convergence / Pattern Formation / Scatterings and Coverings / Flocking / Other Directions |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

Computational Models | 7 |

Gathering and Convergence | 17 |

Pattern Formation | 65 |

Scatterings and Coverings | 103 |

Flocking | 117 |

xii | 135 |

Bibliography | 153 |

Authors Biographies | 167 |

### Other editions - View all

Distributed Computing by Oblivious Mobile Robots Paola Flocchini,Giuseppe Prencipe,Nicola Santoro Limited preview - 2012 |

### Common terms and phrases

achieved activated agreement angle Arbitrary Pattern Formation assumed Assumptions Async asynchronous autonomous mobile robots axis biangular configuration chirality Cited on page(s clockwise closest collisions common coordinate system consider ConsistentCompass convergence Convergence problem convex hull cops defined denote dense point destination point deterministic deterministic algorithm discrete spaces distinct Distributed Computing execution exploration Figure final positions Fsync gathering algorithm Gathering problem given global guided trajectory initial configuration leader election Lemma limited visibility Module movement n-gon Near-Gathering non-faulty robots number of robots oblivious robots ofrobots ofthe robots orientation Pattern Formation problem possible probabilistic probabilistic algorithm protocol reach rendezvous rendezvous problem robot ri robots form robots move Rotate scheduler SIROCCO smallest enclosing circle snapshot solid robots solution solvable solve Ssync strong multiplicity detection symmetric target Theorem three robots tilt uniform circle formation unique vertex visibility graph visibility radius