Startseite > Publikationen > Publikationen

Publikationen

Degener, Bastian;Kempkes, Barbara;Kling, Peter;Meyer auf der Heide, Friedhelm:

A continuous, local strategy for constructing a short chain of mobile robots.

In: SIROCCO '10: Proceedings of the 17th International Colloquium on Structural Information and Communication Complexity, LNCS, Band 6058 , S. 168-182, 7. - 11. Jun. 2010, Springer

Abstract

We are given an arbitrarily shaped chain of n robots with fixed end points in the plane. We assume that each robot can only see its two neighbors in the chain, which have to be within its viewing range. The goal is to move the robots to the straight line between the end points. Each robot has to base the decision where to move on the relative positions of its neighbors only. Such local strategies considered until now are based on discrete rounds, where a round consists of a movement of each robot. In this paper, we initiate the study of continuous local strategies: The robots may perpetually observe the relative positions of their neighbors, and may perpetually adjust their speed and direction in response to these observations. We assume a speed limit for the robots, that we normalize to one, which corresponds to the viewing range. Our contribution is a continuous, local strategy that needs time O(min{n, (OPT+d)log(n)}). Here d is the distance between the two stationary end points, and OPT is the time needed by an optimal global strategy. Our strategy has the property that the robot which reaches its destination last always moves with maximum speed. Thus, the same bound as above also holds for the distance travelled.

Dateien

MOBFinal.pdf



Bibtex

@inproceedings{hniid=4994,
author = {Degener, Bastian and Kempkes, Barbara and Kling, Peter and Meyer auf der Heide, Friedhelm},
title = {A continuous, local strategy for constructing a short chain of mobile robots},
booktitle = {SIROCCO '10: Proceedings of the 17th International Colloquium on Structural Information and Communication Complexity},
volume = {6058},
series = {LNCS},
pages = {168-182},
publisher = {Springer},
month = {7~-~11~} # jun,
year = {2010},
}

BibTeX in die Zwischenablage kopieren

Permalink

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