Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2503.22521 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909556194410496 |
|---|---|
| author | Gavoille, Cyril Hanusse, Nicolas Bouder, Gabriel Le Marcé, Taïssir |
| author_facet | Gavoille, Cyril Hanusse, Nicolas Bouder, Gabriel Le Marcé, Taïssir |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_22521 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Distributed Freeze Tag: a Sustainable Solution to Discover and Wake-up a Robot Swarm Gavoille, Cyril Hanusse, Nicolas Bouder, Gabriel Le Marcé, Taïssir Data Structures and Algorithms 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. |
| title | Distributed Freeze Tag: a Sustainable Solution to Discover and Wake-up a Robot Swarm |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2503.22521 |