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

P. Brandes, B. Degener, B. Kempkes, F. Meyer auf der Heide, (2010).

BoundedStepwidth.pdf 476.53 KB
Preprint | English
Author
; ; ;
Abstract
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.
Publishing Year
LibreCat-ID

### Cite this

Brandes P, Degener B, Kempkes B, Meyer auf der Heide F. Building short chains of mobile robots locally with a bounded stepwidth. 2010.
Brandes, P., Degener, B., Kempkes, B., & Meyer auf der Heide, F. (2010). Building short chains of mobile robots locally with a bounded stepwidth.
@article{Brandes_Degener_Kempkes_Meyer auf der Heide_2010, title={Building short chains of mobile robots locally with a bounded stepwidth}, author={Brandes, Philipp and Degener, Bastian and Kempkes, Barbara and Meyer auf der Heide, Friedhelm}, year={2010} }
Brandes, Philipp, Bastian Degener, Barbara Kempkes, and Friedhelm Meyer auf der Heide. “Building Short Chains of Mobile Robots Locally with a Bounded Stepwidth,” 2010.
P. Brandes, B. Degener, B. Kempkes, and F. Meyer auf der Heide, “Building short chains of mobile robots locally with a bounded stepwidth.” 2010.
Brandes, Philipp, et al. Building Short Chains of Mobile Robots Locally with a Bounded Stepwidth. 2010.
Main File(s)
File Name
BoundedStepwidth.pdf 476.53 KB
Access Level
Closed Access