---
res:
bibo_abstract:
- "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.@eng"
bibo_authorlist:
- foaf_Person:
foaf_givenName: Jannik
foaf_name: Castenow, Jannik
foaf_surname: Castenow
foaf_workInfoHomepage: http://www.librecat.org/personId=38705
- foaf_Person:
foaf_givenName: Peter
foaf_name: Kling, Peter
foaf_surname: Kling
- foaf_Person:
foaf_givenName: Till
foaf_name: Knollmann, Till
foaf_surname: Knollmann
foaf_workInfoHomepage: http://www.librecat.org/personId=39241
orcid: 0000-0003-2014-4696
- foaf_Person:
foaf_givenName: Friedhelm
foaf_name: Meyer auf der Heide, Friedhelm
foaf_surname: Meyer auf der Heide
foaf_workInfoHomepage: http://www.librecat.org/personId=15523
bibo_doi: 10.1007/978-3-030-64348-5_6
bibo_volume: 12514
dct_date: 2020^xs_gYear
dct_isPartOf:
- http://id.crossref.org/issn/978-3-030-64347-8
dct_language: eng
dct_publisher: Springer@
dct_title: A Discrete and Continuous Study of the Max-Chain-Formation Problem –
Slow Down to Speed Up@
...