A Discrete and Continuous Study of the Max-Chain-Formation Problem – Slow Down to Speed Up
Castenow, Jannik
Kling, Peter
Knollmann, Till
Meyer auf der Heide, Friedhelm
Devismes , Stéphane
Mittal, Neeraj
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.
Springer
2020
info:eu-repo/semantics/conferenceObject
doc-type:conferenceObject
text
https://ris.uni-paderborn.de/record/19899
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>
eng
info:eu-repo/semantics/altIdentifier/doi/10.1007/978-3-030-64348-5_6
info:eu-repo/semantics/altIdentifier/isbn/978-3-030-64347-8
info:eu-repo/semantics/altIdentifier/arxiv/2010.02043
info:eu-repo/semantics/closedAccess