Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

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
; and
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
0302-9743
1611-3349
DOI
10.1007/11682462_53
language
English
LU publication?
yes
id
d359cacb-6a15-4d54-b2d3-c8290b21cd25 (old id 617143)
date added to LUP
2016-04-01 11:33:06
date last changed
2024-10-08 01:37:07
@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}},
  booktitle    = {{Lecture Notes in Computer Science}},
  issn         = {{0302-9743}},
  keywords     = {{Metric space; Slumbering robots}},
  language     = {{eng}},
  pages        = {{569--579}},
  publisher    = {{Springer}},
  title        = {{The online freeze-tag problem}},
  url          = {{http://dx.doi.org/10.1007/11682462_53}},
  doi          = {{10.1007/11682462_53}},
  volume       = {{3887 LNCS}},
  year         = {{2006}},
}