Startseite > Publikationen > Publikationen

Publikationen

Cord-Landwehr, Andreas;Degener, Bastian;Fischer, Matthias;Hüllmann, Martina;Kempkes, Barbara;Klaas, Alexander;Kling, Peter;Kurras, Sven;Märtens, Marcus;Meyer auf der Heide, Friedhelm;Raupach, Christoph;Swierkot, Kamil;Warner, Daniel;Weddemann, Christoph;Wonisch, Daniel:

A new Approach for Analyzing Convergence Algorithms for Mobile Robots.

In: Proceedings of the 38th International Colloquium on Automata, Languages and Programming (ICALP 2011), Lecture Notes in Computer Science, Band 6756 , S. 650--661, Jul. 2011, Springer-Verlag, Heidelberg, Germany

Abstract

Given a set of n mobile robots in the d-dimensional Euclidean space, the goal is to let them converge to a single not predefined point. The challenge is that the robots are limited in their capabilities. Robots can, upon activation, compute the positions of all other robots using an individual affine coordinate system. The robots are indistinguishable, oblivious and may have different affine coordinate systems. A very general discrete time model assumes that robots are activated in arbitrary order. Further, the computation of a new target point may happen much earlier than the movement, so that the movement is based on outdated information about other robot's positions. Time is measured as the number of rounds, where a round ends as soon as each robot has moved at least once. In [Cohen, Peleg: Convergence properties of gravitational algorithms in asynchronous robot systems], the Center of Gravity is considered as target function, convergence was proven, and the number of rounds needed for halving the diameter of the convex hull of the robot's positions was shown to be O(n^2) and Omega(n). We present an easy-to-check property of target functions that guarantee convergence and yields upper time bounds. This property intuitively says that when a robot computes a new target point, this point is significantly within the current axes aligned minimal box containing all robots. This property holds, e.g., for the above-mentioned target function, and improves the above O(n^2) to an asymptotically optimal O(n) upper bound. Our technique also yields a constant time bound for a target function that requires all robots having identical coordinate axes.

Bibtex

@inproceedings{hniid=5301,
author = {Cord-Landwehr, Andreas and Degener, Bastian and Fischer, Matthias and H{\"u}llmann, Martina and Kempkes, Barbara and Klaas, Alexander and Kling, Peter and Kurras, Sven and M{\"a}rtens, Marcus and Meyer auf der Heide, Friedhelm and Raupach, Christoph and Swierkot, Kamil and Warner, Daniel and Weddemann, Christoph and Wonisch, Daniel},
title = {A new Approach for Analyzing Convergence Algorithms for Mobile Robots},
booktitle = {Proceedings of the 38th International Colloquium on Automata, Languages and Programming (ICALP 2011)},
volume = {6756},
series = {Lecture Notes in Computer Science},
pages = {650--661},
publisher = {Springer-Verlag, Heidelberg, Germany},
month = jul,
year = {2011},
}

BibTeX in die Zwischenablage kopieren

Permalink

https://www.hni.uni-paderborn.de/pub/5301