Theoretical and Experimental Analysis of Heuristics for the “Freeze-Tag” Robot Awakening Problem

In the “freeze-tag” problem, we are given a swarm of n sleeping (frozen or inactive) robots and a single awake (active) robot. The goal is to awaken all robots in the shortest possible time. A robot is awakened when an active robot “touches” it. The goal is to compute an optimal awakening schedule such that all robots are awake by time t*, for the smallest possible value of t*. We devise and test a variety of heuristic strategies on geometric and network datasets. Our experiments show that all of the strategies perform acceptably well, with the simple greedy strategy performing particularly well. A theoretical analysis of the greedy strategy gives a tight approximation bound of Θ(log n) for points in the plane. We show more generally a tight performance bound of Θ((log n)^1-1/d) in d dimensions. The geometric case contrasts with the case of general metric spaces, where greedy is known to have a Θ(log n) approximation factor, and no method is known to achieve an approximation factor of o(log n).