
























The Freeze Tag Problem consists in waking up a swarm of robots starting with one initially awake robot. Whereas there is a wide literature of the centralized setting, where the location of the robots is known in advance, we focus in the distributed version where the location of the robots $¶$ are unknown, and where awake robots only detect other robots up to distance~$1$. Assuming that moving at distance $δ$ takes a time $δ$, we show that waking up of the whole swarm takes $O(ρ+\ell^2\log( ρ/\ell))$, where $ρ$ stands for the largest distance from the initial robot to any point of $¶$, and the $\ell$ is the connectivity threshold of $¶$. Moreover, the result is complemented by a matching lower bound in both parameters $ρ$ and $\ell$. We also provide other distributed algorithms, complemented with lower bounds, whenever each robot has a bounded amount of energy.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。