---
_id: '19899'
abstract:
- lang: eng
  text: "Most existing robot formation problems seek a target formation of a certain\r\nminimal
    and, thus, efficient structure. Examples include the Gathering\r\nand the Chain-Formation
    problem. In this work, we study formation problems that\r\ntry to reach a maximal
    structure, supporting for example an efficient\r\ncoverage in exploration scenarios.
    A recent example is the NASA Shapeshifter\r\nproject, which describes how the
    robots form a relay chain along which gathered\r\ndata from extraterrestrial cave
    explorations may be sent to a home base.\r\n  As a first step towards understanding
    such maximization tasks, we introduce\r\nand study the Max-Chain-Formation problem,
    where $n$ robots are ordered along a\r\nwinding, potentially self-intersecting
    chain and must form a connected,\r\nstraight line of maximal length connecting
    its two endpoints. We propose and\r\nanalyze strategies in a discrete and in a
    continuous time model. In the\r\ndiscrete case, we give a complete analysis if
    all robots are initially\r\ncollinear, showing that the worst-case time to reach
    an\r\n$\\varepsilon$-approximation is upper bounded by $\\mathcal{O}(n^2 \\cdot
    \\log\r\n(n/\\varepsilon))$ and lower bounded by $\\Omega(n^2 \\cdot~\\log\r\n(1/\\varepsilon))$.
    If one endpoint of the chain remains stationary, this result\r\ncan be extended
    to the non-collinear case. If both endpoints move, we identify\r\na family of
    instances whose runtime is unbounded. For the continuous model, we\r\ngive a strategy
    with an optimal runtime bound of $\\Theta(n)$. Avoiding an\r\nunbounded runtime
    similar to the discrete case relies crucially on a\r\ncounter-intuitive aspect
    of the strategy: slowing down the endpoints while all\r\nother robots move at
    full speed. Surprisingly, we can show that a similar trick\r\ndoes not work in
    the discrete model."
author:
- first_name: Jannik
  full_name: Castenow, Jannik
  id: '38705'
  last_name: Castenow
- first_name: Peter
  full_name: Kling, Peter
  last_name: Kling
- first_name: Till
  full_name: Knollmann, Till
  id: '39241'
  last_name: Knollmann
  orcid: 0000-0003-2014-4696
- first_name: Friedhelm
  full_name: Meyer auf der Heide, Friedhelm
  id: '15523'
  last_name: Meyer auf der Heide
citation:
  ama: 'Castenow J, Kling P, Knollmann T, Meyer auf der Heide F. A Discrete and Continuous
    Study of the Max-Chain-Formation Problem – Slow Down to Speed Up. In: Devismes  S,
    Mittal N, eds. <i>Stabilization, Safety, and Security of Distributed Systems -
    22nd International Symposium, SSS 2020, Austin, Texas, USA, November 18-21, 2020,
    Proceedings</i>. Vol 12514. Lecture Notes in Computer Science (LNCS). Springer;
    2020:65-80. doi:<a href="https://doi.org/10.1007/978-3-030-64348-5_6">10.1007/978-3-030-64348-5_6</a>'
  apa: Castenow, J., Kling, P., Knollmann, T., &#38; Meyer auf der Heide, F. (2020).
    A Discrete and Continuous Study of the Max-Chain-Formation Problem – Slow Down
    to Speed Up. In S. Devismes  &#38; N. Mittal (Eds.), <i>Stabilization, Safety,
    and Security of Distributed Systems - 22nd International Symposium, SSS 2020,
    Austin, Texas, USA, November 18-21, 2020, Proceedings</i> (Vol. 12514, pp. 65–80).
    Springer. <a href="https://doi.org/10.1007/978-3-030-64348-5_6">https://doi.org/10.1007/978-3-030-64348-5_6</a>
  bibtex: '@inproceedings{Castenow_Kling_Knollmann_Meyer auf der Heide_2020, series={Lecture
    Notes in Computer Science (LNCS)}, title={A Discrete and Continuous Study of the
    Max-Chain-Formation Problem – Slow Down to Speed Up}, volume={12514}, DOI={<a
    href="https://doi.org/10.1007/978-3-030-64348-5_6">10.1007/978-3-030-64348-5_6</a>},
    booktitle={Stabilization, Safety, and Security of Distributed Systems - 22nd International
    Symposium, SSS 2020, Austin, Texas, USA, November 18-21, 2020, Proceedings}, publisher={Springer},
    author={Castenow, Jannik and Kling, Peter and Knollmann, Till and Meyer auf der
    Heide, Friedhelm}, editor={Devismes , Stéphane  and Mittal, Neeraj Editors}, year={2020},
    pages={65–80}, collection={Lecture Notes in Computer Science (LNCS)} }'
  chicago: Castenow, Jannik, Peter Kling, Till Knollmann, and Friedhelm Meyer auf
    der Heide. “A Discrete and Continuous Study of the Max-Chain-Formation Problem
    – Slow Down to Speed Up.” In <i>Stabilization, Safety, and Security of Distributed
    Systems - 22nd International Symposium, SSS 2020, Austin, Texas, USA, November
    18-21, 2020, Proceedings</i>, edited by Stéphane  Devismes  and Neeraj  Mittal,
    12514:65–80. Lecture Notes in Computer Science (LNCS). Springer, 2020. <a href="https://doi.org/10.1007/978-3-030-64348-5_6">https://doi.org/10.1007/978-3-030-64348-5_6</a>.
  ieee: J. Castenow, P. Kling, T. Knollmann, and F. Meyer auf der Heide, “A Discrete
    and Continuous Study of the Max-Chain-Formation Problem – Slow Down to Speed Up,”
    in <i>Stabilization, Safety, and Security of Distributed Systems - 22nd International
    Symposium, SSS 2020, Austin, Texas, USA, November 18-21, 2020, Proceedings</i>,
    2020, vol. 12514, pp. 65–80.
  mla: Castenow, Jannik, et al. “A Discrete and Continuous Study of the Max-Chain-Formation
    Problem – Slow Down to Speed Up.” <i>Stabilization, Safety, and Security of Distributed
    Systems - 22nd International Symposium, SSS 2020, Austin, Texas, USA, November
    18-21, 2020, Proceedings</i>, edited by Stéphane  Devismes  and Neeraj  Mittal,
    vol. 12514, Springer, 2020, pp. 65–80, doi:<a href="https://doi.org/10.1007/978-3-030-64348-5_6">10.1007/978-3-030-64348-5_6</a>.
  short: 'J. Castenow, P. Kling, T. Knollmann, F. Meyer auf der Heide, in: S. Devismes
    , N. Mittal (Eds.), Stabilization, Safety, and Security of Distributed Systems
    - 22nd International Symposium, SSS 2020, Austin, Texas, USA, November 18-21,
    2020, Proceedings, Springer, 2020, pp. 65–80.'
