@inproceedings{19899,
  abstract     = {{Most existing robot formation problems seek a target formation of a certain
minimal and, thus, efficient structure. Examples include the Gathering
and the Chain-Formation problem. In this work, we study formation problems that
try to reach a maximal structure, supporting for example an efficient
coverage in exploration scenarios. A recent example is the NASA Shapeshifter
project, which describes how the robots form a relay chain along which gathered
data from extraterrestrial cave explorations may be sent to a home base.
  As a first step towards understanding such maximization tasks, we introduce
and study the Max-Chain-Formation problem, where $n$ robots are ordered along a
winding, potentially self-intersecting chain and must form a connected,
straight line of maximal length connecting its two endpoints. We propose and
analyze strategies in a discrete and in a continuous time model. In the
discrete case, we give a complete analysis if all robots are initially
collinear, showing that the worst-case time to reach an
$\varepsilon$-approximation is upper bounded by $\mathcal{O}(n^2 \cdot \log
(n/\varepsilon))$ and lower bounded by $\Omega(n^2 \cdot~\log
(1/\varepsilon))$. If one endpoint of the chain remains stationary, this result
can be extended to the non-collinear case. If both endpoints move, we identify
a family of instances whose runtime is unbounded. For the continuous model, we
give a strategy with an optimal runtime bound of $\Theta(n)$. Avoiding an
unbounded runtime similar to the discrete case relies crucially on a
counter-intuitive aspect of the strategy: slowing down the endpoints while all
other robots move at full speed. Surprisingly, we can show that a similar trick
does not work in the discrete model.}},
  author       = {{Castenow, Jannik and Kling, Peter and Knollmann, Till and Meyer auf der Heide, Friedhelm}},
  booktitle    = {{Stabilization, Safety, and Security of Distributed Systems - 22nd International Symposium, SSS 2020, Austin, Texas, USA, November 18-21, 2020, Proceedings}},
  editor       = {{Devismes , Stéphane  and Mittal, Neeraj }},
  isbn         = {{978-3-030-64347-8}},
  pages        = {{65--80}},
  publisher    = {{Springer}},
  title        = {{{A Discrete and Continuous Study of the Max-Chain-Formation Problem – Slow Down to Speed Up}}},
  doi          = {{10.1007/978-3-030-64348-5_6}},
  volume       = {{12514}},
  year         = {{2020}},
}

@inproceedings{20185,
  author       = {{Castenow, Jannik and Harbig, Jonas and Jung, Daniel and Knollmann, Till and Meyer auf der Heide, Friedhelm}},
  booktitle    = {{Stabilization, Safety, and Security of Distributed Systems - 22nd International Symposium, SSS 2020, Austin, Texas, USA, November 18-21, 2020, Proceedings }},
  editor       = {{Devismes, Stéphane  and  Mittal, Neeraj}},
  isbn         = {{978-3-030-64347-8}},
  pages        = {{60--64}},
  publisher    = {{Springer}},
  title        = {{{Brief Announcement: Gathering in Linear Time: A Closed Chain of Disoriented & Luminous Robots with Limited Visibility }}},
  doi          = {{10.1007/978-3-030-64348-5_5}},
  volume       = {{12514}},
  year         = {{2020}},
}