Swarm Robots and the Freeze-Tag Problem

Posted 25 Feb 2004 at 17:26 UTC by steve

The Freeze-Tag Problem is a common optimization problem when dealing with swarms of robots. You start out with a swarm of "sleeping" robots in an arbitrary arrangement. One robot has to wake the swarm. To wake a sleeping robot, it must be "tagged" by an active robot. Once a robot is awakened, it can assist in waking other robots. The problem is figuring out how to wake all the robots as early as possible. In a recent paper, The Freeze-Tag Problem: How to Wake Up a Swarm of Robots (PDF format), Esther M. Arkin, Michael A. Bender and several other researcher do a lot of interesting math that proves the problem is NP-hard; a result confirmed by other studies of the problem.