Skip to main content
SpringerLink
Log in

The Freeze-Tag Problem: How to Wake Up a Swarm of Robots

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

An optimization problem that naturally arises in the study of swarm robotics is the Freeze-Tag Problem (FTP) of how to awaken a set of "asleep" robots, by having an awakened robot move to their locations. Once a robot is awake, it can assist in awakening other slumbering robots. The objective is to have all robots awake as early as possible. While the FTP bears some resemblance to problems from areas in combinatorial optimization such as routing, broadcasting, scheduling, and covering, its algorithmic characteristics are surprisingly different. We consider both scenarios on graphs and in geometric environments. In graphs, robots sleep at vertices and there is a length function on the edges. Awake robots travel along edges, with time depending on edge length. For most scenarios, we consider the offline version of the problem, in which each awake robot knows the position of all other robots. We prove that the problem is NP-hard, even for the special case of star graphs. We also establish hardness of approximation, showing that it is NP-hard to obtain an approximation factor better than 5/3, even for graphs of bounded degree. These lower bounds are complemented with several positive algorithmic results, including: · We show that the natural greedy strategy on star graphs has a tight worst-case performance of 7/3 and give a polynomial-time approximation scheme (PTAS) for star graphs. · We give a simple O(log δ)-competitive online algorithm for graphs with maximum degree δ and locally bounded edge weights. · We give a PTAS, running in nearly linear time, for geometrically embedded instances.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Author information

Authors and Affiliations

  1. Department of Applied Mathematics and Statistics, State University of New York, Stony Brook, NY 11794-3600, USA

    Esther M. Arkin & Joseph S. B. Mitchell

  2. Department of Computer Science, State University of New York, Stony Brook, NY 11794-4400, USA

    Michael A. Bender

  3. Department of Mathematical Optimization, Braunschweig University of Technology, Pockelsstr. 14, 38106, Braunschweig, Germany

    Sandor P. Fekete

  4. Fachbereich Mathematik, Universitat Dortmund, 4422, Dortmund, Germany

    Martin Skutella

Authors
  1. Esther M. Arkin
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Michael A. Bender
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Sandor P. Fekete
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Joseph S. B. Mitchell
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Martin Skutella
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding authors

Correspondence to Esther M. Arkin, Michael A. Bender, Sandor P. Fekete, Joseph S. B. Mitchell or Martin Skutella.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Arkin, E., Bender, M., Fekete, S. et al. The Freeze-Tag Problem: How to Wake Up a Swarm of Robots. Algorithmica 46, 193–221 (2006). https://doi.org/10.1007/s00453-006-1206-1

Download citation

  • Received:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00453-006-1206-1

Keywords

Search

Navigation