NewsnewsArchivearchive

Swarm Robots and the Freeze-Tag Problem

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. ArkinMichael A. Bender, and several other researchers do a lot of interesting math that proves the problem is NP-hard; a result confirmed by other studies of the problem.

Leave a Reply

Your email address will not be published. Required fields are marked *