Next: Problem 36: Inplace Convex Hull of a Simple Polygonal Chain
Previous: Problem 34: Extending Pseudosegment Arrangements by Subdivision
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_1) plane? In more general metric spaces, can one obtain an approximation algorithm with better than O(\log n) performance ratio?
[ABF+02] conjecture that the freeze-tag problem is NP-hard in the Euclidean (or L_1) plane. (They show it to be NP-complete in star metrics.)
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?
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)
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.
optimization; scheduling; robotics
E. Demaine, 20 Nov. 2001; J. Mitchell, 21 Nov. 2001.
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, pages 568–577, 2002.