date_created: 2020-10-06T07:27:10Z
date_updated: 2022-01-06T06:54:14Z
department:
- _id: '63'
doi: 10.1007/978-3-030-64348-5_6
editor:
- first_name: 'Stéphane '
  full_name: 'Devismes , Stéphane '
  last_name: 'Devismes '
- first_name: 'Neeraj '
  full_name: 'Mittal, Neeraj '
  last_name: Mittal
external_id:
  arxiv:
  - '2010.02043 '
intvolume: '     12514'
language:
- iso: eng
page: 65-80
publication: Stabilization, Safety, and Security of Distributed Systems - 22nd International
  Symposium, SSS 2020, Austin, Texas, USA, November 18-21, 2020, Proceedings
publication_identifier:
  isbn:
  - 978-3-030-64347-8
publication_status: published
publisher: Springer
series_title: Lecture Notes in Computer Science (LNCS)
status: public
title: A Discrete and Continuous Study of the Max-Chain-Formation Problem – Slow Down
  to Speed Up
type: conference
user_id: '38705'
volume: 12514
year: '2020'
...
---
_id: '20185'
author:
- first_name: Jannik
  full_name: Castenow, Jannik
  id: '38705'
  last_name: Castenow
- first_name: Jonas
  full_name: Harbig, Jonas
  id: '47213'
  last_name: Harbig
- first_name: Daniel
  full_name: Jung, Daniel
  id: '37827'
  last_name: Jung
- first_name: Till
  full_name: Knollmann, Till
  id: '39241'
  last_name: Knollmann
  orcid: 0000-0003-2014-4696
- first_name: Friedhelm
  full_name: Meyer auf der Heide, Friedhelm
  id: '15523'
  last_name: Meyer auf der Heide
