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

Abstract

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/sup */, for the smallest possible value of t/sup */. 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 /spl Theta/(/spl radic/logn) for points in the plane. We show more generally a tight performance bound of /spl Theta/((logn)/sup 1-1/d/) in d dimensions. The geometric case contrasts with the case of general metric spaces, where greedy is known to have a /spl Theta/(logn) approximation factor, and no method is known to achieve an approximation factor of o(logn).