11:00
12:00

Gabriel Le Bouder (LaBRI)

Title: Distributed Freeze Tag: a Sustainable Solution to Discover and Wake-up a Robot Swarm

Abstract:

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(ρ+ℓ² log(ρ/ℓ)), where ρ stands for the largest distance from the initial robot to any point of 𝒫, and the ℓ is the connectivity threshold of 𝒫. Moreover, the result is complemented by a matching lower bound in both parameters ρ and ℓ. We also provide other distributed algorithms, complemented with lower bounds, whenever each robot has a bounded amount of energy.

https://algodist.labri.fr/index.php/Main/GT

LaBRI salle 178 - lien visio https://webconf.u-bordeaux.fr/b/arn-4tr-7gp