Startseite > Publikationen > Publikationen


Brandes, Philipp;Degener, Bastian;Kempkes, Barbara;Meyer auf der Heide, Friedhelm:

Building short chains of mobile robots locally with a bounded stepwidth.

, preprint 2010


We are given a winding chain of $n$ mobile robots between two stations in the plane, each of them having a limited viewing range. It is only guaranteed that each robot can see its two neighbors in the chain. We analyze a simple and natural parallel strategy to shorten the chain in a time model where each relay is allowed to move up to a distance of $\delta$ in each time step. This model fills the gap between the previously used discrete time model and the continuous time model which was introduced recently in \cite{sirocco}. We analyze the strategy with respect to two quality measures: the number of time steps and the maximum distance to be traveled by the robots, which are the major energy consumers in this scenario. We provide asymptotically tight or almost tight bounds in this time model for both quality measures and it turns out that the best choice for $\delta$ is $\delta \in \Theta(\frac{1}{n})$, since this minimizes the number of time steps as well as the maximum traveled distance.




author = {Brandes, Philipp and Degener, Bastian and Kempkes, Barbara and Meyer auf der Heide, Friedhelm},
title = {Building short chains of mobile robots locally with a bounded stepwidth},
note = {preprint},
year = {2010},

BibTeX in die Zwischenablage kopieren