Advanced

The online freeze-tag problem

Hammar, Mikael LU ; Nilsson, Bengt J. and Persson, Mia LU (2006) LATIN 2006: Theoretical Informatics - 7th Latin American Symposium 3887 LNCS. p.569-579
Abstract
We consider the following problem from swarm robotics: given one or more "awake" robots in some metric space M, wake up a set of "asleep" robots. A robot awakens a sleeping robot by moving to the sleeping robot's position. When a robot awakens, it is available to assist in awakening other slumbering robots. We investigate offline and online versions of this problem and give a 2-competitive strategy and a lower bound of 2 in the case when M is discrete and the objective is to minimize the total movement cost. We also study the case when M is continuous and show a lower bound of 7/3 when the objective is to minimize the time when the last robot awakens.
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
keywords
Metric space, Slumbering robots
host publication
Lecture Notes in Computer Science
volume
3887 LNCS
pages
569 - 579
publisher
Springer
conference name
LATIN 2006: Theoretical Informatics - 7th Latin American Symposium
conference location
Valdivia, Chile
conference dates
2006-03-20 - 2006-03-24
external identifiers
  • scopus:33745628046
ISSN
1611-3349
0302-9743
DOI
10.1007/11682462_53
language
English
LU publication?
yes
id
d359cacb-6a15-4d54-b2d3-c8290b21cd25 (old id 617143)
date added to LUP
2007-11-24 10:11:58
date last changed
2019-02-20 03:31:37
@inproceedings{d359cacb-6a15-4d54-b2d3-c8290b21cd25,
  abstract     = {We consider the following problem from swarm robotics: given one or more "awake" robots in some metric space M, wake up a set of "asleep" robots. A robot awakens a sleeping robot by moving to the sleeping robot's position. When a robot awakens, it is available to assist in awakening other slumbering robots. We investigate offline and online versions of this problem and give a 2-competitive strategy and a lower bound of 2 in the case when M is discrete and the objective is to minimize the total movement cost. We also study the case when M is continuous and show a lower bound of 7/3 when the objective is to minimize the time when the last robot awakens.},
  author       = {Hammar, Mikael and Nilsson, Bengt J. and Persson, Mia},
  issn         = {1611-3349},
  keyword      = {Metric space,Slumbering robots},
  language     = {eng},
  location     = {Valdivia, Chile},
  pages        = {569--579},
  publisher    = {Springer},
  title        = {The online freeze-tag problem},
  url          = {http://dx.doi.org/10.1007/11682462_53},
  volume       = {3887 LNCS},
  year         = {2006},
}