Linear time constant factor approximation algorithm for the Euclidean Freeze-Tag robot awakening problem

The Freeze-Tag Problem (FTP) arises in the study of swarm robotics. The FTP is a combinatorial optimization problem that starts by locating a set of robots in a Euclidean plane. Here, weare given a swarm of n asleep (frozen or inactive) robots and a single awake (active) robot. In order to activate an inactive robotin FTP, the active robot should either be in the physical proximity to the inactive robot or touch it. The new activatedrobot starts moving and can wake up other inactive robots. Thegoal is to find an optimal activating schedule with the minimum time required for activating all robots. In general, FTP is an NPHardproblem and in the Euclidean space is an open problem. In this paper, we present a recursive approximation algorithm with aconstant approximation factor and a linear running time for the Euclidean Freeze-Tag Problem

Keywords:

Freeze Tag Problem , Recursive Algorithm , Optimization , Swarm Robotics , Computational Geometry