Science

Swarm Robots and the Freeze-Tag Problem

Posted 25 Feb 2004 at 17:26 UTC by steve Share This

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.

Robot of the Day

HEXAL-R

Built by
Vibhu Vivek

Recent blogs

4 Jul 2009 limor (Master)
4 Jul 2009 jmhenry (Apprentice)
30 Jun 2009 steve (Master)
29 Jun 2009 svo (Master)
26 Jun 2009 jkkroll (Master)
25 Jun 2009 p.stegemann (Apprentice)
19 Jun 2009 motters (Master)
13 Jun 2009 jwp9447 (Observer)
12 Jun 2009 c6jones720 (Master)
10 Jun 2009 ROB.T. (Master)
9 Jun 2009 Sergey Popov (Apprentice)
8 Jun 2009 MRyan (Apprentice)
5 Jun 2009 kuka (Journeyer)
5 Jun 2009 Roko (Apprentice)
4 Jun 2009 roboilo (Journeyer)
3 Jun 2009 roschler (Master)
31 May 2009 thorn_stevens (Journeyer)
27 May 2009 trossenrobotics (Observer)

Newest Robots

13 May 2009 Spacechair
6 Feb 2009 K-bot
9 Jan 2009 3 in 1 Bot
15 Dec 2008 UMEEBOT
10 Nov 2008 Robot
10 Nov 2008 SAMM
24 Oct 2008 Romulus
30 Sep 2008 CD-Bot
26 Sep 2008 Little Johnny
11 Aug 2008 Chives

User Cert Key

Observer
Apprentice
Journeyer
Master
X
Share this page