citation:
  ama: 'Castenow J, Harbig J, Jung D, Knollmann T, Meyer auf der Heide F. Brief Announcement:
    Gathering in Linear Time: A Closed Chain of Disoriented &#38; Luminous Robots
    with Limited Visibility . In: Devismes S,  Mittal N, eds. <i>Stabilization, Safety,
    and Security of Distributed Systems - 22nd International Symposium, SSS 2020,
    Austin, Texas, USA, November 18-21, 2020, Proceedings </i>. Vol 12514. Lecture
    Notes in Computer Science (LNCS). Springer; 2020:60-64. doi:<a href="https://doi.org/10.1007/978-3-030-64348-5_5">10.1007/978-3-030-64348-5_5</a>'
  apa: 'Castenow, J., Harbig, J., Jung, D., Knollmann, T., &#38; Meyer auf der Heide,
    F. (2020). Brief Announcement: Gathering in Linear Time: A Closed Chain of Disoriented
    &#38; Luminous Robots with Limited Visibility . In S. Devismes &#38; N.  Mittal
    (Eds.), <i>Stabilization, Safety, and Security of Distributed Systems - 22nd International
    Symposium, SSS 2020, Austin, Texas, USA, November 18-21, 2020, Proceedings </i>
    (Vol. 12514, pp. 60–64). Springer. <a href="https://doi.org/10.1007/978-3-030-64348-5_5">https://doi.org/10.1007/978-3-030-64348-5_5</a>'
  bibtex: '@inproceedings{Castenow_Harbig_Jung_Knollmann_Meyer auf der Heide_2020,
    series={Lecture Notes in Computer Science (LNCS)}, title={Brief Announcement:
    Gathering in Linear Time: A Closed Chain of Disoriented &#38; Luminous Robots
    with Limited Visibility }, volume={12514}, DOI={<a href="https://doi.org/10.1007/978-3-030-64348-5_5">10.1007/978-3-030-64348-5_5</a>},
    booktitle={Stabilization, Safety, and Security of Distributed Systems - 22nd International
    Symposium, SSS 2020, Austin, Texas, USA, November 18-21, 2020, Proceedings },
    publisher={Springer}, author={Castenow, Jannik and Harbig, Jonas and Jung, Daniel
    and Knollmann, Till and Meyer auf der Heide, Friedhelm}, editor={Devismes, Stéphane  and  Mittal,
    NeerajEditors}, year={2020}, pages={60–64}, collection={Lecture Notes in Computer
    Science (LNCS)} }'
  chicago: 'Castenow, Jannik, Jonas Harbig, Daniel Jung, Till Knollmann, and Friedhelm
    Meyer auf der Heide. “Brief Announcement: Gathering in Linear Time: A Closed Chain
    of Disoriented &#38; Luminous Robots with Limited Visibility .” In <i>Stabilization,
    Safety, and Security of Distributed Systems - 22nd International Symposium, SSS
    2020, Austin, Texas, USA, November 18-21, 2020, Proceedings </i>, edited by Stéphane  Devismes
    and Neeraj  Mittal, 12514:60–64. Lecture Notes in Computer Science (LNCS). Springer,
    2020. <a href="https://doi.org/10.1007/978-3-030-64348-5_5">https://doi.org/10.1007/978-3-030-64348-5_5</a>.'
  ieee: 'J. Castenow, J. Harbig, D. Jung, T. Knollmann, and F. Meyer auf der Heide,
    “Brief Announcement: Gathering in Linear Time: A Closed Chain of Disoriented &#38;
    Luminous Robots with Limited Visibility ,” in <i>Stabilization, Safety, and Security
    of Distributed Systems - 22nd International Symposium, SSS 2020, Austin, Texas,
    USA, November 18-21, 2020, Proceedings </i>, 2020, vol. 12514, pp. 60–64.'
  mla: 'Castenow, Jannik, et al. “Brief Announcement: Gathering in Linear Time: A
    Closed Chain of Disoriented &#38; Luminous Robots with Limited Visibility .” <i>Stabilization,
    Safety, and Security of Distributed Systems - 22nd International Symposium, SSS
    2020, Austin, Texas, USA, November 18-21, 2020, Proceedings </i>, edited by Stéphane  Devismes
    and Neeraj  Mittal, vol. 12514, Springer, 2020, pp. 60–64, doi:<a href="https://doi.org/10.1007/978-3-030-64348-5_5">10.1007/978-3-030-64348-5_5</a>.'
  short: 'J. Castenow, J. Harbig, D. Jung, T. Knollmann, F. Meyer auf der Heide, in:
    S. Devismes, N.  Mittal (Eds.), Stabilization, Safety, and Security of Distributed
    Systems - 22nd International Symposium, SSS 2020, Austin, Texas, USA, November
    18-21, 2020, Proceedings , Springer, 2020, pp. 60–64.'
date_created: 2020-10-23T08:50:28Z
date_updated: 2022-01-06T06:54:21Z
department:
- _id: '63'
doi: 10.1007/978-3-030-64348-5_5
editor:
- first_name: 'Stéphane '
  full_name: 'Devismes, Stéphane '
  last_name: Devismes
- first_name: Neeraj
  full_name: ' Mittal, Neeraj'
  last_name: ' Mittal'
external_id:
  arxiv:
  - '2010.04424 '
intvolume: '     12514'
language:
- iso: eng
page: 60-64
publication: 'Stabilization, Safety, and Security of Distributed Systems - 22nd International
  Symposium, SSS 2020, Austin, Texas, USA, November 18-21, 2020, Proceedings '
publication_identifier:
  isbn:
  - 978-3-030-64347-8
publication_status: published
publisher: Springer
series_title: Lecture Notes in Computer Science (LNCS)
status: public
title: 'Brief Announcement: Gathering in Linear Time: A Closed Chain of Disoriented
  & Luminous Robots with Limited Visibility '
type: conference
user_id: '38705'
volume: 12514
year: '2020'
...