Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
faculty | junior-faculty | postdocs | students | associate students | former students | former associate students
locations | Term schedule | history
predoc-courses | schools | block-courses | workshops

Monday Lecture and Colloquium

Monday, February 9, 2009

Technische Universität Berlin
Fakultät II, Institut für Mathematik
Str. des 17. Juni 136,
room MA 041

Lecture - 14:15

Friedhelm Meyer auf der Heide - Heinz Nixdorf Institute and Computer Science Department, University of Paderborn

Local Strategies for Maintaining Communication among Mobile Robots

We envision a scenario where a team of robots, so-called explorers, move in a plane. In addition, relay robots are around. Both the explorers and the relays have small communication range. The task of the relays is to make sure that the explorer can communicate with each other, i.e., that the dynamic unit disk graph formed by the explorers and the relays stays connected. Whereas the explorers move in an adversarial manner, the relays move in order to keep the system connected. These relays are very restricted: They have no global view of the scene; rather, they have to base their decisions solely on their local views, i.e., on the relative positions of the robots within their communication range. The goal is to design local rules for the relays that make sure that the system remains globally connected; in addition, as few as possible relays should be employed. In the talk, I will describe and analyse such local strategies for the relays. The main results will be strategies that are guaranteed to use a close-to-minimum number of relays, in case of one explorer to be connected to a stationary base camp. We also present local strategies for the general scenario of many explorers and give theoretical and experimental insights into their behaviour.

This is joint work with Jaroslaw Kutylowski and Barbara Kempkes.

no colloquium today!

Letzte Aktualisierung: 03.02.2009