Problem 35: Freeze-Tag: Optimal Strategies for Awakening a Swarm of Robots

Statement

An optimization problem that naturally arises in the study of ``swarm robotics'' is to wake up a set of ``asleep'' robots, starting with only one ``awake'' robot. One robot can only awaken another when they are in the same location. As soon as a robot is awake, it may assist in waking up other robots. 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^* (the optimal makespan). The n robots are initially at n points of a metric space. The problem is equivalent to finding a spanning tree with maximum out-degree two that minimizes the radius from a fixed source.

Is it NP-hard to determine an optimal awakening schedule for robots in the Euclidean (or L₁) plane? In more general metric spaces, can one obtain an approximation algorithm with better than O(log n) performance ratio?

Origin

[ABF+02]

Status/Conjectures

[ABF+02] conjecture that the freeze-tag problem is NP-hard in the Euclidean (or L₁) plane. (They show it to be NP-complete in star metrics.)

Motivation

What is the most efficient way to "turn on" a large swarm of robots or to distribute to them a secret or a token that requires close proximity in order to pass from one to another?

Partial and Related Results

There are a variety of related results given in [ABF+02]. They show that the problem is NP-hard for "star metrics" (each asleep robot is at a leaf of a star graph whose spokes have various lengths). For geometric instances (L_p metrics) in fixed dimension, they give an efficient PTAS. For general metric spaces, they give an O(log n)-approximation algorithm. They also give improved approximation methods for other special cases (star graphs, ultrametrics)

Appearances

Posed in [ABF+02], and by Joseph Mitchell during the open problem session at the Fall Workshop on Computational Geometry, Brooklyn, NY, Nov. 2-3, 2001.

Categories

optimization; scheduling; robotics

Entry Revision History

E. Demaine, 20 Nov. 2001; J. Mitchell, 21 Nov. 2001.

Bibliography

ABF+02

E. M. Arkin, M. A. Bender, S. P. Fekete, J. S. B. Mitchell, and M. Skutella.
The freeze-tag problem: How to wake up a swarm of robots.
In Proc. 13th ACM-SIAM Sympos. Discrete Algorithms, 2002.
To appear.