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.